TOPICS
Search

Successive Overrelaxation Method


The successive overrelaxation method (SOR) is a method of solving a linear system of equations Ax=b 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,

 x_i^((k))=omegax^__i^((k))+(1-omega)x_i^((k-1)),

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

In matrix terms, the SOR algorithm can be written as

 x^((k))=(D-omegaL)^(-1)[omegaU+(1-omega)D]x^((k-1))+omega(D-omegaL)^(-1)b,

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

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

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


See also

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

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

Subject classifications