http://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method

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 guaranteed if the matrix is either diagonally dominant, or symmetric and positive definite.

[hide]

Description

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.^{[citation needed]} Furthermore, the values at each iteration are dependent on the order of the original equations.

Convergence

The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either:

A is symmetric positive-definite, or
A is strictly or irreducibly diagonally dominant.

The Gauss–Seidel method sometimes converges even if these conditions are not satisfied.

Algorithm

Inputs: A , b
Output:

φ

Choose an initial guess

φ (0)

to the solution
repeat until convergence

for i from 1 until n do

$\sigma \leftarrow 0$

for j from 1 until i − 1 do

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

end (j-loop)

for j from i + 1 until n do

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

end (j-loop)

$\phi_i^{(k+1)} \leftarrow \frac 1 {a_{ii}} (b_i - \sigma)$

end (i-loop)

check if convergence is reached

end (repeat)
Gauss-Seidel is the same as SOR (successive over-relaxation) with

ω = 1

Examples

An example for the matrix version

A linear system shown as $A \mathbf{x} = \mathbf{b}$ is given by:

$A= \begin{bmatrix} 16 & 3 \\ 7 & -11 \\ \end{bmatrix}$ and $b= \begin{bmatrix} 11 \\ 13 \end{bmatrix}.$

We want to use the equation

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

in the form

$\mathbf{x}^{(k+1)} = T \mathbf{x}^{(k)} + C$

where:

$T = - L_*^{-1} U$ and $C = L_*^{-1} \mathbf{b}.$

We must decompose $A_{}^{}$ into the sum of a lower triangular component $L_*^{}$ and a strict upper triangular component $U_{}^{}$ :

$L_*= \begin{bmatrix} 16 & 0 \\ 7 & -11 \\ \end{bmatrix}$ and $U = \begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix}.$

The inverse of $L_*^{}$ is:

$L_*^{-1} = \begin{bmatrix} 16 & 0 \\ 7 & -11 \end{bmatrix}^{-1} = \begin{bmatrix} 0.0625 & 0.0000 \\ 0.0398 & -0.0909 \\ \end{bmatrix}$ .

Now we can find:

$T = - \begin{bmatrix} 0.0625 & 0.0000 \\ 0.0398 & -0.0909 \end{bmatrix} \times \begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix},$

$C = \begin{bmatrix} 0.0625 & 0.0000 \\ 0.0398 & -0.0909 \end{bmatrix} \times \begin{bmatrix} 11 \\ 13 \end{bmatrix} = \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix}.$

Now we have $T_{}^{}$ and $C_{}^{}$ and we can use them to obtain the vectors $\mathbf{x}$ iteratively.
First of all, we have to choose $\mathbf{x}^{(0)}$ : we can only guess. The better the guess, the quicker will perform the algorithm.
We suppose:

$x^{(0)} = \begin{bmatrix} 1.0 \\ 1.0 \end{bmatrix}.$

We can then calculate:

$x^{(1)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 1.0 \\ 1.0 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.5000 \\ -0.8636 \end{bmatrix}.$

$x^{(2)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 0.5000 \\ -0.8636 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8494 \\ -0.6413 \end{bmatrix}.$

$x^{(3)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 0.8494 \\ -0.6413 \\ \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8077 \\ -0.6678 \end{bmatrix}.$

$x^{(4)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 0.8077 \\ -0.6678 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8127 \\ -0.6646 \end{bmatrix}.$

$x^{(5)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 0.8127 \\ -0.6646 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8121 \\ -0.6650 \end{bmatrix}.$

$x^{(6)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 0.8121 \\ -0.6650 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8122 \\ -0.6650 \end{bmatrix}.$

$x^{(7)} = \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \times \begin{bmatrix} 0.8122 \\ -0.6650 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8122 \\ -0.6650 \end{bmatrix}.$

As expected, the algorithm converges to the exact solution:

$\mathbf{x} = A^{-1} \mathbf{b} = \begin{bmatrix} 0.8122\\ -0.6650 \end{bmatrix}.$

In fact, the matrix A is diagonally dominant (but not positive definite).

Another example for the matrix version

Another linear system shown as $A \mathbf{x} = \mathbf{b}$ is given by:

$A= \begin{bmatrix} 2 & 3 \\ 5 & 7 \\ \end{bmatrix}$ and $b= \begin{bmatrix} 11 \\ 13 \\ \end{bmatrix}.$

We want to use the equation

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

in the form

$\mathbf{x}^{(k+1)} = T \mathbf{x}^{(k)} + C$

where:

$T = - L_*^{-1} U$ and $C = L_*^{-1} \mathbf{b}.$

We must decompose $A_{}^{}$ into the sum of a lower triangular component $L_*^{}$ and a strict upper triangular component $U_{}^{}$ :

$L_*= \begin{bmatrix} 2 & 0 \\ 5 & 7 \\ \end{bmatrix}$ and $U = \begin{bmatrix} 0 & 3 \\ 0 & 0 \\ \end{bmatrix}.$

The inverse of $L_*^{}$ is:

$L_*^{-1} = \begin{bmatrix} 2 & 0 \\ 5 & 7 \\ \end{bmatrix}^{-1} = \begin{bmatrix} 0.500 & 0.000 \\ -0.357 & 0.143 \\ \end{bmatrix}$ .

Now we can find:

$T = - \begin{bmatrix} 0.500 & 0.000 \\ -0.357 & 0.143 \\ \end{bmatrix} \times \begin{bmatrix} 0 & 3 \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 0.000 & -1.500 \\ 0.000 & 1.071 \\ \end{bmatrix},$

$C = \begin{bmatrix} 0.500 & 0.000 \\ -0.357 & 0.143 \\ \end{bmatrix} \times \begin{bmatrix} 11 \\ 13 \\ \end{bmatrix} = \begin{bmatrix} 5.500 \\ -2.071 \\ \end{bmatrix}.$

$x^{(0)} = \begin{bmatrix} 1.1 \\ 2.3 \\ \end{bmatrix}.$

We can then calculate:

$x^{(1)} = \begin{bmatrix} 0 & -1.500 \\ 0 & 1.071 \\ \end{bmatrix} \times \begin{bmatrix} 1.1 \\ 2.3 \\ \end{bmatrix} + \begin{bmatrix} 5.500 \\ -2.071 \\ \end{bmatrix} = \begin{bmatrix} 2.050 \\ 0.393 \\ \end{bmatrix}.$

$x^{(2)} = \begin{bmatrix} 0 & -1.500 \\ 0 & 1.071 \\ \end{bmatrix} \times \begin{bmatrix} 2.050 \\ 0.393 \\ \end{bmatrix} + \begin{bmatrix} 5.500 \\ -2.071 \\ \end{bmatrix} = \begin{bmatrix} 4.911 \\ -1.651 \\ \end{bmatrix}.$

$x^{(3)} = \cdots. \,$

If we test for convergence we'll find that the algorithm diverges. In fact, the matrix A is neither diagonally dominant nor positive definite. Then, convergency to the exact solution

$\mathbf{x} = A^{-1} \mathbf{b} = \begin{bmatrix} -38\\ 29 \end{bmatrix}$

is not guaranteed and, in this case, will not occur.

An example for the equation version

Suppose given k equations where x_n are vectors of these equations and starting point x₀. From the first equation solve for x₁ in terms of $x_{n+1}, x_{n+2}, \dots, x_n.$ For the next equations substitute the previous values of xs.
To make it clear let's consider an example.

$\begin{align} 10x_1 - x_2 + 2x_3 & = 6, \\ -x_1 + 11x_2 - x_3 + 3x_4 & = 25, \\ 3x_2 - x_3 + 8x_4 & = 15. \end{align}$

Solving for

x 1

x 2

x 3

and

x 4

gives:

$\begin{align} x_1 & = x_2/10 - x_3/5 + 3/5, \\ x_2 & = x_1/11 + x_3/11 - 3x_4/11 + 25/11, \\ x_3 & = -x_1/5 + x_2/10 + x_4/10 - 11/10, \\ x_4 & = -3x_2/8 + x_3/8 + 15/8. \end{align}$

Suppose we choose (0, 0, 0, 0) as the initial approximation, then the first approximate solution is given by

$\begin{align} x_1 & = 3/5 = 0.6, \\ x_2 & = (3/5)/11 + 25/11 = 3/55 + 25/11 = 2.3272, \\ x_3 & = -(3/5)/5 +(2.3272)/10-11/10 = -3/25 + 0.23272-1.1 = -0.9873,\\ x_4 & = -3(2.3272)/8 +(-0.9873)/8+15/8 = 0.8789. \end{align}$

Using the approximations obtained, the iterative procedure is repeated until the desired accuracy has been reached. The following are the approximated solutions after four iterations.

$x 1$	$x 2$	$x 3$	$x 4$
$0.6$	$2.32727$	$- 0.987273$	$0.878864$
$1.03018$	$2.03694$	$- 1.01446$	$0.984341$
$1.00659$	$2.00356$	$- 1.00253$	$0.998351$
$1.00086$	$2.0003$	$- 1.00031$	$0.99985$

The exact solution of the system is (1, 2, −1, 1).

References

Black, Noel and Moore, Shirley, "Gauss-Seidel Method" from MathWorld.

This article incorporates text from the article Gauss-Seidel_method on CFD-Wiki that is under the GFDL license.

External links

Gauss–Seidel from www.math-linux.com
Module for Gauss–Seidel Iteration
Gauss–Seidel From Holistic Numerical Methods Institute
Gauss Siedel Iteration from www.geocities.com
The Gauss-Seidel Method
Bickson
Matlab code
C++ Sources - solving systems of linear algebraic equations (Gauss_Seidel_method).

[hide]v · d · eNumerical linear algebra

Key concepts	Floating point · Numerical stability · BLAS

Problems	Matrix multiplication · Matrix decompositions · Linear equations · Sparse problems

Hardware	CPU cache · TLB · Cache-oblivious algorithm · SIMD · Multiprocessing

Software	Specialized libraries · General purpose software

Retrieved from "http://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method"

Categories: Numerical linear algebra | Articles with example pseudocode

Hidden categories: All articles with unsourced statements | Articles with unsourced statements from October 2010 | GFDL

Chunlei Chen

Search This Blog

Monday, January 17, 2011

Least significant bits (LSB)

http://en.wikipedia.org/wiki/Least_significant_bit

Least significant bit

Least significant byte

See also

Sunday, January 16, 2011

stencil