mathajax

Matrix A = LU Decompose

LU decompose - a square matrix A that can be expressed as product of L and U matrix, is called LU decomposition. A = LU

A=LU matrix decompose

Matrix L - It is called Lower triangular Matrix, whose elements above the main diagonal is zero valued elements.

Matrix U - It is called Upper Triangular Matrix, whose elements below the main diagonal is zero valued elements.

How to LU decompose - a square matrix A is decomposed or factorized into L and U matrix by elementary row operation, such as swapping two rows and adding or subtracting row by a scalar value.

Application of LU decompose It is useful to find solution of system of linear equation and matrix inverse.


Algorithm steps for A= LU decompose

      Read matrix A
      U = copy (A)
      L = Identity-matrix()      
      i,j - position of a element in the matrix  
 
     For i=1  To  N 
  
       Eor j=i+1 To  N 
          lambda=Uji/Uii
          Rj <- Rj  - lambda x Ri                
          Lji= lamda
       End 
    End

Java programming - Matrix LU Decompose

 
public class LUMatrix {

 Matrix L,U; 
 int rc[];
 
 public LUMatrix(double A[][]) {
  
  int nrow=A.length;
  int ncol=A[0].length;
  
  rc=new int[nrow];
  U = new Matrix(nrow,ncol);
  for(int r=0;r<nrow;r++) {
   for(int c=0;c<ncol;c++) 
        U.setElement(r, c, A[r][c]);    
  }
  
  L =new Matrix(nrow,ncol);
  L.identity();  
 }
  
 public void maxdiagonal() {
  
  for(int r=0;r<U.getNrow();r++)    
      rc[r] = r;
  
  for(int r=0;r<U.getNrow();r++)  
  {    
       double mx=0; int mr=r;   
       for (int c=r;c<U.getNrow();c++){ 
      if (  Math.abs(U.getElement(c, r)) > mx ) {
           mx = Math.abs(U.getElement(c, r));
        mr = c;
       }      
      }       
     if ( mr!=r ) {     
    rc[r] = mr;rc[mr] = r;
           RowOperation.swap(U, r, mr);    
     }
  } 
 }
 
   public void decompose() {
     
      this.maxdiagonal();  
      for (int row=0 ; row< U.getNrow() ; row++) {
          for (int index= row+1 ; index< U.getNrow(); index++) {
             if(  U.getElement(index, row) != 0 ){
               doublelamda=U.getElement(index, row)/U.getElement(row, row);
                RowOperation.subtract(U, index, row,lamda);                    
                L.setElement(index, row, lamda);                   
              }                 
           }
         }                          
 }
  
       public Matrix getL() {                   
          return L;
     }     
      public Matrix getU(){
         return U; 
     }
      public int[] roworder() {
         return rc; 
  }
 
 public static void main(String[] args) {      
            double A[][] = { {2,1 ,2,3},{1,0 ,1,1},{-2,1,-1,1},{2,1,-1,0} };
    
  LUMatrix de=new LUMatrix(A);
  de.decompose();
  
  Matrix L = de.getL();
  Matrix U =de.getU();
  
  System.out.println("Upper Triangular matrix");
  System.out.println(U.toString());
  
  System.out.println("Lower Triangular matrix");
  System.out.println(L.toString());
    
  System.out.println(" Verify that A =L*U");
  Matrix LU = MatrixOpr.multiply(L, U);    
  System.out.println(LU.toString());        
 }
}

Java program output of Matrix LU Decompose


Matrix A 
2.0  1.0  2.0  3.0  
-2.0  1.0  -1.0  1.0  
1.0  0.0  1.0  1.0  
2.0  1.0  -1.0  0.0  

Upper Triangular Matrix U
2.0  1.0  2.0  3.0  
0.0  2.0  1.0  4.0  
0.0  0.0  0.25  0.5  
0.0  0.0  0.0  3.0  

Lower Triangular Matrix L
1.0  0.0  0.0  0.0  
-1.0  1.0  0.0  0.0  
0.5  -0.25  1.0  0.0  
1.0  0.0  -12.0  1.0  

Verify that A =L*U
2.0  1.0  2.0  3.0  
-2.0  1.0  -1.0  1.0  
1.0  0.0  1.0  1.0  
2.0  1.0  -1.0  0.0  



Comments

Popular posts from this blog

Solving System of Linear Equations by Gauss Jordan Elimination

Matrix Forward and Back Substitution

Solve System of Linear Equations by LU Decompose

Distance Metric - Euclidean Distance

Matrix Determinant by Upper Triangular Matrix