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

LU Decomposition method 01

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

;

Leave a Reply

Your email address will not be published. Required fields are marked *