Bound $\frac{\lVert x-y \rVert}{\lVert x \rVert}$ with perturbation 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?
 A: 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)
$$
