Successive over-relaxation

The " Successive Over- Relaxation" method ( overrelaxation ) or SOR method is an algorithm of numerical analysis for the approximate solution of linear equation systems. It is, as the Gauss- Seidel method and the Jacobi method, a special splitting procedure (A = B ( A - B ) with B = (1 / ) D L).

Description of the procedure

Given a square linear system with n equations and unknowns x. Here are

The SOR method solves this equation, starting from a starting vector by the iteration

The real Überrelaxationsparameter ensures that the method converges more quickly as the Gauss- Seidel method, which is a special case of this formula.

Algorithm

As a sketch algorithm with termination condition easily by:

In this case, an error bound was adopted as the input size of the algorithm; the approximate solution is the vectorial return size. The error bound measures here at how great the last change of the variable vector.

For sparse matrices, the effort of the method per iteration is significantly reduced.

Derivation

The SOR method is obtained by relaxation of the Gauss - Seidel method:

Thus obtained for Gauss-Seidel back. To analyze the process, the formulation offers a splitting process that makes it possible to analyze the characteristics of the process. The matrix A is written to the sum of a diagonal matrix D and two strict triangular matrices L and R:

Said linear system of equations is then equivalent to

With ω > 0, the iteration matrix is then so

And the process is consistent and converges if and only if the spectral radius is.

The above formulation for the component-wise calculation of obtained from this matrix representation when taking advantage of the triangular form of the matrix. This matrix can be inverted directly by forward substitution.

Convergence

It can be shown that the method of symmetric positive definite A converged for each. To accelerate the convergence with the Gauss-Seidel method, one uses heuristic values ​​between 1.5 and 2.0. The best choice depends on the coefficient matrix A. Values ​​can be chosen to stabilize a solution that otherwise easily diverges.

The theorem of Kahan (1958 ) shows that for ω outside the interval (0,2) there is no convergence.