2

I am just working through some exam practice questions and I would like to show that for non-negative integers, $m,n$,

$$x^{(m+n)}-x^{(m)} = S^m(I+S+...+S^{n-1})(x^{(1)}-x^{(0)})$$

in the Gauss-seidel iteration scheme.

I have that the scheme can be written in the form:

$x^{(m+1)} = c + Sx^{(m)}$, where $S$ is a matrix and $c$ a vector.

I have tried a few different approaches and I can't seem to get the above expression.

Using that

$x^{(m+n)} = c + Sx^{(m+n)-1}$ and $x^{(m)} = c + Sx^{(m-1)}$, I get:

$$x^{(m+n)}-x^{(m)} = c +Sx^{(m+n)-1} - c - Sx^{(m-1)} = S(x^{(m+n-1)}-x^{(m-1)})$$

Then repeating the process $m$ times, I get to:

$$x^{(m+n)}-x^{(m)} = S^{m}(x^{(n)}-x^{(0)})$$

Then I'm not sure how to proceed. I have tried other methods, but then I get stuck with getting rid of the vector $c$.

Any help would be greatly appreciated!

JJJ
  • 874

1 Answers1

2

Applying repeatedly $x^{(k)}=Sx^{(k-1)}+c$ we get $$ x^{(k)}=S^kx^{(0)}+(I+S+\cdots+S^{k-1})c. $$ We need to get rid of $c$ and introduce $x^{(1)}$: from $x^{(1)}=Sx^{(0)}+c$ we have $c=x^{(1)}-Sx^{(0)}$. Combining the two together gives $$ \begin{split} x^{(k)}&=S^kx^{(0)}+(I+S+\cdots+S^{k-1})(x^{(1)}-Sx^{(0)}) \\&= S^kx^{(0)}+(I+S+S^2+\cdots+S^{k-1})x^{(1)}-(S+S^2+\cdots+S^k)x^{(0)} \\&= (I+S+S^2+\cdots+S^{k-1})x^{(1)}-(S+S^2+\cdots+S^{k-1})x^{(0)} \\&=x^{(1)}+(S+\cdots+S^{k-1})(x^{(1)}-x^{(0)}). \end{split} $$ So $$ \begin{split} x^{(m+n)}-x^{(m)}&=(S+\cdots+S^{m+n-1})(x^{(1)}-x^{(0)})-(S+\cdots+S^{m-1})(x^{(1)}-x^{(0)}) \\&=(S^{m}+\cdots+S^{m+n-1})(x^{(1)}-x^{(0)})\\&=S^m(I+S+\cdots+S^{n-1})(x^{(1)}-x^{(0)}). \end{split} $$

Algebraic Pavel
  • 22,928