Module

for

Successive Over Relaxation - SOR Method

Background

Suppose that iteration is used to solve the linear system   , and that    is an approximate solution.  We call    the residual vector, and if    is a good approximation then .  A method based on reducing the norm of the residual will produce a sequence that converges faster.  The successive over relaxation - SOR method introduces a parameter   which speeds up convergence.  The SOR method can be used in the numerical solution of certain partial differential equations.

Consider that the n×n square matrix A is split into three parts, the main diagonal D, below diagonal L and above diagonal U.  We have  A = D - L - U.

=

--

Definition (Diagonally Dominant).  The matrix    is strictly diagonally dominant if

for   .

Theorem (Jacobi Iteration).  The solution to the linear system    can be obtained starting with  , and using iteration scheme

where

and  .

If   is carefully chosen a sequence is generated which converges to the solution  P,  i.e.  .
A sufficient condition for the method to be applicable is that A is strictly diagonally dominant or diagonally dominant and irreducible.

Theorem (Gauss-Seidel Iteration).  The solution to the linear system    can be obtained starting with  , and using iteration scheme

where

and  .

If   is carefully chosen a sequence is generated which converges to the solution  P,  i.e.  .
A sufficient condition for the method to be applicable is that A is strictly diagonally dominant or diagonally dominant and irreducible.

Theorem (SOR Iteration).  Given a value of the parameter    (chosen in the interval ),  the solution to the linear system    can be obtained starting with  , and using iteration scheme

where

and  .

If   is carefully chosen a sequence is generated which converges to the solution  P,  i.e.  .
Remark.  A theorem of Kahan states that the SOR method will converge only if    is chosen in the interval   .

Remark.  When we choose    the SOR method reduces to the Gauss-Seidel method.

Computer Programs  Successive Over Relaxation  Successive Over Relaxation

Mathematica Subroutine (Jacobi Iteration).

Mathematica Subroutine (Gauss-Seidel Iteration).

Mathematica Subroutine (Successive Over Relaxation).

Example 1.  Use successive over relaxation - SOR iteration to solve the linear system  .
1 (a).  Use 10 iterations.  Compare the speed of convergence with Jacobi and Gauss-Seidel iteration.
1 (b).  Use 20 iterations.  Compare the speed of convergence with Jacobi and Gauss-Seidel iteration.
Solution 1 (a).
Solution 1 (b).

Example 2.  Use successive over relaxation - SOR iteration to solve the linear system  .
Try 10 iterations.  Compare the speed of convergence with Jacobi and Gauss-Seidel iteration.
Solution 2.

Successive Over Relaxation  Successive Over Relaxation  Internet hyperlinks to web sites and a bibliography of articles.

(c) John H. Mathews 2004