5
$\begingroup$

Consider the equation $A\mathbf{x}=\mathbf{b}$. It is equivalent to $$S\mathbf{x}=(S-A)\mathbf{x}+\mathbf{b}$$ where $S$ is a splitting matrix. We now consider the iteration scheme $$S\mathbf{x}_{i+1}=(S-A)\mathbf{x}_i+\mathbf{b}.$$

Suppose $S$ is invertible, then we have $$\mathbf{x}_{i+1}=(I-S^{-1}A)\mathbf{x}_i+S^{-1}\mathbf{b}.$$ It follows that $\{\mathbf{x}_{n}\}$satisfies $$\mathbf{x}_{k}=(I-S^{-1}A)^k\mathbf{x}_0+\sum_{i=0}^{k-1}(I-S^{-1}A)^iS^{-1}\mathbf{b}.$$ Furthermore, we have $$\mathbf{x}_{i+1}-\mathbf{x}=(I-S^{-1}A)(\mathbf{x}_i-\mathbf{x}).$$

It follows quickly that if $\|I-S^{-1}A\|<1$ for some subordinate matrix norm $\|\cdot\|$, the above iterative scheme would converges for any $\mathbf{b}$ and $\mathbf{x}_0$.

Now, I have difficult in establishing the following statements:

The above iterative scheme would converge for any $\mathbf{b}$ and $\mathbf{x}_0$ iff $\rho(I-S^{-1}A)<1$.

The if part is obvious. What about the only if part? [Solved]

If $\|I-S^{-1}A\|<1$ for some subordinate matrix norm $\|\cdot\|$ and $\{\mathbf{x}_{n}\}$ converges to $\mathbf{x}$, then $$\|\mathbf{x}_{n}-\mathbf{x}\|\leq \frac{\|I-S^{-1}A\|}{1-\|I-S^{-1}A\|}\|\mathbf{x}_{n}-\mathbf{x}_{n-1}\|.$$

I think that the fraction here comes from the sum to infinity formula, but how to obtain that?

Thanks in advance.

As suggested, I add these:

$$\mathbf{x}_{n}-\mathbf{x}_{n-1} = (I-S^{-1}A)^{n-2}[-(I-S^{-1}A)(S^{-1}A)\mathbf{x}_0 - S^{-1}\mathbf{b}].$$

$\endgroup$
6
  • 1
    $\begingroup$ The only if part is obvious because you assume any $b$ and $x_0$. Thus if the spectral radius is not less than $1$, it could happen that $x_0-x$ is an eigenvector of $I-S^{-1}A$ whose eigenvalue has magnitude at least $1$. Then $x_k-x$ would not go to zero. $\endgroup$
    – Ian
    Apr 13, 2016 at 10:43
  • $\begingroup$ For your second part, why not write out a formula for $x_n-x$ (you did this) and $x_n-x_{n-1}$ (you didn't do this) and compare them? We could help you from there. $\endgroup$
    – Ian
    Apr 13, 2016 at 10:46
  • $\begingroup$ @Ian : Thanks for the first statement. I have edited the post. $\endgroup$
    – Nighty
    Apr 13, 2016 at 10:56
  • $\begingroup$ So that formula for $x_n-x_{n-1}$ is pretty much a dead end, I think. My guess would be that there is a telescoping trick that will give something like $x_n-x=(\sum_k (I-S^{-1}A)^k)(x_n-x_{n-1})$ over some range of $k$'s (presumably $k=1$ to $n$ or something like this.) An equation like that would easily give your result. $\endgroup$
    – Ian
    Apr 13, 2016 at 13:45
  • $\begingroup$ are you sure there are no typos in the following expression? $$\|\mathbf{x}_{n}-\mathbf{x}\|\leq \frac{\|I-S^{-1}A\|}{1-\|I-S^{-1}A\|}\|\mathbf{x}_{n}-\mathbf{x}_{n-1}\|$$ $\endgroup$
    – etothepitimesi
    Apr 13, 2016 at 17:42

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .