In numerical analysis, catastrophic cancellation[1][2] is the phenomenon that subtracting good approximations to two nearby numbers may yield a very bad approximation to the difference of the original numbers.
long, and they are measured with a ruler that is good only to the centimeter, then the approximations could come out to be
These may be good approximations, in relative error, to the true lengths: the approximations are in error by less than 0.2% of the true lengths,
However, if the approximate lengths are subtracted, the difference will be
, is in error by almost 100% of the magnitude of the difference of the true values,
It depends only on how large the difference is, and on the error of the inputs.
Catastrophic cancellation may happen even if the difference is computed exactly, as in the example above—it is not a property of any particular kind of arithmetic like floating-point arithmetic; rather, it is inherent to subtraction, when the inputs are approximations themselves.
Formally, catastrophic cancellation happens because subtraction is ill-conditioned at nearby inputs: even if approximations
Thus, the relative error of the exact difference
which can be arbitrarily large if the true values
Subtracting nearby numbers in floating-point arithmetic does not always cause catastrophic cancellation, or even any error—by the Sterbenz lemma, if the numbers are close enough the floating-point difference is exact.
But cancellation may amplify errors in the inputs that arose from rounding in other floating-point arithmetic.
, the naive attempt to compute the mathematical function
are close in magnitude, because the subtraction can expose the rounding errors in the squaring.
In IEEE 754 binary64 arithmetic, evaluating the alternative factoring
gives the correct result exactly (with no rounding), but evaluating the naive expression
, lost due to rounding when calculating the intermediate squared values.
When computing the complex arcsine function, one may be tempted to use the logarithmic formula directly:
is evaluated in floating-point arithmetic giving
denotes floating-point rounding, then computing the difference
, but using the naive logarithmic formula in IEEE 754 binary64 arithmetic may give
, with only five out of sixteen digits correct and the remainder (underlined) all incorrect.
, so the subtraction is effectively addition with the same sign which does not cancel.
Numerical constants in software programs are often written in decimal, such as in the C fragment double x = 1.000000000000001; to declare and initialize an IEEE 754 binary64 variable named x.
is not a binary64 floating-point number; the nearest one, which x will be initialized to in this fragment, is
Although the radix conversion from decimal floating-point to binary floating-point only incurs a small relative error, catastrophic cancellation may amplify it into a much larger one: The difference
, and the floating-point subtraction y - x is computed exactly by the Sterbenz lemma.
of the original values as written in decimal: catastrophic cancellation amplified a tiny error in radix conversion into a large error in the output.
Cancellation is sometimes useful and desirable in numerical algorithms.
For example, the 2Sum and Fast2Sum algorithms both rely on such cancellation after a rounding error in order to exactly compute what the error was in a floating-point addition operation as a floating-point number itself.