Numerical Stability

A procedure is considered Numerically Stable if it is not susceptible to rounding errors. Consider the equation:

$y = 1 - \sqrt{1 - x}$

Suppose we can only work to a maximum of 6 significant figures, and wanted to evaluate for $$x = 0.0001$$, we could proceed as follows:

\begin{align} y & = 1.00000 - \sqrt{1.00000 - 0.000100000} \\ y & = 1.00000 - \sqrt{0.999900} \\ y & = 1.00000 - 0.999950 \\ y & = 0.0000500000 \end{align}

Now let’s try again, but this time we can only work to 3 significant figures:

\begin{align} y & = 1.00 - \sqrt{1.00 - 0.000100} \\ y & = 1.00 - \sqrt{1.00} \\ y & = 1.00 - 1.00 \\ y & = 0.00 \end{align}

Even though the same answer could be represented by 3 significant figures, rounding errors have led to an incorrect answer because this approach is numerically unstable:

• We are adding or subtracting a large number and a small number such that the small number is lost due to rounding.
• The correct solution is very sensitive to the value of the small number

We can resolve this by choosing an alternative method that eliminates the large numbers in the expression by using a binomial approximation:

\begin{align} y = 1 - \sqrt{1 - x} & \approx 1 - (1 - \frac{1}{2}x) \\ & = 1 - 1 + \frac{1}{2}x \\ & = \frac{1}{2}x \end{align}

Note that this expression allows us to cancel out the “$$1 - 1$$” that causes the rounding errors, and gives us a more reliable answer for small $$x$$:

\begin{align} y & = \frac{1.00}{2.00}0.000100 \\ y & = 0.0000500 \end{align}

This approach will always give an appropriate answer for the accuracy we are working to, we would get the same answer even for just one signficiant figure of accuracy, so is considered numerically stable.

For a practical example, I calculated $$1 - \sqrt{1 - x}$$ for various values of $$x$$ in Excel using both the direct and binomial method and normalised against the correct value, shown as a chart in Figure 1, such that a $$1.0$$ indicates the correct value.

We can see that above about $$10^{-3}$$ the binomial method is a poor approximation, but below $$10^{-14}$$ the direct method becomes numerically unstable. To robustly evaluate the expression, we might draw a line at, say $$10^{-8}$$ and use the direct method for values larger than this and the binomial method for values smaller.