Gauss Elimination method
Gauss elimination method (also called row reduction method) named after German physicist and mathematician
Carl Friedrich Gauss is a direct method to find the solution to a system of simultaneous
linear equations. In this method the system of equations is reduced to a upper-triangular system. The solutions can be obtained from the upper-triangular system by back-substitution.
Let there be a system of `n` linear equations in `n` variables given by:
`a_11x_1+a_12x_2+* * * +a_(1n)x_n=b_1`
`a_21x_1+a_22x_2+* * * +a_(2n)x_n=b_2`
`a_31x_1+a_32x_2+* * * +a_(3n)x_n=b_3`
`vdots` ` vdots` ` vdots` ` vdots`
`a_(n1)x_1+a_(n2)x_2+* * * +a_(n n)x_n=b_n`
The corresponding `n xx (n+1)` augmented matrix is given by:
` A=[[a_11,a_12,* * *,a_(1n),|,b_1],
[a_21,a_22,* * *,a_(2n),|,b_2],
[vdots,vdots,ddots,vdots,|,vdots],
[a_(n1),a_(n2),* * *,a_(n n),|,b_n]]`
Row operations are performed on the augmented matrix to reduce the coefficint matrix into upper-triangular form.
In the process we go on eliminating the unknowns systematically so that the last row has only one unknown with non-zero coefficient.
At first, we shall eliminate the coefficients of `x_1` in all of the rows except the first. To achieve this, we perform the
following row operations on all the rows except the first row.
`R_j-(a_(j1)/a_11)R_1 rightarrow R_j`
for each `j = 2,3,* * *,n`.
The above operations can be performed only if `a_11 != 0`.
Now, the coeffient of `x_1` in all the rows except in the first is zero as shown below. All the coefficients from second row onwards are modefied (denoted by superscript(1)) due to the above row operations, for instance, `a_22^((1))=a_(22)-(a_(21)/a_11)a_12`.
`A=[[a_11,a_12,* * *,a_(1n),|,b_1],
[0,a_22^((1)),* * *,a_(2n)^((1)),|,b_2^((1))],
[vdots,vdots,ddots,vdots,|,vdots],
[0,a_(n2)^((1)),* * *,a_(n n)^((1)),|,b_n^((1))]]`
We apply same procedure to eliminate the coefficients of the `i^{th}` variable from `(i+1)^(th)` to `n^(th)` row, provided `a_(ii)!=0`. We go on repeating the process until we get the following matrix.
`A'=[[a_11,a_12,* * ,* *,a_(1n),|,b_1],
[0,a_22^',* *,* *,a_(2n)^',|,b_2^'],
[vdots,vdots,ddots,vdots,vdots,|,vdots],
[0,0,0,ddots,vdots,|,vdots],
[0,0,0,0,a_(n n)^',|,b_n^']]`
The matrix`A^'` represents a linear system with the same solutions as the original system. The new system is given by:
$$
\begin{align}
a_{11}x_1+a_{12}x_2+... +a_{1n}x_n&=b_1 \\
a_{22}x_2+... +a_{2n}x_n&=b_2 \\
\ddots \hspace{15pt}\quad \vdots \quad &\hspace{15pt} \vdots\\
a_{nn}x_n &= b_n
\end{align}
$$
We can now solve the `n^(th)` equation in the above system to get:
$$
x_n=\frac{b_{n}}{a_{nn}}
$$
which can be substituted in the `(n-1)^(th)` equation to get `x_(n-1)`, and so on.
Program in C
=======================================================================
Program to solve a system of linear algebraic equations using
GAUSS ELIMINATION METHOD (Without Pivoting)
Language : C
Compiler : GNU GCC Compiler
=======================================================================
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int n;
printf("Enter the number of variables: ");
scanf("%d",&n);
float a[n][n+1]; //The augmented matrix
float x[n]; //The unknowns/solutions
int i,j,k;
float multiplier;
printf("\nEnter the augmented matrix:\n");
for (i = 0;i<n;i++){
for (j = 0;j<n+1;j++){
scanf("%f",&a[i][j]); //reading the matrix
}
}
printf("\n");
//------------ to get upper triangular matrix -------------------|
for (k = 0;k<n-1;k++){
for (i=k+1; i<n; i++){
multiplier = a[i][k]/a[k][k];
for (j=0; j<n+1; j++){
a[i][j] = a[i][j] - a[k][j]*multiplier;
}
}
}
//-------------- Printing the upper triangular matrix -----------|
printf("\nupper triangular\n");
for (i = 0;i<n;i++){
for (j = 0;j<n+1;j++){
printf("\t%f",a[i][j]);
}
printf("\n");
}
// -------------------Finding the Solutions----------------------|
for (i=n-1; i<=0; i--){
x[i] = a[i][n];
for (j=n-1; j>i; j--){
x[i] = x[i] - a[i][j]*x[j];
}
x[i] = x[i]/a[i][i];
}
// -------------------Printing the Solutions---------------------|
printf("\nThe Solutions are:\n");
for (j = 0;j<n;j++){
printf("\t x%d = %f",j+1,x[j]);
}
return 0;
}
-------------------------------OUTPUT------------------------------
Enter the number of variables: 3
Enter the augmented matrix:
1 1 1 9
7 -5 4 9
2 3 8 10
The upper triangular matrix:
1.000000 1.000000 1.000000 9.000000
0.000000 -12.000000 -3.000000 -54.000000
0.000000 0.000000 5.750000 -12.500000
The Solutions are:
x1 = 6.130435 x2 = 5.043478 x3 = -2.173913
-------------------------------------------------------------------
Program in Fortran 95
======================================================================
Program to solve a system of linear algebraic equations using
GAUSS ELIMINATION METHOD (Without Pivoting)
Language : Fortran 95
Compiler : GNU Fortran
!======================================================================
PROGRAM gaussElimination
IMPLICIT NONE
INTEGER :: n,i,j,k
REAL,ALLOCATABLE :: a(:,:),x(:) !The augmented matrix 'a' and the solutions x
REAL multiplier
WRITE(*,*)'Enter the number of variables'
READ(*,*)n
ALLOCATE (a(n,n+1))
ALLOCATE (x(n))
WRITE(*,*)'Enter the augmented matrix:'
DO i=1,n
READ(*,*)(a(i,j),j=1,n+1) !reading the matrix
END DO
!!------------ to get upper triangular matrix -------------------|
DO k = 1,n-1
DO i=k+1,n
multiplier = a(i,k) / a(k,k)
DO j=1,n+1
a(i,j) = a(i,j) - a(k,j)*multiplier
END DO
END DO
END DO
!!-------------- Printing the upper triangular matrix -----------|
WRITE(*,'(/)')
WRITE(*,*)'The upper triangular matrix:'
DO i = 1,n
WRITE(*,'(*(2X,F10.6))')(a(i,j),j=1,n+1)
END DO
!! -------------------Finding the Solutions----------------------|
DO i=n,1,-1
x(i) = a(i,n+1)
DO j=n,i+1,-1
x(i) = x(i) - a(i,j)*x(j)
END DO
x(i) = x(i)/ a(i,i)
END DO
!! -------------------Printing the Solutions---------------------|
WRITE(*,'(/)')
WRITE(*,*)'The Solutions are:'
DO j = 1,n
WRITE(*,'(2X,A1,I1,A1,F10.6,2X)')'x',j,'=',x(j)
END DO
END PROGRAM
=================== OUTPUT =====================
Enter the number of variables
3
Enter the augmented matrix:
1 1 1 9
7 -5 4 9
2 3 8 10
The upper triangular matrix:
1.000000 1.000000 1.000000 9.000000
0.000000 -12.000000 -3.000000 -54.000000
0.000000 -0.000000 5.750000 -12.500000
The Solutions are:
x1= 6.130435
x2= 5.043478
x3= -2.173913
-----------------------------------------------
Gauss elimination method (also called row reduction method) named after German physicist and mathematician Carl Friedrich Gauss is a direct method to find the solution to a system of simultaneous linear equations. In this method the system of equations is reduced to a upper-triangular system. The solutions can be obtained from the upper-triangular system by back-substitution.
Let there be a system of `n` linear equations in `n` variables given by:
`a_11x_1+a_12x_2+* * * +a_(1n)x_n=b_1`
`a_21x_1+a_22x_2+* * * +a_(2n)x_n=b_2`
`a_31x_1+a_32x_2+* * * +a_(3n)x_n=b_3`
`vdots` ` vdots` ` vdots` ` vdots`
`a_(n1)x_1+a_(n2)x_2+* * * +a_(n n)x_n=b_n`
The corresponding `n xx (n+1)` augmented matrix is given by:
` A=[[a_11,a_12,* * *,a_(1n),|,b_1], [a_21,a_22,* * *,a_(2n),|,b_2], [vdots,vdots,ddots,vdots,|,vdots], [a_(n1),a_(n2),* * *,a_(n n),|,b_n]]`
Row operations are performed on the augmented matrix to reduce the coefficint matrix into upper-triangular form. In the process we go on eliminating the unknowns systematically so that the last row has only one unknown with non-zero coefficient.
At first, we shall eliminate the coefficients of `x_1` in all of the rows except the first. To achieve this, we perform the following row operations on all the rows except the first row.
`R_j-(a_(j1)/a_11)R_1 rightarrow R_j`
for each `j = 2,3,* * *,n`.
The above operations can be performed only if `a_11 != 0`. Now, the coeffient of `x_1` in all the rows except in the first is zero as shown below. All the coefficients from second row onwards are modefied (denoted by superscript(1)) due to the above row operations, for instance, `a_22^((1))=a_(22)-(a_(21)/a_11)a_12`.
`A=[[a_11,a_12,* * *,a_(1n),|,b_1], [0,a_22^((1)),* * *,a_(2n)^((1)),|,b_2^((1))], [vdots,vdots,ddots,vdots,|,vdots], [0,a_(n2)^((1)),* * *,a_(n n)^((1)),|,b_n^((1))]]`
We apply same procedure to eliminate the coefficients of the `i^{th}` variable from `(i+1)^(th)` to `n^(th)` row, provided `a_(ii)!=0`. We go on repeating the process until we get the following matrix.
`A'=[[a_11,a_12,* * ,* *,a_(1n),|,b_1], [0,a_22^',* *,* *,a_(2n)^',|,b_2^'], [vdots,vdots,ddots,vdots,vdots,|,vdots], [0,0,0,ddots,vdots,|,vdots], [0,0,0,0,a_(n n)^',|,b_n^']]`
The matrix`A^'` represents a linear system with the same solutions as the original system. The new system is given by:
$$ \begin{align} a_{11}x_1+a_{12}x_2+... +a_{1n}x_n&=b_1 \\ a_{22}x_2+... +a_{2n}x_n&=b_2 \\ \ddots \hspace{15pt}\quad \vdots \quad &\hspace{15pt} \vdots\\ a_{nn}x_n &= b_n \end{align} $$
We can now solve the `n^(th)` equation in the above system to get: $$ x_n=\frac{b_{n}}{a_{nn}} $$ which can be substituted in the `(n-1)^(th)` equation to get `x_(n-1)`, and so on.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int n;
printf("Enter the number of variables: ");
scanf("%d",&n);
float a[n][n+1]; //The augmented matrix
float x[n]; //The unknowns/solutions
int i,j,k;
float multiplier;
printf("\nEnter the augmented matrix:\n");
for (i = 0;i<n;i++){
for (j = 0;j<n+1;j++){
scanf("%f",&a[i][j]); //reading the matrix
}
}
printf("\n");
//------------ to get upper triangular matrix -------------------|
for (k = 0;k<n-1;k++){
for (i=k+1; i<n; i++){
multiplier = a[i][k]/a[k][k];
for (j=0; j<n+1; j++){
a[i][j] = a[i][j] - a[k][j]*multiplier;
}
}
}
//-------------- Printing the upper triangular matrix -----------|
printf("\nupper triangular\n");
for (i = 0;i<n;i++){
for (j = 0;j<n+1;j++){
printf("\t%f",a[i][j]);
}
printf("\n");
}
// -------------------Finding the Solutions----------------------|
for (i=n-1; i<=0; i--){
x[i] = a[i][n];
for (j=n-1; j>i; j--){
x[i] = x[i] - a[i][j]*x[j];
}
x[i] = x[i]/a[i][i];
}
// -------------------Printing the Solutions---------------------|
printf("\nThe Solutions are:\n");
for (j = 0;j<n;j++){
printf("\t x%d = %f",j+1,x[j]);
}
return 0;
}
-------------------------------OUTPUT------------------------------
Enter the number of variables: 3
Enter the augmented matrix:
1 1 1 9
7 -5 4 9
2 3 8 10
The upper triangular matrix:
1.000000 1.000000 1.000000 9.000000
0.000000 -12.000000 -3.000000 -54.000000
0.000000 0.000000 5.750000 -12.500000
The Solutions are:
x1 = 6.130435 x2 = 5.043478 x3 = -2.173913
-------------------------------------------------------------------
PROGRAM gaussElimination
IMPLICIT NONE
INTEGER :: n,i,j,k
REAL,ALLOCATABLE :: a(:,:),x(:) !The augmented matrix 'a' and the solutions x
REAL multiplier
WRITE(*,*)'Enter the number of variables'
READ(*,*)n
ALLOCATE (a(n,n+1))
ALLOCATE (x(n))
WRITE(*,*)'Enter the augmented matrix:'
DO i=1,n
READ(*,*)(a(i,j),j=1,n+1) !reading the matrix
END DO
!!------------ to get upper triangular matrix -------------------|
DO k = 1,n-1
DO i=k+1,n
multiplier = a(i,k) / a(k,k)
DO j=1,n+1
a(i,j) = a(i,j) - a(k,j)*multiplier
END DO
END DO
END DO
!!-------------- Printing the upper triangular matrix -----------|
WRITE(*,'(/)')
WRITE(*,*)'The upper triangular matrix:'
DO i = 1,n
WRITE(*,'(*(2X,F10.6))')(a(i,j),j=1,n+1)
END DO
!! -------------------Finding the Solutions----------------------|
DO i=n,1,-1
x(i) = a(i,n+1)
DO j=n,i+1,-1
x(i) = x(i) - a(i,j)*x(j)
END DO
x(i) = x(i)/ a(i,i)
END DO
!! -------------------Printing the Solutions---------------------|
WRITE(*,'(/)')
WRITE(*,*)'The Solutions are:'
DO j = 1,n
WRITE(*,'(2X,A1,I1,A1,F10.6,2X)')'x',j,'=',x(j)
END DO
END PROGRAM
=================== OUTPUT =====================
Enter the number of variables
3
Enter the augmented matrix:
1 1 1 9
7 -5 4 9
2 3 8 10
The upper triangular matrix:
1.000000 1.000000 1.000000 9.000000
0.000000 -12.000000 -3.000000 -54.000000
0.000000 -0.000000 5.750000 -12.500000
The Solutions are:
x1= 6.130435
x2= 5.043478
x3= -2.173913
-----------------------------------------------