0
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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\|)$. $\endgroup$ – pikachuchameleon Jun 20 '17 at 14:31
  • $\begingroup$ @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. $\endgroup$ – Algebraic Pavel Jun 20 '17 at 15:40
  • $\begingroup$ Yeah, I neglected the higher-order term. But can it be justified? $\endgroup$ – pikachuchameleon Jun 20 '17 at 15:43
  • $\begingroup$ @pikachuchameleon Well, yes, by them being "H.O.T." $\endgroup$ – Algebraic Pavel Jun 20 '17 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.