Successive over-relaxation: Information from Answers.com

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 and by H. Frankel in 1950 for the purpose of automatically solving linear systems on digital computers. Over-relaxation methods have been used before the work of Young and Frankel. For instance, the method of Lewis Fry Richardson, and the methods developed by R. V. Southwell. However, these methods were designed for computation by human calculators, and they required 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.^[1]

1 Formulation
2 Algorithm
3 Other applications of the method
4 See also
5 Notes
6 References
7 External links

Formulation

Given a square system of n linear equations with unknown x:

$A\mathbf x = \mathbf b$

where:

$A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.$

Then A can be decomposed into a diagonal component D, and strictly lower and upper triangular components L and U:

$A=D+L+U \qquad \text{where} \quad D = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & a_{nn} \end{bmatrix}, \quad L = \begin{bmatrix} 0 & 0 & \cdots & 0 \\ a_{21} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & 0 \end{bmatrix}, \quad U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}$

The system of linear equations may be rewritten as:

$(D+\omega L) \mathbf{x} = \omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x}$

for a constant ω > 0.

The method of successive over-relaxation is an iterative technique that solves the left hand side of this expression for x, using previous value for x on the right hand side. Analytically, this may be written as:

$\mathbf{x}^{(k+1)} = (D+\omega L)^{-1} \big(\omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x}^{(k)}\big).$

However, by taking advantage of the triangular form of (D+ωL), the elements of x^(k+1) can be computed sequentially using forward substitution:

$x^{(k+1)}_i = (1-\omega)x^{(k)}_i + \frac{\omega}{a_{ii}} \left(b_i - \sum_{j>i} a_{ij}x^{(k)}_j - \sum_{j<i} a_{ij}x^{(k+1)}_j \right),\quad i=1,2,\ldots,n.$

The choice of relaxation factor is not necessarily easy, and depends upon the properties of the coefficient matrix. For symmetric, positive-definite matrices it can be proven that 0 < ω < 2 will lead to convergence, but we are generally interested in faster convergence rather than just convergence.

Algorithm

Inputs: A , b, ω
Output: $φ$

Choose an initial guess $φ (0)$ to the solution
repeat until convergence

for i from 1 until n do

$\sigma \leftarrow 0$

for j from 1 until i − 1 do

$\sigma \leftarrow \sigma + a_{ij} \phi_j^{(k+1)}$

end (j-loop)

for j from i + 1 until n do

$\sigma \leftarrow \sigma + a_{ij} \phi_j^{(k)}$

end (j-loop)

$\phi_i^{(k+1)} \leftarrow (1-\omega)\phi_i^{(k)} + \frac{\omega}{a_{ii}} (b_i - \sigma)$

end (i-loop)

check if convergence is reached

end (repeat)

Note:
$(1-\omega)\phi_i^{(k)} + \frac{\omega}{a_{ii}} (b_i - \sigma)$ can also be written $\phi_i^{(k)} + \omega \left( \frac{b_i - \sigma}{a_{ii}} - \phi_i^{(k)}\right)$ , thus saving one multiplication in each iteration of the outer for-loop.

Other applications of the method

Main article: Richardson extrapolation

A similar technique can be used for any iterative method. If the original iteration had the form

$x n + 1 = f (x n)$

then the modified version would use

$x^\mathrm{SOR}_{n+1}=(1-\omega)x^{\mathrm{SOR}}_n+\omega f(x^\mathrm{SOR}_n)$ .

Values of $ω > 1$ are used to speedup convergence of a slow-converging process, while values of $ω < 1$ are often used to help establish convergence of a diverging iterative 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

Notes

^ Young, David M. (May 1 1950), Iterative methods for solving partial difference equations of elliptical type, PhD thesis, Harvard University, http://www.ma.utexas.edu/CNA/DMY/david_young_thesis.pdf, retrieved on 2009-06-15

References

This article incorporates text from the article Successive_over-relaxation_method_-_SOR on CFD-Wiki that is under the GFDL license.

Black, Noel and Moore, Shirley, Successive Overrelaxation Method at MathWorld.
Yousef Saad, Iterative Methods for Sparse Linear Systems, 1st edition, PWS, 1996.
Netlib's copy of Jack Dongarra's section of "Templates for the Solution of Linear Systems"

External links

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What is the differences between Abbreviated progressive relaxation and progressive relaxation training? Read answer...
	How do you make a quick successive erection? Read answer...
	Who were three successive presidents born in Ohio? Read answer...

	You are looking to open up your own place for meditation yoga relaxation would the relaxation therapy course give you what you are looking for?
	What is a relaxation device and why UJT called as relaxation oscillator?
	What are successive integers?

Successive over-relaxation

Contents