Why bound the intermediate entries?
Gaussian elimination changes the matrix before the triangular solve begins. Even when every entry of the original matrix is modest, an intermediate entry can become much larger. Such element growth matters in floating-point error analysis because rounding occurs during these intermediate operations. It is different from the condition number, which measures sensitivity of the mathematical problem itself.
We study exact arithmetic first. Let be nonsingular. Ties among equally large candidates may be broken by any stated rule, and the definition below applies to each such rule.
Definition 2.2.1
(Partial pivoting and the growth factor)
At each column, partial pivoting exchanges the current row with a row, among the remaining rows, whose entry in that column has largest absolute value. Let , and let denote the active matrix at the start of stage before its row exchange. Put
where the maximum ranges over active entries at all stages, including the final stage. The number is the growth factor of the elimination.
The selected pivot is nonzero: otherwise rows of column would be zero. The first columns would then lie in the span of the first coordinate vectors and be dependent, contradicting nonsingularity preserved by row operations. Row exchanges do not change the largest magnitude. Since is nonsingular, and .
A general upper bound
Theorem 2.2.2
(Growth bound for partial pivoting)
For every nonsingular and every tie rule, partial pivoting in exact arithmetic gives
Proof
(Each stage at most doubles the largest entry)
At stage , write the selected pivot as and a lower entry in its column as . Partial pivoting ensures . For every entry in the remaining block,
where is the largest active-entry magnitude immediately before the elimination. Thus . Induction over the elimination stages gives , and every active entry at every stage is at most in magnitude.
Proof X-ray
Where the factor two comes from
Nonsingularity is used only to guarantee a nonzero pivot at each stage, so that the quotient exists and . The pivoting rule is used exactly once, to give . The key step is the triangle inequality, not a cancellation argument: the new entry is minus a multiple of with multiplier of magnitude at most one, so each of the two terms has magnitude at most and their difference can reach . The proof closes because holds at every stage whatever the tie rule, so stages give ; it says nothing about which stages actually double. Without the pivoting rule nothing of this kind survives: for the unpivoted multiplier is and the new entry is , unbounded as .
The bound is a worst-case statement: it does not say that all matrices experience doubling at every step, or that the final answer has relative error times machine precision.
A family that attains the bound
For , define by putting on its diagonal and in its last column, strictly below the diagonal in columns , and above the diagonal in columns . For example,
Proposition 2.2.3
(A matrix family with maximal growth)
Apply partial pivoting to with the tie rule that keeps the current row whenever its pivot magnitude is tied for the largest. Then no row exchange occurs, is nonsingular, and .
Proof
(Elimination of under the keep-current-row rule)
All initial entries have magnitude at most one. In each of the first columns, the pivot is and each entry below it is , so the multiplier is and this tie rule performs no exchange. The explicit invariant is that the stage- active matrix is with its last column multiplied by (taking ). It holds at . The pivot row has zeros between the pivot and its last entry, so adding it to each lower row changes only the last column: every lower last entry becomes , which is the invariant at stage . The tie rule therefore applies at every stage. The final pivot is , so is nonsingular, and this entry together with the growth bound gives .
Worked example 2.2.4
(Elimination of without exchanges)
At stage 1 the pivot is , and adding row 1 to each lower row gives lower rows , , . The active block is , which is with last column doubled. At stage 2, adding the pivot row to the two rows below gives the block , and at stage 3 one more addition gives . The resulting upper triangular matrix is
Since and the largest active entry is , .
Worked example 2.2.5
(Another tie rule on )
Break ties by choosing the lowest row. In column 1 of all entries have magnitude one, so rows 1 and 3 are exchanged, giving . The multipliers are and ; subtracting accordingly gives rows and , so the active block is . In column 2 the pivot is and the multiplier is , giving final pivot . The largest active magnitude is , so this rule has rather than . Thus the family establishes the worst case for an allowed rule, not identical growth for every tie rule.
Counterexample mode
Bounded multipliers do not ensure bounded growth independent of dimension
The matrices have all multipliers equal to under the specified tie rule, yet their growth factors are . Thus controlling each multiplier is useful but does not yield a dimension-independent growth bound.
A small pivot without an exchange
Worked example 2.2.6
(A small leading entry)
For , let
Without pivoting, the first multiplier is and the second pivot is , which becomes arbitrarily large in magnitude as . Partial pivoting exchanges the rows first: the multiplier becomes and the second pivot becomes . Here every active entry has magnitude at most one, so . The example shows how pivoting can avoid large intermediate entries; it is not a proof that pivoting always prevents growth.
Growth, conditioning and computation
The growth factor depends on the elimination path and pivot rule; a condition number depends on the original matrix and a chosen norm. Neither number alone is the forward error. Floating-point backward-error estimates depend on rounding, dimensions, the factors and intermediate magnitudes, while forward error additionally depends on conditioning. The exact-arithmetic calculation above isolates one mechanism without claiming a universal error certificate for a particular implementation.
Common mistake
(Reading the growth factor as the error of the computed solution)
The bound compares intermediate magnitudes with the original entries in exact elimination. It does not assert that the computed solution has relative error times machine precision; rounding and the conditioning of the original problem enter separately.
Common mistake
(Treating the growth factor as a property of the matrix alone)
The same matrix can have different growth under different allowed tie rules: has when the current row is kept and when the lowest tied row is chosen. A stated value of must name the pivot rule.
Practice with solutions
Exercise 2.2.7
(For , perform the elimination with the keep-current-row tie rule and find its growth factor.)
Foundation
Solution(3)
- 1
Eliminate column 1
Adding row 1 to rows 2 and 3 of gives lower rows and .
Because: The pivot is and both lower entries are , so the multiplier is and no row is exchanged.
- 2
Eliminate column 2
The active block is with pivot ; adding row 1 to row 2 gives in the last position.
- 3
Read off the growth factor
and , so .
Quick check
(Why does partial pivoting give multipliers of magnitude at most one?)
Compare each lower entry with the pivot.
Solution · Answer
The pivot has maximum magnitude in the active column, so for every lower entry, and the multiplier is .
Quick check
(For in the two-by-two example, compare the second pivots with and without the row exchange.)
Compute and .
Solution · Answer
Without the exchange the pivot is ; after exchanging it is .
Quick check
(Does the bound assert that the computed solution has that relative forward error?)
Recall what compares.
Solution · Answer
No. It bounds intermediate magnitudes in exact elimination relative to the original entries; rounding and the conditioning of the original problem require further analysis.