Control elimination while tracking its backward error

Try

For A=[[0.001,1],[1,1]], eliminating without pivoting uses multiplier 1000, making intermediate numbers much larger than the inputs. Swapping rows first uses multiplier 0.001. Both are exact algebraic routes to the same solution, but their rounding behavior can differ sharply. Partial pivoting chooses the largest available magnitude in the current column to avoid dividing by an unnecessarily tiny pivot.

Predict

Predict whether bounded multipliers prove every later number stays small. They do not. Elimination repeatedly subtracts scaled pivot rows, and entries of the remaining matrix can grow. Partial pivoting is highly effective in many problems but has worst-case growth examples. A realistic analysis includes growth and conditioning rather than declaring any pivoted solve automatically accurate to machine precision.

Experiment

Compare the first elimination update.

Strategy	Pivot	Multiplier	Remaining second diagonal entry
No exchange	0.001	1000	−999
Exchange rows	1	0.001	0.999

Compute these values directly. Add a right-hand side of your choice and apply the same row operations to it; modifying A without modifying b is a different, incorrect system.

Understand

Pivoted elimination produces PA=LU in exact arithmetic, with P a permutation, L unit lower triangular and U upper triangular. At step k, choose a maximum-magnitude pivot among remaining rows, exchange rows, and form multipliers aᵢₖ/aₖₖ. Their magnitudes are at most one. Update the trailing matrix and right-hand side consistently. If row exchanges occur after earlier columns have been processed, previously stored multipliers must move with those rows. A zero pivot after searching the entire remaining column signals rank deficiency in exact arithmetic; a tiny computed pivot requires scale-aware numerical interpretation.

Apply

Under standard rounding assumptions, elimination can often be interpreted as factoring A+ΔA, with a componentwise bound involving unit roundoff, problem size and the product |L||U|. Large U growth enlarges that bound. The computed solution’s residual r=b−Ax̂ provides an independent diagnostic. Relative perturbations to both A and b motivate η=‖r‖/(‖A‖‖x̂‖+‖b‖); relative right-hand-side-only error is instead ‖r‖/‖b‖. State the model and norm. Small backward error gives small forward error only when the system is sufficiently well conditioned. Near singularity, a tiny residual can accompany substantial coefficient error.

For repeated right-hand sides, retain the same factors only while A is unchanged. Apply the stored permutation to each new b, solve Ly=Pb, then Ux=y. This sequence is an exact algorithmic contract. A common implementation error is to permute the matrix during factorization but forget the right-hand side during subsequent solves. Test with a permutation matrix whose solution is known by inspection before moving to a difficult dense matrix.

Continue

Iterative refinement recomputes a residual, solves a correction equation and updates the solution. Higher-accuracy residual evaluation can improve the result, but success depends on the factorization and conditioning. Test a written implementation with known solutions, row exchanges at multiple stages, singular matrices and scale disparities. Count factorization separately from triangular solves, especially for repeated right-hand sides. Next, stationary iterations replace direct elimination by repeated residual corrections, with convergence governed by an iteration matrix rather than pivot choices.

Review calculus and linear algebra when a prerequisite needs practice. Continue to Make an iteration matrix explain convergence.