Editing Numerical stability (section)

== Stability in numerical linear algebra ==
There are different ways to formalize the concept of stability. The following definitions of forward, backward, and mixed stability are often used in [[numerical linear algebra]].

[[File:Forward and backward error.svg|frame|Diagram showing the '''forward error''' {{math|Δ''y''}} and the '''backward error''' {{math|Δ''x''}}, and their relation to the exact solution map&nbsp;{{mvar|f}} and the numerical solution&nbsp;{{mvar|f*}}.]]

Consider the problem to be solved by the numerical algorithm as a [[function (mathematics)|function]]&nbsp;{{mvar|f}} mapping the data&nbsp;{{mvar|x}} to the solution&nbsp;{{mvar|y}}. The result of the algorithm, say {{mvar|y}}*, will usually deviate from the "true" solution&nbsp;{{mvar|y}}. The main causes of error are [[round-off error]] and [[truncation error]]. The ''forward error'' of the algorithm is the difference between the result and the solution; in this case, {{math|1=Δ''y'' = ''y''* − ''y''}}. The ''backward error'' is the smallest {{math|Δ''x''}} such that {{math|1=''f'' (''x'' + Δ''x'') = ''y''*}}; in other words, the backward error tells us what problem the algorithm actually solved. 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.

In many cases, it is more natural to consider the [[relative error]] <math display="block"> \frac{|\Delta x|}{|x|} </math> instead of the absolute error {{math|Δ''x''}}.

The algorithm is said to be ''backward stable'' if the backward error is small for all inputs&nbsp;{{mvar|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]].

[[File:Mixed stability diagram.svg|thumb|Mixed stability combines the concepts of forward error and backward error.]]

The usual definition of numerical stability uses a more general concept, called ''mixed stability'', which combines the forward error and the backward error. An algorithm is stable in this sense if it solves a nearby problem approximately, i.e., if there exists a {{math|Δ''x''}} such that both {{math|Δ''x''}} is small and {{math|''f'' (''x'' + Δ''x'') − ''y''*}} is small. Hence, a backward stable algorithm is always stable.

An algorithm is ''forward stable'' if its forward error divided by the condition number of the problem is small. This means that an algorithm is forward stable if it has a forward error of magnitude similar to some backward stable algorithm.