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.

Theorem on Iterative Method Convergence

If $\vert \vert I - Q^{-1}A \vert \vert <1$ for some subordinate matrix norm, then the sequence produced by $Qx^{(k)} = (Q-A)x^{(k-1)} + b$ converges to the solution of $Ax = B$ for any intial vector $x^{(0)}$.

My question is related to the proof of this theorem. In my textbook they have the following steps in the proof:

Obtain $x^{(k)} = (I-Q^{-1}A)x^{(k-1)} + Q^{-1}b$ from $Qx^{(k)} = (Q-A)x^{(k-1)} + b$

Now obtain the actual solution $x = (I-Q^{-1}A)x+Q^{-1}b$. Subtract these and obtain:

$x^{(k)}-x = (I-Q^{-1}A)(x^{(k-1)}-x)$

The following statements can be found:

$\vert \vert x^{(k)}-x \vert \vert \leq \vert \vert I-Q^{-1}A \vert \vert \cdot \vert \vert x^{(k-1)}-x\vert \vert $

By repeating this step obtain

$\vert \vert x^{(k)}-x \vert \vert \leq \vert \vert I-Q^{-1}A \vert \vert ^{k} \cdot \vert \vert x^{(0)}-x\vert \vert $

Thus if $\vert \vert I - Q^{-1}A \vert \vert <1$ then $\lim_{k \to \infty}\vert \vert x^{(k)}-x \vert \vert = 0$ for any $x^{0}$

My question

I don't understand the last conclusion:

Thus if $\vert \vert I - Q^{-1}A \vert \vert <1$ then $\lim_{k \to \infty}\vert \vert x^{(k)}-x \vert \vert = 0$ for any $x^{(0)}$

My quess is that when you compute a new $x^{(k)}$, you can interpretend this as a $x^{(0)}$ value, and therefore the next value $x^{(k+1)}$ will be closer to x?

Someone who can explain it?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

This has nothing to do with matrices and vectors; it's merely a statement about the real numbers $a_k=\Vert x^{(k)}-x \Vert$, $q =\Vert I-Q^{-1}A \Vert$ and $r=\Vert x^{(0)}-x\Vert$:

If $0\le a_k\le q^kr$ and $0\le q\lt 1$, then $\lim_{k\to\infty}a_k=0$ independent of $r$.

share|improve this answer
    
Of course :) Thank you! –  user12358 Oct 27 '11 at 12:25
add comment

Look at $\vert \vert x^{(k)}-x \vert \vert \leq \vert \vert I-Q^{-1}A \vert \vert ^{k} \cdot \vert \vert x^{(0)}-x\vert \vert$.

If $\vert \vert I-Q^{-1}A \vert \vert < 1$, then $\vert \vert I-Q^{-1}A \vert \vert ^{k}$ converges to $0$ and so does $\vert \vert x^{(k)}-x \vert \vert$.

share|improve this answer
add comment

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.