Stable and Unstable Algorithms

Conditioning tells us how sensitive a problem is. Now the other half: does an algorithm add more error than the problem forces? Two formulas that are equal in exact arithmetic can behave very differently in floating point.

An algorithm $\tilde{f}$ for $f$ is backward stable if for every input $x$, $$\tilde{f}(x) = f(\tilde{x})\quad\text{for some } \tilde{x} \text{ with } \frac{|\tilde{x} - x|}{|x|} = O(u).$$ In words: the computed answer is the exact answer to a slightly changed question. An algorithm that magnifies its own rounding errors far beyond that is unstable.

Key idea

Accuracy depends on both: for a backward stable algorithm, relative error $\approx \kappa \cdot u$. A stable method on a well-conditioned problem gives an accurate answer; an unstable method can fail even on an easy problem; and no method beats an ill-conditioned problem.

Why it works

If $\tilde{f}(x) = f(\tilde{x})$ with $\tilde{x} = x(1 + \delta)$ and $|\delta| \approx u$, then by the definition of the condition number $$\frac{|\tilde{f}(x) - f(x)|}{|f(x)|} = \frac{|f(\tilde{x}) - f(x)|}{|f(x)|} \approx \kappa|\delta| \approx \kappa u.$$ So the error splits into two factors: $u$, which a stable algorithm keeps small, and $\kappa$, which belongs to the problem.

Worked example: Same formula, two algorithms

The small root of $x^{2} - 200x + 1 = 0$ is $0.00500012\ldots$ Compute it in 4-digit arithmetic with $\frac{200 - \sqrt{200^{2} - 4}}{2}$ and with $\frac{2}{200 + \sqrt{200^{2} - 4}}$.

$200^{2} - 4 = 39996$ rounds to $40000$, and $\sqrt{40000} = 200.0$.
First formula: $\frac{200 - 200.0}{2} = 0$. Every digit is lost to cancellation.
Second formula (the first times the conjugate over itself): $\frac{2}{400.0} = 0.005000$, right to all 4 digits.
The root itself is well-conditioned; the first formula is unstable for it, the second is stable.

Answer: $0$ versus $0.005000$

The unstable formula subtracts two nearly equal numbers: with 4 digits kept, nothing correct survives.

Worked example: An unstable recurrence

$I_n = \int_0^1 x^{n}e^{x - 1}\,dx$ satisfies $I_n = 1 - nI_{n-1}$ with $I_0 = 1 - e^{-1}$. If $I_0$ is stored with error $10^{-16}$, how large is the error in $I_{20}$?

An error $\epsilon$ in $I_{n-1}$ becomes $n\epsilon$ in size in $I_n$, so after 20 steps the error is $20!\,\epsilon$.
$20! \approx 2.4 \times 10^{18}$, so the error is about $2.4 \times 10^{18} \times 10^{-16} \approx 243$.
But $0 < I_{20} < \frac{1}{21}$: the computed value is garbage. Running the recurrence backward, $I_{n-1} = \frac{1 - I_n}{n}$, divides errors by $n$ each step: stable.

Answer: about $243$

Worked example: A stable method on a hard problem

A backward stable solver is used on a problem with $\kappa \approx 10^{10}$. How many digits can we expect?

Relative error $\approx \kappa u \approx 10^{10} \times 10^{-16} = 10^{-6}$.
About 6 correct digits: the method did its job; the problem allows no more.

Answer: about 6 digits

Common mistake

Thinking a stable algorithm always gives an accurate answer. Stability promises only a small backward error; on an ill-conditioned problem that still means a large error in the answer. Check both: estimate $\kappa$ for the problem, and ask whether the algorithm subtracts nearly equal numbers or multiplies errors step after step.

Stable and Unstable Algorithms

Practice

Builds on

Leads to

Sources and further reading