Numerical stability: Encyclopedia II - Numerical stability - Backward stability

Numerical stability - Backward stability

Consider the problem being solved by the numerical algorithm as a function f mapping the data x to the solution y. The actual result of the algorithm, say y*, will usually deviate from the exact solution. The main causes of error are round-off error, truncation error and data error. The forward error of the algorithm is the difference between the actual result and the exact solution. The backward error is the smallest Δx such that f(x + Δx) = y*; in other words, the backward error tells us what is the problem actually solved by the algorithm. The forward and backward error are related by the condition number: the forward error is at most as big in magnitude as the condition number multiplied by the magnitude of the backward error.

The algorithm is said to be backward stable if the backward error is small for all inputs x. Of course, "small" is a relative term and its definition will depend on the context. Often, we want the error to be of the same order as, or perhaps only a few orders of magnitude bigger than, the unit round-off.

In many cases, it is more natural to consider the relative error

instead of the absolute error Δx.

Adapted from the Wikipedia article "Backward stability", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki