Approximation error and numerical stability

Intuitive problem

A calculator carrying ten digits looks exact, yet it can hand back an answer wrong in its very first digit. Subtract 1.000000001 from 1.000000002 and the true difference is one part in a billion; the calculator, holding only so many digits, may have already rounded both inputs and now returns a difference built almost entirely from the digits it could not keep. The size of the numbers said nothing about the trouble. The trouble came from how close they were, and from the operation performed on them.

Definition

Two measures of error matter, and they must be kept apart. Absolute error is the plain difference between the computed value and the true one; relative error is that difference divided by the true value, and it is usually what counts because it tracks how many significant digits survive. Two sources feed them. Truncation error is the gap left when an infinite process is stopped after finitely many steps, as when a series is cut off. Rounding error is what enters because each stored number and each operation is held to finite precision.

The distinction the whole entry turns on is between conditioning and stability. Conditioning is a property of the problem: how much the true answer moves when the inputs move a little. Stability is a property of the method: whether the algorithm amplifies the rounding it cannot avoid. For subtraction the conditioning is captured by a condition number, the ratio of the sum of the magnitudes to the magnitude of the difference, written as the quantity mod x plus mod y over mod of x minus y; when x and y are close that ratio is enormous, and the problem itself is ill-conditioned regardless of how carefully it is computed.

Derivation

The analysis starts from one axiom, the floating-point rounding model: any single stored operation returns the true result multiplied by one plus a small relative perturbation, with the perturbation bounded in size by the machine precision, usually written u. In symbols the computed value of x op y equals the true x op y times the quantity one plus delta, with mod delta at most u.

Propagate this through the four operations. Under multiplication and division the relative errors of the inputs add, plus one more unit of u from the operation itself, so the relative error grows slowly and predictably. Under addition of like-signed numbers the result is likewise well behaved. Subtraction of nearly equal numbers is where it breaks. The absolute error carried in from earlier steps is unchanged by the subtraction, but the result is tiny, so the relative error, absolute error over result, is magnified by exactly the ratio in the condition number above. Catastrophic cancellation is not an anecdote to memorize; it falls straight out of the rounding model once the result of a subtraction is small.

Visual representation

Two pictures fix the ideas. The first is a row of significant digits: two ten-digit numbers agreeing in their first eight digits, subtracted, leave a result whose leading eight digits have cancelled to zero and whose meaning now rests on the final two, so eight digits of confidence became two. The second is the total-error curve against step size in a method that trades truncation for rounding, such as a numerical derivative: as the step shrinks the truncation error falls but the rounding error rises, so the total traces a U, and the best step is the bottom of the U, not the smallest step available.

Counterexample

Blame runs in both directions, and honesty requires both cases. First, method's fault: computing the variance of a data set by the one-pass textbook formula, which subtracts the square of the mean from the mean of the squares, can lose most of the digits when the mean is large and the spread small, even though the variance itself is a perfectly well-conditioned quantity; a two-pass method that subtracts the mean first computes the same variance with the digits intact. There the problem was fine and the algorithm was to blame. Second, problem's fault: subtracting two numbers that are nearly equal and already carry measurement error is ill-conditioned no matter how the subtraction is arranged, because the damage is in the inputs; no clever algorithm rescues it, and the only fix is to reformulate the question so the near-equal subtraction never happens.

Common mistakes

The first mistake is trusting digits because the machine displays them, when the last several may be pure noise from a cancellation. The second is blaming the algorithm for what is really an ill-conditioned problem, or the reverse, excusing an unstable algorithm by pointing at the data. The third is shrinking a step size toward zero to reduce truncation error while walking straight up the rising side of the rounding curve, making the total answer worse.

Practice problems

Take a data set whose mean is far larger than its spread, for instance values clustered near one million but differing only in their last few digits. Compute the variance two ways, once with the one-pass formula that subtracts the square of the mean from the mean of the squares, and once with the two-pass method that subtracts the mean from each value first. Decide in advance which you expect to trust and predict how many significant digits the one-pass subtraction will lose, reasoning from the condition number of that subtraction. Then compute both and compare. Success is the correct trust call together with a digit-loss prediction within one digit of what you actually observe.