Wilkinson's Backward Error Analysis Theorem

James Wilkinson's backward error analysis provides a powerful framework for understanding numerical stability by showing that computed solutions are exact solutions to slightly perturbed problems.

TheoremWilkinson's Theorem for Linear Systems

Let $A \in \mathbb{R}^{n \times n}$ be nonsingular and let $\tilde{x}$ be the computed solution to $Ax = b$ using Gaussian elimination with partial pivoting in floating point arithmetic. Then there exists a matrix $\Delta A$ such that: $(A + \Delta A)\tilde{x} = b$ where $\frac{\|\Delta A\|}{\|A\|} \leq c(n)\epsilon_{\text{mach}} g$ with $c(n)$ a modest polynomial in $n$ , and $g$ is the growth factor from pivoting (typically $g = O(1)$ in practice, though worst-case $g = 2^{n-1}$ ).

This theorem establishes that Gaussian elimination with partial pivoting is backward stable: the computed solution is the exact solution to a problem whose coefficient matrix differs from the original by a relative amount proportional to machine precision.

Remark

Interpreting Backward Stability: Backward stability does not guarantee a small forward error $\|x - \tilde{x}\|$ . The forward error is bounded by: $\frac{\|x - \tilde{x}\|}{\|x\|} \leq \kappa(A) \frac{\|\Delta A\|}{\|A\|} + O(\|\Delta A\|^2)$ where $\kappa(A) = \|A\|\|A^{-1}\|$ is the condition number. An ill-conditioned matrix ( $\kappa(A) \gg 1$ ) amplifies backward error into large forward error.

The proof technique extends beyond linear systems to general numerical algorithms. The key insight is to work backward from the computed result: given output $\tilde{y}$ , find input perturbation $\Delta x$ such that $\tilde{y} = f(x + \Delta x)$ exactly, then bound $\|\Delta x\|$ .

ExampleQR Factorization Stability

For QR factorization of $A \in \mathbb{R}^{m \times n}$ , Householder reflections produce computed matrices $\tilde{Q}$ , $\tilde{R}$ satisfying: $\tilde{Q}\tilde{R} = A + \Delta A$ where $\|\Delta A\|_F \leq c(m,n)\epsilon_{\text{mach}}\|A\|_F$ and $\tilde{Q}$ is orthogonal to machine precision: $\|\tilde{Q}^T\tilde{Q} - I\| = O(\epsilon_{\text{mach}})$ .

This backward stability makes QR factorization preferred over forming the normal equations $A^TAx = A^Tb$ for least squares, since the normal equations square the condition number.

Wilkinson's approach revolutionized numerical analysis by shifting focus from forward error to backward error. A backward stable algorithm guarantees that:

The computed result is an exact solution to a nearby problem
The nearby problem differs from the original by amounts within data uncertainty
Forward error is bounded by problem conditioning times backward error

This framework separates algorithm quality (backward error) from problem difficulty (conditioning). Modern numerical linear algebra prioritizes backward stable algorithms: QR factorization for least squares, singular value decomposition (SVD) for rank-deficient problems, and iterative refinement for ill-conditioned systems.

The theorem also guides algorithm design: achieving backward stability typically requires careful ordering of operations, pivoting strategies, and sometimes compensated arithmetic. For example, Givens rotations and Householder reflections both achieve backward stability for orthogonalization, while classical Gram-Schmidt does not.