Successive over-relaxation method - SOR

From CFD-Wiki

(Difference between revisions)

Latest revision as of 02:08, 19 December 2005

Introduction

We seek the solution to set of linear equations

$A \phi = b.$

In matrix terms, the successive over-relaxation (SOR) iteration can be expressed as

$\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$

where $D$ , $L$ , and $U$ represent the diagonal, lower triangular, and upper triangular parts of the coefficient matrix $A$ , $k$ is the iteration count, and $\omega$ is a relaxation factor. This matrix expression is not usually used to program the method, and an element-based expression is used:

$\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.$

Note that for $\omega = 1$ that the iteration reduces to the Gauss-Seidel iteration. As with the Gauss-Seidel 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 $0<\omega<2$ will lead to convergence, but we are generally interested in faster convergence rather than just convergence.

Algorithm

Chose an initial guess $\phi^{0}$ to the solution

for k := 1 step 1 until convergence do

for i := 1 step until n do

$\sigma = 0$

for j := 1 step until i-1 do

$\sigma = \sigma + a_{ij} \phi_j^{(k)}$

end (j-loop)

for j := i+1 step until n do

$\sigma = \sigma + a_{ij} \phi_j^{(k-1)}$

end (j-loop)

$\sigma = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }}$

$\phi_i^{(k)} = \phi_i^{(k - 1)} + \omega \left( {\sigma - \phi_i^{k - 1} } \right)$

end (i-loop)

check if convergence is reached

end (k-loop)

TODO - add references, more about relaxation factor

@@ Line 1: / Line 1: @@
-We seek the solution to set of linear equations: <br>
+== Introduction ==
-:<math> A \bullet X = Q </math> <br>
+We seek the solution to set of linear equations <br>
-For the given matrix '''A''' and vectors '''X''' and '''Q'''. <br>
+:<math> A \phi = b. </math> <br>
-In matrix terms, the definition of the SOR method can be expressed as : <br>
-<math>
-x^{(k)}  = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)x^{(k - 1)}  + \omega \left( {D - \omega L} \right)^{ - 1} q
-</math><br>
-Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter.<br>
-<math> \omega </math> is extrapolation factor. <br>
-The pseudocode for the SOR algorithm: <br>
+In matrix terms, the successive over-relaxation (SOR) iteration can be expressed as
-=== Algorithm ===
+:<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
-:    Chose an intital guess <math>X^{0}</math> to the solution <br>
+</math>
-:    for k := 1 step 1 untill convergence do <br>
+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 element-based 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 [[Gauss-Seidel method| Gauss-Seidel]] iteration.  As with the [[Gauss-Seidel 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>
 :::  <math> \sigma = 0 </math> <br>
 :::   for j := 1 step until i-1 do <br>
-::::      <math> \sigma  = \sigma  + a_{ij} x_j^{(k)} </math>
+::::      <math> \sigma  = \sigma  + a_{ij} \phi_j^{(k)} </math>
 :::    end (j-loop) <br>
 :::   for j := i+1 step until n do <br>
-::::      <math> \sigma  = \sigma  + a_{ij} x_j^{(k-1)} </math>
+::::      <math> \sigma  = \sigma  + a_{ij} \phi_j^{(k-1)} </math>
 :::    end (j-loop) <br>
-:::    <math>  \sigma  = {{\left( {q_i  - \sigma } \right)} \over {a_{ii} }} </math>
+:::    <math>  \sigma  = {{\left( {b_i  - \sigma } \right)} \over {a_{ii} }} </math>
-:::    <math> x_i^{(k)}  = x_i^{(k - 1)}  + \omega \left( {\sigma  - x_i^{k - 1} } \right)  </math>
+:::    <math> \phi_i^{(k)}  = \phi_i^{(k - 1)}  + \omega \left( {\sigma  - \phi_i^{k - 1} } \right)  </math>
 ::   end (i-loop)
 ::   check if convergence is reached
 :    end (k-loop)
-----
-----
+''TODO - add references, more about relaxation factor''
-<i> Return to [[Numerical methods | Numerical Methods]] </i>

Successive over-relaxation method - SOR

From CFD-Wiki

Latest revision as of 02:08, 19 December 2005

Introduction

Algorithm

Views

My wiki

wiki navigation

wiki search

wiki toolbox