CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Wiki > Gauss-Seidel method

Gauss-Seidel method

From CFD-Wiki

(Difference between revisions)
Jump to: navigation, search
(towards a uniform notation for linear systems : A*Phi = B)
(Added more material)
Line 1: Line 1:
 +
== Introduction ==
 +
We seek the solution to set of linear equations: <br>
We seek the solution to set of linear equations: <br>
-
:<math> A \cdot \Phi = B </math> <br>
+
:<math> A \phi = b </math> <br>
-
For the given matrix '''A''' and vectors '''X''' and '''Q'''. <br>
+
In matrix terms, the the Gauss-Seidel iteration can be expressed as
-
In matrix terms, the definition of the Gauss-Seidel method can be expressed as : <br>
+
-
<math>
+
-
\phi^{(k)}  = \left( {D - L} \right)^{ - 1} \left( {U\phi^{(k - 1)}  + b} \right)
+
-
</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>
+
-
The pseudocode for the Gauss-Seidel algorithm: <br>
+
:<math>
 +
\phi^{(k)}  = \left( {D - L} \right)^{ - 1} \left( {U\phi^{(k - 1)}  + b} \right),
 +
</math>
-
=== Algorithm ===
+
where <math>D</math>, <math>L</math> and <math>U</math> represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix <math>A</math> and <math>k</math> is the iteration count.  This matrix expression is mainly of academic interest, and is not used to program the method.  Rather, an element-based approach is used:
-
----
+
 
-
:    Chose an intital guess <math>X^{0}</math> to the solution <br>
+
:<math>
-
:    for k := 1 step 1 untill convergence do <br>
+
\phi^{(k)}_i  = \frac{1}{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 the computation of <math>\phi^{(k)}_i</math> uses only those elements of <math>\phi^{(k+1)}</math> that have already been computed.  This means that no additional storage is required, and the computation can be done in place (<math>\phi^{(k+1)}</math> replaces <math>\phi^{(k)}</math>).  While this might seem like a rather minor concern, for large systems it is unlikely that every iteration can be stored.  Thus, unlike the [[Jacobi method]], we do not have to do any vector copying should we wish to use only one storage vector.  The iteration is generally continued until the changes made by an iteration are below some tolerance.
 +
 
 +
== Algorithm ==
 +
:    Chose an initial guess <math>\phi^{0}</math> <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 28: Line 34:
::  check if convergence is reached
::  check if convergence is reached
:    end (k-loop)
:    end (k-loop)
-
----
 
-
 
-
 
-
----
 
-
<i> Return to [[Numerical methods | Numerical Methods]] </i>
 

Revision as of 01:02, 19 December 2005

Introduction

We seek the solution to set of linear equations:

A \phi = b

In matrix terms, the the Gauss-Seidel iteration can be expressed as

\phi^{(k)} = \left( {D - L} \right)^{ - 1} \left( {U\phi^{(k - 1)} + b} \right),

where D, L and U represent the diagonal, lower triangular and upper triangular matrices of coefficient matrix A and k is the iteration count. This matrix expression is mainly of academic interest, and is not used to program the method. Rather, an element-based approach is used:

\phi^{(k)}_i = \frac{1}{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 the computation of \phi^{(k)}_i uses only those elements of \phi^{(k+1)} that have already been computed. This means that no additional storage is required, and the computation can be done in place (\phi^{(k+1)} replaces \phi^{(k)}). While this might seem like a rather minor concern, for large systems it is unlikely that every iteration can be stored. Thus, unlike the Jacobi method, we do not have to do any vector copying should we wish to use only one storage vector. The iteration is generally continued until the changes made by an iteration are below some tolerance.

Algorithm

Chose an initial guess \phi^{0}
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)
\phi_i^{(k)} = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }}
end (i-loop)
check if convergence is reached
end (k-loop)
Retrieved from "https://cfd-online.com/Wiki/Gauss-Seidel_method"
My wiki