The SOR Method

If we regard the Gauss-Seidel method as adding to $\mbox{\boldmath$\space x $ } _m$ an increment $\mbox{\boldmath$\space x $ } _{m+1}-\mbox{\boldmath$\space x $ } _m$, then we can try adding on a larger increment if the iteration is proceeding too slowly. We write the Gauss-Seidel method as $\mbox{\boldmath$\space x $ } _{m+1}=\mbox{\boldmath$\space x $ } _m+(\mbox{\boldmath$\space x $ } _{m+1}-\mbox{\boldmath$\space x $ } _m)$, where the increment is given by (7.5) as

$$\mbox{\boldmath$ x $ } _{m+1}-\mbox{\boldmath$ x $ } _m=D^{-1... ... } _m+D^{-1}\mbox{\boldmath$ f $ } -\mbox{\boldmath$ x $ } _m.$$

For Successive Over Relaxation, we multiply this increment by a parameter $\omega$ to obtain the step

 

$$\mbox{\boldmath$ x $ } _{m+1} \mbox{\boldmath$ x $ } _m+\omega (\mbox{\boldmath$ x $ } _{m+1}-\mbox{\boldmath$ x $ } _m)$$ = (4.7)

$$\mbox{\boldmath$ x $ } _m+\omega (D^{-1}L\mbox{\boldmath$ x $ } _... ...ox{\boldmath$ x $ } _m+D^{-1}\mbox{\boldmath$ f $ } -\mbox{\boldmath$ x $ } _m)$$ =

$$(1-\omega )\mbox{\boldmath$ x $ } _m+\omega \{ D^{-1}L\mbox{\bold... ...x $ } _{m+1}+D^{-1}U\mbox{\boldmath$ x $ } _m+D^{-1}\mbox{\boldmath$ f $ } \} .$$ = (4.8)

Collecting the terms in $\mbox{\boldmath$\space x $ } _{m+1}$ on the left we find

$$(I-\omega D^{-1}L)\mbox{\boldmath$ x $ } _{m+1}=\{ (1-\omega ... ...mbox{\boldmath$ x $ } _m+\omega D^{-1}\mbox{\boldmath$ f $ } ,$$

so that the iteration matrix is

$$M_{SOR}=(I-\omega D^{-1}L)^{-1}\{ (1-\omega )I+\omega D^{-1}U\},$$

provided that $I-\omega D^{-1}L$ is nonsingular.

The characteristic equation is

$$\begin{eqnarray*}\det [\lambda I-(I-\omega D^{-1}L)^{-1}\{ (1-\omega )I+\omega D... ...arrow~ \det [(\lambda -1+\omega)D-\lambda \omega L-\omega U ]=0, \end{eqnarray*}$$

or in displayed form

$$\left\vert \begin{array}{cccc}(\lambda -1+\omega)a_{11} & \om... ... a_{n,n-1} & (\lambda -1+\omega)a_{nn}\end{array} \right\vert.$$

The computational form comes directly from (7.8):

$$x_i^{(m+1)}=(1-\omega )x_i^{(m)}+\omega \left(-\sum _{j=1}^{i... ...+1}^n\frac{a_{ij}}{a_{ii}}x_j^{(m)}+\frac{f_i}{a_{ii}}\right).$$

Working through $i=1,2,\ldots ,n$ allows the computation of the new iterate without the matrix inversion suggested by the form of M_GS.