Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Successive over-relaxation
Summary
In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging iterative process.
It was devised simultaneously by David M. Young Jr. and by Stanley P. Frankel in 1950 for the purpose of automatically solving linear systems on digital computers. Over-relaxation methods had been used before the work of Young and Frankel. An example is the method of Lewis Fry Richardson, and the methods developed by R. V. Southwell. However, these methods were designed for computation by human calculators, requiring some expertise to ensure convergence to the solution which made them inapplicable for programming on digital computers. These aspects are discussed in the thesis of David M. Young Jr.
Given a square system of n linear equations with unknown x:
where:
Then A can be decomposed into a diagonal component D, and strictly lower and upper triangular components L and U:
where
The system of linear equations may be rewritten as:
for a constant ω > 1, called the relaxation factor.
The method of successive over-relaxation is an iterative technique that solves the left hand side of this expression for x, using the previous value for x on the right hand side. Analytically, this may be written as:
where is the kth approximation or iteration of and is the next or k + 1 iteration of .
However, by taking advantage of the triangular form of (D+ωL), the elements of x(k+1) can be computed sequentially using forward substitution:
The choice of relaxation factor ω is not necessarily easy, and depends upon the properties of the coefficient matrix.
In 1947, Ostrowski proved that if is symmetric and positive-definite then for .
Thus, convergence of the iteration process follows, but we are generally interested in faster convergence rather than just convergence.
The convergence rate for the SOR method can be analytically derived.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.