Why is 'catastrophic cancellation' called so?

Solution 1:

The root of the evil is that calculators work with a finite number of digits (well, we can't afford machines with infinite resources yet). When you want to represent real-life numbers, some can be huge, some can be tiny, and this raises an issue.

Floating-point:

If the decimal point is fixed, you can' represent them all, there can be so-called overflow or underflow; and for intermediate orders of magnitude, you lose significant digits.

For example, using the $5.5$ fixed-point representation, $127500.$ and $0.0000096695$ cannot be represented, and $\pi=3.14159$ just uses six significant digits, four positions are wasted.

The floating-point representation solves these problems by specifying the position of the decimal point, as in the scientific notation:

$127500.=1.275000000\cdot10^5, 0.0000096695=9.669500000\cdot10^{-6}, \pi=3.141592654\cdot10^0$.

Catastrophic cancellation:

(This concept is actually unrelated to floating-point.)

Assume you want to play with the approximation $\pi\approx355/113=3.14159292\cdots$.

If you want to take the sum with $\pi$, all goes well.

$$\frac{3.14159265+3.14159292}2=3.14159278.$$

But now if you want to take the difference,

$$\frac{3.14159265-3.14159292}2=-0.000000135,$$

only three significant decimals remain. This is a catastrophy, because you started with nine figures and end-up with just three, and this is irreversible ! (Floating-point will not come to the rescue, $-0.000000135=-1.35\cdot10^{-7}$ still has three significant digits.)

This phenomenon makes some problems very difficult to solve numerically.

In some cases, catastrophic cancellation can be avoided. For example, when solving the quadratic equation

$$x^2-1000.001x+1=0,$$

the classical formula says

$$x=\frac{1000.001\pm\sqrt{1000.001^2-4}}2=\frac{100.001\pm999.999}2.$$

Assuming you can only compute with five significant digits, using floating-point, you obtain

$$x=\frac{1000.00\pm999.99}2=999.95\text{ and }0.005,$$ where the second root is very very inaccurate.

You can get a much better estimate by using the fact that the product of the roots is $1$, and the second root evaluates to

$$\frac1{999.95}=0.0010005$$