Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
Of course :) Thank you! – user12358 Oct 27 '11 at 12:25

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|cite|improve this answer

Your Answer


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.