Relation between condition number and perturbed matrix

Question

Prove that if $A\vec{x} = \vec{b}$ and $(A+\delta{}A)(\vec{x}+\delta\vec{x}) = \vec{b}$, then $\dfrac{\|\delta\vec{x}\|/\|\vec{x}+\delta\vec{x}\|}{\|\delta{}A\|/\|A\|} \le \kappa{(A)}$, where $\kappa{(A)} = \|A\|\cdot\|A^{-1}\|$ is the condition number of the matrix $A$.

Attempt at a solution:
$$A\delta\vec{x} + \delta{}A(\vec{x} + \delta\vec{x}) = 0 \Rightarrow \|A\delta\vec{x} + \delta{}A(\vec{x} + \delta\vec{x})\| = 0$$ $$\Rightarrow \|A\delta\vec{x}\| + \|\delta{}A(\vec{x} + \delta\vec{x})\| \ge 0$$ $$\Rightarrow \|A\|\cdot\|\delta\vec{x}\| + \|\delta{}A\|\cdot\|(\vec{x} + \delta\vec{x})\| \ge 0$$ $$\Rightarrow 1 + \frac{\|\delta{}A\|/\|A\|}{\|\delta\vec{x}\|/\|\vec{x}+\delta\vec{x}\|} \ge 0 \quad\quad\text{(dividing by }\|A\|\cdot\|\delta\vec{x}\|)$$ or
$$\Rightarrow 1 + \frac{|\|\delta\vec{x}\|/\|\vec{x}+\delta\vec{x}|\|}{|\|\delta{}A\|/\|A\|} \ge 0 \quad\quad\text{(dividing by }\|\delta{}A\|\cdot\|(\vec{x} + \delta\vec{x})\|)$$ This is what I've got so far, and I'm not sure how to bring $\kappa{}(A)$ into the equation.

Answer 1

The relation $$ (A+\delta A)(x+\delta x)=b, $$ implies that $$ Ax+\delta A (x+\delta x)+A\delta x=b, $$ and since $Ax=b$, the above becomes $$ \delta A (x+\delta x)+A\delta x=0, $$ and hence $$ \delta x= -A^{-1}\delta A (x+\delta x), $$ which implies that $$ \|\delta x\|\le \|A^{-1}\|\|\delta A\|\|x+\delta x\|=\kappa(A)\cdot\frac{\|\delta A\|}{\|A\|}\|x+\delta x\|, $$ and finally $$ \frac{\frac{\|\delta x\|}{\|x+\delta x\|}}{\frac{\|\delta A\|}{\|A\|}}\le \kappa(A). $$

Note. This error estimate is known as backward error analysis and it is due to J.H. Wilkinson.

Answer 2

This is not quite an answer, but perhaps complements Yiorgos' approach.

The idea is to view $x$ as a function of $A$ and compute the derivative. The implicit function theorem provides a convenient way of computing the derivative.

Let $\phi(y,A) = Ay-b$, we have ${\partial \phi(y,A) \over \partial y} = A$, and ${\partial \phi(y,A) \over \partial A}(\Delta) = \Delta y$, hence the implicit function theorem give the existence of a locally defined $x$ that satisfies $A x(A) = b$, and ${\partial x(A) \over \partial A}(\Delta) = ({\partial \phi(y,A) \over \partial y})^{-1} {\partial \phi(y,A) \over \partial A}(\Delta) = A^{-1} \Delta x(A)$.

This gives $\|{\partial x(A) \over \partial A}(\Delta)\| \le \|A^{-1}\| \|\Delta\| \|x(A)\|$. Dividing by ${\|\Delta\| \over \|A\|} \|x(A)\| $ gives ${\left({\|{\partial x(A) \over \partial A}(\Delta)\| \over \|x(A)\|} \right) \over \left( { \|\Delta\| \over \|A\| } \right) } \le \kappa(A)$.