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 R₂ and R₀ \[ \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] \] R₁<- -1.0R₂+R₁ \[ \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] \] R₀<- 0.3333R₂+R₀ \[ \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 R₁ and R₀ \[ \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] \] R₀-> -0.42857R₁+R₀ \[ \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,

1. lower-triangular - it converts augmented matrix into lower triangular matrix by elementary row operations.


2. 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]