Gauss Seidel Iteration Method

A simple modification of Jocobi’s iteration sometimes gives faster convergence, the modified method is known as Gauss Seidel method.
Let us consider a system of n linear equations with n variables
\[{{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+….+{{a}_{1n}}{{x}_{n}}={{b}_{1}}\]
\[{{a}_{21}}{{x}_{1}}+{{a}_{22}}{{x}_{2}}+….+{{a}_{2n}}{{x}_{n}}={{b}_{2}}\]
\[………………………………………\]
\[{{a}_{n1}}{{x}_{1}}+{{a}_{n2}}{{x}_{2}}+….+{{a}_{nn}}{{x}_{n}}={{b}_{n}}\]
Assume that the diagonal coefficients a_ii, i = 1, 2, …, n are diagonally dominant. If this is not the case then the above system of equations are rearranged in such a way that the above condition holds.
The equation are rewritten in the following form:
\[{{x}_{1}}=\frac{1}{{{a}_{11}}}\left( {{b}_{1}}-{{a}_{12}}{{x}_{2}}-{{a}_{13}}{{x}_{3}}-….-{{a}_{1n}}{{x}_{n}} \right)\]
\[{{x}_{2}}=\frac{1}{{{a}_{22}}}\left( {{b}_{2}}-{{a}_{21}}{{x}_{1}}-{{a}_{23}}{{x}_{3}}-….-{{a}_{2n}}{{x}_{n}} \right)\]
\[…………………………………………………….\]
\[{{x}_{n}}=\frac{1}{{{a}_{nn}}}\left( {{b}_{n}}-{{a}_{n1}}{{x}_{1}}-{{a}_{n2}}{{x}_{2}}-….-{{a}_{nn-1}}{{x}_{n-1}} \right)\]
To solve these equations an initial approximation  x₁⁽⁰⁾, x₂⁽⁰⁾,…, x_n⁽⁰⁾ for the variables x₁, x₂,…, x_n respectively is considered. Substituting these values to the above system and get the first approximate value of x₁, denoted by x₁⁽¹⁾. Now, substituting x₁⁽¹⁾ for x1 and x₃⁽⁰⁾, x₄⁽⁰⁾,…, x_n⁽⁰⁾ for x₃, x₄,…, x_n respectively and we find x₂⁽¹⁾ from second equation of the above system of equations, the first approximate value of x₂. Then substituting x₁⁽¹⁾, x₂⁽¹⁾,…, x_i-1⁽¹⁾, x_i+1⁽¹⁾ ,…, x_n⁽¹⁾ for x₁, x₂,…, x_i-1, x_i+1 ,…, x_n to the ith equation of the above system of equations respectively and obtain x_i⁽¹⁾ and so on.

If x_i^(k), i =1, 2 , …, n be the kth approximate value of xi, then the (k+ 1)th approximate value of x₁, x₂,…, x_n are given by
\[{{x}_{1}}^{\left( k+1 \right)}=\frac{1}{{{a}_{11}}}\left( {{b}_{1}}-{{a}_{12}}{{x}_{2}}^{\left( k \right)}-{{a}_{13}}{{x}_{3}}^{\left( k \right)}-….-{{a}_{1n}}{{x}_{n}}^{\left( k \right)} \right)\]
\[{{x}_{2}}^{\left( k+1 \right)}=\frac{1}{{{a}_{22}}}\left( {{b}_{2}}-{{a}_{21}}{{x}_{1}}^{\left( k \right)}-{{a}_{23}}{{x}_{3}}^{\left( k \right)}-….-{{a}_{2n}}{{x}_{n}}^{\left( k \right)} \right)\]
\[…………………………………………………….\]
\[{{x}_{n}}^{\left( k+1 \right)}=\frac{1}{{{a}_{nn}}}\left( {{b}_{n}}-{{a}_{n1}}{{x}_{1}}^{\left( k \right)}-{{a}_{n2}}{{x}_{2}}^{\left( k \right)}-….-{{a}_{nn-1}}{{x}_{n-1}}^{\left( k \right)} \right)\]
\[\text{Where},k=0,1,2,…\]
That is,
\[{{x}_{i}}^{\left( k+1 \right)}=\frac{1}{{{a}_{ii}}}\left( {{b}_{i}}-\sum\limits_{j=1}^{i-1}{{{a}_{ij}}{{x}_{j}}^{\left( k+1 \right)}-\sum\limits_{j=i+1}^{n}{{{a}_{ij}}{{x}_{j}}^{\left( k \right)}}} \right)\]
The method is repeated until | x_i^(k+1) – x_i^(k)| < ϵ for all i = 1, 2, …, n, where ϵ > 0 is any pre-assigned number called the error tolerance. This method is called Gauss-Seidel iteration method.

Algorithm of Gauss Seidel Method

Step 1. Read the coefficients aij, i,j = 1, 2, …., n and the right hand vector bi, i = 1, 2, …, n of the system of equations and error tolerance ϵ.
Step 2. Rearrange the given equations, if possible, such that the system becomes diagonally dominant.
Step 3. Rewrite the ith equation as
\[{{x}_{i}}=\frac{1}{{{a}_{ii}}}\left( {{b}_{i}}-\sum\limits_{j<i}{{{a}_{ij}}{{x}_{j}}-\sum\limits_{j>i}{{{a}_{ij}}{{x}_{j}}}} \right)for~~i=1,2,…,n.\]
Step 4. Set the initial solution as
\[{{x}_{i}}=0,~~~i=1,2,3,…,n\]
Step 5. Calculate the new values x_ni of x_i as
\[{{x}_{{{n}_{i}}}}=\frac{1}{{{a}_{ii}}}\left( {{b}_{i}}-\sum\limits_{j<i}{{{a}_{ij}}{{x}_{{{n}_{j}}}}-\sum\limits_{j>i}{{{a}_{ij}}{{x}_{j}}}} \right)for~~i=1,2,…,n.\]
Step 6. If | x_i – x_ni| < ϵ (ϵ is an error tolerance) for all i then go to Step 7 else set x_i = x_ni for all i and go to Step 5.
Step 7. Print x_ni for i = 1, 2, 3, …, n as solution.

Implementation of Gauss-Seidel’s Iteration method in C

/* Program Gauss-Seidel
   Solution of a system of linear equations by Gauss-Seidel's
   iteration method. Assume that the coefficient matrix satisfies
   the condition of convergence.*/

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

void main()
{
	float a[10][10],b[10],x[10],xn[10],epp=0.00001,sum;
	int i,j,n,flag;

	printf("Enter number of variables: ");
	scanf("%d",&n);
	printf("Enter the coefficients row-wise: ");
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%f",&a[i][j]);
	printf("Enter right hand vectors: ");
	for(i=0;i<n;i++)
		scanf("%f",&b[i]);
	for(i=0;i<n;i++)
		x[i]=0; //initialize

	/* testing of diagonal dominance may be included here from 
	   the program of Gauss-Jacobi's method */
	do{
		for(i=0;i<n;i++)
		{
			sum=b[i];
			for(j=0;j<n;j++)
			{
				if(j<i)
					sum-=a[i][j]*xn[j];
				else if(j>i)
					sum-=a[i][j]*x[j];
				xn[i]=sum/a[i][j];
			}
		}
		flag=0; // indicates |x[i]-xn[i]|<epp for all i
		for(i=0;i<n;i++)
			if(fabs(x[i]-xn[i])>epp)
				flag=1;
		if(flag==1)
			for(i=0;i<n;i++)
				x[i]=xn[i]; // reset x[i]			
	}while(flag==1);
	printf("Solution is \n");
	for(i=0;i<n;i++)
		printf("%8.5f ",xn[i]);
}

Output
Enter number of variables 3

Enter the coefficients row-wise
3            1            -1

2            5            2

2            4            6

Enter right hand vectors
7            9            8

Solution is
2.00000              1.00000              0.00000

Solve by Gauss-Seidel iteration method
\[10{{x}_{1}}-2{{x}_{2}}-{{x}_{3}}-{{x}_{4}}=3\]
\[-2{{x}_{1}}+10{{x}_{2}}-{{x}_{3}}-{{x}_{4}}=15\]
\[-{{x}_{1}}-{{x}_{2}}+10{{x}_{3}}-2{{x}_{4}}=27\]
\[-{{x}_{1}}-{{x}_{2}}-2{{x}_{3}}+10{{x}_{4}}=-9\]
Solution:
Since |a_ij / a_ii| <1 for all i, hence the above equations can be solved by Gauss-Seidel iterative method.
The above equations can be rewritten as:
\[{{x}_{1}}=0.3+0.2{{x}_{2}}+0.1{{x}_{3}}+0.1{{x}_{4}}\]
\[{{x}_{2}}=1.5+0.2{{x}_{1}}+0.1{{x}_{3}}+0.1{{x}_{4}}\]
\[{{x}_{3}}=2.7+0.1{{x}_{1}}+0.1{{x}_{2}}+0.2{{x}_{4}}\]
\[{{x}_{4}}=-0.9+0.1{{x}_{1}}+0.1{{x}_{2}}+0.2{{x}_{3}}\]

For the zeroth approximation, we get
Applying the Gauss-Seidel process, we successively get

Hence, x₁ = 1.0, x₂ = 2.0, x₃ = 3.0, x₄ = 0.0

<< Previous     Next>>

;