Solving System of Linear Equation by Gaussian Elimination
Solving linear equation by matrix inverse method is difficult when a system has more than 3 equations and 3 unknown variables. hence, Gaussian elimination is preferred for solving system of linear equations, which has N linear equations and N unknown variables.
Gaussian elimination is performed by two steps. they,
- upper triangular matrix
- back substitution
System of Linear Equation by Gaussian Elimination - algorithm
Given - system of Linear equations
represents it in matrix form -:
A - coefficient matrix
X - unknown vector
b - non-homogeneous vector
form augmented matrix, A|b
convert augmented matrix, A|b into upper triangular matrix, U
by row operation
U = A|b
to get solution vector for X
apply back substitution on triangular matrix, U
Example for System of Linear Equation by Gaussian Elimination
Given System of Linear Equation \[\begin{array}{c} 2.0x+4.0y+6.0z=18 \\ 4.0x+5.0y+6.0z=24 \\ 3.0x+1y-2.0z=4 \end{array} \] Augmented matrix A|b \[ \left[\begin{array}{rrr|r} 2.0 & 4.0 & 6.0 & 18.0 \\ 4.0 & 5.0 & 6.0 & 24.0 \\ 3.0 & 1.0 & -2.0 & 4.0 \end{array} \right] \] Swap rows R0 and R1 \[ \left[\begin{array}{rrr|r} 4.0 & 5.0 & 6.0 & 24.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \\ 3.0 & 1.0 & -2.0 & 4.0 \end{array} \right] \] R1<- -0.5R0+R1 \[ \left[\begin{array}{rrr|r} 4.0 & 5.0 & 6.0 & 24.0 \\ 0.0 & 1.5 & 3.0 & 6.0 \\ 3.0 & 1.0 & -2.0 & 4.0 \end{array} \right] \] R2<- -0.75R0+R2 \[ \left[\begin{array}{rrr|r} 4.0 & 5.0 & 6.0 & 24.0 \\ 0.0 & 1.5 & 3.0 & 6.0 \\ 0.0 & -2.75 & -6.5 & -14.0 \end{array} \right] \] R2<- 1.833R1+R2 \[ \left[\begin{array}{rrr|r} 4.0 & 5.0 & 6.0 & 24.0 \\ 0.0 & 1.5 & 3.0 & 6.0 \\ 0.0 & 0.0 & -1.0 & -3.0 \end{array} \right] \] \[ \left[\begin{array}{rrr|r} 4.0 & 5.0 & 6.0 & 24.0 \\ 0.0 & 1.5 & 3.0 & 6.0 \\ 0.0 & 0.0 & -1.0 & -3.0 \end{array} \right] \]
Back substitution
\[\begin{array}{c} 4.0x+5.0y+6.0z=24 \\ 0.0x+1.5y+3.0z=6.0 \\ 0x+0y-1.0z=-3.0 \end{array} \] find z from equ 3 \( 0x+0y-1.0z=-3 \) $$-1.0z = -3.0 $$ $$z = {-3.0/-1.0}$$ $$z =3 $$ find y from equ 2 \( 0x+1.5y + 3.0z=6.0\) and z=3 $$1.5y+3.0z = 6.0. $$ $$1.5y + 3.0(3) =6.0 $$ $$y = (6.0 -9)/1.5 $$ $$y = -2 $$ find x from equ 1 \( 4.0x+5.0y+6.0z=24\) and z=3,y=-2 $$4.0x+5.0y+6.0z=24 $$ $$4.0x+5.0(-2)+6.0(3)=24 $$ $$4.0x =24 + 10 -18 $$ $$x = 16/4.0 = 4.0 $$ Solution of Equations [x=4.0, y=-2.0, z=3.0]Gaussian Elimination by Java programming
The Java program finds solution vector from system of linear equations using Gaussian elimination method. It has the following member functions by which the solution vector is found.
- GaussainElimiation - it is a constructors of the class, converts array of elements into augmented matrix.
- uppertriangular - it makes augmented matrix into upper triangular matrix using elementary matrix row operations.
- backsubsitute - it carry outs back substitution method on upper triangular matrix.
- soultion - it finds a solution vector for linear equations by comprising above member functions upper-triangular and back-substitute method.
import java.util.Arrays;
public class GaussianElimination {
Matrix mat;
public GaussianElimination(double A[][],double b[]) {
int row=A.length;
int col=A[0].length;
mat = new Matrix(row,col+1);
for(int r=0;r<row;r++) {
for(int c=0;c<col;c++)
mat.setElement(r, c, A[r][c]);
}
for(int r=0;r<row;r++)
mat.setElement(r, col, b[r]);
}
public int maxpivot(int c) {
int mr=c; double mx=0;
for(int r=c;r<mat.getNrow();r++)
{
if ( mat.getElement(r, c) > mx ) {
mx = mat.getElement(r, c);
mr = r;
}
}
return mr;
}
public void backsubsitute(int r,double sol[]) {
double val =0;
for(int c=mat.getNcol()-2;c>r;c--) {
val =val + sol[c] *mat.getElement(r, c);
}
val = mat.getElement(r, mat.getNcol()-1) - val;
sol[r] = val/mat.getElement(r, r);
}
public void uppertriangular() {
for(int r=0;r<mat.getNrow()-1;r++)
{
int mr = this.maxpivot(r);
if ( mr != r)
RowOperation.swap(mat, r, mr);
for(int r2=r+1;r2<mat.getNrow();r2++)
{
double ratio= mat.getElement(r2, r) / mat.getElement(r, r);
RowOperation.add(mat, r2, r, -ratio);
}
}
}
public double[] solution()
{
double sol[]=new double[mat.getNrow()];
System.out.println("Augmented matrix");
System.out.println(mat.toString());
this.uppertriangular();
System.out.println("Upper Triangular matrix");
System.out.println(mat.toString());
for(int r=mat.getNrow()-1;r>=0;r--) {
backsubsitute(r,sol) ;
}
return sol;
}
public static void main(String[] args) {
double A[][]= { {2,4,6},{4,5,6},{3,1,-2}};
double b[]= {18,24,4};
GaussianElimination ge= new GaussianElimination(A,b);
double solution[]=ge.solution();
System.out.println("Solution of Equation");
System.out.println(Arrays.toString(solution));
}
}
Gaussian Elimination Java programming Output
Augmented matrix 2.0 4.0 6.0 18.0 4.0 5.0 6.0 24.0 3.0 1.0 -2.0 4.0 Upper Triangular matrix 4.0 5.0 6.0 24.0 0.0 1.5 3.0 6.0 0.0 0.0 -1.0 -3.0 Solution of System of Linear Equation [4.0, -2.0, 3.0]
Comments
Post a Comment