Gauss-Seidel method

The Gauss-Seidel method is a technique used to solve a linear system of equations. The method is named after the German mathematicians Carl Friedrich Gauss and Philipp Ludwig von Seidel. The method is similar to the Jacobi method (and likewise diagonal dominance of the system is sufficient to ensure convergence, meaning the method will work).

We seek the solution to a set of linear equations, expressed in matrix terms as

A  \phi = b.\,

The Gauss-Seidel iteration is

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

where $D$ , $-L$ , and $-U$ represent the diagonal, lower triangular, and upper triangular parts of the 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+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{ji}a_{ij}\phi^{(k)}_j\right),\, i=1,2,\ldots,n.

Note that the computation of $\phi^{(k+1)}_i$ uses only those elements of $\phi^{(k+1)}\,$ that have already been computed and only those elements of $\phi^{(k)}\,$ that have yet to be advanced to iteration $k+1$ . 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)}  =

end (i-loop)

check if convergence is reached

end (k-loop)

External links

Numerical linear algebra | Gauß-Seidel-Verfahren

Gourt Home::Gourt :: Gauss-Seidel method

Algorithm

External links