Relative error in solution when the matrix is perturbed

Suppose that $A \in \mathbb{R}^{n \times n}$ is an invertible matrix and that $Ax=b$ for some $x,b \in \mathbb{R}^{n}$. If $\kappa(A)$ denotes the condition number of $A$, it is well known that if $b$ is perturbed by $\Delta b$, then $x$ gets perturbed by $\Delta x$ which satisfies $$\frac{\|\Delta x \|}{\|x\|} \leq \kappa(A) \frac{\|\Delta b\|}{\|b\|}.$$

If in addition $A$ is also perturbed to $A+\Delta A$, which is invertible, I am wondering if it is possible to say something along the similar lines such as $$\frac{\|\Delta x \|}{\|x\|} \leq \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|}+ \frac{\|\Delta b\|}{\|b\|} \right).$$ In other words, by changing both $A,b$ to $A+\Delta A, b+\Delta b$, how do we control the change is the solution $x$ to $x+\Delta x$?

Yes, something like that is true. You can find the proof, e.g., in this book and can go around these lines.

We have $Ax=b$ and $(A+\Delta A)(x+\Delta x)=b+\Delta b$. This gives $(A+\Delta A)\Delta x=\Delta b-\Delta Ax$. If $A+\Delta A$ is invertible, we have $\Delta x=(A+\Delta A)^{-1}(\Delta b-\Delta Ax)$. Taking a norm and using $\|b\|=\|Ax\|\leq\|A\|\|x\|$ gives $$\frac{\|\Delta x\|}{\|x\|} \leq \|(A+\Delta A)^{-1}\|\|A\|\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right). \tag{\star}$$

It remains to bound the norm of the inverse of $A+\Delta A$. From $I=(A+\Delta A)^{-1}(A+\Delta A)$ we have $(A+\Delta A)^{-1}=A^{-1}-(A+\Delta A)^{-1}\Delta A A^{-1}.$ Taking the norm gives $$\|(A+\Delta A)^{-1}\|\leq \|A^{-1}\| + \|(A+\Delta A)^{-1}\|\|\Delta AA^{-1}\|.$$ so if $\|\Delta AA^{-1}\|<1$ then $$\|(A+\Delta A)^{-1}\|\leq\frac{\|A^{-1}\|}{1-\|\Delta AA^{-1}\|}.$$

Substituting to ($\star$) gives that

If ($\ast$) holds, then $$\frac{\|\Delta x\|}{\|x\|} \leq \frac{\kappa(A)}{1-\|\Delta AA^{-1}\|}\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right).$$

From $\|\Delta AA^{-1}\|\leq\|\Delta A\|\|A^{-1}\|$ you can get a bit more "neat" statement.

If $$\frac{\|\Delta A\|}{\|A\|}<\frac{1}{\kappa(A)}$$ then $$\frac{\|\Delta x\|}{\|x\|} \leq \frac{\kappa(A)}{1-\frac{\|\Delta A\|}{\|A\|}\kappa(A)}\left(\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta A\|}{\|A\|}\right)$$ and if $\|\Delta A\|\leq\epsilon\|A\|$ and $\|\Delta b\|\leq\epsilon\|b\|$ then $$\frac{\|\Delta x\|}{\|x\|} \leq \frac{2\epsilon\kappa(A)}{1-\epsilon\kappa(A)}.$$

You can of course remove the "annoying" denominator using a stronger assumption. For example, if $\epsilon\kappa(A)<1/2$, then $$\frac{\|\Delta x\|}{\|x\|} \leq 4\epsilon\kappa(A).$$

• Is it also possible to bound just the absolute errors too? Assuming $\|x\| \leq 1$ I obtained that $\|\Delta x\| \leq \|A^{-1}\| (\|\Delta A\|+\|\Delta b\|)$. – pikachuchameleon Jun 20 '17 at 14:31
• @pikachuchameleon I don't know how did you get this bound without neglecting the "higher order term" $\Delta A\Delta x$. Otherwise, of course you can get a bound for the absolute error. – Algebraic Pavel Jun 20 '17 at 15:40
• Yeah, I neglected the higher-order term. But can it be justified? – pikachuchameleon Jun 20 '17 at 15:43
• @pikachuchameleon Well, yes, by them being "H.O.T." – Algebraic Pavel Jun 20 '17 at 17:18