mathajax

Solve System of Linear Equations by LU Decompose

By -

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)

system of linear equation
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
  Ax = b1
System 2
  Ax = b2
  • LU = LU-decompose(A)
  • System 1
    1. y = forward-substitute (L , b1)
    2. x = back-substitute (U,y)
  • System 2
    1. y = forward-substitute (L , b2)
    2. x= back-substitute (U,y)


Algorithm Steps for Solving System of Linear Equations by LU Decompose 

       Input : a square matrix, A,
        non-homogeneous vector b    
       Output : Solution vector, X 
  
       read matrix A
       read vector b
       [L,U] = LUDecompose(A)
       Y = forward-substitute(L,b)
       X = back-substitute(U,Y)          
      print X, "is solution vector"

Java programming code for Solve System of Linear Equations by LU Decompose

 
import java.util.Arrays;
public class LUSolution {

 
 public static void main(String[] args) {
    
 double A [][]= {{2,4,6},{4,5,6},{3,1,-2} };
 double b[] = {24,18,4};  
  
        LUMatrix lu=new LUMatrix(A); 
        lu.decompose();
        Matrix L= lu.getL();
        Matrix U = lu.getU();
        
        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("verify that Matrix A = LU");
        System.out.println(MatrixOpr.multiply(L, U).toString());
        
        
        System.out.println(" Y = Lb");
        double Y[]=Subsitution.forward(L, b);
        System.out.println("Y =" +  Arrays.toString(Y));
        
        System.out.println(" X = UY");
        double X[]=Subsitution.backward(U, Y);                     
        System.out.println("Solution of Matrix A,  X =" 
                                             + Arrays.toString(X));                  
 }

}

Java program output of Solve System of Linear Equations by LU Decompose


Matrix A
2  4   6  
4  5   6
3  1  -2

 b = [24 18 4] 

Lower Triangular Matrix L
1.0  0.0  0.0  
0.5  1.0  0.0  
0.75  -1.8333333  1.0  

Upper Triangular Matrix U
4.0  5.0  6.0  
0.0  1.5  3.0  
0.0  0.0  -1.0  

verify that Matrix A = LU
4.0  5.0  6.0  
2.0  4.0  6.0  
3.0  1.0  -2.0  

Y = Lb
Y =[24.0, 6.0, -3.0]

X = UY
Solution of Matrix A,  X =[4.0, -2.0, 3.0]

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

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