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

Matrix Forward and Back Substitution

Chebyshev distance between two points

Complex number Multiplication and Division

Solve System of Linear Equations by LU Decompose

Matrix Determinant, Matrix Adjoint and Matrix Inverse