Proving a formula for the error bound

Question

Given a system $Ax=b$, $A$ being nonsingular, and also $\kappa:=||A||*||A^{-1}||$, the condition number. $x$ and $\widetilde{x}$ are solutions to $Ax=b$ and $A\widetilde{x}=\widetilde{b}$, respectively and $e=b-\widetilde{b}.$ I am trying to prove the following:

$$\kappa^{-1}\frac{||e||}{||b||}\le\frac{||x-\widetilde{x}||}{||x||}\le\kappa\frac{||e||}{||b||}$$

It's easy to prove the inequality on the right, but how to prove the left one, i.e., how to prove the lower bound?

Answer 1

$e=A(x-\tilde x)$ and $b=Ax$ then :

$$\kappa^{-1}\frac{\|e||}{\|b\|} = \frac{\|A(x-\tilde x)\|}{\|A\|\|A^{-1}\|\|Ax\|} \le \frac{\|A\|\|x-\tilde x\|}{\|A\|\|(A^{-1}A)x\|} = \frac{\|x-\tilde x\|}{\|x\|}$$

Ps : formatting tip : writing \| produces $\|$ in MathJax.

Answer 2

From the relations $Ax=b$ and $A \tilde x = \tilde b$, you can easily see that $x-\tilde x= A^{-1}(b -\tilde b)$. Taking norms, you get $ \|x-\tilde x \| \leq \|A^{-1}\| \|b - \tilde b\|$. Finally, dividing both sides by $\|x \|$:

$$ \frac{\|x- \tilde x\|}{\|x\|} \leq \|A^{-1}\| \frac{\|b -\tilde b\|}{\|x\|}\leq \|A^{-1}\| \|A\| \frac{\|b -\tilde b\|}{\|b\|}, $$

where the last inequality comes from the fact that $$Ax = b \Rightarrow \|Ax\| =\|b\| \Rightarrow \|A\| \|x\| \ge \|b\| \Rightarrow \|x\| \ge \frac{\|b\|}{\|A\|}.$$