TOPICS

# 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.

Jacobi Method, Linear System of Equations, Nonstationary Iterative Method, Stationary Iterative Method, Symmetric Successive Overrelaxation Method

This entry contributed by Noel Black and Shirley Moore, adapted from Barrett et al. (1994) (author's link)

## Explore with Wolfram|Alpha

More things to try:

## 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.

## Referenced on Wolfram|Alpha

Successive Overrelaxation Method

## Cite this as:

Black, Noel and Moore, Shirley. "Successive Overrelaxation Method." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/SuccessiveOverrelaxationMethod.html