Conditioning and Stability: Whose Fault Is the Error

When a numerical result is inaccurate, there are exactly two candidates, and they demand opposite responses.

The algorithm may be at fault: a sequence of operations that loses precision unnecessarily, like the textbook quadratic formula from the second lesson. This is a bug, and rewriting the computation fixes it.

The problem may be at fault: the true mathematical answer may be so sensitive to its inputs that no algorithm could do better, because the inputs themselves are only known to sixteen digits. This is not a bug, and no rewriting fixes it.

Conflating the two wastes effort in both directions. People rewrite stable code chasing an error that was inherent to the problem, and they accept inherent-looking errors that were actually a fixable algorithm.

Numerical analysis separates them with two named quantities: conditioning describes the problem, stability describes the algorithm. Getting these apart is the single most useful idea in the subject.

The condition number measures how much a small relative change in the input changes the output, relatively. It is a property of the mathematical problem and the specific input, and it exists whether or not a computer is involved.

A condition number of 1 means input and output perturbations are the same size. A condition number of 10 to the 8 means a relative input perturbation of 10 to the minus 16 becomes a relative output perturbation of 10 to the minus 8: eight of your sixteen digits are gone before any algorithm runs.

The rule of thumb follows directly. Digits lost is roughly the base-10 logarithm of the condition number. Sixteen available digits, a condition number of 10 to the 12, and four digits survive.

What makes this a hard limit is that your inputs are already inexact. They were measured, or they were rounded on entry, so a perturbation of at least machine epsilon is present before the computation begins. The problem then amplifies it by its condition number, and no algorithm can un-amplify it.

An ill-conditioned problem is one where that factor is large. Its answer is genuinely uncertain given the precision of its inputs.

A two by two system makes the effect visible without any linear algebra machinery.

def solve2(a, b, c, d, e, f):
    """Solve [a b; c d] x = [e f] by Cramer's rule."""
    det = a*d - b*c
    return ((e*d - b*f) / det, (a*f - e*c) / det)

# two nearly parallel lines
solve2(1.0, 1.0, 1.0, 1.0000001, 2.0, 2.0000001)
# (1.000000002220446, 0.999999997779554)     true answer: (1, 1)

# nudge one right-hand side entry by 1e-7
solve2(1.0, 1.0, 1.0, 1.0000001, 2.0, 2.0000002)
# (0.0, 2.0)

A change of 1e-7 in one input moved the answer from (1, 1) to (0, 2). The output moved by order 1 in response to an input change of order 1e-7, so the amplification factor is about 10 to the 7.

Geometrically the two equations are nearly parallel lines, and their intersection point slides enormously when either line tilts slightly. That is what ill-conditioning is, and it is a fact about the geometry rather than about the code.

Nothing here is fixable by a better solver. The question "where do these two nearly parallel lines cross" does not have a well-determined answer when the lines are known to only seven digits.

Stability is the complementary property, and it belongs to the algorithm rather than the problem.

The useful formulation is backward error analysis, developed by James Wilkinson. Rather than asking how far the computed answer is from the true one, it asks a different question: for what nearby problem is this computed answer the exact solution?

An algorithm is backward stable when the answer it produces is the exact answer to a problem within rounding distance of the one you asked. That is the strongest guarantee a finite-precision algorithm can offer, and it is achievable.

The reframing is powerful because it separates the two concerns cleanly. A backward stable algorithm has done everything possible: it solved a problem indistinguishable from yours, given your input precision. If the answer is still inaccurate, the amplification came from conditioning, and the algorithm is exonerated.

An unstable algorithm produces an answer that is not the exact solution to any nearby problem. It manufactured error. The textbook quadratic formula does this: its bad root is not the exact root of any quadratic close to the one supplied.

Reading the diagram in order prevents the two most common wasted efforts.

The left path is a genuine bug with a genuine fix. The quadratic formula, naive summation, and 1 - cos(x) all live here, and rewriting recovers the accuracy.

The box at the bottom right is the one people resist. If the problem is ill-conditioned and the algorithm is backward stable, the inaccuracy is real, unavoidable, and correctly reported. Switching libraries will not help, and higher precision only buys digits proportional to the extra precision, which is a delaying tactic rather than a fix.

The response there is to change the question. Reformulate to a better-conditioned equivalent, add regularisation to trade a little bias for far more stability, or improve the inputs.

That last option is the one most often overlooked. If the condition number is 10 to the 8 and the inputs are known to six digits, the answer is meaningless regardless of the arithmetic, and the fix is measurement rather than code.

Crossing the two properties gives four cases, and each has a different correct response.

The bottom right cell is where debugging goes wrong. With both problems present, rewriting the algorithm improves matters and does not make the result accurate, which reads as evidence the rewrite failed. It did not; the remaining error is the conditioning.

The correct sequence is to fix stability first, then measure what is left and compare it against what the condition number predicts. If they agree, you are done, and the residual inaccuracy is a property of the question rather than a defect.

The top right cell is the encouraging one, and it is more common than expected: an ordinary, well-behaved problem being computed badly. Every example in the second lesson was this case, and every one was fixed by rearranging the arithmetic without any change to precision.

Neither quantity requires theory to approximate, and both are worth measuring before optimising anything.

Conditioning by perturbation. Nudge each input by a relative amount around 10 to the minus 8, rerun, and observe the relative change in the output. The ratio estimates the condition number directly, and the two-by-two example above was exactly this experiment. It costs a handful of extra runs and answers the question that determines everything else.

Stability by the residual. Substitute the computed answer back into the original problem. A backward stable algorithm produces a small residual even on an ill-conditioned problem, because it solved a nearby problem exactly. A large residual indicates instability rather than conditioning.

That pairing is diagnostic. Small residual plus inaccurate answer means ill-conditioned and stable, so stop optimising the code. Large residual means the algorithm is at fault, whatever the conditioning.

For library routines, the work is usually already done. Standard implementations of matrix factorisations, linear solvers and eigenvalue problems are backward stable and documented as such, and many expose a condition number estimate alongside the answer. Reading it is the cheapest possible version of this analysis.

Four lessons, from representation to diagnosis.

A float is a finite value from a logarithmically spaced set, and every operation is correctly rounded to about sixteen relative digits. That guarantee is per-operation and relative, which leaves the loophole: when a result is much smaller than its inputs, inherited error is promoted from insignificant to dominant. Comparison then needs a tolerance, and no universal one exists because "close enough" is a claim about the problem. And accuracy itself has two independent causes, only one of which is in your code.

The transferable habit is a single question asked in the right order. Is this problem well conditioned? If yes, any inaccuracy is a bug and worth hunting. If no, find out how many digits the conditioning permits, and stop when you have them.

That inverts the usual instinct, which is to reach for higher precision when results look wrong. Higher precision helps only in the well-conditioned case, where it was rarely needed, and merely delays the problem in the ill-conditioned one, where the answer was never determined by the inputs to begin with.

The standard reference for going further is Nicholas Higham's Accuracy and Stability of Numerical Algorithms, which works through the analysis for essentially every algorithm in common use.