Backward stability and input/output spaces dimensions I was reading Numerical Linear Algebra book by Bau & Trefethen, and saw there that if the output space dimension is larger than that of the input space, then the algorithm is rarely backward stable.
Please, can someone explain the rationale behind this statement ?
Thanks,
 A: Simple example: $f(x)=(x+c_1,x+c_2)$. Both results can have a different floating-point error, and will usually do so. Then there is not a single input $\hat x$ so that reproduces the floating-point result in exact arithmetic, $f(\hat x)=(x+_{fl}c_1,x+_{fl}c_2)$ is impossible.
A: Consider the very general problem of computing $y = f(x)$ where $f : \Omega \rightarrow \mathbb{R}^n$ and $\Omega \subseteq \mathbb{R}^m$. We cannot hope to compute the exact value of $y$, and we must therefore consider the qualities of the value $\hat{y}$ that is returned by the computer. We say that an algorithm for computing $f$ is normwise relative backward stable if $$\forall x \in \Omega \: \exists C > 0 \: \exists \bar{x} \in \Omega \: : \: \left(\hat{y} = f(\bar{x}) \wedge \frac{\|x-\bar{x}\|}{\|x\|} \leq Cu \right).$$
Here $u$ is the unit roundoff used by the computer. In popular terms, an algorithm is backward stable if the computed result is the exact result corresponding to an input that is a small perturbation of the original input. We now reach the point that is critical for the OP:
When does there exist a $\bar{x}$ such that $\hat{y} = f(\bar{x})$?
This is question of being able to solve $n$ equations in $m$ unknowns. If $m=n$, then we can hope that there is a unique solution courtesy of the inverse function theorem. If $m > n$, then we can hope that there are infinitely many solutions courtesy of the implicit function theorem. But in the present case where $m < n$ and there are more equations than unknowns, there is no reason to expect that there is even a single $\bar{x}$ such that $\hat{y} = f(\bar{x})$.
