Symmetric Gauss Seidel iteration

Question

Let $A=L+D+R$, where $L$ is a strict lower triangular, $D$ a diagonal and $R$ an strict upper triangular matrix.

Consider the symmetric Gauss Seidel iteration:

\begin{align*} (L+D)x^{(k+1/2)}+Rx^{(k)}&=b \\ Lx^{(k+1/2)}+(D+R)x^{(k+1)}&=b \end{align*}

How can I show that this iteration is consistent? My idea is to plug in the solution $x$ into $x^{(k)}$ and try to get the same solution $x$ into $x^{(k+1)}$, but I am having trouble with this.

Answer 1

You can take the actual solution $x=x^{(k)}$ and get $$(L+D)x^{(k+1/2)} + Rx= b = (L+D+R)x.$$ If $L+D$ is invertible (it has to be, else the algorithm will not work), you get $x=x^{(k+1/2)}$. The same argument will now apply to the second equation, thus you will get $x=x^{(k+1)}$.

By subtracting the two equations, you can prove that if $x^{(k)}=x^{(k+1)}$ you have $Ax^{(k)}=b$.

Answer 2

This is probably not the best thing to do if you only want to show consistency. But it is also useful for other purposes such as convergence analysis.

First, modify your equations to arrive at: $$ x^{(k+1/2)} = x^k + (D+L)^{-1}(b-Ax^k),$$ $$ x^{(k+1)} = x^{(k+1/2)} + (D+R)^{-1}(b-Ax^{(k+1/2)}).$$ Then plugging the first equation into the second one yields: \begin{array} &x^{(k+1)} & = x^k + \{(D+L)^{-1} + (D+R)^{-1} - (D+R)^{-1}A(D+L)^{-1}\} (b-Ax^k) \\ & = x^k + (D+R)^{-1}D(D+L)^{-1} (b-Ax^k). \end{array} This directly implies that $x^{(k+1)}=x^k$ if $b-Ax^k=0$.