Autar Kaw

Benjamin Rigsby

http://nm.MathForCollege.com
Transforming Numerical Methods Education for STEM Undergraduates
http://nm.MathForCollege.com
1. LU Decomposition is another method to solve

a set of simultaneous linear equations

2. Which is better, Gauss Elimination or LU

Decomposition?
 Method
For most non-singular matrix [A] that one could conduct
Naïve Gauss Elimination forward elimination steps, one
can always write it as

[A] = [L][U]
where
[L] = lower triangular matrix
[U] = upper triangular matrix
 If solving a set of linear equations [A][X] = [C]
If [A] = [L][U] then [L][U][X] = [C]
Multiply by [L]-1
Which gives [L]-1[L][U][X] = [L]-1[C]
Remember [L]-1[L] = [I] which leads to [I][U][X] = [L]-1[C]
Now, if [I][U] = [U] then [U][X] = [L]-1[C]
Now, let [L]-1[C]=[Z]
Which ends with [L][Z] = [C] (1)
and [U][X] = [Z] (2)
 How can this be used?

Given [A][X] = [C]

1. Decompose [A] into [L] and [U]
2. Solve [L][Z] = [C] for [Z]
3. Solve [U][X] = [Z] for [X]
 Solve [A][X] = [B]
T = clock cycle time and n n = size of the matrix
Forward Elimination Decomposition to LU
 8n 3 32n   8n 3 20n 
CT | FE = T  + 8n 2 −  CT | DE = T  + 4n 2 − 
 3 3   3 3 

Back Substitution Forward Substitution

(
CT | BS = T 4n 2 + 12n ) (
CT | FS = T 4n 2 − 4n )
Back Substitution
(
CT | BS = T 4n 2 + 12n )
 To solve [A][X] = [B]
Time taken by methods
Gaussian Elimination LU Decomposition

 8n3 4n   8n3 4n 
T  + 12n 2 +  T  + 12n 2 + 
 3 3   3 3 

T = clock cycle time and n n = size of the matrix

So both methods are equally efficient.

Time taken by Gaussian Elimination Time taken by LU Decomposition
= n(CT |FE +CT |BS ) = CT |LU + n  CT |FS + n  CT |BS
 8n 4 4n 2   32n3 20n 
= T  + 12n +
3
 = T  + 12n 2 + 
 3 3   3 3 
Time taken by Gaussian Elimination Time taken by LU Decomposition
 8n 4 4n 2   32n3 20n 
T  + 12n +
3
 T  + 12n 2 − 
 3 3   3 3 

Table 1 Comparing computational times of finding inverse of a matrix using LU

decomposition and Gaussian elimination.
n 10 100 1000 10000
CT|inverse GE / CT|inverse LU 3.288 25.84 250.8 2501

For large n, CT|inverse GE / CT|inverse LU ≈ n/4

http://numericalmethods.eng.usf.edu
 1 0 0 u11 u12 u13 
A = LU  =  21 1 0  0 u 22 u 23 
 31  32 1  0 0 u 33 

[U] is the same as the coefficient matrix at the end of the forward elimination step.
[L] is obtained using the multipliers that were used in the forward elimination process
 Using the Forward Elimination Procedure of Gauss Elimination

 25 5 1
 64 8 1
 
144 12 1
 25 5 1 
= 2.56; Row2 − Row1(2.56) =  0 − 4.8 − 1.56
64
Step 1:
25
144 12 1 

25 5 1 
= 5.76; Row3 − Row1(5.76) =  0 − 4.8 − 1.56 
144
25
 0 − 16.8 − 4.76
 25 5 1 
Matrix after Step 1:  0 − 4.8 − 1.56 
 
 0 − 16.8 − 4.76

25 5 1 
− 16.8
Step 2: = 3.5; Row3 − Row2(3.5) =  0 − 4.8 − 1.56
− 4.8
 0 0 0.7 

25 5 1 
U  =  0 − 4.8 − 1.56
 0 0 0.7 
 1 0 0
 1 0
 21
 31  32 1

Using the multipliers used during the Forward Elimination Procedure

a 21 64
 25 5 1  21 = = = 2.56
From the first step of
forward elimination
 64 8 1 a11 25
   31 =
a31 144
= = 5.76
144 12 1 a11 25
From the second step 25 5 1 
0  a32 − 16.8
of forward

 =
− 4.8 − 1.56  32 a = − 4.8 = 3.5
elimination 22
 0 − 16.8 − 4.76

 1 0 0
L = 2.56 1 0
5.76 3.5 1
  1 0 0 25 5 1 
LU  = 2.56 1 0  0 − 4.8 − 1.56 = ?
5.76 3.5 1  0 0 0.7 
Solve the following set of  25 5 1  x1  106.8 
linear equations using LU  64 8 1  x  = 177.2 
Decomposition
   2  
144 12 1  x3  279.2

Using the procedure for finding the [L] and [U] matrices

 1 0 0 25 5 1 
A = LU  = 2.56 1 0  0 − 4.8 − 1.56
5.76 3.5 1  0 0 0.7 
Set [L][Z] = [C]  1 0 0  z1  106.8 
2.56 1 0  z  = 177.2 
  2   
5.76 3.5 1  z 3  279.2

Solve for [Z] z1 = 10

2.56 z1 + z 2 = 177.2
5.76 z1 + 3.5 z 2 + z 3 = 279.2
 Complete the forward substitution to solve for [Z]

z1 = 106.8
z 2 = 177.2 − 2.56 z1  z1   106.8 
= 177.2 − 2.56(106.8)
= −96.2
Z  =  z2  = − 96.21
z3 = 279.2 − 5.76 z1 − 3.5 z 2  z3   0.735 
= 279.2 − 5.76(106.8) − 3.5(− 96.21)
= 0.735
Set [U][X] = [Z]
25 5 1   x1   106.8 
 0 − 4.8 − 1.56  x  = − 96.21
   2  
 0 0 0.7   x3   0.735 

Solve for [X] The 3 equations become

25a1 + 5a2 + a3 = 106.8

− 4.8a2 − 1.56a3 = −96.21
0.7a3 = 0.735
 Substituting in a3 and using the second
From the 3rd equation equation

0.7 a3 = 0.735 − 4.8a2 − 1.56a3 = −96.21

a3 =
0.735 − 96.21 + 1.56a3
a2 =
0.7 − 4.8
a3 = 1.050 − 96.21 + 1.56(1.050)
a2 =
− 4.8
a2 = 19.70
Substituting in a3 and a2 using the Hence the Solution Vector is:
first equation

25a1 + 5a2 + a3 = 106.8

 a1  0.2900
106.8 − 5a2 − a3 a  =  19.70 
a1 =
25
 2  
106.8 − 5(19.70) − 1.050
 a3   1.050 
=
25
= 0.2900
The inverse [B] of a square matrix [A] is defined as

[A][B] = [I] = [B][A]

How can LU Decomposition be used to find the inverse?
Assume the first column of [B] to be [b11 b12 … bn1]T
Using this and the definition of matrix multiplication

First column of [B] Second column of [B]

b11  1  b12  0
b  0  b  1
A  21  =   A  22  =  
         
       
bn1  0 bn 2  0

The remaining columns in [B] can be found in the same manner

 Find the inverse of a square matrix [A]
 25 5 1
A =  64 8 1
144 12 1

Using the decomposition procedure, the [L] and [U] matrices are found to be

 1 0 0 25 5 1 
A = LU  = 2.56 1 0  0 − 4.8 − 1.56
5.76 3.5 1  0 0 0.7 
Solving for the each column of [B] requires two steps
1) Solve [L] [Z] = [C] for [Z]
2) Solve [U] [X] = [Z] for [X]

 1 0 0  z1  1
Step 1: LZ  = C  → 2.56 1 0  z2  = 0
5.76 3.5 1  z3  0
This generates the equations:
z1 = 1
2.56 z1 + z2 = 0
5.76 z1 + 3.5 z2 + z3 = 0
Solving for [Z]

z1 = 1
 z1   1 
z 2 = 0 − 2.56 z1
= 0 − 2.56(1)
Z  =  z2  = − 2.56
= −2.56  z3   3.2 
z3 = 0 − 5.76 z1 − 3.5 z 2
= 0 − 5.76(1) − 3.5(− 2.56 )
= 3.2
 25 5 1  b11   1 
Solving [U][X] = [Z] for [X]
 0 − 4.8 − 1.56 b  = − 2.56
   21   
 0 0 0.7  b31   3.2 

25b11 + 5b21 + b31 = 1

− 4.8b21 − 1.56b31 = −2.56
0.7b31 = 3.2
Using Backward Substitution
3.2
b31 = = 4.571 So the first column of the
0.7
inverse of [A] is:
−2.56 + 1.560b31
b21 =
−4.8 b11   0.04762 
−2.56 + 1.560(4.571) b  = − 0.9524
= = −0.9524
−4.8  21   
b11 =
1 − 5b21 − b31 b31   4.571 
25
1 − 5(− 0.9524 ) − 4.571
= = 0.04762
25
Repeating for the second and third columns of the inverse

Second Column Third Column

 25 5 1 b12  0  25 5 1  b13  0
 64 8 1 b  = 1  64 8 1 b  = 0
   22       23   
144 12 1 b32  0 144 12 1 b33  1
b12  − 0.08333 b13   0.03571 
b  =  1.417  b  = − 0.4643
 22     23   
b32   − 5.000  b33   1.429 
 The inverse of [A] is

 0.04762 − 0.08333 0.03571 

A−1 = − 0.9524 1.417 − 0.4643
 4.571 − 5.000 1.429 

To check your work do the following operation

[A][A]-1 = [I] = [A]-1[A]

For all resources on this topic such as digital audiovisual
lectures, primers, textbook chapters, multiple-choice tests,
worksheets in MATLAB, MATHEMATICA, MathCad and
MAPLE, blogs, related physical problems, please visit

http://numericalmethods.eng.usf.edu/topics/lu_decompositio
n.html
 THE END

http://numericalmethods.eng.usf.edu