Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.