Why does this naive solution to catastrophic cancellation not work?

Question

I see on wikipedia that catastrophic cancellation is a phenomena where B~=A then A-B will have very high relative error compared to the true difference.

I quite naive solution occurred to me: why not just take: A-B~=(NA-NB)/N s.t. N>>1? This would make the 'true difference' much larger and should therefore decrease the relative error of approximating A-B by a lot right?

Answer 1

Consider a typical case where A and B are floating point numbers of the form M*(2^EXP). Catastrophic cancellation happens because M only has a limited number of bits, and M_A is approximately M_B so the high bits cancel. You only have a few significant bits left.

Now consider what happens is your solution, with N=16. That just performs the same calculation, except that the numbers now have the form M*(2^(EXP+4)). The problem is still M, not EXP.

You do have an additional problem, though, if EXP+4 overflows. Then the result would be INF-INF, which is NaN : Not a Number

Answer 2

We need to distinguish between the error when subtracting floating point numbers, and the error when subtracting two numbers which are approximated by their two closest floating point representables.

If A and B are floating point numbers with A/2 <= B <= 2A, then the subtraction A - B is exact. This is the Sterbenz lemma. So if you were thinking that A and B are floating point representables, the premise of the question is incorrect.

However, if you imagined that A and B are arbitrary real numbers, then they must be approximated by floating point numbers a and b, according to the rounding model a = A(1+?), b = B(1+?), where ?<=? ?<=? where ? is the unit round off.

The relative error is |(a - b) - (A-B)|/|A - B| = |A? - ??|/|A-B| <= ?|A+B|/|A-B|. If you rescale all these quantities, you also rescale the error, i.e.,

|Na - Nb - (NA-NB)|/|NA - NB| = |NA? - N??|/|NA-NB| = |A? - ??|/|A-B|.