Numerical stability

Definition

Let $X$ and $Y$ be normed spaces with norms $\norm{\cdot}$, and let $f \colon X \to Y$ be a problem. An algorithm for $f$ is a family of maps $\tilde f \colon X \to Y$, one for each floating-point system, with unit roundoff $u$ as in machine epsilon. All $O$ bounds below are as $u \to 0$, uniform in $x \ne 0$.

1. The algorithm is backward stable if for each $x$ there is $\tilde x$ with $\tilde f(x) = f(\tilde x)$ and $\norm{\tilde x - x}/\norm{x} = O(u)$.
2. The algorithm is stable if for each $x$ there is $\tilde x$ with $\norm{\tilde x - x}/\norm{x} = O(u)$ and $\norm{\tilde f(x) - f(\tilde x)}/\norm{f(\tilde x)} = O(u)$.
3. The algorithm is forward stable if $\norm{\tilde f(x) - f(x)}/\norm{f(x)} = O(\kappa(x) \, u)$, where $\kappa(x)$ is the relative condition number of $f$ at $x$.