# 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 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.

## 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:

1. 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.

2. 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.

3. 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.

4. 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
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com