1
$\begingroup$

I'm trying to follow the wikipedia page about catastrophic cancellation but I've hit something that just doesn't make sense to me. They say that subtraction can amplify existing approximation errors (by making relative error of the difference much larger than relative error of the terms).

But also they say that relative approximation error of the difference $x-y$ is $\delta_{x-y}=|(x\delta_x-y\delta_y)/(x-y)|$ s.t. $\forall z, \delta_z:=$ relative approximation error of z (pic below):

enter image description here

And naively you could say that $\delta_x=\delta_y=\epsilon$ (machine epsilon, upper bound of relative approximation error of floats). Which gives: $\delta_{x-y}=|(x\epsilon-y\epsilon)/(x-y)|=\epsilon|(x-y)/(x-y)|=\epsilon$. But this contradicts the statement that subtraction can greatly increase the relative error... What am I missing?

$\endgroup$

1 Answer 1

4
$\begingroup$

The issue they are talking about is if $x$ and $y$ are close. For example, suppose we know that $x = y (1 + \epsilon) > y$ for some small $\epsilon > 0$. Then the relative error you wrote can be written as:

$$\left\lvert\frac{x \delta_x - y \delta_y}{x - y}\right\rvert = \left|(\delta_x - \delta_y)/\epsilon +\delta_x\right|$$

As $\epsilon$ gets smaller, the error blows up to an arbitrarily large size. The only way this is not true is if in fact $\delta_x = \delta_y$ such as in your example, but this is a special case that is not going to be the case in practice.

$\endgroup$
7
  • $\begingroup$ Thanks for the answer! Would you be able to add a remark about how you can calculate, estimate or bound this error in practice? The idea that leaped to my mind was the naive assumption I mentioned which doesn't work. $\endgroup$
    – profPlum
    Jan 31 at 21:23
  • $\begingroup$ @profPlum I don't know what techniques might exist in practice, but one thing you could do is perform the computation with the level of precision you want to normally use (say double precision) and then do the same computation using a library for multiprecision and see how different the results are. Not perfect but should be enough in general to get a sense of how much your implementation for some computation is sensitive to these issues. $\endgroup$
    – spektr
    Feb 1 at 18:10
  • $\begingroup$ That makes sense, but it makes me wonder what the point in the equations are lol. Another approach I've tried recently is randomly sampling d_x & d_y ~ U(0, machine_eps) & approximating your epsilon directly with floating point arithmetic to get an approx distribution of relative error. $\endgroup$
    – profPlum
    Feb 1 at 18:24
  • $\begingroup$ Anyhow you answered my question thanks. $\endgroup$
    – profPlum
    Feb 1 at 18:25
  • 1
    $\begingroup$ @profPlum if I had a numerical function that I wanted to see if it was doing computations in a way to avoid this issue, I would probably throw lots of random inputs at it and perform the computations in both double precision and extended precision and see how they compare so I can get a distribution of the relative error. If the errors look pretty good relative to machine epsilon for double precision, then I might feel pretty good. Of course this is not exhaustive, though, so a better analysis still might be worthwhile. $\endgroup$
    – spektr
    Feb 1 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.