Forward and backward stability for a problem family under an arithmetic model

Fix normed spaces $(X,\parallel \cdot {\parallel }_X)$ and $(Y,\parallel \cdot {\parallel }_Y)$ over $\mathbb{R}$ (A norm on a real vector space, the induced metric, and the dictionary with the metric axioms), a map $f:X\to Y$, a class $\mathcal{I}\subseteq \mathrm{dom}f$ of inputs, an arithmetic model with unit roundoff $u$ (The standard relative floating-point model and unit roundoff), and an algorithm that, for each input $x\in \mathcal{I}$, returns an approximate value $\widehat{y}\in Y$ of Absolute and relative forward error for an approximate value of a problem map.

Backward stability. The algorithm is backward stable on $\mathcal{I}$ when there is a constant $C\ge 0$ such that for every $x\in \mathcal{I}$ there is an input $\tilde{x}\in \mathrm{dom}f$ with

$\widehat{y}=f(\tilde{x})\text{and}\parallel \tilde{x}-x{\parallel }_X\le Cu\parallel x{\parallel }_X\mathrm{.}$

The computed answer is exactly right for a slightly perturbed input, and the perturbation is at most a fixed multiple $C$ of the unit roundoff.

Forward stability. The algorithm is forward stable on $\mathcal{I}$ when there is a constant $C\ge 0$ such that for every $x\in \mathcal{I}$ with $f(x)\mathrm{\ne }0$,

$\frac{\parallel \widehat{y}-f(x){\parallel }_Y}{\parallel f(x){\parallel }_Y}\le Cu\mathrm{.}$

The standard linear-system specialization. Fix $n\ge 1$ and a rational $p\ge 1$. For the problem "given $A\in {\mathrm{GL}}_n(\mathbb{R})$ and $b$, return $x$ with $Ax=b$", one usually measures the two data components separately rather than forcing the pair $(A,b)$ into the single fixed input norm above. An algorithm is called normwise backward stable on a declared class of systems when one constant $C$ makes every returned $\widehat{x}$ satisfy ${\eta }_p(\widehat{x})\le Cu$ in the sense of Normwise and componentwise backward error for an approximate linear-system solution; the componentwise specialization requires $\omega (\widehat{x})\le Cu$. Thus there are perturbations $\mathrm{\Delta }A,\mathrm{\Delta }b$ with $(A+\mathrm{\Delta }A)\widehat{x}=b+\mathrm{\Delta }b$ and separately measured relative sizes at most $Cu$. These are specialized product-wise definitions, not literal instances of one undeclared norm on the data pairs. Stability remains a property of the algorithm on the problem class, while the condition number is a property of the problem itself.

• Backward stability does not by itself bound the forward error. It bounds the data perturbation; converting that into an answer bound costs one factor of the condition number, by Local conditioning times backward error controls forward error to first order. A backward-stable algorithm on an ill-conditioned problem can still return a large forward error: for $A=\mathrm{diag}(1,\epsilon )$, $b=(1,\epsilon )$, and $\widehat{x}=(1,0)$, the backward error is $O(\epsilon )$ while the relative forward error is $1\mathrm{/}\sqrt{2}$.

• The constant $C$ is part of the honest statement. The definition records "at most $C$ times the unit roundoff" for some fixed $C$, not "exactly the unit roundoff"; polynomial growth in the dimension is folded into $C$, and a stability claim without its class $\mathcal{I}$ and its constant is not a stability claim.