Skip to main content

Subsection C.2 Catastrophic 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*}
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.

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.

login