LU Decomposition in Matrices

Previous
Quiz
Next

LU Decomposition in Matrices is a method of decomposing a square matrix into two matrices, one of which is a lower triangular matrix and the other is an upper triangular matrix.

The LU decomposition is used in numerical analysis to solve systems of linear equations.

The LU decomposition is also used in the solution of linear systems of equations, the calculation of the determinant of a matrix, and the calculation of the inverse of a matrix.

What is LU Decomposition in Data Structures?

In data structures, LU decomposition means splitting a square matrix A into two smaller matrices:

  • L - Lower triangular matrix

  • U - Upper triangular matrix

This decomposition helps in efficient computation of the determinant and inverse of a matrix.

Why LU Decomposition is Important?

It simplifies the process of solving linear equations and calculating the determinant and inverse of a matrix by breaking down the original matrix into two simpler matrices.

Imagine you have a project where you have to build a feature that require solving linear equations and you don't want it to be complex. In this case, you can use LU decomposition to simplify the process. It means you can solve the same equations with less effort and complexity by breaking down the matrix into two simpler matrices.

LU Decomposition Algorithm

The LU decomposition algorithm is as follows:

1. Read the matrix A
2. Set the size of the matrix A as n x n
3. Initialize the matrices L and U as n x n matrices
4. Set the diagonal elements of L as 1 and the other elements as 0
5. Set the elements of U as the elements of A
6. For k = 1 to n-1
7. For i = k+1 to n
8. Set L[i][k] = U[i][k]/U[k][k]
9. For j = k to n
10. Set U[i][j] = U[i][j] - L[i][k]*U[k][j]
11. Display the matrices L and U

LU Decomposition Example

Let's consider a 3x3 matrix A. We will perform LU decomposition on this matrix. Following is the example, using Java, CPP, C and Python programming languages.

C C++ Java Python 
        //C Program to perform LU Decomposition
#include <stdio.h>

int main(){
   int n = 3;
   float A[3][3] = {{2, -1, -2}, {-4, 6, 3}, {-4, -2, 8}};
   float L[3][3], U[3][3];
   int i, j, k;

   for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
         if(i > j){
            U[i][j] = 0;
            L[i][j] = A[i][j];
         }
         else if(i == j){
            L[i][j] = 1;
            U[i][j] = A[i][j];
         }
         else{
            L[i][j] = 0;
            U[i][j] = A[i][j];
         }
      }
   }
   for(k = 0; k < n; k++){
      for(i = k + 1; i < n; i++){
         L[i][k] = U[i][k] / U[k][k];
         for(j = k; j < n; j++){
            U[i][j] = U[i][j] - L[i][k] * U[k][j];
         }
      }
   }
   printf("L Matrix\n");
   for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
         printf("%f ", L[i][j]);
      }
      printf("\n");
   }
   printf("U Matrix\n");
   for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
         printf("%f ", U[i][j]);
      }
      printf("\n");
   }
   return 0;
}

Output

The output obtained is as follows −

L Matrix
1.000000 0.000000 0.000000
-2.000000 1.000000 0.000000
-2.000000 1.000000 1.000000
U Matrix
2.000000 -1.000000 -2.000000
0.000000 4.000000 7.000000
0.000000 0.000000 1.000000


//CPP Program
#include <iostream>
using namespace std;

int main(){
   int n = 3;
   float A[3][3] = {{2, -1, -2}, {-4, 6, 3}, {-4, -2, 8}};
   float L[3][3], U[3][3];
   int i, j, k;

   for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
         if(i > j){
            U[i][j] = 0;
            L[i][j] = A[i][j];
         }
         else if(i == j){
            L[i][j] = 1;
            U[i][j] = A[i][j];
         }
         else{
            L[i][j] = 0;
            U[i][j] = A[i][j];
         }
      }
   }
   for(k = 0; k < n; k++){
      for(i = k + 1; i < n; i++){
         L[i][k] = U[i][k] / U[k][k];
         for(j = k; j < n; j++){
            U[i][j] = U[i][j] - L[i][k] * U[k][j];
         }
      }
   }
   cout << "L Matrix" << endl;
   for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
         cout << L[i][j] << " ";
      }
      cout << endl;
   }
   cout << "U Matrix" << endl;
   for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
         cout << U[i][j] << " ";
      }
      cout << endl;
   }
   return 0;
}

Output

The output produced is as follows −

L Matrix
1 0 0 
0 1 0 
0 0 1 
U Matrix
2 -1 -2 
0 6 3 
0 0 8 

      //java Program
public class Main{
   public static void main(String[] args){
      int n = 3;
      float A[][] = {{2, -1, -2}, {-4, 6, 3}, {-4, -2, 8}};
      float L[][] = new float[3][3];
      float U[][] = new float[3][3];
      int i, j, k;

      for(i = 0; i < n; i++){
         for(j = 0; j < n; j++){
            if(i > j){
               U[i][j] = 0;
               L[i][j] = A[i][j];
            }
            else if(i == j){
               L[i][j] = 1;
               U[i][j] = A[i][j];
            }
            else{
               L[i][j] = 0;
               U[i][j] = A[i][j];
            }
         }
      }
      for(k = 0; k < n; k++){
         for(i = k + 1; i < n; i++){
            L[i][k] = U[i][k] / U[k][k];
            for(j = k; j < n; j++){
               U[i][j] = U[i][j] - L[i][k] * U[k][j];
            }
         }
      }
      System.out.println("L Matrix");
      for(i = 0; i < n; i++){
         for(j = 0; j < n; j++){
            System.out.print(L[i][j] + " ");
         }
         System.out.println();
      }
      System.out.println("U Matrix");
      for(i = 0; i < n; i++){
         for(j = 0; j < n; j++){
            System.out.print(U[i][j] + " ");
         }
         System.out.println();
      }
   }
}

Output

The output obtained is as shown below −

L Matrix
1.0 0.0 0.0 
0.0 1.0 0.0 
0.0 0.0 1.0 
U Matrix
2.0 -1.0 -2.0 
0.0 6.0 3.0 
0.0 0.0 8.0 

def main():
    n = 3
    A = [[2, -1, -2], [-4, 6, 3], [-4, -2, 8]]
    L = [[0 for i in range(n)] for j in range(n)]
    U = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i > j:
                U[i][j] = 0
                L[i][j] = A[i][j]
            elif i == j:
                L[i][j] = 1
                U[i][j] = A[i][j]
            else:
                L[i][j] = 0
                U[i][j] = A[i][j]
    for k in range(n):
        for i in range(k + 1, n):
            L[i][k] = U[i][k] / U[k][k]
            for j in range(k, n):
                U[i][j] = U[i][j] - L[i][k] * U[k][j]
    print("L Matrix")
    for i in range(n):
        for j in range(n):
            print(L[i][j], end = " ")
        print()
    print("U Matrix")
    for i in range(n):
        for j in range(n):
            print(U[i][j], end = " ")
        print()
main()

Output

Following is the output of the above code −

L Matrix
1 0 0 
0.0 1 0 
0.0 0.0 1 
U Matrix
2 -1 -2 
0.0 6.0 3.0 
0.0 0.0 8.0

Applications of LU Decomposition

LU decomposition is used in various applications, such as:

  • Solving systems of linear equations
  • Calculating the determinant of a matrix
  • Calculating the inverse of a matrix

LU decomposition is also used in numerical analysis, scientific computing, and engineering to solve complex problems.

Conclusion

In this chapter, we learned about LU decomposition in matrices. We discussed the importance of LU decomposition in data structures and its applications in solving linear equations, calculating the determinant and inverse of a matrix. We also saw the LU decomposition algorithm and an example of LU decomposition in a 3x3 matrix using different programming languages.

Print Page
Previous
Next
Advertisements