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

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

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

Complex number Multiplication and Division

By -
Image
The arithmetic operation like multiplication and division over two Complex numbers is explained Complex number Multiplication multiply two complex numbers z1 and z2. note i^2 = -1 z1 = a + bi z2 = c + di z1*z2 = (a+bi) * (c+di) = a*c + a*di + bi*c + bi*di = a*c + a*di + bi*c + b*d*(i^2) = a*c + a*di + bi*c + b*d*(-1) = a*c + a*di + c*bi - b*d = (a*c - b*d) + (a*di + c*bi) Complex number Division divide two c omplex numbers z1 and z2. note i^2= -1 z1 = a + bi z2 = c + di z1 / z2 = (a+bi ) / (c+di) multiply numerator and denumerator by conjugate z2 conjugate z2 = c + (-1)* di = c - di z1 / z2 = (a+bi) (c-di) / (c+di ) (c-di) (a+bi) (c-di) = a*c - a*di + c*bi -bi*di = a*c - a*di + c*bi -b*d*(i^2) =
Keep reading

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