Suppose we use $\oplus$ to compute $x+1$, given $x \in \mathbb{C}$. $\widetilde{f(x)} = \mathop{\text{fl}}(x) \oplus 1$. This algorithm is stable but not backward stable. The reason is that for $x \approx 0$, the addition $\oplus$ will introduce absolute errors of size $O(\epsilon_M)$. Relative to the size of $x$, these errors are unbounded, so they cannot be interpreted as caused by small perturbations in the data.
For a quick notation summary:
- $\epsilon_M$ is machine epsilon that provides an upper bound on relative approximation error.
- $\mathop{\text{fl}}(x)$ is the floating point approximation of $x$. For any $x$, there is some $\epsilon$ such that $\mathop{\text{fl}}(x) = x (1 + \epsilon)$ where ${\lvert \epsilon \rvert} < \epsilon_M$
- $\oplus$ is the floating point approximation of mathematical addition. For any floating point $x,y$ there exists some $\epsilon$ such that $x \oplus y = (x+y)(1 + \epsilon)$ where ${\lvert \epsilon \rvert} < \epsilon_M$
- $\widetilde{f(x)}$ is the algorithmic approximation to $f(x)$
For backward stability we need to show that:
\begin{gather*} \forall \vec{x}, \exists \vec{y}: \widetilde{f(\vec{x})} = f(\vec{y}) \; \text{and} \; \frac{ {\lVert \vec{x} - \vec{y} \rVert} }{ {\lVert \vec{x} \rVert} } = O(\epsilon_M) \\ \end{gather*}
\begin{align*} \widetilde{f(x)} &= \mathop{\text{fl}}(x) \oplus 1 % = (\mathop{\text{fl}}(x) + 1)(1 + \epsilon_2) = (x(1 + \epsilon_1) + 1)(1 + \epsilon_2), \quad {\lvert \epsilon_1 \rvert} < \epsilon_M, {\lvert \epsilon_2 \rvert} < \epsilon_M \\ &= (x(1 + \epsilon_3) + 1) = y + 1 = f(y), \quad \epsilon_3 = O(\epsilon_M) \\ \end{align*}
To show that there exists some $\epsilon_3 = O(\epsilon_M)$ such that $y = x(1 + \epsilon_3)$:
\begin{align*} (x(1 + \epsilon_1) + 1)(1 + \epsilon_2) &= (x(1 + \epsilon_3) + 1) \\ x + x \epsilon_1 + 1 + x \epsilon_2 + x \epsilon_1 \epsilon_2 + \epsilon_2 &= x + x \epsilon_3 + 1 \\ x \epsilon_1 + x \epsilon_2 + x \epsilon_1 \epsilon_2 + \epsilon_2 &= x \epsilon_3 \\ \epsilon_3 &= \epsilon_1 + \epsilon_2 + \epsilon_1 \epsilon_2 + \epsilon_2/x \\ \end{align*}
$\epsilon_1,\epsilon_2$ are both $O(\epsilon_M)$. $\epsilon_1 \epsilon_2$ is $O(\epsilon_M^2)$ and can be discarded. However, $\epsilon_2/x$ is unbounded. so we can't find an $\epsilon_3$ of $O(\epsilon_M)$ satisfying $y = x(1 + \epsilon_3)$. Is this correct?