mathajax

Matrix Forward and Back Substitution

A square matrix is transformed into a Lower triangular matrix L or an Upper triangular matrix U by applying elementary row operation (Gaussian elimination) for solving system linear of equations.

A solution vector X of system of linear equations is obtained by applying substitution method.

  • The forward substitution method is applied to matrix L
  • The back substitution method is applied to matrix U

lower triangular forward substitution

Algorithm steps for forward substitution to matrix L

       Input : a square matrix, A
        a non-homogeneous vector b    
       Output : Solution vector, X 
  
   read matrix A
   read vector b
   L = transform_to_L(A,b)
   X = substitute-forward(L);
  

Example of forward substitution to matrix L

substitute unknown variables top to bottom approach

           0.4286x                  = 1.7143
           3.6667x  + 2.3334y       = 10.0
           2.0x+    + 4.0y   + 6.0z = 18.0

    find x,  from equation 1     
              0.4286x   = 1.7143
              x = 1.7143/0.4286
              x = 3.999

     substitute x = 20.998 in equation 2
           3.6667(3.999)  + 2.3334y  = 10.0  
                             2.3334y  = 10.0 - 14.665
                             y = -1.9996

     substitute x = 3.999,y=-1.9996 in equation 3  
            2.0(3.999)+    + 4.0(-1.9996)   + 6.0z = 18
              7.9992    -  7.9984  + 6.0z  =  18
                                     6.0z  = 18 - 0.0008
                                     z =  17.9992 / 6 
                                     z = 2.999  

     solution vector x=3.999,y=-1.9996,z=2.999 
    

Algorithm steps for back substitution to matrix U

    Input -  a square matrix A 
             a non-homogeneous vector b     
    Output - solution vector X 

         read matrix A
         read vector b
  
         U = transform_to_U(A,b)
         X = substitute-back(U);
 

Example of back substitution to matrix U

substitute unknown variables from bottom to top approach

                    
           1.0x + 2.0y + 3.0z  = 9
                  1.0y + 2.0z  = 4
                        + 1.0z = 3

  find z,  from equation 3     
       1.0z = 3 
          z = 3

   find y, substitute z = 3 in equation 2
           1.0y + 2.0(3) =4
           1.0y = 4-6 
              y = -2      
   
  find x, substitute z=3, y=-2 in equation 1
               1.0x + 2.0(-2) + 3.0(3) = 9
               1.0x - 4 +  9  = 9   
               x = 4   
   solution vector x=4,y=-2,z=4  
  


Java programming code - Forward and Backward Substitution

 
import java.util.Arrays;
public class Substitution {

 public static double[] forward(Matrix mat,double b[]) {
  
  int nrow =mat.getNrow();  
  double sol[] =new double[nrow];
  
  for (int r=0;r<nrow; r++) 
  {
     double val =0;   
     for (int c=0;c<r; c++) {
         val =val +  sol[c] *mat.getElement(r, c);     
     }    
     val = b[r] - val;
     sol[r] = val/mat.getElement(r, r);
  }        
  return sol;
 }
 
  public static double[] backward(Matrix Umat,double b[]) {
   
  int nrow =Umat.getNrow();
  int ncol = Umat.getNcol();  
  double sol[] =new double[nrow];
  
     for(int r=nrow-1; r>=0; r--)
      {
      double val =0;
      for(int c=ncol-1;c>r;c--) {
           val =val +  sol[c] *Umat.getElement(r, c);  
        }
      val = b[r] - val;
      sol[r] = val/Umat.getElement(r, r); 
      }     
    return sol; 
 } 
 
  public static void main(String[] args) {    
   double u[][]={{1,2,3},{0,1,2},{0,0,1}};
   double b[] = {9,4,3};
  
  Matrix U = new Matrix(u);  
  System.out.println("Upper Triangular matrix U");
  System.out.println(U.toString());
  double sol[]=Substitution.backward(U, b);
  
  System.out.println("Solution of UX=b");
  System.out.println(Arrays.toString(sol));
  
                     
 double l[][]={{0.4286, 0.0, 0.0},{3.6667, 2.3334, 0.0},
                                                     {2.0,4.0,6.0}};
 double b2[] = {1.7143,10.0,18.0};
  
  Matrix L = new Matrix(l);  
  System.out.println("Lower Triangular matrix L");
  System.out.println(L.toString());
  double sol2[]=Substitution.forward(L, b2);
  
  System.out.println("Solution of LX=b");
  System.out.println(Arrays.toString(sol2));
  
 }
}

Java programming output of Forward and Backward Substitution


Upper Triangular matrix U
1.0  2.0  3.0  
0.0  1.0  2.0  
0.0  0.0  1.0  

 b vector 
 [9  4  3]

Solution of UX=b
[4.0, -2.0, 3.0]

Lower Triangular matrix L
0.4286  0.0  0.0  
3.6667  2.3334  0.0  
2.0  4.0  6.0  

 b vector 
 [1.7143 10.0 18.0]

Solution of LX=b
[3.9997666822211855, -1.9996333649183253, 2.9998333492051548]



Comments

Popular posts from this blog

Solving System of Linear Equations by Gauss Jordan Elimination

Solve System of Linear Equations by LU Decompose

Distance Metric - Euclidean Distance

Matrix Determinant by Upper Triangular Matrix