# Relation between condition number and perturbed matrix

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.

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.

• Thanks for pointing this out! Just a minor note - the inequality required contains $\vec{x}+\delta\vec{x}$ and not just $\vec{x}$. So putting $\delta\vec{x} = -A^{-1}\delta{}A(\vec{x}+\delta\vec{x})$ and proceeding with your derivation yields the required inequality.
– R.K.
Commented Mar 2, 2014 at 0:33
• @R.K.: Corrected. Commented Mar 2, 2014 at 0:37
• Hi @YiorgosS.Smyrlis, does this inequality apply to rectangular matrix as well, where there might not be a $x$ that satisfy this equality and we can only find a least-square solution by taking the pseudo-inverse? Commented Jul 11 at 17:57
• Hi @YiorgosS.Smyrlis, and why does the (4) equation in this paper state a different inequality? Looks like the (4) equation is a much weaker inequality. Paper: researchgate.net/profile/Adi-Ben-Israel/publication/… Commented Jul 11 at 18:39

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