finding lower bound with given facts (relative error and relative residual)

Question

Given:

$A \in R^{n\times n}$

$x, \hat{x},r,b \in R^{n}, x \neq \hat{x}$

$r = b - A \hat{x}$

1) $\|x - \hat{x}\| \le \|A^{-1}\| \,\|r\|$

2) $\|b\| \le \|A\| \, \|x\|$

How do I reach this conclusion (lowerbound):

$\frac{1}{\|A\| \, \|A^{-1}\|}\frac{\|r\|}{\|b\|} \le \frac{\|x-\hat{x}\|}{\|x\|}$

The proof of upperbound was shown as an example:

$\frac{\|x- \hat{x}\|}{\|A\| \, \|x\|} \le \frac{\|A^{-1}\| \,\|r\|}{\|b\|}$

$\implies \frac{\|x - \hat{x}\|}{\|x\|} \le \|A\| \, \|A^{-1}\| \, \frac{\|r\|}{\|b\|}$

The proof for lowerbound was skipped, it just said "Similar argument leads to ...". but I'm lost on how to apply a similar argument for the lower bound :(

Answer 1

As you used $b=Ax$ and $x-\hat x=A^{-1}b$ to conclude $$ \|x-\hat x\|·\|b\|\le \|A\|·\|x\|·\|A^{-1}\|·\|r\|\implies \frac{\|x-\hat x\|}{\|x\|}\le \|A\|·\|A^{-1}\|·\frac{\|r\|}{\|b\|} $$ you can conversely start with $x=A^{-1}b$ and $r = b-A\hat x=A(x-\hat x)$ to conclude $$ \|x\|·\|b\|\le\|A^{-1}\|·\|b\|·\|A\|·\|x-\hat x\|\implies \frac1{\|A\|·\|A^{-1}\|}·\frac{\|r\|}{\|b\|}\le\frac{\|x-\hat x\|}{\|x\|} $$