Solving Linear equations by Lower Triangular & Forward Substitution
The Java program that wrote down, finds a solution vector for a system of linear equations which has N equations and N variables by Lower Triangular matrix and Forward Substitution method.
A system linear equations has a system matrix (coefficient matrix ), A and a non-homogeneous vector, b thereby, Augmented matrix A|b is formed to find solution vector for unknown variables of the system using lower triangular and forward substitution method.
Example for Lower Triangular & Forward substitution
The example shown below explains how to solve solution of linear system having 3 equations and 3 variables by lower triangular and forward substitution method.
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 R2 and R0 \[ \left[\begin{array}{rrr|r} 3.0 & 1.0 & -2.0 & 4.0 \\ 4.0 & 5.0 & 6.0 & 24.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \end{array} \right] \] R1<- -1.0R2+R1 \[ \left[\begin{array}{rrr|r} 3.0 & 1.0 & -2.0 & 4.0 \\ 2.0 & 1.0 & 0.0 & 6.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \end{array} \right] \] R0<- 0.3333R2+R0 \[ \left[\begin{array}{rrr|r} 3.66666 & 2.33333 & 0.0 & 10.0 \\ 2.0 & 1.0 & 0.0 & 6.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \end{array} \right] \] Swap rows R1 and R0 \[ \left[\begin{array}{rrr|r} 2.0 & 1.0 & 0.0 & 6.0 \\ 3.66666 & 2.33333 & 0.0 & 10.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \end{array} \right] \] R0-> -0.42857R1+R0 \[ \left[\begin{array}{rrr|r} 0.42857 & 0.0 & 0.0 & 1.71428 \\ 3.66666 & 2.33333 & 0.0 & 10.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \end{array} \right] \] Lower Triangular matrix \[ \left[\begin{array}{rrr|r} 0.42857 & 0.0 & 0.0 & 1.71428 \\ 3.66666 & 2.33333 & 0.0 & 10.0 \\ 2.0 & 4.0 & 6.0 & 18.0 \end{array} \right] \] forward substitution \[\begin{array}{c} 0.42857x+0.0y+0.0z=1.71428 \\ 3.66666x+2.33333y+0.0z=10 \\ 2.0x+4.0y+6.0z=18.0 \end{array} \] find x from equation 1 \( 0.42857x+0.0y+0.0z=1.71428 \) $$ 0.42857x =1.71428 $$ $$ x = {1.71428/0.42857}.$$ $$ x =3.9999 $$ find y from equation 2 \( 3.66666x+2.33333y+0.0z=10 \) and x=3.9999 $$ 3.66666x+2.33333y=10 $$ $$ 3.66666(3.9999)+2.33333y=10 $$ $$ 2.33333y=(10 - 14.6666)/2.3333 $$ $$ y =-1.9999 $$ find z from equation 3 \( 2.0x+4.0y+6.0z=18.0 \) and x=3.9999,y=-1.9999 $$ 2.0x+4.0y+6.0z=18.0 $$ $$ 2.0(3.999)+4.0(-1.999)+6.0z=18.0 $$ $$ 6.0z=18.0 -7.9998 + 7.9996 $$ $$ z=(18.0 - 0.0002)/6.0 $$ $$ z= 2.9999 $$ Solution vector of the Equations [x= 3.9999, y=-1.9999, z=2.9999]Java programming code - Lower Triangular & Forward Substitution
The Java program finds a solution vector for system of linear equations by two member functions they are,
- lower-triangular - it converts augmented matrix into lower triangular matrix by elementary row operations.
- forward-substitute - finds solution vector for unknown vector X by applying forward-substitution method (finds solution for variables from top to bottom manner).
The program constructor accepts two arguments, first argument a system matrix it must be a 2-D double array and second a non-homogeneous vector, it must be a 1-D double array.
import java.util.Arrays;
public classLinearequations {
Matrix mat;
public Linearequations(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=0;r<c;r++) {
if ( mat.getElement(r, c) > mx ) {
mx = mat.getElement(r, c);
mr = r;
}
}
return mr;
}
public void forwardsubsitute(int r,double sol[]) {
double val =0;
for (int c=0;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 Matrix lowertriangular() {
for(int c=mat.getNrow()-1;c>0;c--) {
int mr =this.maxpivot(mat,c);
if ( mr !=c )
RowOperation.swap(mat, c, mr);
for(int c2=c-1;c2>=0;c2--)
{
double ratio= mat.getElement(c2, c) / mat.getElement(c, c);
RowOperation.add(mat, c2, c, -ratio);
}
}
return mat;
}
public double[] solution()
{
double sol[]=new double[mat.getNrow()];
System.out.println("Augmented matrix :");
System.out.println(mat.toString());
this.lowertriangular();
System.out.println("Lower Triangular matrix :");
System.out.println(mat.toString());
for(int r=0;r<mat.getNrow();r++) {
forwardsubsitute(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};
Linearequations ge= new Linearequations(A,b);
double solution[]=ge.solution();
System.out.println("Solution of Equation :");
System.out.println(Arrays.toString(solution));
}
}
Java programming code output for solution of linear equations by lower triangular matrix
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 Lower Triangular matrix 0.42857 0.0 0.0 1.71428 3.66666 2.3333 0.0 10.0 2.0 4.0 6.0 18.0 Solution of Linear Equations [3.999999, -1.999999, 2.999999]
Comments
Post a Comment