0

In Numerical Linear Algebra by Trefethen&Bau,

backward stability

It is mentioned that a backward stable algorithm gives "exactly" the right answer to nearly the right question.

What I am thinking is, an algorithm has error. How can it be exactly equal to f(x+deltax) when both deltax and the error in the algorithm is all random? What does the word "exact" mean?

Here is an example from the book on page 109: example

It claims that x1(1 + epsilon4) - x2(1+epsilon5) exactly equal to x1~ - x2~. It is alright to say the order of error is equal. But I do not see the importance to mention the value is exactly equal.

Don Hatch
  • 1,047
Ronald Ku
  • 101
  • Neither $\delta_x$ nor the error in the algorithm are random. Algorithms in numerics are deterministic, they are just not exact matches to the function they implement. – Mees de Vries Aug 23 '17 at 09:32
  • Can I say under back stability, the algorithm is made with an offset so when x is input, it produces exactly the value given by f(x+deltax) . – Ronald Ku Aug 23 '17 at 10:52
  • Yes, I think that is fair. Note that $\delta_x$ depends on $x$, though; it is not a uniform offset, there are different small offsets for all inputs. – Mees de Vries Aug 23 '17 at 11:05
  • I think I still cannot see the importance or intuition of backward stability given that a back stable algorithm produces the same value given by f(x+deltax) when the input to the algorithm is x. Could you elaborate on this point? – Ronald Ku Aug 23 '17 at 11:11
  • The point is that $\delta_x$ ought to be very small, so that the error produced by an algorithm is at most as bad as what would have been caused by a small error in the input. – Mees de Vries Aug 23 '17 at 11:13
  • I understand the meaning of " the error produced by an algorithm is at most as bad as what would have been caused by a small error in the input". I cannot understand why the definition use "exactly equal" but not something like "algorithm error < the error produced when the input is perturbed and the method is exact". This is the definition of stability and I think it is much more reasonable. I cannot see the importance of the word "exactly equal". – Ronald Ku Aug 23 '17 at 11:23
  • Your 'something like' also uses the word 'exact', though. Is the problem the word 'equal'? Edit: or let me rephrase. Can you give an example of a function and an algorithm for that function where the book's definition and your definition of what "backwards stable" ought to mean disagree? – Mees de Vries Aug 23 '17 at 11:27
  • Yes. I do not see the importance of the word "equal" in terms of stability. It seems to be a useless concept to me but I feels it is important since the author emphasized it. My meaning of "exact method" is the method without any machine error in the calculation. – Ronald Ku Aug 23 '17 at 11:30
  • Actually, on second look, the author does not use the word "equal" at all. Just the word "exactly". – Mees de Vries Aug 23 '17 at 11:35
  • I have add an example to my question.In addition, the author did use "equal" in the equation f~(x) = f(x~) in the definition of backward stability. – Ronald Ku Aug 23 '17 at 11:51
  • How would you express the definition of backwards stability in a formula without using the "=" sign? – Mees de Vries Aug 23 '17 at 11:54
  • I cannot not and I must use the "=" if backward stability is needed to be defined in this way. The problem is I think the definition of backward stability is not reasonable. The thing that makes it not reasonable is the wording "exactly equal" or the sign "=". I think "<" than a certain threshold is much more reasonable. – Ronald Ku Aug 23 '17 at 12:22
  • So what do you think a reasonable formulation is, then? – Mees de Vries Aug 23 '17 at 12:24
  • I think the statement " the error produced by an algorithm is at most as bad as what would have been caused by a small error in the input" is an appropriate definition for stability. And I think the definition of stability in the book already captures the idea of this statement. – Ronald Ku Aug 23 '17 at 13:05
  • It's just a different definition, though. An algorithm $\tilde \cos$ for $\cos$ which produces $\tilde \cos(0) = 1.000000000000000001$ may be stable, but it is not backwards stable. – Mees de Vries Aug 23 '17 at 13:09

0 Answers0