Successive over relaxation

Formulation

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

A x = b

where:

A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] , x = [ x 1 x 2 ⋮ x n ] , b = [ b 1 b 2 ⋮ b n ] .

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

A = D + L + U ,

where

D = [ a 11 0 ⋯ 0 0 a 22 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ a n n ] , L = [ 0 0 ⋯ 0 a 21 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ 0 ] , U = [ 0 a 12 ⋯ a 1 n 0 0 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 0 ] .

The system of linear equations may be rewritten as:

( D + ω L ) x = ω b − [ ω U + ( ω − 1 ) D ] x

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 previous value for x on the right hand side. Analytically, this may be written as:

x ( k + 1 ) = ( D + ω L ) − 1 ( ω b − [ ω U + ( ω − 1 ) D ] x ( k ) ) = L w x ( k ) + c ,

where x ( k ) is the kth approximation or iteration of x and x ( k + 1 ) is the next or k + 1 iteration of x . 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 i ( k + 1 ) = ( 1 − ω ) x i ( k ) + ω a i i ( b i − ∑ j < i a i j x j ( k + 1 ) − ∑ j > i a i j x j ( k ) ) , i = 1 , 2 , … , n .

The choice of relaxation factor ω is not necessarily easy, and depends upon the properties of the coefficient matrix. In 1947, Ostrowski proved that if A is symmetric and positive-definite then ρ ( L ω ) < 1 for 0 < ω < 2 . Thus convergence of the iteration process follows, but we are generally interested in faster convergence rather than just convergence.

Algorithm

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:

Inputs: A, b, ωOutput: ϕ Choose an initial guess ϕ to the solutionrepeat until convergence for i from 1 until n do σ ← 0 for j from 1 until n do if j ≠ i then σ ← σ + a i j ϕ j end if end (j-loop) ϕ i ← ( 1 − ω ) ϕ i + ω a i i ( b i − σ ) end (i-loop) check if convergence is reachedend (repeat)

Note

( 1 − ω ) ϕ i + ω a i i ( b i − σ ) can also be written ϕ i + ω ( b i − σ a i i − ϕ i ) , thus saving one multiplication in each iteration of the outer for-loop.

Symmetric successive over-relaxation

The version for symmetric matrices A, in which

U = L T ,

is referred to as Symmetric Successive Over-Relaxation, or (SSOR), in which

P = ( D ω + L ) 1 2 − ω D − 1 ( D ω + U ) ,

and the iterative method is

x k + 1 = x k − γ k P − 1 ( A x k − b ) ,   k ≥ 0.

The SOR and SSOR methods are credited to David M. Young, Jr..

Other applications of the method

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 n + 1 S O R = ( 1 − ω ) x n S O R + ω f ( x n S O R ) .

Note however that 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

x ( k + 1 ) = ( 1 − ω ) x ( k ) + ω L ∗ − 1 ( b − U x ( k ) ) ,

where L ∗ = L + D . Values of ω > 1 are used to speed up convergence of a slow-converging process, while values of ω < 1 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.