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

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 🙂

Leave a Reply

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