mathajax

Inverse Matrix by LU Decomposition

One of the application of LU matrix decomposition finds inverse of a square matrix,A.

A A -1 = I


The square matrix (coefficient matrix) A decomposed into LU (lower triangular and upper triangular) matrix by elementary-row-operations.

A = LU


after that, inverse matrix A -1 is found by applying forward and back substitution on each column of identity matrix, I and place returning solution vectors x to column of A -1 matrix.


Algorithm steps for Matrix Inverse by LU Decomposition

         Input : a square matrix, A         
         Output : a square matrix, A -1

         read matrix A
         [L,U]=LUDecompose(A)  
         
         [nrow,ncol]=size(A) 
         I = Identity-matrix(nrow,ncol);
         iA = zero-matrix(nrow,ncol);

         For c =1 to ncol 
          Y = forward-substitute(L,I(c))
          X = back-substitute(U,Y)
          A-1(c,:) = X    // set vector X to column of A -1
         End 
    
        print A-1, "is inverse of A"  
  

Java programming code - Matrix Inverse by LU Decomposition

 
import java.util.Arrays;
public class LUInverse {

 public static void main(String[] args) {
  
 double A [][]= {{25,5,1},{64,8,1},{144,12,1} };
    
        LUMatrix lu=new LUMatrix(A); 
        lu.decompose();
        Matrix L= lu.getL();
        Matrix U = lu.getU();
        int rc[] = lu.roworder();
        
        System.out.println("Lower Triangular Matrix L");
        System.out.println(L.toString());
        
        System.out.println("Upper Triangular Matrix U");
        System.out.println(U.toString());
        
        System.out.println("Row Order Change");
        System.out.println(Arrays.toString(rc));
        
                
        System.out.println("verify that Matrix A = LU");
        System.out.println(MatrixOpr.multiply(L, U).toString());
                        
       
       double I[][] = {{1,0,0},{0,1,0},{0,0,1}};       
       double A1[][] = new double[L.getNrow()][L.getNcol()] ;
                       
        for (int r=0;r<L.getNrow();r++) {
           double Y[]=Substitution.forward(L, I[r]);           
           double X[]=Substitution.backward(U, Y);           
           for (int c=0;c<X.length;c++)
              A1[c][rc[r]] = X[c];                   
        }
        
        System.out.println("Matrix A Inverse");        
        System.out.println(new Matrix(A1).toString());
        
        System.out.println("prove that Matrix A*A-1 = I");
        System.out.println(MatrixOpr.multiply(new Matrix(A), 
                                      new Matrix(A1)).toString());             
 }
}


 

Java program output of Matrix Inverse by LU Decomposition


Matrix A
25   5   1  
64   8   1  
144  12  1

Lower Triangular Matrix L
1.0  0.0  0.0  
0.4444444  1.0  0.0  
0.1736111  1.09375  1.0  

Upper Triangular Matrix U
144.0  12.0  1.0  
0.0  2.66666  0.55555
0.0  0.0  0.2187499  

Row Order Change
[2, 1, 0]

verify that Matrix A = LU
144.0  12.0  1.0  
64.0  8.0  1.0  
25.0  5.0  0.9999999  

Inverse of Matrix A 
0.047619047619047644  -0.08333333333333336  0.035714285714285726  
-0.9523809523809529  1.4166666666666672  -0.4642857142857144  
4.571428571428574  -5.000000000000003  1.4285714285714293  

prove that Matrix A*A-1 = I
1.0000000000000004  -8.881784197001252E-16  4.440892098500626E-16  
0.0  1.0  4.440892098500626E-16  
8.881784197001252E-16  8.881784197001252E-16  1.0000000000000004  



Comments

Popular posts from this blog

Matrix Forward and Back Substitution

Solving System of Linear Equations by Gauss Jordan Elimination

Distance Metric - Euclidean Distance

Solve System of Linear Equations by LU Decompose

Matrix in Java