# Successive over-relaxation method - SOR

(Difference between revisions)
 Revision as of 20:33, 15 December 2005 (view source)Tsaad (Talk | contribs) (fixed dot product notation)← Older edit Revision as of 20:49, 15 December 2005 (view source)Tsaad (Talk | contribs) (towards a uniform notation for linear systems : A*Phi = B)Newer edit → Line 1: Line 1: We seek the solution to set of linear equations:
We seek the solution to set of linear equations:
- :$A \cdot X = Q$
+ :$A \cdot \Phi = B$
- For the given matrix '''A''' and vectors '''X''' and '''Q'''.
In matrix terms, the definition of the SOR method can be expressed as :
In matrix terms, the definition of the SOR method can be expressed as :
$[itex] - 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 + \phi^{(k)} = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)\phi^{(k - 1)} + \omega \left( {D - \omega L} \right)^{ - 1} B$
[/itex]
Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter.
Where '''D''','''L''' and '''U''' represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix '''A''' and k is iteration counter.
- $\omega$ is extrapolation factor.
+ $\omega$ is a relaxation factor.
The pseudocode for the SOR algorithm:
The pseudocode for the SOR algorithm:
Line 15: Line 14: === Algorithm === === Algorithm === ---- ---- - :    Chose an intital guess $X^{0}$ to the solution
+ :    Chose an intital guess $\Phi^{0}$ to the solution
:    for k := 1 step 1 untill convergence do
:    for k := 1 step 1 untill convergence do
::  for i := 1 step until n do
::  for i := 1 step until n do
:::  $\sigma = 0$
:::  $\sigma = 0$
:::  for j := 1 step until i-1 do
:::  for j := 1 step until i-1 do
- ::::      $\sigma = \sigma + a_{ij} x_j^{(k)}$ + ::::      $\sigma = \sigma + a_{ij} \phi_j^{(k)}$ :::    end (j-loop)
:::    end (j-loop)
:::  for j := i+1 step until n do
:::  for j := i+1 step until n do
- ::::      $\sigma = \sigma + a_{ij} x_j^{(k-1)}$ + ::::      $\sigma = \sigma + a_{ij} \phi_j^{(k-1)}$ :::    end (j-loop)
:::    end (j-loop)
- :::    $\sigma = {{\left( {q_i - \sigma } \right)} \over {a_{ii} }}$ + :::    $\sigma = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }}$ - :::    $x_i^{(k)} = x_i^{(k - 1)} + \omega \left( {\sigma - x_i^{k - 1} } \right)$ + :::    $\phi_i^{(k)} = \phi_i^{(k - 1)} + \omega \left( {\sigma - \phi_i^{k - 1} } \right)$ ::  end (i-loop) ::  end (i-loop) ::  check if convergence is reached ::  check if convergence is reached

## Revision as of 20:49, 15 December 2005

We seek the solution to set of linear equations:

$A \cdot \Phi = B$

In matrix terms, the definition of the SOR method can be expressed as :
$\phi^{(k)} = \left( {D - \omega L} \right)^{ - 1} \left( {\omega U + \left( {1 - \omega } \right)D} \right)\phi^{(k - 1)} + \omega \left( {D - \omega L} \right)^{ - 1} B$
Where D,L and U represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix A and k is iteration counter.
$\omega$ is a relaxation factor.

The pseudocode for the SOR algorithm:

### Algorithm

Chose an intital guess $\Phi^{0}$ to the solution
for k := 1 step 1 untill 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)