mathajax

Inverse Matrix by LU Decomposition

By -

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

Post a Comment

Popular posts from this blog

Solving System of Linear Equations by Gauss Jordan Elimination

By -
Image
It finds a solution vector X for solving a system of linear equations which has NxN elements using Gauss-Jordan elimination method. Gauss-Jordan elimination method matrix A has N x N elements I, Identity matrix has N x N elements b is a vector has Nx1 system of non-homogeneous elements A|b is a augmented matrix result X, is a solution vector has Nx1 elements Elementary row operation is applied to augmented matrix, until it transforms A|b into I|X Algorithm Steps for solving system of linear equations by Gauss-Jordan Elimination Read Matrix A Read vector b form Augmented matrix A|b For i=1 To N For j=1 To N IF i not-equal j apply RowOperation.add(j,i ,-a ii /a ji ) on augmented matrix A|I End End End Divide each i th row of non-zero elements in A|b by a ii Java programming code- Gauss Jordan solving Linear equations im...
Keep reading

Matrix Forward and Back Substitution

By -
Image
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 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 ...
Keep reading

Solve System of Linear Equations by LU Decompose

By -
Image
One of the application of LU matrix decomposition is solving system of linear equations. Ax = b A - coefficient matrix b - non-homogeneous vector x - unknown vector (solution vector) The square matrix (coefficient matrix) A decomposed into LU (lower triangular and upper triangular) matrix by elementary-row-operations. A = LU the solution vector X of system found by forward and back substitution. y = forward-substitute L and b X = back-substitute U and y The two or more system of equations have same coefficient matrix A but have different non-homogeneous vectors (b1 ,b2,..), the solutions vectors (x1,x2,..) obtained by once applying LU decomposition over matrix A. System 1 &nbsp&nbsp Ax = b1 ...
Keep reading

Matrix Determinant by Upper Triangular Matrix

By -
Image
Determinant, a properties of matrix determines the matrix is singular or not. Upper triangular method is preferred over minor or cofactor of matrix method while finding determinant of the matrix's size over 3x3. The matrix A is converted into upper triangular matrix U by elementary row operation and then multiplication of main diagonal elements is called determinant of the matrix A. Read matrix A Convert matrix A into U by applying Row operation Read Main Diagonal elements from U Determinant = product of Main Diagonal elements Algorithm steps for Determinant by Upper Triangular Matrix Read matrix A a - element of the matrix A i,j - position of a element in the matrix for i=1 To N for j=i+1 To N RowOperation.add (j,i ,-a ii /a ji ) end end Determinant = a 11 x a 22 x ... x a nn Java program for Determinant by Upper Triangular Matrix...
Keep reading

Chebyshev distance between two points

By -
Image
The java program finds distance between two points using chebyshev distance equation . The points can be a scalar or a vector . 1D distance metric It measures distance between two points by absolute difference between them. Each point has one element. 2-Dimensional distance metric It measures distance between two points (2D vector) by selecting maximum absolute difference on 2D vector element absolute difference. N-Dimensional distance metric It measures distance between two N-Dimensional vector by selecting maximum absolute difference on the two N-D vector element. Example Calculation on 2D vectors This is an example calculation shown below explain how to find the distance between two vectors using Chebyshev distance formula. A vector,array of elements declared and initialized in Java using one dimensional array. int A[] = { 2 ,6 }; // 2D vector A int B[] = { 4,1 }; // 2D vector B max - operators finds greatest val...
Keep reading