Why a safe-looking pivot is not the whole story
Gaussian elimination replaces a system by a triangular one. In exact arithmetic this is an identity, but a computer rounds arithmetic operations. The size of intermediate entries affects how much rounding can matter. Partial pivoting chooses, in the active column, a largest-magnitude entry as pivot and swaps its row into place. It controls the multipliers; it does not guarantee that every later entry remains small. Nor does a small residual by itself guarantee a small error in the computed solution. These are distinct questions.
Throughout, is nonsingular, , and matrix and vector norms in the error discussion are the Euclidean induced norm and Euclidean norm. Elimination and all residual identities below are exact unless explicitly stated otherwise.
Multipliers and intermediate growth
At step , let be the active matrix entries before elimination, with . After choosing the pivot row and swapping it into position , eliminate below the pivot using
The superscript in the update denotes the entries after the row swap. Nonsingularity ensures a nonzero pivot at every step: otherwise the active column would be zero, making the remaining Schur complement, and hence the original matrix, singular. Because the pivot has maximum absolute value in its column, . Ties may be resolved by any specified rule.
Definition 1.4.1
(Growth factor)
Let . The growth factor of an elimination is the largest absolute value of an entry in the active matrices , , including the original matrix, divided by . In particular .
The growth factor can be bounded using nothing but the multiplier bound.
Proposition 1.4.2
(A worst-case growth bound)
Exact Gaussian elimination with partial pivoting on a nonsingular has growth factor .
Proof
(Each step at most doubles the largest entry)
Let be the largest magnitude in the active matrix before step , so . A row swap does not change it. For each updated entry, the triangle inequality and give
Thus and induction gives . There are at most updates. Entries already placed in were active entries at an earlier step, so this also bounds them. This is a worst-case upper bound, not a prediction that every matrix attains it.
Proof X-ray
Where does the factor two come from?
The proof tracks a single number, the largest active magnitude , and uses partial pivoting at exactly one point: , which holds because the pivot is largest in its column after the swap. The swap itself is harmless, since it permutes entries without changing .
The key move is to bound each new entry by two old ones, and , each at most . Nothing forces the subtraction to cancel, so the two magnitudes can add; that is the whole source of the factor two. The induction closes after steps because each step removes one row and one column from the active matrix, and every entry of was an active entry when it was frozen. The argument never uses cancellation, which is why it is attained only by special matrices; the three-by-three example below attains it.
A complete growth example
Worked example 1.4.3
(Pivot growth in a three-by-three system)
Choose the first available row when there is a tie. For
the first column has three tied entries of magnitude one. No swap occurs, and both multipliers are . Adding row 1 to rows 2 and 3 produces
The next pivot is again a tie; adding row 2 to row 3 yields
The original largest magnitude is and the largest encountered is , so . The nonzero diagonal of also confirms nonsingularity. Bounded multipliers did not prevent growth.
Worked example 1.4.4
(Why the swap matters in rounded arithmetic)
Solve , whose exact solution is and . Use decimal arithmetic that rounds every result to three significant digits.
Without a swap, the multiplier is and the second equation becomes . Both and round to , so , and then . The growth factor is , and the computed is completely wrong.
With partial pivoting, the rows are swapped and the multiplier is . The new second equation is ; both sides round to , so and . Both components are correct to the digits carried, and . Elimination without a swap is legal here, because the leading entry is nonzero; the failure comes from combining a huge intermediate entry with rounding.
Common mistake
(Forgetting to permute the right-hand side)
Partial pivoting factors , not , so the forward solve must use . For and , the swap gives and . With one obtains , which satisfies . Solving instead gives , and .
Residual, backward error and forward error
Given an approximate solution , define . Its forward error is , where . Since , nonsingularity yields . Thus a small absolute residual bounds the absolute error only after multiplication by . Dividing by the sizes of and gives a relative version.
Proposition 1.4.5
(Residual bound for the relative forward error)
If , then , and
Proof
(Two norm inequalities)
Since , we have . Since , we have , so and . Multiplying the two inequalities gives the bound.
A large condition number makes this upper bound weak; it does not force every right-hand side to produce a large error.
Worked example 1.4.6
(A well-conditioned system with a nonzero residual)
Let , , and . Then and . The relative forward error is , while the relative residual is . Since , the bound gives . Here the residual is nonzero and small, and the modest condition number makes the bound informative. The two relative quantities use different denominators and need not be equal.
There is another useful interpretation: the residual measures how far must move for to become exact.
Proposition 1.4.7
(Backward error for perturbations of the matrix)
Suppose and only is perturbed, with fixed. Then
and the minimum is attained by .
Proof
(A lower bound attained by a rank-one matrix)
The constraint is , so , that is, . The rank-one matrix satisfies , and for every , Cauchy–Schwarz gives , with equality at . Its norm is therefore exactly ; dividing by gives the formula.
This is a backward error for perturbations to alone. It does not allow simultaneous perturbations to , and it is not the same number as the relative residual.
Common mistake
(The relative residual is not the backward error)
The quantities and agree only when . In the well-conditioned example above, , while and give a backward error of about . State which one is meant; neither is a forward error.
Counterexample mode
A small residual can hide a large error
Take , , so . For , the residual is , but the relative forward error is . The problem is ill-conditioned: . A small residual is evidence of a nearby problem, not automatically an accurate answer to the original one.
In floating-point arithmetic, the residual itself may be rounded, and growth can enlarge the perturbation produced by elimination. The exact bound above concerns intermediate entries; it is not a full floating-point backward-stability theorem. A reliable numerical assessment also considers precision, the computed residual and an estimate of conditioning.
Practice with solutions
Quick check
(Eliminate using partial pivoting. Give the row swap, , and the growth factor.)
Look at the first column before choosing a pivot.
Solution · Answer
The first column is , so partial pivoting swaps rows 1 and 2, giving . The multiplier is , so . The largest magnitude is throughout, so .
Quick check
(For with , and , find the relative residual and the relative forward error. What happens as ?)
The exact solution is easy to read off.
Solution · Answer
The residual is and . The relative residual is ; the relative forward error is . The first tends to zero while the second stays fixed, consistent with .
Quick check
(Let , and . Find a smallest spectral-norm perturbation of that makes exact, and its relative norm.)
Use the rank-one matrix from the backward-error proposition.
Solution · Answer
Here . The rank-one construction gives , which sends to . Its spectral norm is and , and the proposition proves minimality. The exact solution is , so the relative forward error is . This differs from the relative backward error : the two quantities measure changes in different objects, and their denominators differ.