Module

for

Successive Over Relaxation - SOR Method

     

Background

    
    Suppose that iteration is used to solve the linear system   [Graphics:Images/SORmethodMod_gr_1.gif], and that  [Graphics:Images/SORmethodMod_gr_2.gif]  is an approximate solution.  We call  [Graphics:Images/SORmethodMod_gr_3.gif]  the residual vector, and if  [Graphics:Images/SORmethodMod_gr_4.gif]  is a good approximation then [Graphics:Images/SORmethodMod_gr_5.gif].  A method based on reducing the norm of the residual will produce a sequence [Graphics:Images/SORmethodMod_gr_6.gif] that converges faster.  The successive over relaxation - SOR method introduces a parameter  [Graphics:Images/SORmethodMod_gr_7.gif] 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.

[Graphics:Images/SORmethodMod_gr_8.gif] =

[Graphics:Images/SORmethodMod_gr_9.gif]-[Graphics:Images/SORmethodMod_gr_10.gif]-[Graphics:Images/SORmethodMod_gr_11.gif]  

 

Definition (Diagonally Dominant).  The matrix  [Graphics:Images/SORmethodMod_gr_12.gif]  is strictly diagonally dominant if

        [Graphics:Images/SORmethodMod_gr_13.gif][Graphics:Images/SORmethodMod_gr_14.gif][Graphics:Images/SORmethodMod_gr_15.gif][Graphics:Images/SORmethodMod_gr_16.gif][Graphics:Images/SORmethodMod_gr_17.gif]   for   [Graphics:Images/SORmethodMod_gr_18.gif].  

 

Theorem (Jacobi Iteration).  The solution to the linear system  [Graphics:Images/SORmethodMod_gr_19.gif]  can be obtained starting with  [Graphics:Images/SORmethodMod_gr_20.gif], and using iteration scheme
    
        [Graphics:Images/SORmethodMod_gr_21.gif]  
where  

        [Graphics:Images/SORmethodMod_gr_22.gif]  and  [Graphics:Images/SORmethodMod_gr_23.gif].  

If  [Graphics:Images/SORmethodMod_gr_24.gif] is carefully chosen a sequence [Graphics:Images/SORmethodMod_gr_25.gif] is generated which converges to the solution  P,  i.e.  [Graphics:Images/SORmethodMod_gr_26.gif].  
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  [Graphics:Images/SORmethodMod_gr_27.gif]  can be obtained starting with  [Graphics:Images/SORmethodMod_gr_28.gif], and using iteration scheme
    
        [Graphics:Images/SORmethodMod_gr_29.gif]  
where  

        [Graphics:Images/SORmethodMod_gr_30.gif]  and  [Graphics:Images/SORmethodMod_gr_31.gif].  

If  [Graphics:Images/SORmethodMod_gr_32.gif] is carefully chosen a sequence [Graphics:Images/SORmethodMod_gr_33.gif] is generated which converges to the solution  P,  i.e.  [Graphics:Images/SORmethodMod_gr_34.gif].  
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  [Graphics:Images/SORmethodMod_gr_35.gif]  (chosen in the interval [Graphics:Images/SORmethodMod_gr_36.gif]),  the solution to the linear system  [Graphics:Images/SORmethodMod_gr_37.gif]  can be obtained starting with  [Graphics:Images/SORmethodMod_gr_38.gif], and using iteration scheme
    
        [Graphics:Images/SORmethodMod_gr_39.gif]  
where  

        [Graphics:Images/SORmethodMod_gr_40.gif]  and  [Graphics:Images/SORmethodMod_gr_41.gif].  

If  [Graphics:Images/SORmethodMod_gr_42.gif] is carefully chosen a sequence [Graphics:Images/SORmethodMod_gr_43.gif] is generated which converges to the solution  P,  i.e.  [Graphics:Images/SORmethodMod_gr_44.gif].  
Remark.  A theorem of Kahan states that the SOR method will converge only if  [Graphics:Images/SORmethodMod_gr_45.gif]  is chosen in the interval   [Graphics:Images/SORmethodMod_gr_46.gif].    

Remark.  When we choose  [Graphics:Images/SORmethodMod_gr_47.gif]  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).

[Graphics:Images/SORmethodMod_gr_48.gif]

Mathematica Subroutine (Gauss-Seidel Iteration).

[Graphics:Images/SORmethodMod_gr_49.gif]

Mathematica Subroutine (Successive Over Relaxation).

[Graphics:Images/SORmethodMod_gr_50.gif]

Example 1.  Use successive over relaxation - SOR iteration to solve the linear system  [Graphics:Images/SORmethodMod_gr_51.gif].   
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  [Graphics:Images/SORmethodMod_gr_118.gif].  
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