2.3.3 Gauss-Seidel Relaxation (GSR)

Somewhat faster convergent than Jacobi.
Choose $\mbox{${\bf B}$}=\mbox{${\bf D}$}+\mbox{${\bf L}$}$ (i. e. lower triangle):

$$\fbox{ $ \left[ \mbox{${\bf D}$} + \mbox{${\bf L}$} \right] \cdot... ...x{$\bf x$}_{k+1}=\mbox{$\bf b$} - \mbox{${\bf R}$} \cdot \mbox{$\bf x$}_{k} $ }$$

Solving the set of implicit equations

$$a_{ii} \, x_{i}^{(k+1)} = b_{i} - \sum_{j > i} a_{ij} \, x_{j}^{(k)} - \sum_{j<i} a_{ij} \, x_{i}^{(k+1)} \; ; \;\;\; i=1,\dots,N$$ (2.1)

is almost as simple as solving the explicit Jacobi equations. Since the matrices $\mbox{${\bf D+L}$}$ and $\mbox{${\bf R}$}$ are triangular the only change is that in the downward recursion 2.1 some of the right hand terms refer to the present iteration $k+1$ instead of the previous, $k$; however, each term is available as soon as it is required.



EXAMPLE: With the same data as in the previous example we find the first two improved solutions

$$\mbox{$\bf x$}_{1}=\mbox{$\left( \begin{array}{r} 0.933 \\ \... ...{r} 0.989 \\ \vspace{-9 pt}\\ 0.006 \end{array} \right)$} \, .$$

The convergence rate of the GSR scheme is governed by the matrix

$$\mbox{${\bf G}$} \equiv - \left[ \mbox{${\bf D}$} + \mbox{${\bf L}$} \right]^{-1} \cdot \mbox{${\bf R}$}$$

It can be shown that the spectral radius of $\mbox{${\bf G}$}$ is given by

$$\lambda_{G} = \lambda_{J}^{2}$$

so that the rate of convergence is now

$$r_{G} \approx \left\vert \lambda_{J}^{2}-1 \right\vert$$

In our example $\lambda_{G}=0.17$ and $r \approx 0.83$.