Is the composition of backward stable algorithms again backward stable?

Question

I have heard the claim that a composition of two backward stable problems is again backward stable, but I have trouble proving it.

Let $f: X \to Y, g: Y \to Z$ be problems and $\tilde f, \tilde g$ their algorithms. Take input data $x$. Since $\tilde f$ is backward stable, we have an $\tilde x \in X$ st. $\frac {||x - \tilde x ||}{||x||} = O(\epsilon)$ and $\tilde f(x) = f(\tilde x)$.

Now if we apply $\tilde g$ to $y = f (\tilde x)$ we'll get $\tilde y \in Y$ with a similar condition. Still, there are several problems:

• $\tilde y$ may no longer be in range of $f$
• even if $\tilde y$ is in image of $f$, it may appear that its preimages fall far away from $x$ or $\tilde x$. We probably need to assume some bilipschitz continuity of both $f$, but this sounds like a very strong condition.

Is it at all true that a composition of backward stable algorithms is again backward stable? It would be nice to have a simple criterion for compositions of backward stable algorithms to be able to break the proof into several independent steps.

Answer 1

It's certainly not true in general. Here's a counterexample with some very well behaved functions: Let $\tilde{f}(x) = f(x) = 1+(x-1)^3$. Let $g(y) = y$ and $\tilde{g}(y) = y + \epsilon$. It is straightforward to see that $\tilde{f}$ and $\tilde{g}$ are backward stable everywhere.

But at $x=1$ we have $$(\tilde{g}\circ \tilde{f}) (1) = 1 + \epsilon = (g \circ f) (1+\sqrt[3]{\epsilon}).$$ And for any constant $C>0$ we have $$\frac{\sqrt[3]{\epsilon}}{|x|} = \sqrt[3]{\epsilon} > C \epsilon$$ whenever $\epsilon>0$ is sufficiently small. Hence, $(\tilde{g}\circ\tilde{f})$ is not backward stable at $x=1$.

It's true that $f=\tilde{f}$ is not bilipschitz at $x=1$, but, as you point out, that seems like a very strong condition to impose--perhaps too strong to be useful.