Analysis of the SOR Iteration for the 9-Point Laplacian

The SOR iteration for solving linear systems of equations depends upon an overrelaxation factor $\omega $. A theory for determining $\omega $ was given by Young (“Iterative methods for solving partial differential equations of elliptic types,” Trans. Amer. Math. Soc., 76(1954), pp. 92–111) for consistently ordered matrices. Here we determine the optimal $\omega $ for the 9-point stencil for the model problem of Laplace’s equation on a square. We consider several orderings of the equations, including the natural rowwise and multicolor orderings, all of which lead to nonconsistently ordered matrices, and find two equivalence classes of orderings with different convergence behavior and optimal $\omega $’s. We compare our results for the natural rowwise ordering to those of Garabedian (“Estimation of the relaxation factor for small mesh size,” Math. Comp., 10 (1956), pp. 183–185) and explain why both results are, in a sense, correct, even though they differ. We also analyze a pseudo-SOR method for the model problem and show that it is not as effective as the SOR methods. Finally, we compare the point SOR methods to known results for line SOR methods for this problem.