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 system of linear equations.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 13 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 system of linear equations. It is named after the German mathematicians Carl Friedrich Gauss and Philipp Ludwig von Seidel.

Though it can be applied to any matrix with non-zero elements on the diagonals, convergence is only guaranteed if the matrix is either strictly diagonally dominant, or symmetric and positive definite. It was only mentioned in a private letter from Gauss to his student Gerling in 1823. A publication was not delivered before 1874 by Seidel.

Let \mathbf A\mathbf x = \mathbf b be a square system of linear equations, where: \mathbf 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}. When \mathbf A and \mathbf b are known, and \mathbf x is unknown, the Gauss–Seidel method can be used to iteratively approximate \mathbf x . The vector \mathbf x^{(0)} denotes the initial guess for \mathbf x , often \mathbf x^{(0)}_i=0 for i=1,2,...,n . Denote by \mathbf{x}^{(k)} the k -th approximation or iteration of \mathbf{x} , and by \mathbf{x}^{(k+1)} the approximation of \mathbf{x} at the next (or k+1 -th) iteration. \mathbf L \mathbf{x}^{(k+1)} = \mathbf{b} - \mathbf U \mathbf{x}^{(k)}, where the matrix \mathbf A is decomposed into a lower triangular component \mathbf L , and a strictly upper triangular component \mathbf U such that \mathbf {A} = \mathbf L + \mathbf U . More specifically, the decomposition of \mathbf A into \mathbf L and \mathbf U is given by: \mathbf A = \underbrace{ \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} }_{\textstyle \mathbf L} + \underbrace{ \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix} }_{\textstyle \mathbf U} . \mathbf A \mathbf x &= \mathbf b \\ (\mathbf L + \mathbf U) \mathbf x &= \mathbf b \\ \mathbf L \mathbf x+ \mathbf U \mathbf x &= \mathbf b \\ \mathbf L \mathbf{x} &= \mathbf{b} - \mathbf U \mathbf{x} \end{alignat} The Gauss–Seidel method now solves the left hand side of this expression for \mathbf{x} , using the previous value for \mathbf{x} on the right hand side.

Analytically, this may be written as \mathbf {x}^{(k+1)} = \mathbf L^{-1} \left(\mathbf{b} - \mathbf U \mathbf{x}^{(k)}\right). x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1}a_{ij}x^{(k+1)}_j - \sum_{j=i+1}^{n}a_{ij}x^{(k)}_j \right),\quad i=1,2,\dots,n. Notice that the formula uses two summations per iteration which can be expressed as one summation \sum_{j \ne i} a_{ij}x_j that uses the most recently calculated iteration of x_j . The procedure is generally continued until the changes made by an iteration are below some tolerance, such as a sufficiently small residual. Gauss-Seidel is the same as successive over-relaxation with \omega=1 .

Convergence

The convergence properties of the Gauss–Seidel method are dependent on the matrix \mathbf A . Namely, the procedure is known to converge if either: \mathbf A is symmetric positive-definite, or \mathbf A is strictly or irreducibly diagonally dominant. The Gauss–Seidel method may converge even if these conditions are not satisfied.

Golub and Van Loan give a theorem for an algorithm that splits \mathbf A into two parts. Suppose \mathbf A = \mathbf M - \mathbf N is nonsingular.

Let r = \rho (\mathbf M^ {-1} \mathbf N) be the spectral radius of \mathbf M^{-1} \mathbf N . Then the iterates \mathbf x^{(k)} defined by \mathbf M \mathbf x^{(k+1)} = \mathbf N \mathbf x^{(k)} + \mathbf b converge to \mathbf x = \mathbf A^{-1} \mathbf b for any starting vector \mathbf x^{(0)} if \mathbf M is nonsingular and r .

An example for the matrix version

A linear system shown as \mathbf A \mathbf{x} = \mathbf{b} is given by: \mathbf A= \begin{bmatrix} 16 & 3 \\ 7 & -11 \\ \end{bmatrix} \quad \text{and} \quad \mathbf b = \begin{bmatrix} 11 \\ 13 \end{bmatrix}. Use the equation \mathbf{x}^{(k+1)} = \mathbf L^{-1} (\mathbf{b} - \mathbf U \mathbf{x}^{(k)}) in the form \mathbf{x}^{(k+1)} = \mathbf T \mathbf{x}^{(k)} + \mathbf c where: \mathbf T = - \mathbf L ^{-1} \mathbf U \quad \text{and} \quad \mathbf c = \mathbf L ^{-1} \mathbf{b}.

Decompose \mathbf A into the sum of a lower triangular component \mathbf L and a strict upper triangular component U : \mathbf L= \begin{bmatrix} 16 & 0 \\ 7 & -11 \\ \end{bmatrix} \quad \text{and} \quad \mathbf U = \begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix}. The inverse of \mathbf L is: \mathbf L^{-1} = \begin{bmatrix} 16 & 0 \\ 7 & -11 \end{bmatrix}^{-1} = \begin{bmatrix} 0.0625 & 0.0000 \\ 0.0398 & -0.0909 \\ \end{bmatrix}.

Now find: \begin{align} \mathbf T & = - \begin{bmatrix} 0.0625 & 0.0000 \\ 0.0398 & -0.0909 \end{bmatrix} \begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 0.6875 \\ -0.7439 \end{bmatrix}. \end{align} With \mathbf T and \mathbf c the vectors \mathbf{x} can be obtained iteratively. First of all, choose \mathbf{x}^{(0)} , for example \mathbf x^{(0)} = \begin{bmatrix} 1.0 \\ 1.0 \end{bmatrix}.

The closer the guess to the final solution, the fewer iterations the algorithm will need. Then calculate: \begin{align} \mathbf x^{(1)} &= \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \begin{bmatrix} 1.0 \\ 1.0 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.5000 \\ -0.8636 \end{bmatrix}. \\[1ex] \mathbf x^{(2)} &= \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \begin{bmatrix} 0.5000 \\ -0.8636 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8494 \\ -0.6413 \end{bmatrix}. \\[1ex] \mathbf x^{(3)} &= \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \begin{bmatrix} 0.8494 \\ -0.6413 \\ \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8077 \\ -0.6678 \end{bmatrix}. \\[1ex] \mathbf x^{(4)} &= \begin{bmatrix} 0.000 & -0.1875 \\ 0.000 & -0.1193 \end{bmatrix} \begin{bmatrix} 0.8077 \\ -0.6678 \end{bmatrix} + \begin{bmatrix} 0.6875 \\ -0.7443 \end{bmatrix} = \begin{bmatrix} 0.8122 \\ -0.6650 \end{bmatrix}. \end{align} As expected, the algorithm converges to the solution: \mathbf{x} = \mathbf A ^{-1} \mathbf{b} \approx \begin{bmatrix} 0.8122\\ -0.6650 \end{bmatrix}.

In fact, the matrix is strictly diagonally dominant, but not positive definite.

Another example for the matrix version

Another linear system shown as \mathbf A \mathbf{x} = \mathbf{b} is given by: \mathbf A= \begin{bmatrix} 2 & 3 \\ 5 & 7 \\ \end{bmatrix} \quad \text{and} \quad \mathbf b = \begin{bmatrix} 11 \\ 13 \\ \end{bmatrix}. Use the equation \mathbf{x}^{(k+1)} = \mathbf L^{-1} (\mathbf{b} - \mathbf U \mathbf{x}^{(k)}) in the form \mathbf{x}^{(k+1)} = \mathbf T \mathbf{x}^{(k)} + \mathbf c where: \mathbf T = - \mathbf L ^{-1} \mathbf U \quad \text{and} \quad \mathbf c = \mathbf L^{-1} \mathbf{b}.

Decompose \mathbf A into the sum of a lower triangular component \mathbf L and a strict upper triangular component \mathbf U : \mathbf L = \begin{bmatrix} 2 & 0 \\ 5 & 7 \\ \end{bmatrix} \quad \text{and} \quad \mathbf U = \begin{bmatrix} 0 & 3 \\ 0 & 0 \\ \end{bmatrix}. The inverse of \mathbf L is: \mathbf L ^{-1} = \begin{bmatrix} 2 & 0 \\ 5 & 7 \\ \end{bmatrix}^{-1} = \begin{bmatrix} 0.500 & 0.000 \\ -0.357 & 0.143 \\ \end{bmatrix} .

Now find: \begin{align} \mathbf T & = - \begin{bmatrix} 0.500 & 0.000 \\ -0.357 & 0.143 \\ \end{bmatrix} \begin{bmatrix} 0 & 3 \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 5.500 \\ -2.071 \\ \end{bmatrix}. \end{align} With \mathbf T and \mathbf c the vectors \mathbf{x} can be obtained iteratively. First of all, we have to choose \mathbf{x}^{(0)} , for example \mathbf {x} ^{(0)} = \begin{bmatrix} 1.1 \\ 2.3 \end{bmatrix} Then calculate: \begin{align} \mathbf {x}^{(1)} &= \begin{bmatrix} 0 & -1.500 \\ 0 & 1.071 \\ \end{bmatrix} \begin{bmatrix} 1.1 \\ 2.3 \\ \end{bmatrix} + \begin{bmatrix} 5.500 \\ -2.071 \\ \end{bmatrix} = \begin{bmatrix} 2.050 \\ 0.393 \\ \end{bmatrix}. \\[1ex] \mathbf {x}^{(2)} &= \begin{bmatrix} 0 & -1.500 \\ 0 & 1.071 \\ \end{bmatrix} \begin{bmatrix} 2.050 \\ 0.393 \\ \end{bmatrix} + \begin{bmatrix} 5.500 \\ -2.071 \\ \end{bmatrix} = \begin{bmatrix} 4.911 \\ -1.651 \end{bmatrix}. \\[1ex] \mathbf {x}^{(3)} &= \cdots. \end{align} In a test for convergence we find that the algorithm diverges.

In fact, the matrix \mathbf A is neither diagonally dominant nor positive definite. Then, convergence to the exact solution \mathbf{x} = \mathbf 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 n equations and a starting point \mathbf {x} _0 . At any step in a Gauss-Seidel iteration, solve the first equation for x_1 in terms of x_{2}, \dots, x_n ; then solve the second equation for x_2 in terms of x_1 just found and the remaining x_{3}, \dots, x_n ; and continue to x_n . Then, repeat iterations until convergence is achieved, or break if the divergence in the solutions start to diverge beyond a predefined level.

Consider an example: \begin{array}{rrrrl} 10x_1 &- x_2 &+ 2x_3 & & = 6, \\ -x_1 &+ 11x_2 &- x_3 &+ 3x_4 & = 25, \\ 2x_1 &- x_2 &+ 10x_3 &- x_4 & = -11, \\ & 3x_2 &- x_3 &+ 8x_4 & = 15. \end{array} 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 is 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.

The exact solution of the system is .

An example using Python and NumPy

The following iterative procedure produces the solution vector of a linear system of equations: import numpy as np ITERATION_LIMIT = 1000 initialize the matrix A = np.array( [ [10.0, -1.0, 2.0, 0.0], [-1.0, 11.0, -1.0, 3.0], [2.0, -1.0, 10.0, -1.0], [0.0, 3.0, -1.0, 8.0], ] ) initialize the RHS vector b = np.array([6.0, 25.0, -11.0, 15.0]) print("System of equations:") for i in range(A.shape[0]): row = " + ".join(f"{A[i, j]:3g}*x{j + 1}" for j in range(A.shape[1])) print(f"[{row}] = [{b[i]:3g}]") x = np.zeros_like(b) for it_count in range(1, ITERATION_LIMIT): x_new = np.zeros_like(x) print(f"Iteration {it_count}: {x}") for i in range(A.shape[0]): s1 = A[i, :i] @ x_new[:i] s2 = A[i, i + 1 :] @ x[i + 1 :] x_new[i] = (b[i] - s1 - s2) / A[i, i] if np.allclose(x, x_new, rtol=1e-8): break x = x_new print(f"Solution: {x}") error = A @ x - b print(f"Error: {error}") Produces the output: System of equations: [ 10*x1 + -1*x2 + 2*x3 + 0*x4] = [ 6] [ -1*x1 + 11*x2 + -1*x3 + 3*x4] = [ 25] [ 2*x1 + -1*x2 + 10*x3 + -1*x4] = [-11] [ 0*x1 + 3*x2 + -1*x3 + 8*x4] = [ 15] Iteration 1: [ 0. 0.

0. 0.]

Iteration 2: [ 0.6 2.32727273 -0.98727273 0.87886364] Iteration 3: [ 1.03018182 2.03693802 -1.0144562 0.98434122] Iteration 4: [ 1.00658504 2.00355502 -1.00252738 0.99835095] Iteration 5: [ 1.00086098 2.00029825 -1.00030728 0.99984975] Iteration 6: [ 1.00009128 2.00002134 -1.00003115 0.9999881 ] Iteration 7: [ 1.00000836 2.00000117 -1.00000275 0.99999922] Iteration 8: [ 1.00000067 2.00000002 -1.00000021 0.99999996] Iteration 9: [ 1.00000004 1.99999999 -1.00000001 1. ] Iteration 10: [ 1. 2. -1.

1.] Solution: [ 1. 2. -1.

1.] Error: [ 2.06480930e-08 -1.25551054e-08 3.61417563e-11 0.00000000e+00]

Program to solve arbitrary number of equations using Matlab

The following code uses the formula x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j i}a_{ij}x^{(k)}_j \right),\quad \begin{array}{l} i=1,2,\ldots,n \\ k=0,1,2,\ldots \end{array} function x = gauss_seidel(A, b, x, iters) for i = 1:iters for j = 1:size(A,1) x(j) = (b(j) - sum(A(j,:)'.*x) + A(j,j)*x(j)) / A(j,j); end end end

See also

Conjugate gradient method Gaussian belief propagation Iterative method: Linear systems Kaczmarz method (a "row-oriented" method, whereas Gauss-Seidel is "column-oriented". See, for example, this paper.) Matrix splitting Richardson iteration

References

. .

Gauss–Seidel from www.math-linux.com Gauss–Seidel From Holistic Numerical Methods Institute Gauss Siedel Iteration from www.geocities.com The Gauss-Seidel Method Bickson Matlab code C code example

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370485839 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.