Motivation
A factorization is useful because its factors are easier to work with than the original matrix. Reliability requires another question: which nearby problem do the computed factors and triangular solves actually solve? This question is separate from whether that nearby problem has a solution close to the original one. Backward error describes the nearby data; conditioning describes their possible effect on the answer.
We extend the earlier introduction to elimination by examining growth and factorization residuals, then develop orthogonal QR for rectangular least squares. The main proofs separate exact algebra from explicitly assumed floating-point contracts. This makes “stable” a statement with hypotheses, rather than a promise attached to an algorithm's name.
Definitions
Definition 14.1.1
(Partial pivoting and growth factor)
For nonsingular square , elimination with partial row pivoting produces in exact arithmetic. The permutation records every swap, has unit diagonal, and is upper triangular. Subsequent swaps must also move already stored multipliers in the corresponding columns of . Partial pivoting bounds the exact multipliers by one in magnitude. Define the growth factor as the largest magnitude entry in any active elimination matrix divided by the largest magnitude entry of the initial matrix.
Definition 14.1.2
(Factorization residual)
For computed factors, define their exact factorization residual by
This is a mathematical difference; evaluating it on a computer introduces another error. It is not the solution residual . We use componentwise absolute values in inequalities such as , and write when .
Definition 14.1.3
(Least squares, full QR, and Householder reflectors)
For rectangular with and independent columns, least squares minimizes . A full orthogonal QR factorization has
where is nonsingular upper triangular. A Householder reflector associated with a nonzero vector is . It is symmetric and orthogonal, and can be applied as without storing a dense matrix.
Concept lensStructural
Three residuals, three questions
The factorization residual checks whether the factors represent the intended matrix. The system residual checks a candidate against square equations. A least-squares residual measures unavoidable misfit and should be orthogonal to the model space at the optimum. The same word cannot substitute for the different mathematical roles.
Theorem/Proposition
Theorem 14.1.4
(From factor and solve errors to a nearby system)
Suppose computed triangular solves satisfy
with and . Then for a matrix satisfying
For any candidate , its exact residual also gives the smallest Frobenius-norm matrix-only perturbation making it an exact solution:
Theorem 14.1.5
(Orthogonal reduction solves full-rank least squares)
Let with . Then the unique least-squares solution satisfies , and its minimum residual norm is . Equivalently, . For full-column-rank rectangular with singular values , define . Then
Thus forming the normal equations squares the matrix condition number; orthogonal reduction avoids forming that matrix. It does not make every least-squares problem well conditioned.
Proof sketch or proof idea
A factorization error is only one part of the solve
Proof
(Assembling the nearby system)
Substituting the two triangular relations gives . Since , choose
Taking componentwise absolute values proves the bound. Small alone is insufficient if the product of absolute factors is large. Conversely, a small, properly normalized and reliably computed solution residual certifies a small backward error for that particular solve, even when a worst-case factor bound is pessimistic. It does not alone certify small forward error; the residual-computation budget below is part of that assessment.
For the second statement, , so . The Frobenius norm of an outer product is the product of the vector norms. Any other with satisfies , proving minimality. This permits arbitrary matrix perturbations. A sparsity-preserving or componentwise uncertainty model is a different problem. A right-hand-side-only explanation instead uses .
For , the forward-error identity gives
The residual and matrix-only backward error answer different normalization questions; neither removes the condition number from a forward guarantee.
What partial pivoting controls
Proposition 14.1.6
(Growth bound for partial pivoting)
In exact arithmetic, elimination with partial pivoting on a nonsingular matrix has growth factor at most .
Proof
(Each update at most doubles the active maximum)
An active update has the form . With , we get , which is at most twice the current active maximum. Hence the maximum active magnitude can at most double at each of the elimination steps. Row swaps only permute entries and do not change the maximum.
This is an exponential bound, not a universal small constant. The family in the examples attains it under a stated tie rule.
Common mistake
(Equating bounded multipliers with small growth)
Partial pivoting guarantees , which controls a local division. The growth factor tracks repeated updates, and bounded multipliers still allow it to reach , as the matrix in the examples shows. Confusing these two is the source of many false stability claims.
For ordinary backward substitution, the usual rounding model is with . Assume nonzero pivots, , and no overflow or operations outside that relative-error model. Expanding each row's rounded products, running sum, and division assigns a multiplicative perturbation to its triangular coefficients. Each such coefficient accumulates at most rounding factors, giving in . This explains the triangular contracts used above. A factorization-specific analysis is still needed to bound in terms of the input and rounding; our theorem deliberately keeps the actual factorization residual explicit.
Even residual computation needs a budget. For straightforward rounded matrix-vector products and subtraction, a safe componentwise bound is under the same normal-operation model, with . This loose constant follows by counting all possible product, addition, and subtraction rounding factors in a row. A residual printed as zero need not be the exact residual.
Building QR without a cancellation-prone sign
Proof
(Reflectors and orthogonal invariance)
For a nonzero active column , let , choose with , and set . Then
so . The first component of has magnitude , avoiding subtraction of nearly equal positive magnitudes. If the active vector is zero, no reflector is needed. Apply successive reflectors only to the remaining rows and columns. Their product gives ; full column rank forces nonsingular.
Orthogonal invariance of the Euclidean norm now gives
The first term has unique minimum zero. Expanding the objective around any candidate shows that its linear term in a displacement is ; vanishing of this term is the stated orthogonality condition, and for nonzero proves uniqueness. Finally, the eigenvalues of are the squared singular values, proving the condition-number identity.
Holding the design matrix fixed gives a particularly transparent sensitivity statement. If only the right-hand side changes by , the solution changes by , where contains the first columns of . Its norm is at most . Changes orthogonal to the column space alter only the residual and leave the fitted coefficients unchanged. Perturbing the design matrix is a different sensitivity problem, especially when the optimal residual is large. Thus neither a small triangular residual nor the avoidance of normal equations alone certifies accurate coefficients for uncertain or nearly dependent data.
A precise finite-precision QR contract
Exact orthogonality does not mean that a stored floating-point matrix is exactly orthogonal. Here is a useful conditional model with a complete propagation argument. Suppose each computed reduction is represented by an exact orthogonal and a local perturbation:
Assume the final stored matrix is .
Proof
(Transporting local errors through exact reflectors)
After steps, put . Orthogonal invariance gives . Transport each local error back through preceding orthogonal factors and sum their norms. The resulting exact relation is
Applying the same reflectors to with analogous local bounds gives a perturbation bounded by . If the triangular solve has an additional normwise perturbation , with , absorb it into . The total matrix bound becomes . The returned vector then exactly minimizes a nearby least-squares problem, provided the perturbed triangular factor remains nonsingular.
Proof X-ray
Why local errors add instead of multiply
The hypotheses are the local contracts: each step is an exact orthogonal applied to slightly perturbed data. Orthogonality is used twice. First, , so each step enlarges the norm by at most the factor . Second, and this is the key move, every local error is transported back to the original data through , which does not change its norm. The errors therefore add, , and the geometric sum closes to . The final solve perturbation is absorbed by the same transport. If the reflectors in the contract were only approximately orthogonal, the transport step would no longer preserve norms and the bound would need an additional term; the sign choice for matters because it helps an implementation meet the local contract, not because it appears in this argument.
Carefully implemented Householder routines obtain dimension-dependent local bounds of order for small , with a modest kernel-dependent constant , under appropriate rounding assumptions. The proof above starts from those stated contracts; it does not derive their constants for every implementation. Norm evaluation should use scaling to avoid avoidable overflow/underflow, and reflector formation/application must respect the analyzed operation order. The LAPACK least-squares error analysis gives the corresponding normwise backward interpretation for its full-rank solvers. That is an algorithmic backward guarantee, not a universal small forward-error claim.
Worked examples
Worked example 14.1.7
(A reflector whose sign is deliberate)
For , , , and . Thus
Choosing the opposite target sign would form in the first component; when is much closer to its norm, that alternative subtraction becomes vulnerable to cancellation. Both signs work in exact algebra, but their arithmetic behavior can differ.
Worked example 14.1.8
(Partial pivoting can still have exponential growth)
Consider
If ties retain the first available row, partial pivoting makes no swaps. Every multiplier is . The factor has unit diagonal in its first three positions, zeros above the diagonal except in the last column, and last column . The initial maximum is one, so growth is eight. The analogous -dimensional family has last column . This demonstrates possible growth, not a claim that this exactly representable small example must produce an inaccurate answer.
Worked example 14.1.9
(Fitting a line without forming normal equations)
Fit to values at . The design columns are and . An exact orthonormal basis is
It gives and . Back substitution gives slope and intercept . The residual is , of norm , and is orthogonal to both design columns. These columns of are displayed to check the result; a Householder implementation can obtain the same reduction without explicitly storing full .
Common mistakes
Counterexample mode
A large least-squares residual need not mean solver failure
Let and , with . The unique least-squares solution is zero and its residual norm is . No choice of the scalar unknown can change the second equation. An arbitrarily large residual can therefore be the exact optimal result. In least squares, residual orthogonality and backward error answer questions that the residual magnitude alone cannot answer.
Common mistake
(Forming the normal equations because they are exact)
The normal equations are valid exact equations, but forming can magnify conditioning and introduce rounding in the matrix itself. Householder QR avoids that formation; it does not restore information lost in nearly dependent columns. Rank-deficient and underdetermined problems require additional rank and minimum-norm decisions beyond the full-column-rank theorem here.
Summary
Pivoting controls multipliers but permits exponential worst-case growth. Factorization and triangular-solve errors combine into a nearby-system statement; conditioning determines how much that may affect a solution. Householder transformations reduce full-rank least squares to a triangular solve without normal equations. Explicit local backward contracts explain how this exact construction becomes a normwise stable numerical method.
Exercises
Quick check
(Factor with partial pivoting, and solve . Check the permutation as well as the solution.)
The first pivot is the larger entry in the first column.
Solution · Answer
swaps the rows, , and . Their product is . Solve , giving . Then and . Multiplication by the original returns .
Quick check
(A candidate has and residual . Find the smallest Frobenius-norm matrix perturbation making it an exact solution, and prove that its norm is .)
Use .
Solution · Answer
. Its product with is , and its Frobenius norm is . Every admissible satisfies , proving minimality, including the zero case.
Quick check
(Construct the stated sign-safe Householder reflector for . Verify orthogonality and its action directly. Explain the convention at .)
With , .
Solution · Answer
The convention gives and . Thus , so and . The convention is needed only to make the formula definite: at both target signs give , so neither choice involves cancellation.
Quick check
(Fit a constant to the three values by least squares. Find the residual vector and norm, and verify the normal orthogonality condition. Does a nonzero optimal residual prove numerical instability?)
The design matrix is the column .
Solution · Answer
The design column is . The fitted constant is the mean, three. The residual has norm , and its component sum is zero, so . This is the exact unique optimum. Its nonzero residual describes model misfit, rather than an error committed by the solver.