LU Decomposition Method� I M.sc Mathematics,� Numerical Methods.

Presented by,

B.Suguna Selvarani,

Assistant Professor,

Department of Mathematics,

Cardamom Planters’ Association College,

Bodinayakanur.

​

​

������������LU Decomposition Method�� ����

LU Decomposition

LU Decomposition is another method to solve a set of simultaneous linear equations

​

Which is better, Gauss Elimination or LU Decomposition?

​

To answer this, a closer look at LU decomposition is needed.

LU Decomposition

Method

For most non-singular matrix [A] that one could conduct 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

​

How does LU Decomposition work?

If solving a set of linear equations

If [A] = [L][U] then

Multiply by

Which gives

Remember [L]^-1[L] = [I] which leads to

Now, if [I][U] = [U] then

Now, let

Which ends with

and

[A][X] = [C]

[L][U][X] = [C]

[L]^-1

[L]^-1[L][U][X] = [L]^-1[C]

[I][U][X] = [L]^-1[C]

[U][X] = [L]^-1[C]

[L]^-1[C]=[Z]

[L][Z] = [C] (1)

[U][X] = [Z] (2)

LU Decomposition

How can this be used?

Given [A][X] = [C]

1. Decompose [A] into [L] and [U]
2. Solve [L][Z] = [C] for [Z]
3. Solve [U][X] = [Z] for [X]

Method: [A] Decomposes to [L] and [U]

[U] is the same as the coefficient matrix at the end of the forward elimination step.

[L] is obtained using the multipliers that were used in the forward elimination process

Finding the [U] matrix

Using the Forward Elimination Procedure of Gauss Elimination

Step 1:

Finding the [U] Matrix

Step 2:

Matrix after Step 1:

Finding the [L] matrix

Using the multipliers used during the Forward Elimination Procedure

From the first step of forward elimination

Finding the [L] Matrix

From the second step of forward elimination

Does [L][U] = [A]?

?

Using LU Decomposition to solve SLEs

Solve the following set of linear equations using LU Decomposition

Using the procedure for finding the [L] and [U] matrices

Example

Set [L][Z] = [C]

​

​

Solve for [Z]

Example

Complete the forward substitution to solve for [Z]

Example

Set [U][X] = [Z]

​

​

​

Solve for [X] The 3 equations become

​

Example

From the 3^rd equation

Substituting in a₃ and using the second equation

Example

Substituting in a₃ and a₂ using the first equation

Hence the Solution Vector is:

Finding the inverse of a square matrix

The inverse [B] of a square matrix [A] is defined as

​

[A][B] = [I] = [B][A]

Finding the inverse of a square matrix

How can LU Decomposition be used to find the inverse?

Assume the first column of [B] to be [b₁₁ b₁₂ … b_n1]^T

Using this and the definition of matrix multiplication

​

First column of [B] Second column of [B]

The remaining columns in [B] can be found in the same manner

Example: Inverse of a Matrix

Find the inverse of a square matrix [A]

Using the decomposition procedure, the [L] and [U] matrices are found to be

Example: Inverse of a Matrix

Solving for the each column of [B] requires two steps

1. Solve [L] [Z] = [C] for [Z]
2. Solve [U] [X] = [Z] for [X]

Step 1:

This generates the equations:

​

Example: Inverse of a Matrix

Solving for [Z]

Example: Inverse of a Matrix

Solving [U][X] = [Z] for [X]

Example: Inverse of a Matrix

Using Backward Substitution

So the first column of the inverse of [A] is:

Example: Inverse of a Matrix

Repeating for the second and third columns of the inverse

​

Second Column Third Column

Example: Inverse of a Matrix

The inverse of [A] is

To check your work do the following operation

[A][A]^-1 = [I] = [A]^-1[A]

Thank You

​

​

​

​