Successive over-relaxation

Remarks

Componentwise, SOR computes the Gauss–Seidel value $\tilde{x}_i$ for the $i$-th unknown and takes $x^{(k+1)}_i = (1 - \omega) x^{(k)}_i + \omega \tilde{x}_i$. For $\omega = 1$ it is the Gauss–Seidel method. Kahan's bound comes from the determinant: $\det G_\omega = \det(D)^{-1} \det((1 - \omega) D) = (1 - \omega)^n$, and this is the product of the eigenvalues. The Ostrowski–Reich theorem follows because the energy norm of the error decreases strictly at each step when $A$ is positive definite and $0 < \omega < 2$. Assume moreover that $A$ is consistently ordered, for example tridiagonal. Assume also that the Jacobi iteration matrix has real eigenvalues and spectral radius $\mu < 1$. Then Young's theory gives the best parameter $\omega_{\mathrm{opt}} = 2 / (1 + \sqrt{1 - \mu^2})$, with $\rho(G_{\omega_{\mathrm{opt}}}) = \omega_{\mathrm{opt}} - 1$. For the model Poisson problem with mesh width $h$ this improves the convergence factor from $1 - O(h^2)$ to $1 - O(h)$.

Going deeper

For a student

SOR was for decades the main iterative method for large elliptic problems, because a good $\omega$ makes it far faster than Jacobi or Gauss–Seidel. The best $\omega$ depends on the spectrum of the Jacobi matrix, which is known exactly for model problems and estimated otherwise. Symmetric SOR runs a forward and a backward sweep and gives a symmetric preconditioner for the conjugate gradient method.