0
$\begingroup$

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?

1 Answers 1

1

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.