Conditioning and Backward Stability

Two distinct ideas that together explain when a computed answer can be trusted: sensitivity of the problem and quality of the algorithm.

Two separate questions

The accuracy of a numerical result depends on two independent things. First, how sensitive is the problem itself to perturbations in its data? This is conditioning, a property of the problem, not of any algorithm. Second, how well does the chosen algorithm cope with the inexact arithmetic of a computer? This is stability, a property of the algorithm. Confusing the two leads to blaming an algorithm for errors that are inherent in the problem.

Condition number

The condition number measures how much a relative change in the input can be amplified into a relative change in the output. A problem with a large condition number is ill-conditioned: even tiny input perturbations (including the unavoidable rounding of the input) can cause large output changes, and no algorithm can fully repair this. For solving a linear system, the relevant condition number is the ratio of the largest to smallest singular value of the matrix; a matrix near singularity is severely ill-conditioned.

Backward stability

An algorithm is backward stable if the answer it computes is the exact answer to a slightly perturbed version of the original problem, with the perturbation on the order of machine precision. Backward stability is a strong and practical guarantee: it says the algorithm introduces no more error than an unavoidable tiny change in the input would. Gaussian elimination with partial pivoting, the QR algorithm, and Householder QR factorization are backward stable.

The governing rule of thumb

Combining the two: the forward error (how wrong the answer is) is bounded roughly by the condition number times the backward error. So a backward-stable algorithm applied to a well-conditioned problem gives an accurate answer, while the same algorithm on an ill-conditioned problem may give a poor one, and that is not the algorithm's fault. This decomposition, forward error bounded by conditioning times backward error, is the central organizing principle of numerical analysis and the frame for judging every method covered here.