To find the solution of system of linear equations, in this article we will discuss Gauss-Jacobi’s iteration method.

Solution of System of Linear Equations

Generally, two types of methods are used to solve a system of linear equations, viz., direct and iteration. If the system of equations has a large number of variables, then the direct methods are not much suitable. In this case, the approximate numerical methods are used to determine the variables to the system.
The approximate methods for solving system of linear equation make it possible to obtain the values of the roots of the system with the specified accuracy as the limit of the sequence of some vectors. The process of constructing such a sequence is known as the iterative process.
The efficiency of the application of approximate methods depends on the choice of the initial vector and the rate of convergence of the process.

Gauss-Jacobi’s Iteration Method

Let us consider a system of n linear equations containing 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}}\]
Also, we assume that the quantities a_ii are pivot elements.
The above equations can be rewritten as:
\[{{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)\]
Let x₁⁽⁰⁾, x₂⁽⁰⁾,…, x_n⁽⁰⁾ be the initial guess to the variables x₁, x₂,…, x_n respectively (initial guess may be taken as zeros). Substituting these values in the right hand side of the above equation, this yields the first approximation as follows:
\[{{x}_{1}}^{\left( 1 \right)}=\frac{1}{{{a}_{11}}}\left( {{b}_{1}}-{{a}_{12}}{{x}_{2}}^{\left( 0 \right)}-{{a}_{13}}{{x}_{3}}^{\left( 0 \right)}-….-{{a}_{1n}}{{x}_{n}}^{\left( 0 \right)} \right)\]
\[{{x}_{2}}^{\left( 1 \right)}=\frac{1}{{{a}_{22}}}\left( {{b}_{2}}-{{a}_{21}}{{x}_{1}}^{\left( 0 \right)}-{{a}_{23}}{{x}_{3}}^{\left( 0 \right)}-….-{{a}_{2n}}{{x}_{n}}^{\left( 0 \right)} \right)\]
\[…………………………………………………….\]
\[{{x}_{n}}^{\left( 1 \right)}=\frac{1}{{{a}_{nn}}}\left( {{b}_{n}}-{{a}_{n1}}{{x}_{1}}^{\left( 0 \right)}-{{a}_{n2}}{{x}_{2}}^{\left( 0 \right)}-….-{{a}_{nn-1}}{{x}_{n-1}}^{\left( 0 \right)} \right)\]
Again, substituting x₁⁽¹⁾, x₂⁽¹⁾,…, x_n⁽¹⁾ in the right hand side of the equation we obtain the second approximation x₁⁽²⁾, x₂⁽²⁾,…, x_n⁽²⁾.
In general, if x₁^(k), x₂^(k),…, x_n^(k) be the kth approximate root then the next approximate roots 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,…\]
The iteration process is continued until all the roots converge to the required number of significant figures. This iteration method is called Jocobi’s iteration or simply the method of iteration.
The Jocobi’s iteration method surely converges if the coefficient matrix is diagonally dominant.
In Gauss-Jacobi’s iteration method will terminate when | x_i^(k+1) – x_i^(k)| < ϵ, where ϵ is the supplied error tolerance, for all i.

Algorithm of Gauss-Jacobi’s Iteration 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=1,j\ne i}^{n}{{{a}_{ij}}{{x}_{j}}} \right)for~i=1,2,….,n\]
Step 4. Set the initial solution as
\[{{x}_{i}}=0,~i=1,2,….,n\]
Step 5. Calculate the new value x_i⁽ⁿ⁾ of x_i as
\[{{x}_{i}}^{(n)}=\frac{1}{{{a}_{ii}}}\left( {{b}_{i}}-\sum\limits_{j=1,j\ne i}^{n}{{{a}_{ij}}{{x}_{j}}} \right)for~i=1,2,….,n\]
Step 6. If | x_i – x_i⁽ⁿ⁾| < ϵ for all i, then goto Step 7 else x_i = x_i⁽ⁿ⁾ for all i and goto step 5.
Step 7. Print x_i⁽ⁿ⁾ , i = 1, 2, …, n as solution.

Implementation of Gauss-Jacobi’s Iteration method in C

/* Program Gauss_Jacobi
   Solution of a system of linear equations by Gauss-Jacobi's iteration
   method. Testing of diagonal dominance is also incorporated */

#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("\nEnter number of variables: ");
	scanf("%d",&n);
	printf("\nEnter the coefficients row-wise: ");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			scanf("%f",&a[i][j]);
		}
	}
	printf("\nEnter right hand vector: ");
	for(i=0;i<n;i++)
		scanf("%f",&b[i]);
	for(i=0;i<n;i++)
		x[i]=0; //initialize

	//checking for row dominance
	flag=0;
	for(i=0;i<n;i++)
	{
		sum=0;
		for(j=0;j<n;j++)
			if(i!=j)
				sum+=fabs(a[i][j]);
			if(sum>fabs(a[i][i]))
				flag=1;
	}

	//checking for column dominance
	if(flag==1)
		flag=0;
	for(j=1;j<n;j++)
	{
		sum=0;
		for(i=1;i<n;i++)
			if(i!=j)
				sum+=fabs(a[i][j]);
			if(sum>fabs(a[j][j]))
				flag=1;
	}

	if(flag==1)
	{
		printf("The coefficient matrix is not diagonally dominant \n");
		printf("The Gauss-Jacobi method does not converge surely");
		exit(0);
	}

	for(i=0;i<n;i++)
		printf(" x[%d] ",i);
	printf("\n");

	do
	{
		for(i=0;i<n;i++)
		{
			sum=b[i];
			for(j=0;j<n;j++)
				if(j!=i)
					sum-=a[i][j]*x[j];
				xn[i]=sum/a[i][i];
		}
		for(i=0;i<n;i++)
			printf("%8.5f ",xn[i]);
		printf("\n");
		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=1;i<n;i++)
				x[i]=xn[i]; //reset x[i]	

	}while(flag==1);

	printf("Solutoin is \n");
	for(i=0;i<n;i++)
		printf("%8.5f ",xn[i]);
}

Output

Enter number of variables 3
Enter the coefficients row-wise
9            2            4
1            10          4
2            -4           10

Enter right hand vector
20          6            -15

x[1]                     x[2]                     x[3]
2.22222              0.60000              -1.50000
2.75556              0.97778              -1.70444
2.76247              1.00622              -1.66000
2.73640              0.98775              -1.65000
2.73606              0.98636              -1.65218
2.73733              0.98727              -1.65267
2.73735              0.98733              -1.65256
2.73729              0.98729              -1.65254
2.73729              0.98729              -1.65254

Solution is
2.73729   0.98729   -1.65254

Using Gauss-Jacobi iteration method, find the solutions of the equations
\[8{{x}_{1}}-3{{x}_{2}}+2{{x}_{3}}=20\]
\[6{{x}_{1}}+3{{x}_{2}}+12{{x}_{3}}=35\]
\[4{{x}_{1}}+11{{x}_{2}}-{{x}_{3}}=33\]

Solution:

Here the coefficient matrix is

And so |a₂₁|=6, |a₂₂|=3, |a₂₃|=12 showing that |a₂₂| < |a₂₁| +|a₂₃|. Thus the given system is not diagonally dominant. We, therefore, rearrange the system as
\[8{{x}_{1}}-3{{x}_{2}}+2{{x}_{3}}=20\]
\[4{{x}_{1}}+11{{x}_{2}}-{{x}_{3}}=33\]
\[6{{x}_{1}}+3{{x}_{2}}+12{{x}_{3}}=35\]
Obviously, the above system is diagonally dominant. We rewrite the system in the form
\[{{x}_{1}}=\frac{1}{8}\left( 20+3{{x}_{2}}-2{{x}_{3}} \right)\]
\[{{x}_{2}}=\frac{1}{11}\left( 33-4{{x}_{1}}+{{x}_{3}} \right)\]
\[{{x}_{3}}=\frac{1}{12}\left( 35-6{{x}_{1}}-3{{x}_{2}} \right)\]
And choose the initial approximation x₁⁽⁰⁾ = x₂⁽⁰⁾ = x₃⁽⁰⁾ =0. Substituting these on the right hand side of the above equations, the first approximation to the solutions are
\[{{x}_{1}}=\frac{1}{8}\left( 20+3.0-2.0 \right)=2.5\]
\[{{x}_{2}}=\frac{1}{11}\left( 33-4.0+0 \right)=3\]
\[{{x}_{3}}=\frac{1}{12}\left( 35-6.0-3.0 \right)=2.916667\]
Proceeding in this way, the successive iterations are given in the following table:

Thus the solutions of the given system, correct to three decimal places are x₁ = 3.016, x₂ = 1.988, x₃ = 0.915.

<< Previous     Next>>

;