## 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 l_{21} and l_{31} find the multiplier that was used to make the a_{21} and a_{31} 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 l_{32}, what multiplier was used to make a_{32} element zero? Remember a_{32} 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

l_{32} = -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

z_{1} = 106.8

2.56z_{1} +z_{2} = 177.2

5.76z_{1} + 3.5z_{2} +z_{3}

Forward substitution starting from the first equation gives

z_{1} = 106.8

z_{2} = 177.2 - 2.56z_{1}

= 177.2 - 2.56 × 106.8

= - 96.208

z_{3} = 279.2 - 5.76z_{1} - 3.5z_{2}

=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 a_{3} = 0.76

a_{3} = 0.76/0.7 = 1.0857

Substituting the value of a_{3} in the second equation,

Substituting the value of a_{2} and a_{3} 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