Gauss Seidel Method – Algorithm, Implementation in C With Solved Examples


Numerical Methods & Algorithms / Thursday, October 18th, 2018

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 aii, 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  x1(0), x2(0),…, xn(0) for the variables x1, x2,…, xn respectively is considered. Substituting these values to the above system and get the first approximate value of x1, denoted by x1(1). Now, substituting x1(1) for x1 and x3(0), x4(0),…, xn(0) for x3, x4,…, xn respectively and we find x2(1) from second equation of the above system of equations, the first approximate value of x2. Then substituting x1(1), x2(1),…, xi-1(1), xi+1(1) ,…, xn(1) for x1, x2,…, xi-1, xi+1 ,…, xn to the ith equation of the above system of equations respectively and obtain xi(1) and so on.

If xi(k), i =1, 2 , …, n be the kth approximate value of xi, then the (k+ 1)th approximate value of x1, x2,…, xn 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 | xi(k+1) – xi(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 xni of xi 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 | xi – xni| < ϵ (ϵ is an error tolerance) for all i then go to Step 7 else set xi = xni for all i and go to Step 5.
Step 7. Print xni 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

 Example 01

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 |aij / aii| <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

n x1 x2 x3 x4
0 0.3000 1.5000 2.7000 -0.9000
1 0.7200 1.8240 2.7744 -0.0196
2 0.9403 1.9635 2.9864 -0.0125
3 0.9901 1.9954 2.9960 -0.0023
4 0.9984 1.9990 2.9993 -0.0004
5 0.9997 1.9998 2.9998 -0.0003
6 0.9998 1.9998 2.9998 -0.0003
7 1.0000 2.0000 3.0000  0.0000

Hence, x1 = 1.0, x2 = 2.0, x3 = 3.0, x4 = 0.0

Leave a Reply

Your email address will not be published. Required fields are marked *