# LU Decomposition Method – Algorithm, Implementation in C With Solved Examples

Numerical Methods & Algorithms / Saturday, October 20th, 2018

# LU Decomposition Method

LU Decomposition Method is also known as factorization or Crout’s reduction method. Let the system of linear equations be

$Ax=b……….(1)$

Where A, x, b are respectively coefficient matrix, variable vector and right hand side vector.
The matrix A can be factorized into the form

$A=LU$

Where L and U are the lower and upper triangular matrices respectively. If the principal minors of A are non-singular, then this factorization is possible and it is unique.
The matrices L and U are of the form

The equation Ax = b becomes Lux = b. let Ux = z then Lz = b, where z = (z1, z2, …, zn)t is an intermediate variable vector. The value of z i.e., z1, z2, …, zn can be determined by forward substitution in the following equations.

${{l}_{11}}{{z}_{1}}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~={{b}_{1}}$

${{l}_{21}}{{z}_{1}}+{{l}_{22}}{{z}_{2}}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~={{b}_{2}}$

${{l}_{31}}{{z}_{1}}+{{l}_{32}}{{z}_{2}}+{{l}_{33}}{{z}_{3}}~~~~~~~~~~~~~~~~~~~={{b}_{3}}$

$…………………………………$

${{l}_{n1}}{{z}_{1}}+{{l}_{n2}}{{z}_{2}}+{{l}_{n3}}{{z}_{3}}~+….+~{{l}_{nn}}{{z}_{n}}~~={{b}_{n}}$

After determination of z, one can compute the value of x i.e., x1, x2, …, xn from the equation Ux = z i.e., from the following equations by the backward substitution

${{u}_{11}}{{x}_{1}}+{{u}_{12}}{{x}_{2}}+{{u}_{13}}{{x}_{3}}+…+{{u}_{1n}}{{x}_{n}}={{z}_{1}}$

$~~~~~~~~~~{{u}_{22}}{{x}_{2}}+{{u}_{23}}{{x}_{3}}+…+{{u}_{2n}}{{x}_{n}}={{z}_{2}}$

$~~~~~~~~~~~~~~~~~~~~~{{u}_{33}}{{x}_{3}}+…+{{u}_{3n}}{{x}_{n}}={{z}_{3}}$

$…………………………………$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{{u}_{nn}}{{x}_{n}}={{z}_{n}}$

When uii = 1, for i =1, 2, …, n, then the method is known as Crout’s decomposition method.

## Procedure to Compute L and U

Here we assume that uii = 1, for i =1, 2, …, n. from the relation LU = A i.e., from
We obtain,

${{l}_{i1}}={{a}_{i1}},i=1,2,…,n~~and~~{{u}_{1j}}=\frac{{{a}_{1j}}}{{{l}_{11}}},j=1,2,…,n.$

The second column of L and the second row of U are determined from the relations

${{l}_{i2}}={{a}_{i2}}-{{l}_{i1}}{{u}_{12}}~~for~~i=1,2,…,n~$

${{u}_{2j}}=\frac{{{a}_{2j}}-{{l}_{21}}{{u}_{1j}}}{{{l}_{22}}}~~for~~j=1,2,…,n$

Next, third column of L and third row of U are determined in a similar way. In general, lij and uij given by

${{l}_{ij}}={{a}_{ij}}-\sum\limits_{k=1}^{j-1}{{{l}_{ik}}{{u}_{kj}},i\ge j}$

${{u}_{ij}}=\frac{{{a}_{ij}}-\sum\limits_{k=1}^{i-1}{{{l}_{ik}}{{u}_{kj}}}}{{{l}_{ii}}},i<j$

${{u}_{ii}}=1,~~{{l}_{ij}}=0,~~j>i~~and~~{{u}_{ij}}=0,~~i>j$

Alternatively, the vectors z and x can be determined from the equations

$z={{L}^{-1}}b~~and~~x={{U}^{-1}}z$

It may be noted that the computation of inverse of a triangular matrix is easier than an arbitrary matrix.
The inverse of A can also be determined from the relation

${{A}^{-1}}={{U}^{-1}}{{L}^{-1}}$

## Algorithm of LU Decomposition Method

Let Ax = b be the systems of equations and A = [aij], b = (b1, b2, …, bn)t, x = (x1, x2, …, xn)t
//Assume that the principal minors of all order are non-zero
//Determine the Matrices L and U.

Step 1. Read the matrix A = [aij], i,j = 1, 2, ….n and the right hand vector b = (b1, b2, …, bn)t.

Step 2. li1 = ai1 for i = 1, 2, …, n; u1j = a1j / l11 for j = 1, 2, …, n; uii = 1 for i = 1, 2, …, n

Step 3. For i, j = 2, 3, …,n compute the following

${{l}_{ij}}={{a}_{ij}}-\sum\limits_{k=1}^{j-1}{{{l}_{ik}}{{u}_{kj}},i\ge j}$

${{u}_{ij}}=\frac{{{a}_{ij}}-\sum\limits_{k=1}^{i-1}{{{l}_{ik}}{{u}_{kj}}}}{{{l}_{ii}}},i<j$

Step 4. //Solve the system Lz = b by forward substitution

${{z}_{1}}=\frac{{{b}_{1}}}{{{l}_{11}}},{{z}_{i}}=\frac{1}{{{l}_{ii}}}\left( {{b}_{i}}-\sum\limits_{j=1}^{i-1}{{{l}_{ij}}{{z}_{j}}} \right)~~for~~i=2,3,…,n$

Step 5. //Solve the system Ux = z by backward substitution

$Set~~{{x}_{n}}={{z}_{n}};$

${{x}_{i}}={{z}_{i}}-\sum\limits_{j=i+1}^{n}{{{u}_{ij}}{{x}_{j}}}~~for~~i=n-1,n-2,….,1$

Step 6. Print x1, x2, …, xn as solution.

## Implementation of LU Decomposition Method in C

/* Program LU-Decomposition.
Solution of a system of equations by LU Decomposition Method.
Assume that all order principal minors are non-zero. */

#include<stdio.h>

void main()
{
float a[10][10],l[10][10],u[10][10],z[10],x[10],b[10];
int i,j,k,n;

printf("\nEnter the size of the coefficient matrix: ");
scanf("%d",&n);
printf("Enter the elements row-wise: ");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%f",&a[i][j]);
printf("Enter the right hand vector: ");
for(i=0;i<n;i++)
scanf("%f",&b[i]);

//Computation oof L and U matrices
for(i=0;i<n;i++)
l[i][1]=a[i][1];
for(j=2;j<=n;j++)
u[1][j]=a[1][j]/l[1][1];
for(i=0;i<n;i++)
u[i][i]=1;
for(i=2;i<=n;i++)
for(j=2;j<=n;j++)
if(i>=j)
{
l[i][j]=a[i][j];
for(k=1;k<=j-1;k++)
l[i][j]-=l[i][k]*u[k][j];
}
else
{
u[i][j]=a[i][j];
for(k=1;k<=j-1;k++)
u[i][j]=-l[i][k]*u[k][j];
u[i][j]/=l[i][i];
}
printf("\nThe lower triangular matrix L: \n");
for(i=0;i<=n;i++)
{
for(j=0;j<n;j++)
printf("%f ",l[i][j]);
printf("\n");
}
printf("\nThe upper triangular matrix U: \n");
for(i=0;i<=n;i++)
{
for(j=0;j<i;j++)
printf(" ");
for(j=i;j<n;j++)
printf("%f ",l[i][j]);
printf("\n");
}

//solve Lz=b by forward substitution
z[1]=b[1]/l[1][1];
for(j=1;i<n;i++)
{
z[i]=b[i];
for(j=0;j<i-1;j++)
z[i]-=l[i][j]*z[j];
z[i]/=l[i][i];
}

//solve Ux=z by backward substitution
x[n]=z[n];
for(i=n-1;i>=0;i--)
{
x[i]=z[i];
for(j=i+1;j<n;j++)
x[i]-=u[i][j]*x[j];
}
printf("The solution is: ");
for(i=0;i<n;i++)
printf("%f ",x[i]);
}

Output

Enter the size of the coefficient matrix 3
Enter the elements row-wise
4   2    1

2   5   -2

1   -2   7

Enter the right hand vector

3   4   5

The lower triangular matrix L:

4.000000

2.000000   4.000000

1.000000   -2.5000000   5.187500

The upper triangular matrix U:

1.000000   0.500000   0.250000

1.000000   -0.625000

1.000000

The solution is  -0.192771   1.325301   1.120482

 Example

## Coming Soon 🙂

<< Previous     Next>>

;