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 (1950) for consistently ordered matrices. Here the optimal omega is determined for the 9-point stencil for the model problem of Laplace's equation on a square. Several orderings of the equations are considered, including the natural rowwise and multicolor orderings, all of which lead to non-consistently ordered matrices, and two equivalence classes of orderings are found with different convergence behavior and optimal omega's. The results for the natural rowwise ordering are compared to those of Garabedian (1956) and it is explained why both results are, in a sense, correct, even though they differ. Also analyzed is a pseudo SOR method for the model problem and it is shown that it is not as effective as the SOR methods. Finally, the point SOR methods are compared to known results for line SOR methods for this problem.