SOR iteration as a splitting method

This may not be obvious at first sight, but SOR is a splitting method:

$$x_{SOR}^{(k+1)}=x_{SOR}^{(k)}+\omega \left[D^{-1}\right(b+L{x}_{SOR}^{(k+1)}+U{x}_{SOR}^{(k)})-x_{SOR}^{(k)}]$$

This implies:

$$(\frac{1}{\omega }D-L)x_{SOR}^{(k+1)}=b+\left(\right(\frac{1}{\omega }-1)D+U)x_{SOR}^{(k)}$$

So we indeed have a splitting method with the following choices:

$$\begin{array}{c}A=M-N,\\ M=\frac{1}{\omega }D-L,\\ N=(\frac{1}{\omega }-1)D+U\end{array}$$

The choice $\omega =1$ corresponds to Gauss-Seidel.

Convergence

Theorem 1.

We have

$$G_{\text{SOR}}=M^{-1}N$$

We can prove that

$$\rho (G_{\text{SOR}})\ge |\omega -1|.$$

Therefore $0<\omega <2$ is required for convergence.

Proof

The proof uses the determinant of $G_{\text{SOR}}$:

$$\det G_{\text{SOR}}=(\det ({\omega }^{-1}D-L){)}^{-1}\det (({\omega }^{-1}-1)D+U)$$

Using the fact that the matrices are triangular, we get

$$\det G_{\text{SOR}}={\omega }^n({\omega }^{-1}-1{)}^n=(1-\omega {)}^n$$

If all the eigenvalues are smaller than 1, then the determinant is in the interval $(-1,1)$ and

$$|1-\omega |<1$$

which implies that $0<\omega <2$ for stability. This is a required but not sufficient condition.

Theorem 2.

• If $A$ is symmetric positive definite, then $\rho (G_{SOR})<1$ for all $0<\omega <2$.
• In that case, SOR converges for all $0<\omega <2$.
• With $\omega =1$, we recover that Gauss-Seidel converges for symmetric positive definite matrices.