Franklin's Notes

Stability in floating-point

Let $f:X\to Y$ represent an "algorithm" mapping from a normed vector space $X$ to $Y$, and let $\tilde f:X\to Y$ be the floating point/computer version of this algorithm. We assume the following properties of floating point arithmetic:

where $\cdot$ is some operation like $+,\times,-,\div$ and $\odot$ is its floating-point analogue, and $\epsilon$ is a small number $|\epsilon|<\epsilon_m$ that depends on $x,y$.

Some functions $f$ simply cannot be implemented in such a way that the relative error between $\tilde f$ and $f$ is guaranteed to be small. For instance, poorly conditioned functions cannot be implemented with a guarantee of small relative error. Therefore, rather than seeking algorithms with small relative error, we seek algorithms that are stable. Stability requires that for any given input value $x\in X$, there exists $\tilde x\in X$ such that and where the $\mathcal O\text{s}$ hide two universal constants that are independent of $x$. Trefethen and Bau pithily summarize stability by saying

$\tilde f$ is stable if it gives nearly the right answer to nearly the right question.

There is also a stronger form of stability called backwards stability which requires that there always exists $\tilde x$ such that and $\tilde f(x)=f(\tilde x)$, or in other words,

$\tilde f$ is backwards stable if it gives exactly the right answer to nearly the right question.

The usage of $\mathcal O$ in the above definitions is a bit confusing. It is meant to conceal a constant $C>0$ independent of the input value $x$, such that the LHS is bounded above by $C\epsilon_m$ in the limit as $\epsilon_m\to 0$. Philosophically, it's as if we were considering a sequence of different computer architectures capable of supporting greater and greater amounts of precision, and designating as "stable" the algorithms that satisfy these properties for "sufficiently precise" computer architectures. Because all norms on finite-dimensional vector spaces are also known to be equivalent, our definitions of stability and backwards stability are independent of our choice of norm.