C++ Program To Perform Lu Decomposition Of Any Matrix

A well-known technique in numerical computations for solving systems of linear equations and calculating matrix inverses is LU decomposition. This technique involves decomposing a matrix into the product of a lower triangular matrix (L) and an upper triangular matrix (U). Various fields such as engineering, physics, and computational mathematics rely on LU decomposition for various applications. The upcoming sections detail the principles behind LU decomposition and its practical implementation in the provided C++ code:

1. LU Decomposition

The LU factorization technique requires an input of an n×n matrix denoted as A and identifies two matrices, L and U, where A = LU.

With ones on the main diagonal, matrix L is in lower triangular form, while matrix U is in upper triangular form.

2. Algorithmic Steps

Different techniques such as Doolittle's approach or Crout's technique, involving a systematic breakdown of the initial matrix into lower (L) and upper (U) matrices, are commonly employed to accomplish LU decomposition.

The values within the initial matrix are employed to establish the components of L and U during the decomposition procedure.

3. Implementation in the C++ Program

The provided C++ code creates an empty matrix for L and U, then proceeds to populate a sample matrix A.

The input matrix A gets separated into the upper triangular matrix U and the lower triangular matrix L through the decomposeLU function.

The program will display the generated L and U matrices.

4. Application and Usage

LU decomposition is a valuable technique for effectively calculating matrix inverses, determinants, and solving systems of linear equations.

It is applied in various numerical methods, including structural evaluation, analysis of electrical circuits, and solving differential equations.

Example:

Let's consider an example to demonstrate the application of LU decomposition of a matrix in the C++ programming language.

#include <iostream>
#include <vector>
using namespace std;
const int N = 3; 
// Size of the matrix
void decomposeLU(vector<vector<double>>& A, vector<vector<double>>& L, vector<vector<double>>& U)
{
 for (int i = 0; i < N; i++)
 {
 // Decomposing the upper triangular matrix
 for (int k = i; k < N; k++) 
 {
 int sum = 0;
 for (int j = 0; j < i; j++)
 {
 sum += (L[i][j] * U[j][k]);
 }
 U[i][k] = A[i][k] - sum;
 }
 // Decomposing the lower triangular matrix
 for (int k = i; k < N; k++)
 {
 if (i == k)
 L[i][i] = 1; // Diagonal elements of L are 1
 else
 {
 int sum = 0;
 for (int j = 0; j < i; j++)
 {
 sum += (L[k][j] * U[j][i]);
 }
 L[k][i] = (A[k][i] - sum) / U[i][i];
 }
 }
 }
}
int main()
{
 // Sample matrix
 vector<vector<double>> A = {{2, -1, -2}, {-4, 6, 3}, {-4, -2, 8}};
 // Initializing L and U as 2D vectors
 vector<vector<double>> L(N, vector<double>(N, 0));
 vector<vector<double>> U(N, vector<double>(N, 0));
 decomposeLU(A, L, U);
 // Printing the results
 cout << "Lower Triangular Matrix (L):" << endl;
 for (int i = 0; i < N; i++) 
 {
 for (int j = 0; j < N; j++)
 {
 cout << L[i][j] << " ";
 }
 cout << endl;
 }
 cout << "\nUpper Triangular Matrix (U):" << endl;
 for (int i = 0; i < N; i++)
 {
 for (int j = 0; j < N; j++)
 {
 cout << U[i][j] << " ";
 }
 cout << endl;
 }
 return 0;
}

Output:

Lower Triangular Matrix (L):
1 0 0 
-2 1 0 
-2 -1 1 

Upper Triangular Matrix (U):
2 -1 -2 
0 4 -1 
0 0 3

Explanation:

1. File headers and global constants

• ✅ In this example, the program comes with the required header files, <iostream> and <vector> or input/output operations and vector data structures.
• ✅ It indicates the square matrix's size: const int N = 3 . It's configured to 3x3 in this instance.

1. Function for LU Decomposition decomposeLU

• ✅ The decomposeLU function was created to carry out LU decomposition. Three requirements must be met.
• ✅ A represents the original matrix in two dimensions.
• ✅ There are two 2D vectors called L and U that hold the bottom and upper triangular matrices.

1. LU Decomposition

• ✅ The function iterates through the components of the input matrix A using nested loops to determine the values of matrices L and U.
• ✅ The typical LU decomposition algorithm is followed throughout the decomposition procedure.
• ✅ The procedure determines the value for each element in the higher triangular matrix U by deducting the sum of products of elements from both the lower triangular matrix L and the upper triangular matrix U.
• ✅ As it should be, the diagonal members of the lower triangular matrix L are set to 1.
• ✅ The non-diagonal elements of the bottom triangular matrix L are computed based on the elements of the upper triangular matrix U and the original matrix A.

1. Main Function

• ✅ A sample 3x3 matrix A is defined in the main function.
• ✅ The output of the LU decomposition is stored in empty matrices L and U, each of the same size.

1. LU Decomposition call

Displaying the Outcome

The program displays the upper triangular matrix U and the lower triangular matrix L on the console.

1. Result

The result showcases the upper and lower triangular matrices generated from decomposing the example matrix A utilizing the LU technique.