prove 1d back substitution is backward stable 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?
 A: I think there's just a simple misunderstanding of the definition of backwards stability. As I understand it, backward stability requires two things:

*

*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).$$


*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)$.
