Determining a bound on the relative error of a linear system Suppose that the linear system $A\mathbf{x}=\mathbf{b}$ is perturbed so that $(A+\delta A)\mathbf{x}=\mathbf{b}$.
We can calculate the relative error $\frac{\|\mathbf{x-\bar{x}\|}}{\|\mathbf{x}\|}$ if we know the true value of $\mathbf{x}$ and have an estimate for $\mathbf{\bar{x}}$, but if we want to put a general bound on the relative error in the system in terms of the system's condition number $K(A) = \|A^{-1}\|\cdot\|A\|$ and $\|\delta A\|/\|A\|$, how can this be done?
I have been trying to rearrange what is known in order to gain an expression in terms of this, and have so far obtained, with working:
$A\mathbf{x}=(A+\delta A)\mathbf{\bar{x}}$ equating the given formulae
$(A+\delta A)^{-1}A\mathbf{x}=\mathbf{\bar{x}}$ multiplying both sides by inverse
$(A+\delta A)^{-1}(A^{-1})^{-1}\mathbf{x}=\mathbf{\bar{x}}$ rewriting $A = (A^{-1})^{-1}$
$((A^{-1})(A+\delta A))^{-1}\mathbf{x}=\mathbf{\bar{x}}$ rearranging the inversion
$(I + A^{-1}\delta A)^{-1}\mathbf{x}=\mathbf{\bar{x}}$ multiplying out the brackets
At this point I become a bit dubious about the next step. I know that at some point the left hand side will need to look like ${\|\mathbf{x-\bar{x}\|}}$ so as to rearrange for the relative error, but multiplying the last line above by $-1$ then adding $\mathbf{x}$ to both sides, then taking the norm to obtain:
$\|\mathbf{x}-(I + A^{-1}\delta A)^{-1}\mathbf{x}\|=\|\mathbf{\mathbf{x}-\bar{x}}\|$
seems a bit too convenient and following this through with pen and paper doesn't seem to lead anywhere. Is this the correct approach, and if not, is there a chance of some guidance towards the correct manner?
 A: To answer your question in an appropriate way, we need to resort to the following theorem:

Theorem 1 (Neumann Series) 
  Let $\|\cdot\|$ be a submultiplicative norm such that $\\\|I\|=1$ and $\|A\|<1$. Then      $(I-A)^{-1}$ exists, $$(I-A)^{-1}=\sum_{j=0}^\infty{A^{j}}$$ and
  $$\frac{1}{1+\|A\|}\leq\|(I-A)^{-1}\|\leq\frac{1}{1-\|A\|}.$$


Let $\tilde A$ be a perturbed matrix with an absolute error $\Delta A=A-\tilde A$. If $\tilde x$ is a solution of the system $\tilde A\tilde x=b$ and $x$ is such that $Ax=b$, then:
$$(A-\Delta A)(x-\Delta x)=b \\
\Rightarrow(A-\Delta A)\Delta x=-\Delta Ax$$
where $\Delta x=x-\tilde x.$ 
Assuming that $A$ is nonsingular, we can multiply both sides of the last equality by $A^{-1}$, obtaining:
$$(I-A^{-1}\Delta A)\Delta x=-A^{-1}\Delta Ax.$$
Now, suppose that $\|A^{-1}\Delta A\|\leq1$ and let $\|\cdot\|$ be a submultiplicative norm. By Theorem 1, we know that $(I-A^{-1}\Delta A)^{-1}$ exists, so we can multiply both sides of the last equality by it; this gives us:
$$\Delta x=(I-A^{-1}\Delta A)^{-1}(-A^{-1}\Delta Ax)$$
Taking norms on both sides, we get:
$$\|\Delta x\|\leq\|(I-A^{-1}\Delta A)^{-1}\|\|A^{-1}\|\|\Delta A\|\|x\|$$
Dividing both sides of the inequality by $\|x\|$ and noting that, by Theorem 1, $$\|(I-A^{-1}\Delta A)^{-1}\|\leq\frac{1}{1-\|A^{-1}\Delta A\|}\leq\frac{1}{1-\|A^{-1}\|\|\Delta A\|}$$ we arrive to:
$$\frac{\|\Delta x\|}{\|x\|}\leq\frac{\|A^{-1}\|}{1-\|A^{-1}\|\|\Delta A\|}\|\Delta A\|$$
Manipulating this expression algebraically, we finally get:
$$\|\delta x\|\leq\frac{\|A^{-1}\|\|A\|}{1-\|A^{-1}\|\|A\|\frac{\|\Delta A\|}{\|A\|}}\frac{\|\Delta A\|}{\|A\|}=\frac{\kappa(A)}{1-\kappa(A)\|\delta A\|}\|\delta A\|$$
where $\|\delta x\|=\frac{\|\Delta x\|}{\|x\|},\|\delta A\|=\frac{\|\Delta A\|}{\|A\|}$ and $\kappa(A)=\|A^{-1}\|\|A\|.$
PS: Please note that my notations for the absolute error associated with a variable $(\Delta \alpha=\alpha-\tilde\alpha)$ and for its relative error $(\delta\alpha=\frac{\Delta\alpha}{\alpha})$ aren't the same as yours.
