Question: Consider the iterative improvement algorithm below.

enter image description here

Starting with $Az_i = r_i$ and $(A + E)\hat{z}_i = r_i$ derive a formula showing how the absolute error in the $(i + 1)^{st}$ iterate $\Vert\hat{x}_{i+1} - x\Vert$ is bound by a multiple of the absolute error in the $i$-th iterate $\Vert\hat{x}_{i} - x\Vert$. Argue that the magnitude of this multiple is dependent on the condition of A, and is less than one (hence convergence) if $A$ is well-conditioned.

My work:

I know the following:

$$\frac{1}{\kappa(A)} \frac{\Vert r_i\Vert}{\Vert b\Vert} \le \frac{\Vert\hat{x}_{i} - x\Vert}{\Vert x\Vert} \le \kappa(A) \frac{\Vert r_i\Vert}{\Vert b\Vert}$$ being $\kappa(A)$ the condition number of $A$.

Now do: $$ \Vert\hat{x}_{i+1} - x\Vert = \Vert(\hat{x}_{i} + z_i) - x\Vert \le \Vert\hat{x}_{i} - x\Vert + \Vert z_i\Vert \le \frac{\Vert\hat{x}_{i} - x\Vert}{\Vert x\Vert} \le \kappa(A) \frac{\Vert r_i\Vert\, \Vert x\Vert}{\Vert b\Vert} + \Vert A^{-1}r_i\Vert$$

$$= \Vert A\Vert\, \Vert A^{-1}\Vert \frac{\Vert r_i\Vert\, \Vert x\Vert}{\Vert b\Vert} + \Vert A^{-1}r_i\Vert \le \Vert A\Vert \Vert A^{-1}\Vert \frac{\Vert r_i\Vert\, \Vert x\Vert}{\Vert b\Vert} + \Vert A^{-1}\Vert\, \Vert r_i\Vert$$

$$= \Vert A^{-1}\Vert\, \Vert r_i\Vert \left(\Vert A\Vert \frac{\Vert x\Vert}{\Vert b\Vert}\right)$$

What I did is not correct because I need to bound the absolute error of $||\hat{x}_{i+1} - x||$ by a multiple of $||\hat{x}_{i} - x||$ which I am not sure how to do.

  • $\begingroup$ How did you arrive at the inequality $||\hat{x}_i-x|| + ||z_i||\leq\frac{||\hat{x}_i-x||}{||x||}$? I don't think this is correct. $\endgroup$
    – Paul
    Nov 9 '14 at 3:03
  • $\begingroup$ It may be helpful to work without the norms first. You can algebraically manipulate the $z_i$ term in the expression $(\hat{x}_i-x) + z_i$ (without inequalities) until you obtain something in terms of $\hat{x}_i-x$ only. Hint: you may have to add zero in a special way. $\endgroup$
    – Paul
    Nov 9 '14 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.