1

I'm wondering why backward substitution is backward stable. For the 1D case $ax=b$, Let $x = f(a, b) = \frac{b}{a}$, and let $\bar{f}$ be an algorithm for $f$. Also let $\epsilon$ be a small error.

If $a \neq b$: $\bar{f}(a, b) = \frac{b(1+\epsilon_1)}{a(1+\epsilon_2)}(1+\epsilon_3) = \frac{b(1+\epsilon_4)}{a(1+\epsilon_2)} = \frac{\bar{b}}{\bar{a}} = f(\bar{b}, \bar{a})$

In the above, $b$ and $a$ are approximated with floating point numbers, adding an error of $\epsilon_i$ to each. The division is also on a computer, so it also has an error $\epsilon_3$.

It looks stable because $\bar{f}(a, b) = f(\bar{a}, \bar{b})$, where $\bar{a}$ and $\bar{b}$ are within some $\epsilon$ of $a$ and $b$

If $a=b$: $\bar{f}(a, a) = \frac{a(1+\epsilon_1)}{a(1+\epsilon_1)}(1+\epsilon_2) = (1+\epsilon_2) \neq f(\bar{a},\bar{a})= \frac{\bar{a}}{\bar{a}} = 1$

I think this is stable but not backward stable because the algorithm gives $1 + \epsilon$, but the function itself equals $1$.

I'm reading it is supposed to be backward stable though, can anyone tell me what I'm getting wrong?

Frank
  • 880

1 Answers1

1

I think there's just a simple misunderstanding of the definition of backwards stability. As I understand it, backward stability requires two things:

  1. There exists $\delta := (\delta_a, \delta_b)$ (which can depend on $a,b$ and $\epsilon_\text{machine}$) such that $$\bar{f}(a,b) = f(a+\delta_a, b+\delta_b).$$

  2. We must have $$\frac{||\delta||}{|| (a,b) ||} \in O(\epsilon_\text{machine})$$ (where $\epsilon_\text{machine}$ determines the precision of all the arithmetic in the algorithm).

Setting $a = b$ and showing that $\bar f (a, a) \neq f (\bar a, \bar a) $ is insufficient to disprove (1.). The reason is because (1.) only requires existence of some $(\delta_a, \delta_b)$ where the property is satisfied. Inadvertently, you've chosen a specific value for $(\delta_a, \delta_b)$ (you set $\delta_a = \delta_b$) and shown that (1.) doesn't work for that value. For a disproof, you would need to show that for all possible values of $(\delta_a, \delta_b)$, you never have $\bar{f}(a,a) = f(a+\delta_a, a+\delta_b)$.

As an aside, we can satisfy (1.) if we choose $\delta$ so that $\delta_a = a \epsilon_2 $ and $\delta_b = b( \epsilon_1 + \epsilon_3 + \epsilon_1 \epsilon_3)$.

dragonofthewest
  • 44
  • Oh, my assumption was that $a + \delta a$ was supposed to be the nearest floating point approximation of $a$, if so $\delta a$ would be determined by $a$. So if my assumption is wrong, then you are correct, but isn't it strange to not force $a + \delta a$ to be the closest floating point approximation of $a$? – Frank Aug 11 '20 at 17:05
  • 1
    It is a bit strange, I agree. It makes more sense to me when I can consider both parts (1.) and (2.). (2.) is the part concerned with how small it will be. All we're saying with (1.) is that technically, if you choose just the perfect amount of error (might not be the smallest possible error), you can get the actual, true answer out from your imperfect algorithm. Then, part (2.) guarantees that the perfect amount of error you should choose gets smaller and smaller as the smallest possible error ($\epsilon_\text{machine} $) gets smaller. – dragonofthewest Aug 11 '20 at 18:03
  • 1
    Very clear, thanks a lot. I'll probably have nightmares about it not being the closest floating point for a while :-/ – Frank Aug 11 '20 at 22:40
  • 1
    I thought about this some more and actually, having it to be the closest floating point approximation would be a condition that’s basically impossible to achieve. Then we’re saying that even with our imprecise floating point approximations, we always get the exact right answer out from the algorithm, even as we change how precise we are. – dragonofthewest Aug 12 '20 at 23:11
  • 1
    Well exact right answer to almost the right question. The exact right answer to the floating point approximation of the input. That's how it was explained to me in Trefethen & Bau Numerical Linear Algebra – Frank Aug 13 '20 at 14:19
  • That's a better way to put it! I love it! – dragonofthewest Aug 13 '20 at 16:40