ALAFF Catastrophic cancellation

Section C.2 Catastrophic cancellation

$\begin{equation*} \chi^2 + \beta \chi + \gamma = 0 \end{equation*}$

$\begin{equation*} \chi = \frac{- \beta + \sqrt{\beta^2 - 4 \gamma}}{2}. \end{equation*}$

Example C.2.0.1.

We use the quadratic equation in the exact order indicated by the parentheses in

$\begin{equation*} \chi = \left[ \frac{ \left[- \beta + \left[ \sqrt{[[\beta^2] - [4 \gamma]]}\right]\right]}{2}\right], \end{equation*}$

truncating every expression within square brackets to three significant digits, to solve

$\begin{equation*} \chi^2 + 25 \chi + \gamma = 0 \end{equation*}$

$\begin{equation*} \begin{array}{rcl} \chi \amp = \amp \left[ \frac{ \left[- 25 + \left[ \sqrt{[[25^2] - [4]]}\right]\right]}{2}\right] = \left[ \frac{ \left[- 25 + \left[ \sqrt{[625 - 4]}\right]\right]}{2}\right] \\ \amp = \amp \left[ \frac{ \left[- 25 + \left[ \sqrt{621}\right]\right]}{2}\right] = \left[ \frac{ \left[- 25 + 24.9\right]}{2}\right] = \left[ \frac{ -0.1}{2}\right] = -0.05. \end{array} \end{equation*}$

Now, if you do this to the full precision of a typical calculator, the answer is instead approximately $-0.040064 \text{.}$ The relative error we incurred is, approximately, $0.01/0.04 = 0.25 \text{.}$

What is going on here? The problem comes from the fact that there is error in the $24.9$ that is encountered after the square root is taken. Since that number is close in magnitude, but of opposite sign to the $-25$ to which it is added, the result of $-25 + 24.9$ is mostly error.

This is known as catastrophic cancelation: adding two nearly equal numbers of opposite sign, at least one of which has some error in it related to roundoff, yields a result with large relative error.

Now, one can use an alternative formula to compute the root:

$\begin{equation*} \chi = \frac{- \beta + \sqrt{\beta^2 - 4 \gamma}}{2} = \frac{- \beta + \sqrt{\beta^2 - 4 \gamma}}{2} \times \frac{- \beta - \sqrt{\beta^2 - 4 \gamma}} {- \beta - \sqrt{\beta^2 - 4 \gamma}}, % = % \frac{ \beta^2 - ( \beta^2 - 4 \gamma )} % {2(- \beta - \sqrt{\beta^2 - 4 \gamma})}, \end{equation*}$

which yields

$\begin{equation*} \chi = \frac{ 2 \gamma } {- \beta - \sqrt{\beta^2 - 4 \gamma}}. \end{equation*}$

Carrying out the computations, rounding intermediate results, yields $-.0401\text{.}$ The relative error is now $0.00004/0.040064 \approx .001 \text{.}$ It avoids catastrophic cancellation because now the two numbers of nearly equal magnitude are added instead.

🔗

Remark C.2.0.2.

The point is: if possible, avoid creating small intermediate results that amplify into a large relative error in the final result.