What is LU Decomposition?
LU decomposition is a method of matrix factorization that decomposes a matrix A into two triangular matrices, an upper triangular matrix U and a lower triangular matrix L, such that A = LU. The LU decomposition is commonly used for solving systems of linear equations, inverting matrices, and computing determinants.
The LU decomposition can be computed using Gaussian elimination, which is an algorithm for reducing a matrix to its row echelon form by performing a series of row operations. The row echelon form of a matrix is a triangular matrix with ones along the diagonal and zeros below the diagonal. Gaussian elimination can be used to compute both the L and U matrices simultaneously.
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
Then if one is solving a set of equations
[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)
So we can solve Equation (1) first for [Z] by using forward substitution and then use Equation (2) to calculate the solution vector [X] by back substitution.
Decomposition of a Non-Singular Matrix
A non-singular matrix is a matrix that has an inverse. 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. Here, L is a lower triangular matrix and U is an 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? Remember a32 element was made zero in the second step of forward elimination. 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,
Substituting the value of a2 and a3 in the first equation,
Hence the solution vector is
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 often used to solve systems of linear equations, and it can also be used to find 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]
| Other Important GATE Topics | |
| 2's Complement | Data Hazard |
| Floating Point Representation | Asynchronous Counter |
| User-defined Data Types in C | Full Subtractor |
Comments
write a comment