Firstly, I want to say I could not find a proper title sorry. I have a question.
Let $Ax =b$ and $(A+\Delta A)y = b + \Delta b $.
Suppose $\lVert \Delta A \rVert \leq \epsilon \lVert E \rVert, \lVert \Delta b \rVert \leq \epsilon\lVert f\rVert $ and $\epsilon \lVert A^{-1} \rVert\lVert E\rVert < 1.$
Show that $$ \frac{\|x-y\|}{\|x\|} \leq \frac{\epsilon}{1-\epsilon\left\|A^{-1}\right\|\|E\|}\left(\frac{\left\|A^{-1}\right\|\|f\|}{\|x\|}+\left\|A^{-1}\right\| \| E \|\right) $$
I tried to apply some theorem from perturbation theory on this. But, I cannot do. Can you help me?
First, let's obtain some closed forms for $x$ and $y$. For $x$ it is quite trivial: $x = A^{-1} b$.
For the $y$ we have $$ y = (A + \Delta A)^{-1} (b + \delta b) = \left(A (I + A^{-1}\Delta A)\right)^{-1} (b + \Delta b). $$ Under the given conditions the matrix $I + A^{-1} \Delta A$ is invertible: $$ \left(I + A^{-1} \Delta A\right)^{-1} = I + \sum_{k=1}^{\infty} (-A^{-1} \Delta A)^k. $$ This is known as Neumann series and is known to be converging when $\|A^{-1} \Delta A\| < 1$ (sufficient condition). And this is the case, since $$ \|A^{-1} \Delta A\| \leq \|A^{-1}\| \|\Delta A\| < \frac{1}{\epsilon \|E\|}\epsilon \|E\| = 1. $$ We can now write $$ y = \left(I + \sum_{k=1}^\infty (-A^{-1} \Delta A)^k\right) A^{-1} (b + \Delta b). $$ Let us introduce the auxiliary vector $$ z = \left(I + \sum_{k=1}^\infty (-A^{-1} \Delta A)^k\right) A^{-1} b = \left(I + \sum_{k=1}^\infty (-A^{-1} \Delta A)^k\right) x. $$ Now apply the triangle inequality to get $$ \|x - y\| \leq \|x - z\| + \|y - z\|. \tag{1} $$ Estimating each term: $$ \|x - z\| = \left\|\sum_{k=1}^\infty (-A^{-1}\Delta A)^k\right\| \|x\|\\ \|y - z\| = \left\|I + \sum_{k=1}^\infty (-A^{-1} \Delta A)^k\right\| \|A^{-1}\| \|\Delta b\|. \tag{2} $$ Estimating the sums further by simple geometric series: $$ \left\|\sum_{k=1}^\infty (-A^{-1}\Delta A)^k\right\| \leq \sum_{k=1}^\infty \left\|A^{-1}\Delta A\right\|^k \leq \sum_{k=1}^\infty \left\|A^{-1}\|^k \|\Delta A\right\|^k = \frac{\left\|A^{-1}\|\|\Delta A\right\|}{1 - \left\|A^{-1}\|\|\Delta A\right\|} \tag{3}\\ \left\|I + \sum_{k=1}^\infty (-A^{-1}\Delta A)^k\right\| \leq 1 + \sum_{k=1}^\infty \left\|A^{-1}\Delta A\right\|^k \leq 1 + \sum_{k=1}^\infty \left\|A^{-1}\|^k\|\Delta A\right\|^k = \frac{1}{1 - \left\|A^{-1}\|\|\Delta A\right\|}\\ $$ Note, that if we leave $\|A^{-1}\Delta A\|$ instead of $\|A^{-1}\|\|\Delta A\|$ we obtain a slightly tighter bound with $1 - \|A^{-1} \Delta A\|$ in the denominator. But it was not requested.
Plugging (3) to (2) and finally to (1) gives: $$ \| x - y \| \leq \frac{1}{1 - \|A^{-1}\| \|\Delta A\|} \left( \|A^{-1}\|\|\Delta A\| \|x\| + \|A^{-1}\| \|\Delta b\| \right) $$ Now divide both sides by $\|x\|$: $$ \frac{\| x - y \|}{\|x\|} \leq \frac{1}{1 - \|A^{-1}\| \|\Delta A\|} \left( \|A^{-1}\|\|\Delta A\| + \frac{\|A^{-1}\| \|\Delta b\|}{\|x\|} \right) $$ Putting $\|\Delta b\| = \epsilon \|f\|$ and $\|\Delta A\| \leq \epsilon \|E\|$ gives the desired estimation: $$ \frac{\| x - y \|}{\|x\|} \leq \frac{\epsilon}{1 - \epsilon\|A^{-1}\| \|E\|} \left( \|A^{-1}\| \|E\| + \frac{\|A^{-1}\| \|f\|}{\|x\|} \right) $$