LU Decomposition: Method and Examples
By BYJU'S Exam Prep
Updated on: September 25th, 2023
LU Decomposition is also known as LU factorization. LU decomposition is a matrix factorization technique used to solve linear systems of equations. It decomposes a square matrix A into two matrices, L and U, where L is a lower triangular matrix with 1’s on the diagonal and U is an upper triangular matrix. LU decomposition has several applications, including solving linear systems of equations, calculating matrix inverses, and calculating determinants. It can also be used to efficiently solve linear equations for multiple right-hand sides, as the LU decomposition only needs to be performed once for a given matrix.
LU Decomposition PDF(Download GATE Notes)
LU Decomposition is also used in numerical methods such as eigenvalue calculations, singular value decomposition, and optimization problems. There are several methods for computing the LU decomposition, including Gaussian elimination and Crout’s method. Each method has its own advantages and disadvantages, and the choice of method depends on the specific problem being solved. In this article, LU decomposition is discussed in detail with their examples.
Table of content
What is LU Decomposition?
LU decomposition is a widely used matrix decomposition technique in linear algebra. The decomposition factorizes a given square matrix into lower and upper triangular matrices. In other words, LU decomposition is the process of writing a matrix as the product of two triangular matrices. The LU decomposition is commonly used to solve linear equations, matrix inversion, and to find the determinant of a matrix.
Once a matrix has been decomposed into L and U, it can be used to solve linear equations of the form Ax = b, where x is the vector of unknowns, A is the original matrix, and b is the vector of constants. This is done by first solving Ly = b for y using forward substitution and then solving Ux = y for x using backward substitution. It is also a key component in many numerical methods, such as the Gaussian elimination method.
LU Decomposition Method
For a nonsingular matrix [A] on which one can successfully conduct the Naïve Gauss elimination forward elimination steps, one can always write it as
[A]=[L][U]
Where
- [L]= Lower triangular matrix
- [U]= Upper triangular matrix
By solving this set of equations we can get,
[A][X]=[C],
Then
[L][U][X]=[C] as ([A]=[L][U])
Multiplying both sides by [L]-1,
[L]-1[L][U][X]=[L]-1[C]
[I][U][X]=[L]-1[C] as ([L]-1[L]=[I])
[U][X]=[L]-1[C] as ([I][U]=[U])
Let
[L]-1[C]=[Z]
Then
[L][Z]=[C] …(1)
And
[U][X]=[Z] …(2)
For [Z], we need to solve equation 1 with the forward substitution method, and to solve vector [X] we can use equation 2 by the back substitution method.
Decomposition of a Non-Singular Matrix
A matrix can be said as a non-singular matrix if its inverse matrix can be determined. The LU decomposition of a non-singular matrix A is a factorization of A into the product of two triangular matrices L and U, such that A = LU. Where L is called as lower triangular matrix and U is called the upper triangular matrix.
The LU decomposition of a non-singular matrix can be computed using Gaussian elimination with partial pivoting. This algorithm ensures that matrix A is transformed into an upper triangular matrix U with pivots on the diagonal and that the permutation matrix P is used to keep track of the row interchanges performed during the elimination process.
If forward elimination steps of the Naïve Gauss elimination methods can be applied on a non-singular matrix, then can be decomposed into LU as
The elements of the [U] matrix are exactly the same as the coefficient matrix one obtains at the end of the forward elimination steps in Naïve Gauss elimination.
The lower triangular matrix [L] has 1 in its diagonal entries. The non-zero elements on the non-diagonal elements in [L] are multipliers that made the corresponding entries zero in the upper triangular matrix [U] during forward elimination.
Examples of LU Decomposition
Examples of LU Decomposition help to understand the topic, Here a few examples are shown which help to understand the related concepts in detail.
Example-1
Find the LU decomposition of the matrix
Solution
[A]=[L][U]
The [U] matrix is the same as found at the end of the forward elimination of the Naïve Gauss elimination method, that is
To find l21 and l31 find the multiplier that was used to make the a21 and a31 elements zero in the first step of forward elimination of the Naïve Gauss elimination method. It was
l21 = 64/25 = 2.56
l31 = 144/25 = 5.76
To find l32, what multiplier was used to make a32 element zero? It must be noted that a32 element was made zero in the second step of the forward elimination method. The [A] matrix at the beginning of the second step of forward elimination was
So 
l32 = -16.8/-4.8 = 3.5
Hence 
Confirm [L][U]=[A].
Example-2
Use the LU decomposition method to solve the following simultaneous linear equations.
Solution
Recall that
[A][X]=[C]
and if
[A]=[L][U]
then first solving
[L][Z]=[C]
and then
[U][X]=[Z]
gives the solution vector [X].
Now in the previous example, we showed
[A]=[L][U]
First, solve
[L][Z]=[C]
to give
z1 = 106.8
2.56z1 +z2 = 177.2
5.76z1 + 3.5z2 +z3
Forward substitution starting from the first equation gives
z1 = 106.8
z2 = 177.2 – 2.56z1
= 177.2 – 2.56 × 106.8
= – 96.208
z3 = 279.2 – 5.76z1 – 3.5z2
=0.76
Hence
This matrix is the same as the right-hand side obtained at the end of the forward elimination steps of the Naïve Gauss elimination method.
Now solve
[U][X]=[Z]
From the third equation
0.7 a3 = 0.76
a3 = 0.76/0.7 = 1.0857
Substituting the value of a3 in the second equation,
Substitute the value of a2 and a3 in first equation and we get,
Hence the solution vector is
The Inverse of a Square Matrix Using LU Decomposition
LU decomposition is a matrix factorization technique that decomposes a square matrix into two triangular matrices, an upper triangular matrix (U) and a lower triangular matrix (L). LU decomposition is generally used to get the solution of a system of linear equations, and also it can be used to determine the inverse of a square matrix.
To find the inverse of a square matrix using LU decomposition, follow these steps:
-
Perform LU decomposition on matrix A. This can be done using various techniques such as Gaussian elimination or Crout’s method. Once you have obtained the matrices L and U, write the matrix equation as A = LU.
-
Solve the system of linear equations Ly = b, where b is a column vector with the same number of rows as A. This can be done by forward substitution, which involves solving for y in each row of the lower triangular matrix L.
-
Solve the system of linear equations Ux = y, where y is the solution obtained in step 2. This can be done by backward substitution, which involves solving for x in each row of the upper triangular matrix U.
-
The inverse of A is given by A-1 = x, where x is the solution obtained in step 3.
A matrix [B] is the inverse of [A] if
[A][B]=[I]=[B][A]
Purpose of LU Decomposition
The main purpose of LU decomposition is to simplify the process of solving systems of linear equations. By decomposing a matrix into its lower triangular and upper triangular components, we can use forward and backward substitution to solve the system of equations, which is faster and more accurate than the traditional method of elimination.
LU decomposition can also be used to compute determinants and matrix inverses. For example, once a matrix is decomposed into its L and U components, the determinant of the original matrix can be easily computed by taking the product of the diagonal elements of the upper triangular matrix U.
| Other Important GATE Topics | |
| Light Propagation in Optical Fibers | Data Hazard |
| Floating Point Representation | Asynchronous Counter |
| User-defined Data Types in C | Full Subtractor |
