Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading a numerical analysis book which gave very confusing description between stability and backward stability. which says a problem $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 problem is stable if it is backward stable?

share|improve this question

1 Answer 1

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.

share|improve this answer
    
"Life may toss us some ill-conditioned problems, but there is no good reason to settle for an unstable algorithm." - D.P. O'Leary. –  J. M. Nov 4 '11 at 9:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.