Stability

unstable algorithm : an algorithm with error exceeding error expected from conditioning

  • quadratic formula is unstable in finite precision computation
  • sensitivity of a problem/step is governed by condition number, but sensitivity of algorithm depends on condition numbers of individual steps

Backward error: a measure of the change in original data that reproduces the result of the algorithm

\[ \frac{| \tilde{x} - x |}{|x|} \]

If an algorithm always produces small backward errors, then it is stable. (converse not always true)