### 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*.

# analysis

# numerical-analysis

# floating-point

back to home page