$A\in\R^{n\times n}$, invertible, want to solve $Ax=b$, $b\neq0$ and look at errors
Theorem. $$\kappa_\infty=\IN{A}\IN{A^{-1}}$$
$A+E$ representation with error $\IN{E}\leq u\IN{A}$
$b+e$ representation with error $\IN{e}\leq u\IN{b}$
If $(A+E)\hat{x}=b+e$ and if $u\kappa_\infty<1$, then
$$\frac{\IN{X-\hat{X}}}{\IN{X}}\leq\frac{2u\kappa_\infty}{1-u\kappa_\infty}$$
Lemma. $I\in\R^{nn}$, $F\in\R^{nn}$ s.t. $\|F\|_p<1$ for some $p\in[1,\infty]$. Then $I-F$ is invertible and $$\|(I-F)^{-1}\|_p\leq\frac1{1-\|F\|_p}$$
Proof. HOMEWORK
Lemma. Suppose $\exists\varepsilon>0$ s.t. $\|\Delta A\|\leq\varepsilon\|A\|$, $\|\Delta b\|\leq\varepsilon|b\|$, and $y$ s.t. $(A+\Delta A)y=(b+\Delta b)$. If $\epsilon\|A\|\,\|A^{-1}\|=r<1$ then $A+\Delta A$ is invertible and $$\frac{\|y\|}{\|x\|}\leq\frac{1+r}{1-r}$$
Proof.
$A+\Delta A=A(I+A^{-1}\Delta A)$, so $\|A^{-1}\Delta A\|\leq\varepsilon\|A^{-1}\|\,\|A\|$, then $A+\Delta A$ is invertible. Then,
$$\underbrace{(I+A^{-1}\Delta A)}_\text{invertible}\;y\,=\underbrace{A^{-1}b}_x+A^{-1}\Delta b$$ $$y=(I+A^{-1}\Delta A)^{-1}(x+A^{-1}\Delta b)$$ $$\|y\|\leq\|I+A^{-1}\Delta A\|\cdot\left(\|x\|+\varepsilon\|A^{-1}\|\,\|b\|\right)\leq\frac1{1-r}\left(\|x\|+r\frac{\|b\|}{\|A\|}\right)$$ $$\leq\frac1{1-r}(\|x\|+r\|x\|)$$ since $\|A\|\,\|x\|\geq\|b\|$
Lemma. $$\frac{\|y-x\|}{\|x\|}\leq\frac{2\varepsilon\|A^{-1}\|\,\|A\|}{1-r}$$
Proof. $$y-x=A^{-1}\Delta b-A^{-1}\Delta Ay$$ $$\|y-x\|~\leq~\ep\|A\inv\|\,\|b\|+\ep\|A\inv\|\,\|A\|\,\|y\|~\leq~\ep\|A\inv\|\,\|A\|(\|x\|+\|y\|)$$
HOMEWORK
1. What happens if I use $\ell^1$ norm instead of $\ell^\infty$?
2. Generate examples that show bound is conservative
3. Generate examples that show bound is nearly achieved (within factor of 10)