16
$\begingroup$

After my own research, the following picture emerges as the most frequently used example of catastrophic cancellation (It is indeed used in my class).


enter image description here


Could anyone explain why the plot takes that shape? (i.e., the widely fluctuating jagged line to the sides, and the vertical drop near the middle)

Minor point: why does the demonstrating function divides by $x^2$? Isn't $1 - \cos(x)$ enough to cause catastrophic cancellation?

$\endgroup$
8
  • 2
    $\begingroup$ If you plot $1 - \cos x$ over the same range of $x$, you won't see the cancellation because it is of order $x^2$ around the origin. $\endgroup$
    – user66081
    Jan 30, 2015 at 20:25
  • $\begingroup$ Lest anyone suspect, as i did, that this was an artifact of the plotting program used, here's the same weird result coming from (what I hope is) a completely different plotting program: a.pomf.se/inobme.png $\endgroup$
    – MJD
    Jan 30, 2015 at 20:26
  • $\begingroup$ This related question seems to suggest that under some conditions the same problem can occur with $1-\cos x$. $\endgroup$
    – MJD
    Jan 30, 2015 at 20:28
  • 10
    $\begingroup$ I suspect the machine wanted to punish you for having used Comic Sans. ;-) $\endgroup$
    – egreg
    Jan 30, 2015 at 20:41
  • $\begingroup$ I'm seeing the same thing in R. This supports the idea that this is an issue with floating-point numbers. $\endgroup$ Jan 30, 2015 at 21:46

1 Answer 1

17
$\begingroup$

When $\cos(x)$ is computed for a reasonably small $x$, a number like 0.99999999999994598649857etc is obtained; the IEEE double precision standard defines a way to round this number to roughly 16 decimals. Thus out comes something like 0.99999999999995. I didn't count the digits, but you get the idea (and anyway, rounding is done in base 2). This does not seem catastrophic. But now subtract 1 from both numbers, and you see that a huge relative error has been committed to that result. The division by $x^2$ roughly gives you this relative error, because when $x$ is small, then $\cos(x) \approx 1 - \frac12 x^2$ (according to Taylor series). So when $x$ is very small, $\cos(x)$ is rounded to 1 (no digits after the comma), which explains the plateau in your plot.

Follow up on OP's request: To formalize this, let $fl$, for "floating point arithmetics", be the function that rounds a real number to the nearest machine number ($=$ a number representable as double precision IEEE number, of which there are only finitely many). Although maybe not strictly accurately speaking (there may be optimization; there may be hidden extended precision computation; and the rounding is not always to the nearest machine number), the machine computes not $(1 - \cos(x)) / x^2$ but $$ fl( fl( 1 - {\color{red}{fl}}(\cos(x)) ) / fl(x^2) ) , $$ supposing we start with $x$ such that $x = fl(x)$. The issue originates with the application of the $fl$ that is marked in red, because $$ {\color{red}{fl}}(\cos(x)) = \cos(x) (1 + \delta) $$ where $|\delta| \leq \text{eps} \approx 10^{-16}$, and $\text{eps}$ is the smallest positive number such that $$ fl(1 + \text{eps}) \neq 1 . $$ Therefore, $$ 1 - {\color{red}{fl}}(\cos(x)) = 1 - \cos(x) + \delta \cos(x) \approx \tfrac12 x^2 + \delta $$ when $x$ is not too small (otherwise ${\color{red}{fl}}(\cos(x)) = 1$). When $x$ is of order $\sqrt{\text{eps}} \approx 10^{-8}$ (as in your picture), this result $\tfrac12 x^2$ is contaminated by an absolute error of $\delta$, or a relative error of $2 \delta / x^2$. So the final result $(1 - \cos(x)) / x^2$ is contaminated by an absolute error of $\delta / x^2 \approx 1$ when $x \approx \sqrt{\text{eps}}$, which, again, is what you see in the picture.

ps. There have been infamous consequences of finite precision arithmetics.

$\endgroup$
4
  • $\begingroup$ Could you elaborate more about the relative error? Plug in $\cos(x) \approx 1 - \frac12 x^2$ to $f(x) = \frac{1 - \cos(x)}{x^2}$, I simply get $\frac{1}{2}$ when $x$ is small. What's the problem then? $\endgroup$
    – Heisenberg
    Feb 5, 2015 at 20:26
  • 1
    $\begingroup$ @Heisenberg: see extended version $\endgroup$
    – user66081
    Feb 5, 2015 at 21:05
  • $\begingroup$ Isn't $1 - {\color{red}{fl}}(\cos(x)) = 1 - \cos(x) + \delta \cos(x) \approx \tfrac12 x^2 + \delta + \delta \frac{1}{2}x^2$? (note the last term). Are you removing it because multiplying $\delta$ and $x^2$ make it much smaller than the rest? $\endgroup$
    – Heisenberg
    Feb 5, 2015 at 21:12
  • 1
    $\begingroup$ @Heisenberg: yes, significantly smaller in the regime considered $\endgroup$
    – user66081
    Feb 5, 2015 at 21:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .