Table of Contents
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 🙂
;