Partial pivoting avoids dividing by a smaller available entry in the active column. That helps control multipliers, but elimination also rounds every division, multiplication and subtraction. What do the computed factors actually factor? We will prove that they exactly factor a nearby permuted matrix, and see where the intermediate element growth enters the bound. This is a statement about factorization; solving the triangular systems introduces further arithmetic errors.
The computed algorithm and its assumptions
Let , , have represented floating-point entries. At column , partial pivoting chooses an active row with largest absolute entry in that column, interchanges it with row , and performs the updates
Here denotes the active matrix after the step-k row exchange, and . Row exchanges are exact permutations. When rows are exchanged, previously stored multipliers in those rows are exchanged as well; otherwise the final would not record the same row history. Let be the product of the exchanges, the resulting unit lower triangular matrix of multipliers, and the upper triangular matrix of computed pivot rows.
Assume each division, multiplication and subtraction used in (1) obeys the standard relative model
and that every computed pivot is nonzero. Exclude operations for which overflow, underflow or exceptional values make (2) invalid. We analyze the actual rounded pivot choices, not pivots from a separate exact-arithmetic run. Assume and put . Fused multiply-subtract is not the separately rounded algorithm in (1).
Theorem 2.3.1
(Factorization of a nearby matrix)
There is a real matrix such that
Absolute values and the inequality are entrywise; the right-hand side is an ordinary matrix product. In particular, the bound depends on the computed factors, not just on the original entries. It is a backward error in the permuted input matrix; it is not yet a bound for the final solution of .
Proof
(Follow a row through the exchanges and rounded updates)
For a fixed final row i, follow its ancestor backwards through the exact swaps. Swapping the earlier stored multipliers at every exchange ensures that the quantities refer to this same row history. Once row k becomes a pivot row, its computed entries are fixed. Thus each final entry can be traced through the updates preceding its row's pivot, without assuming that the same physical row number stayed in place.
Suppressing indices, one update in (1) has the form
Rearrange it as . Likewise the computed division gives . Repeated substitution expresses as a sum of the terms , each multiplied by a product of rounded factors. For an upper-triangular entry, the terminal term is the stored , with ; for an entry below the diagonal, the terminal term is the computed multiplier times its pivot, with one reciprocal division factor. The previous row exchanges are already incorporated in P and L.
Each term contains at most n factors: at most one numerator from its product and otherwise reciprocals from prior subtractions or the terminal division. Thus, for its combined factor ,
The lower bound uses ; the upper uses and . Consequently with for the nonzero triangular terms. Subtracting from and applying the triangle inequality gives (3). No independence assumption about rounding errors is needed.
Proof X-ray
What the rounding bookkeeping depends on
The proof is bookkeeping with two commitments that are easy to miss. First, stored multipliers are exchanged together with their rows, so following one final row backwards through the swaps always meets the same sequence of and ; without that, (3) would compare with the wrong row history. Second, each term collects at most rounding factors, at most one from a product and otherwise reciprocals , which is why the single constant covers both directions; the hypothesis is exactly what keeps positive. Nothing treats the errors as random, so (3) is a worst-case guarantee for the actual rounded pivot choices. The proof stops at the factorization and never touches the triangular solves.
What growth adds to the estimate
Definition 2.3.2
(Growth factor)
Let . The growth factor of the computed run is the largest absolute entry appearing in any computed active matrix or pivot row, divided by .
It is a property of the computed run, not of exact arithmetic.
Corollary 2.3.3
(Growth-factor form of the backward error)
Under the assumptions above, the matrix of (3) satisfies
Proof
(Bounding the multipliers and the pivot rows)
Partial pivoting chooses a largest active column entry, so the exact quotient in each division has magnitude at most one, and (2) gives . By the definition of , every . Each entry of is a sum of at most products, each at most , so (3) gives (4).
The bound can be pessimistic, and growth depends on the pivot path. It explains why a large intermediate entry can weaken an error guarantee; it does not say that large growth always causes a large actual error. Converting a small backward error into a small forward error also requires a well-conditioned problem.
Common mistake
(Three different errors are not one)
Equation (3) concerns how accurately the computed factors represent a nearby matrix. A computed triangular solve has its own rounding error, so (3) alone does not certify the final solution. Finally, even an exact solution of a nearby system can differ substantially from the original solution when that system is ill-conditioned. Factorization error, solve error and problem sensitivity are separate questions.
Worked example and a sensitivity counterexample
Worked example 2.3.4
(A pivot swap with exact arithmetic)
For , the first pivot is 2, so
In binary arithmetic these operations are exact, so ; the computed growth factor is . The theorem supplies an upper bound, not a claim that every run attains it.
Worked example 2.3.5
(A rounded multiplier)
Take . The largest entry of column is , so . The computed multiplier is with . The product is exact, so with . Then . Since and ,
Only the second row is perturbed. The right-hand side of (3) in position is , which is larger than , so the bound holds with room to spare.
Worked example 2.3.6
(Element growth under partial pivoting)
Let , so . All entries of column have magnitude ; take the first as pivot. The multipliers are and the active matrix becomes . Both entries of its first column again have magnitude ; with the first as pivot the multiplier is and the last entry becomes . Thus and . All operations are exact, so , but for , and (4) is four times weaker than it would be for . This tie case shows that equal magnitudes are allowed as pivots and that large growth can occur although no multiplier exceeds one in magnitude.
Counterexample mode
Small backward error, large forward error
A tempting claim is that a tiny backward error guarantees an accurate solution. Set and with ; the exact solution is . The vector satisfies , so it solves a system whose data differ from the given data by a perturbation tending to zero with . Yet , so the relative forward error is . Even a perfect factorization cannot make a nearly singular problem insensitive; the repair is to combine the backward error with a condition number. This example concerns input perturbation; it does not assert that the factorization in (3) must produce that perturbation.
Practice with solutions
Quick check
(Why must previously stored multipliers follow later row swaps?)
Think of each row's history.
Solution · Answer
They belong to the row history from earlier columns. Failing to swap them breaks the correspondence between the final permutation and the stored .
Quick check
(What is the difference between the matrices and in (3)?)
Multiply (3) by .
Solution · Answer
perturbs ; multiplying (3) by shows that is the corresponding perturbation of in .
Quick check
(If , what does the algorithm do and what is its factorization error?)
Count the divisions and updates.
Solution · Answer
There are no divisions or trailing updates: , and for the stored input.
Quick check
(Does alone guarantee an accurate computed solution for every right-hand side? Explain.)
Recall the three errors.
Solution · Answer
No. Equation (4) can bound factorization error, but the triangular solves also round and the system may be sensitive; the nearly singular example shows sensitivity even before solve rounding is considered.