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.  

Proof  Jacobi and Gauss-Seidel Iteration  Jacobi and Gauss-Seidel Iteration  

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.

Proof  Jacobi and Gauss-Seidel Iteration  Jacobi and Gauss-Seidel Iteration  

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.  

Proof  Successive Over Relaxation  Successive Over Relaxation  

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.

Research Experience for Undergraduates

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

Download this Mathematica Notebook Successive Over Relaxation - SOR Method

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004