Successive overrelaxation method  SOR
From CFDWiki
(towards a uniform notation for linear systems : A*Phi = B) 

Line 1:  Line 1:  
  +  == Introduction ==  
  +  We seek the solution to set of linear equations <br>  
  +  :<math> A \phi = b. </math> <br>  
  <math>  +  
  \phi  +  
  +  
  +  
  +  
  +  In matrix terms, the successive overrelaxation (SOR) iteration can be expressed as  
  ===  +  :<math> 
    +  \phi^{(k+1)} = \left( {D  \omega L} \right)^{  1} \left( {\omega U + \left( {1  \omega } \right)D} \right)\phi^{(k)} + \omega \left( {D  \omega L} \right)^{  1} b 
  +  </math>  
  : for k := 1 step 1  +  
+  where <math>D</math>, <math>L</math>, and <math>U</math> represent the diagonal, lower triangular, and upper triangular parts of the coefficient matrix <math>A</math>, <math>k</math> is the iteration count, and <math> \omega </math> is a relaxation factor. This matrix expression is not usually used to program the method, and an elementbased expression is used:  
+  
+  :<math>  
+  \phi^{(k+1)}_i = (1\omega)\phi^{(k)}_i+\frac{\omega}{a_{ii}} \left(b_i  \sum_{j<i}a_{ij}\phi^{(k+1)}_j\sum_{j>i}a_{ij}\phi^{(k)}_j\right),\, i=1,2,\ldots,n.  
+  </math>  
+  
+  Note that for <math>\omega = 1</math> that the iteration reduces to the [[GaussSeidel method GaussSeidel]] iteration. As with the [[GaussSeidel method]], the computation may be done in place, and the iteration is continued until the changes made by an iteration are below some tolerance.  
+  
+  The choice of relaxation factor is not necessarily easy, and depends upon the properties of the coefficient matrix. For symmetric, positive definite matrices it can be proven that <math>0<\omega<2</math> will lead to convergence, but we are generally interested in faster convergence rather than just convergence.  
+  
+  == Algorithm ==  
+  Chose an initial guess <math>\phi^{0}</math> to the solution <br>  
+  : for k := 1 step 1 until convergence do <br>  
:: for i := 1 step until n do <br>  :: for i := 1 step until n do <br>  
::: <math> \sigma = 0 </math> <br>  ::: <math> \sigma = 0 </math> <br>  
Line 29:  Line 37:  
:: check if convergence is reached  :: check if convergence is reached  
: end (kloop)  : end (kloop)  
  
  
    +  ''TODO  add references, more about relaxation factor'' 
  + 
Latest revision as of 02:08, 19 December 2005
Introduction
We seek the solution to set of linear equations
In matrix terms, the successive overrelaxation (SOR) iteration can be expressed as
where , , and represent the diagonal, lower triangular, and upper triangular parts of the coefficient matrix , is the iteration count, and is a relaxation factor. This matrix expression is not usually used to program the method, and an elementbased expression is used:
Note that for that the iteration reduces to the GaussSeidel iteration. As with the GaussSeidel method, the computation may be done in place, and the iteration is continued until the changes made by an iteration are below some tolerance.
The choice of relaxation factor is not necessarily easy, and depends upon the properties of the coefficient matrix. For symmetric, positive definite matrices it can be proven that will lead to convergence, but we are generally interested in faster convergence rather than just convergence.
Algorithm
Chose an initial guess to the solution
 for k := 1 step 1 until convergence do
 for i := 1 step until n do

 for j := 1 step until i1 do
 end (jloop)
 for j := i+1 step until n do
 end (jloop)

 end (iloop)
 check if convergence is reached
 for i := 1 step until n do
 end (kloop)
TODO  add references, more about relaxation factor