Numerical Linear Algebra

numerical stability

Two different things can go wrong with a computed answer, and it pays to separate them. One is the problem itself: some problems amplify any input error no matter who solves them (these are ill-conditioned). The other is the algorithm: a clumsy method can add error a well-behaved problem never had to suffer. Numerical stability is a property of the algorithm, measuring how much extra error it introduces.

Forward error asks the obvious question: how far is the computed answer x-hat from the true answer x, measured as ||x-hat - x|| / ||x||? Backward error asks a subtler one: for what nearby problem is x-hat the exact answer? An algorithm is backward stable if it always returns the exact solution of a problem that differs from yours by only a tiny relative amount, on the order of machine epsilon.

Backward stability is the gold standard precisely because it is achievable and meaningful. You usually cannot promise a small forward error — that depends on conditioning, which is out of the algorithm's hands. But you can often promise that the algorithm did not do anything worse than perturbing the data slightly. The two are linked by the rule of thumb: forward error <~ condition number times backward error.

So when an algorithm is backward stable and your answer is still bad, the algorithm is not to blame — the problem was ill-conditioned. This is the central diagnostic of numerical linear algebra. Gaussian elimination with partial pivoting, QR via Householder reflections, and the symmetric QR eigensolver are all backward stable; this is why they are trusted.

forward error <~ cond(A) * backward error

The rule of thumb that ties the three ideas together: even with a tiny backward error, a large condition number can blow up the forward error.

A backward-stable algorithm can still give a wildly wrong answer — if the problem is ill-conditioned. Stability is about the algorithm doing its part; conditioning is about the problem doing its part. Always check both.

Also called
backward stabilityforward stability