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


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


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.






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






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,


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



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}\]



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


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


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}\]


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



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

Implementation of LU Decomposition Method in C


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:


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


The solution is  -0.192771   1.325301   1.120482


Coming Soon 🙂


<< Previous     Next>>

Leave a Reply

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