What is Numerical Stability?

Numerical stability concerns how errors introduced during the execution of an algorithm affect the result. It is a property of an algorithm rather than the problem being solved. I will assume that the errors under consideration are rounding errors, but in principle the errors can be from any source.

Consider a scalar function of a scalar . We regard as the input data and as the output. The forward error of a computed approximation to is the relative error . The backward error of is

If has a small backward error then it is the exact answer for a slightly perturbed input. Here, “small’ is interpreted relative to the floating-point arithmetic, so a small backward error means one of the form for a modest constant , where is the unit roundoff.

An algorithm that always produces a small backward error is called backward stable. In a backward stable algorithm the errors introduced during the algorithm have the same effect as a small perturbation in the data. If the backward error is the same size as any uncertainty in the data then the algorithm produces as good a result as we can expect.

If undergoes a relative perturbation of size then can change by as much as , where

is the condition number of at . An algorithm that always produces with a forward error of order is called forward stable.

The definition of implies that a backward stable algorithm is automatically forward stable. The converse is not true. An example of an algorithm that is forward stable but not backward stable is Gauss–Jordan elimination for solving a linear system.

If satisfies

with small in the sense described above, then the algorithm for computing is mixed backward–forward stable. Such an algorithm produces almost the right answer for a slightly perturbed input. The following diagram illustrates the previous equation.

With these definitions in hand, we can turn to the meaning of the term numerically stable. Depending on the context, numerical stability can mean that an algorithm is (a) backward stable, (b) forward stable, or (c) mixed backward–forward stable.

For some problems, backward stability is difficult or impossible to achieve, so numerical stability has meaning (b) or (c). For example, let , where and are -vectors. Backward stability would require the computed to satisfy for some small and , meaning that is a rank- matrix. But the computed contains independent rounding errors and is very unlikely to have rank .

We briefly mention some other relevant points.

• What is the data? For a linear system the data is or , or both. For a nonlinear function we need to consider whether problem parameters are data; for example, for are the and the constants or are they data, like , that can be perturbed?
• We have measured perturbations in a relative sense. Absolute errors can also be used.
• For problems whose inputs are matrices or vectors we need to use norms or componentwise measures.
• Some algorithms are only unconditionally numerically stable, that is, they are numerically stable for some subset of problems. For example, the normal equations method for solving a linear least squares problem is forward stable for problems with a large residual.