2
$\begingroup$

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?

2 Answers 2

2

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$.

  • 0
    Of course :) Thank you!2011-10-27
0

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$.