Successive over-relaxation
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.[1] 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.
is the kth approximation or 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: This can again be written analytically in matrix-vector form without the need of inverting the matrix
:[2] The choice of relaxation factor ω is not necessarily easy, and depends upon the properties of the coefficient matrix.
The convergence rate for the SOR method can be analytically derived.
One needs to assume the following[3][4] Then the convergence rate can be expressed as where the optimal relaxation parameter is given by In particular, for
, which shows SOR is roughly four times more efficient than Gauss–Seidel.
The last assumption is satisfied for tridiagonal matrices since
Since elements can be overwritten as they are computed in this algorithm, only one storage vector is needed, and vector indexing is omitted.
The algorithm goes as follows: We are presented the linear system To solve the equations, we choose a relaxation factor
and an initial guess vector
According to the successive over-relaxation algorithm, the following table is obtained, representing an exemplary iteration with approximations, which ideally, but not necessarily, finds the exact solution, (3, −2, 2, 1), in 38 steps.
A simple implementation of the algorithm in Common Lisp is offered below.
A simple Python implementation of the pseudo-code provided above.
The version for symmetric matrices A, in which is referred to as Symmetric Successive Over-Relaxation, or (SSOR), in which and the iterative method is The SOR and SSOR methods are credited to David M. Young Jr. A similar technique can be used for any iterative method.
If the original iteration had the form then the modified version would use However, the formulation presented above, used for solving systems of linear equations, is not a special case of this formulation if x is considered to be the complete vector.
If this formulation is used instead, the equation for calculating the next vector will look like where
are used to speed up convergence of a slow-converging process, while values of
are often used to help establish convergence of a diverging iterative process or speed up the convergence of an overshooting process.
There are various methods that adaptively set the relaxation parameter
based on the observed behavior of the converging process.
Usually they help to reach a super-linear convergence for some problems but fail for the others.
