Successive Overrelaxation Method

The successive overrelaxation method (SOR) is a method of solving a linear system of equations  derived by extrapolating the Gauss-Seidel method. This extrapolation takes the form of a weighted average between the previous iterate and the computed Gauss-Seidel iterate successively for each component,

where  denotes a Gauss-Seidel iterate and  is the extrapolation factor. The idea is to choose a value for  that will accelerate the rate of convergence of the iterates to the solution.

In matrix terms, the SOR algorithm can be written as

where the matrices , , and  represent the diagonal, strictly lower-triangular, and strictly upper-triangular parts of , respectively.

If , the SOR method simplifies to the Gauss-Seidel method. A theorem due to Kahan (1958) shows that SOR fails to converge if  is outside the interval .

In general, it is not possible to compute in advance the value of  that will maximize the rate of convergence of SOR. Frequently, some heuristic estimate is used, such as  where  is the mesh spacing of the discretization of the underlying physical domain.

REFERENCES:

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van der Vorst, H. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.html.

Hageman, L. and Young, D. Applied Iterative Methods. New York: Academic Press, 1981.

Kahan, W. Gauss-Seidel Methods of Solving Large Systems of Linear Equations. Ph.D. thesis. Toronto, Canada, University of Toronto, 1958.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Successive Overrelaxation (SOR)." Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 866-869, 1992.

Varga, R. Matrix Iterative Analysis. Englewood Cliffs, NJ: Prentice-Hall, 1962.

Young, D. Iterative Solutions of Large Linear Systems. New York: Academic Press, 1971.