I LOVE METHODS: 5.3 Gauss

27 julio 2010

Gauss–Seidel Method

In numerical linear algebra, the Gauss–Seidel method, also known as the Liebmann method or the method of successive displacement, is an iterative method used to solve a linear system of equations. It is named after the German mathematicians Carl Friedrich Gauss and Philipp Ludwig von Seidel, and is similar to the Jacobi method. Though it can be applied to any matrix with non-zero elements on the diagonals, convergence is only guaranteed if the matrix is either diagonally dominant, or symmetric and positive definite.

Given a square system of n linear equations with unknown x:

$A\mathbf x = \mathbf b$

where:

$A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.$

Then A can be decomposed into a lower triangular component L_*, and a strictly upper triangular component U:

$A=L_*+U \qquad \text{where} \qquad L_* = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \quad U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}$

The system of linear equations may be rewritten as:

$L_* \mathbf{x} = \mathbf{b} - U \mathbf{x}$

The Gauss–Seidel method is an iterative technique that solves the left hand side of this expression for x, using previous value for x on the right hand side. Analytically, this may be written as:

$\mathbf{x}^{(k+1)} = L_*^{-1} (\mathbf{b} - U \mathbf{x}^{(k)}).$

However, by taking advantage of the triangular form of L_*, the elements of x^(k+1) can be computed sequentially using forward substitution:

$x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j>i}a_{ij}x^{(k)}_j - \sum_{j<i}a_{ij}x^{(k+1)}_j \right),\quad i=1,2,\ldots,n.$

Note that the sum inside this computation of x_i^(k+1) requires each element in x^(k) except x_i^(k) itself.

The procedure is generally continued until the changes made by an iteration are below some tolerance.

Discussion

The element-wise formula for the Gauss–Seidel method is extremely similar to that of the Jacobi method.

The computation of x_i^(k+1) uses only the elements of x^(k+1) that have already been computed, and only the elements of x^(k) that have yet to be advanced to iteration k+1. This means that, unlike the Jacobi method, only one storage vector is required as elements can be overwritten as they are computed, which can be advantageous for very large problems.

However, unlike the Jacobi method, the computations for each element cannot be done in parallel. Furthermore, the values at each iteration are dependent on the order of the original equations.