Lu Factorization

Back to Programming

Description

Lu factorization is also known as the triangular decomposition method. It is often called Crout’s method also. This method is based on the fact that every square matrix can be expressed as the product of a lower and an upper triangular matrix provided the principal minors of the given square matrix  are non-singular i.e.

Then we can also assure that the factorization is unique.

DERIVATION

Let us assume that the matrix A is factorized as the product of a lower triangular matrix L and upper triangular matrix U so that A = LU

Where,

Here the system of equation AX = b can be written as LUX = b

Putting UX = Y

Now LU = A will give us

From the above equation, we get,

Generalizing the above equation we get,

For j > 1,

And for i > 1 but i < j,

All ${\mathrm{l}}_{\mathrm{ij}}$ , ${\mathrm{u}}_{\mathrm{ij}}$ can be determined by applying the above relations, and hence L and U will be known.

Now can be determined by forwarding substitution from LY = b and all unknown  will be found by back substitution from the equation UX = Y

Alternatively, we can find ${\mathrm{L}}^{-1}$ and ${\mathrm{U}}^{-1}$ and we can write . The inverse of A can be determined from the following relation:

We now discuss the particular case of 3 × 3 matrices of the form.

We get,

Algorithm

INPUT:

A matrix

OUTPUT:

The value after factorization.

PROCESS:

``````Step1: [taking the inputs]
Read n [the order of the matrix]
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
[End of ‘for’ loop]
[End of ‘for’ loop]
for i = 0 to n - 1 repeat
[End of ‘for’ loop]

Step 2: [LU Factorization]
for j = 0 to n - 1 repeat
for i = 0 to n - 1 repeat
If i ≤ j then
Set u[i][j] ← arr[i][j]
for k = 0 to i - 2 repeat
Set u[i][j] ← u[i][j] - l[i][k] × u[k][j]
[End of ‘for’ loop]
If i = j then
Set l[i][j] ← 1.0
else
Set l[i][j] ← 0.0
[End of ‘if’]
[End of ‘if’]
else
Set l[i][j] ← arr[i][j]
for k = 0 to j - 1 repeat
Set l[i][j] = l[i][j] - l[i][k] × u[k][j]
[End of ‘for’ loop]
Set l[i][j] = l[i][j] / u[j][j]
Set u[i][j] ← 0.0
[End of ‘if’]
[End of ‘for’ loop]
[End of ‘for’ loop]
Print "the values of matrix L"
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
Print l[i][j]
[End of ‘for’ loop]
Move to the next line
[End of ‘for’ loop]
Print "the values of matrix U:"
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
Print u[i][j]
[End of ‘for’ loop]
Move to the next line
[End of ‘for’ loop]
for i = 0 to n - 1 repeat
Set y[i] ← constant[i]
for j = 0 to i - 1 repeat
Set y[i] ← y[i] - l[i][j] × y[j]
[End of ‘for’ loop]
[end of ‘for’ loop]
Print "the value of matrix Y"
for i = 0 to n - 1 repeat
Print y[i]
[End of ‘for’ loop]
for i = n - 1 to 0 repeat
Set x[i] ← y[i]
for j = i + 1 to n - 1 repeat
Set x[i] ← x[i] - u[i][j] × x[j]
[End of ‘for’ loop]
Set x[i] ← x[i]/u[i][i]
[End of ‘for’ loop]
Print "the value of matrix X: "
for i = 0 to n - 1 repeat
Print x[i]
[End of ‘for’ loop]
[End of ‘LU Factorization’ method]``````

Code

1. It is done only using the matrix A, so after the factorization, it can be applied to any vector b.

2. It is better than the Gauss elimination and Gauss Jordan elimination method.