Successive over-relaxation


In numerical linear algebra, the method of successive over-relaxation 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.

Formulation

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 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, the elements of x can be computed sequentially using forward substitution:

Convergence

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.

Convergence Rate

The convergence rate for the SOR method can be analytically derived.
One needs to assume the following
Then the convergence rate can be expressed as
where the optimal relaxation parameter is given by

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:,,
Output:
Choose an initial guess to the solution
repeat until convergence
for from 1 until do

for from 1 until do
if ≠ then

end if
end

end
check if convergence is reached
end
;Note: can also be written, thus saving one multiplication in each iteration of the outer for-loop.

Example

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, following table is obtained, representing an exemplary iteration with approximations, which ideally, but not necessarily, finds the exact solution,, in 38 steps.
Iteration
10.25-2.781251.62890620.5152344
21.2490234-2.24489741.96877120.9108547
32.070478-1.66967891.59048810.76172125
...............
372.9999998-2.02.01.0
383.0-2.02.01.0

A simple implementation of the algorithm in Common Lisp is offered below. Beware its proclivity towards floating-point overflows in the general case.

"For each component of the COMPUTED-SOLUTION vector, retrieves its
error with respect to the expected EXACT-SOLUTION, returning a
vector of error values."
)
))
))
"Creates and returns a vector of the SIZE with all elements set to 0."
)


)))
"Implements the successive over-relaxation method, applied upon
the linear equations defined by the matrix A and the right-hand side
vector B, employing the relaxation factor OMEGA, returning the
calculated solution vector.
---
The first algorithm step, the choice of an initial guess PHI, is
represented by the optional keyword parameter PHI, which defaults
to a zero-vector of the same structure as B. If supplied, this
vector will be destructively modified. In any case, the PHI vector
constitutes the function's result value.
---
The terminating condition is implemented by the CONVERGENCE-CHECK,
an optional predicate
lambda => generalized-boolean
which returns T, signifying the immediate termination, upon achieving
convergence, or NIL, signaling continuant operation, otherwise."

)


)))


)
))))

;; Check if convergence is reached.

)))
phi)
;; Summon the function with the exemplary parameters.
:initial-contents
'


)))


)




)))))

A simple Python implementation of the pseudo-code provided above.

import numpy as np
def sor_solver:
"""
This is an implementation of the pseudo-code provided in the Wikipedia article.
Arguments:
A: nxn numpy matrix.
b: n dimensional numpy vector.
omega: relaxation factor.
initial_guess: An initial solution guess for the solver to start with.
convergence_criteria: The maximum discrepancy acceptable to regard the current solution as fitting.
Returns:
phi: solution vector of dimension n.
"""
phi = initial_guess
residual = np.linalg.norm #Initial residual
while residual > convergence_criteria:
for i in range:
sigma = 0
for j in range:
if j != i:
sigma += A * phi
phi = * phi + *
residual = np.linalg.norm
print
return phi
  1. An example case that mirrors the one in the Wikipedia article
residual_convergence = 1e-8
omega = 0.5 #Relaxation factor
A = np.matrix
b = np.matrix
initial_guess = np.zeros
phi = sor_solver
print

Symmetric successive over-relaxation

The version for symmetric matrices A, in which
is referred to as Symmetric Successive Over-Relaxation, or, in which
and the iterative method is
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
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 is considered to be the complete vector. If this formulation is used instead, the equation for calculating the next vector will look like
where. Values of 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.