5
$\begingroup$

I'm reading a numerical analysis book, which gave me very confusing descriptions about stability and backward stability.

It says that an algorithm $f$ is stable, if for any $x$, $ \frac{\|f_b(x)-f(x_b)\|}{\|f(x_b)\|}=\mathcal{O}(e_{machine}) $

Because I am assuming it should be how the approximated function mapping is away from the true function, so I don't understand why it is not the $ \frac{\|f_b(x)-f(x)\|}{\|f(x)\|}=\mathcal{O}(e_{machine}) $

Can anyone give me some description why the stable is defined in this way, and what is the general considerations for stable analysis?

Also, for backward stability, is it true that any algorithm is stable if it is backward stable?

1 Answers 1

7

Conceptually (letting $\varepsilon$ be machine epsilon):

  • A method for computing some result $w$ is forward stable if the computed solution $w^\ast$ is "near" the exact solution: $\|w-w^\ast\|/\|w\|\leq c\varepsilon$, where $c$ is some not-so-large constant.

  • A method is backward stable if $w^\ast$ is the exact solution of a perturbed problem; that is, if $p$ is the problem satisfied by $w$ and $p^\ast$ is the problem satisfied by $w^\ast$, then $\|p-p^\ast\|/\|p\|\leq k\varepsilon$, where $k$ is some constant that is not too large.

The difference is in the focus: forward analysis is concerned with what the method churns out, while backward analysis looks at the problem being solved (which is why we can speak of ill-conditioned methods and ill-conditioned problems). To give a concrete example: in using Cholesky decomposition to solve a system involving the Hilbert matrix, forward analysis will blame Cholesky for the observed instability, while backward analysis will blame Hilbert. Since it turns out that Cholesky tends to solve problems with not-too-large "condition numbers" accurately, we say that Cholesky is backward stable, but not forward-stable.

Nick Higham has a more extensive discussion; you will also want to see the pioneering book by Jim Wilkinson, who came up with the concepts.


See also this other answer I gave.

  • 0
    @user, "why backward is not defined in another way" - because it's the useful definition involving the condition number of the problem (as espoused by Wilkinson). If you can think of a more useful way to present backward stability, have at it.2018-02-26