Skip to main content

Subsection 6.2.4 Stability of a numerical algorithm

Correctness in the presence of error (e.g., when floating point computations are performed) takes on a different meaning. For many problems for which computers are used, there is one correct answer and we expect that answer to be computed by our program. The problem is that most real numbers cannot be stored exactly in a computer memory. They are stored as approximations, floating point numbers, instead. Hence storing them and/or computing with them inherently incurs error. The question thus becomes "When is a program correct in the presense of such errors?"

Let us assume that we wish to evaluate the mapping \(f: {\mathcal D} \rightarrow {\mathcal R} \) where \({\mathcal D} \subset \Rn \) is the domain and \({\mathcal R} \subset \Rm \) is the range (codomain). Now, we will let \(\check f: {\mathcal D} \rightarrow {\mathcal R} \) denote a computer implementation of this function. Generally, for \(x \in {\mathcal D} \) it is the case that \(f( x) \neq \check f( x) \text{.}\) Thus, the computed value is not "correct". From the Notes on Conditioning, we know that it may not be the case that \(\check f(x) \) is "close to" \(f( x ) \text{.}\) After all, even if \(\check f \) is an exact implementation of \(f \text{,}\) the mere act of storing \(x \) may introduce a small error \(\deltax \) and \(f( x + \deltax ) \) may be far from \(f( x ) \) if \(f \) is ill-conditioned.

Figure In this illustation, \(f: {\cal D} \rightarrow {\cal R} \) is a function to be evaluated. The function \(\check f \) represents the implementation of the function that uses floating point arithmetic, thus incurring errors. The fact that for a nearby value, \(\check x \text{,}\) the computed value equals the exact function applied to the slightly perturbed input \(x \text{,}\) that is,
\begin{equation*} f( \check x ) = \check f( x ), \end{equation*}
means that the error in the computation can be attributed to a small change in the input. If this is true, then \(\check f \) is said to be a (numerically) stable implementation of \(f \) for input \(x \text{.}\)

The following defines a property that captures correctness in the presense of the kinds of errors that are introduced by computer arithmetic:

Definition Backward stable implementation.

Given the mapping \(f: D \rightarrow R \text{,}\) where \(D \subset \Rn \) is the domain and \(R \subset \Rm \) is the range (codomain), let \(\check f: D \rightarrow R \) be a computer implementation of this function. We will call \(\check f \) a (numerically) stable implementation of \(f \) on domain \({\mathcal D} \) if for all \(x \in D \) there exists a \(\check x \) "close" to \(x \) such that \(\check f( x ) = f( \check x ) \text{.}\)

In other words, \(\check f \) is a stable implementation if the error that is introduced is similar to that introduced when \(f\) is evaluated with a slightly changed input. This is illustrated in Figure for a specific input \(x \text{.}\) If an implemention is not stable, it is numerically unstable.

The algorithm is said to be forward stable on domain \({\mathcal D} \) if for all \(x \in {\mathcal D} \) it is that case that \(\check f( x ) \approx f( x ) \text{.}\) In other words, the computed result equals a slight perturbation of the exact result.