SectionC.2Catastrophic cancellation

Recall that if

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

then the quadratic formula gives the largest root of this quadratic equation:

\begin{equation*} \chi = \frac{- \beta + \sqrt{\beta^2 - 4 \gamma}}{2}. \end{equation*}
ExampleC.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.

RemarkC.2.0.2.

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

Notice that in this example it is not inherently the case that a small relative change in the input is amplified into a large relative change in the output (as is the case when solving a linear system with a poorly conditioned matrix). The problem is with the standard formula that was used. Later we will see that this is an example of an unstable algorithm.