Factorization Methods and

Matrix Inversion
Chapter 2

LU Decomposition
Computational complexity
The Matrix Inverse
Extending the Gaussian Elimination
Process

1
LU Decomposition /LU factorization

LU-D is a Mathematical method to separate/factorize

square matrix A
𝑎11 … … … 𝑎1𝑛
A= . ……… .
𝑎𝑛1 … … … . 𝑎𝑛𝑛 nxn

To be the product of 2 matrices

 Lower Triangular Form( LTF)

 Upper Triangular Form(UTF)
2
Revision

3
4
 LU Decomposition /LU factorization

[ A ] {X} = {B}
A=[ L ][U]

L : Lower Triangular Matrix ( LTM)

1 0 0 𝑎11 𝑎12 𝑎13

𝑚21 1 0 0 𝑎′22 𝑎′23
𝑚31 𝑚32 1 0 0 𝑎′′33
U : Upper Triangular Matrix ( UTM)

5
 LU Decomposition /LU factorization

[ A ] {X} = {B}
A= [ L ][U]

L : Lower Triangular Matrix ( LTM)

𝑎11 𝑎12 𝑎13
𝑎21 𝑎22 𝑎23 1 0 0 𝑎11 𝑎12 𝑎13
A= 𝑎31 𝑎32 𝑎33 𝑚21 1 0 0 𝑎′22 𝑎′23
= 𝑚31 𝑚32 1 0 0 𝑎′′33
U : Upper Triangular Matrix ( UTM)

6
 LU Decomposition /LU factorization

[ A ] {X} = {B}
[ L ][U] {X} = {B}

L : Lower Triangular Matrix ( LTM)

1 0 0 𝑎11 𝑎12 𝑎13

𝑚21 1 0 0 𝑎′22 𝑎′23
𝑚31 𝑚32 1 0 0 𝑎′′33
U : Upper Triangular Matrix ( UTM)

7
 LU Decomposition /LU factorization

The purpose is to solve system algebraic linear

equations easily by changing the coefficients matrix A
[ U ] {X} = {D}
Step 1 .
[ L ][D] = {B}
Solve [L] { D} = {B} to generate an intermediate vector { D}
by forward substitution
Step 2

Solve [U] { X} ={D} to get { X} by back substitution

8
 LU-Decomposition Procedure

1. Write the system algebraic in matrix formula

AX=b
2. Find LU –Decomposition of matrix A
LU=A
3. Rewrite the given system in the form of lower triangular form
Ld=b
4. Solve (3) using forward substitution to find the values d1..., dn

5. Substitute the values of d1..,dn in the upper triangular

formula ( UTF)
U x=d

9
 LU-Decomposition Procedure

6. Solve (4) using back substitution to find the values x1…..xn

7. Check the validity of the values x1, … .xn

The solution is { x1 ….., xn }

10
 Example 1
Derive LU-D for the coefficients matrix of the following system:

𝑥1 + 2𝑥2 + 3𝑥3 = 9
2𝑥1 − 𝑥2 + 𝑥3 = 8
3𝑥1 − 𝑥3 =3
Solution
1 2 3
1. A= 2 −1 1
3 0 −1

-2R1 + R2 1 2 3
2. A
-3R1 + R3
0 −5 −5 = U1
0 −6 −10
11
 Example 1
Solution (cont..) How to obtain the factorization ?

-6/5R1 + R3 1 2 3
U1 0 −5 −5 = U2 = Upper Triangular Form
0 0 −4

Derive
𝑎21 2
1 0 0 𝑙∗21 = = =2
𝑎11 1
3.
𝐿1 = 𝑙 ∗ 21 1 0
𝑎31 3
𝑙 ∗ 31 𝑙32 1 ∗
𝑙 31 = = =3
𝑎11 1

* Means known
12
 Example 1
Solution (cont..)

𝑎′32 −6
Derive L2 𝑙∗ 32 =𝑎′ = = 1.2
22 −5
1 0 0
𝐿2 = 2 1 0 the Lower triangular
3 1.2 1 form

1 0 0 1 2 3 1 2 3
4. LU = 2 1 0 0 −5 −5 = 2 −1 1 =A
3 1.2 1 0 0 −4 3 0 −1

5. Since LU = A then L and U are LU decomposition of A

13
 Example2
Solve the following system using LU-D method
𝑥1 + 2𝑥2 + 3𝑥3 = 9
2𝑥1 − 𝑥2 + 𝑥3 = 8
3𝑥1 − 𝑥3 =3
Solution
1 2 3 𝑥1 9
2 −1 1 𝑥2 = 8
1. 3 0 −1 𝑥3 3

1 2 3 1 0 0 1 2 3
2.
2 −1 1 = 2 1 0 0 −5 −5
3 0 −1 3 1.2 1 0 0 −4 Forward
Substitution
3. 1 0 0 𝑑1 9
2 1 0 𝑑2 = 8
3 1.2 1 𝑑3 3
14
Solution (cont..)

𝑑1 = 9
4.
2𝑑1 + 𝑑2 = 8
2(9) + 𝑑2 = 8
18 + 𝑑2 = 8
d2= -10
3𝑑1 + 1.2𝑑2 + 𝑑3 = 3
3(9) +1.2 (-10) + 𝑑3 = 3
27 – 12 +𝑑3 = 3
15 +𝑑3 = 3
d3 = -12
15
Solution (cont..)

1 2 3 𝑥1 9
Backward
0 −5 −5 𝑥2 = −10
5.
substitution
0 0 −4 𝑥3 −12

6. −12
X3 = =3
−4

−5𝑥2 − 5𝑥3 = −10

−5𝑥2 − 5 3 = −10
−5𝑥2 − 15 = −10
−5𝑥2 = 15 − 10
−5𝑥2 = 5
X2 = -1
16
Solution (cont..)

𝑥1 + 2𝑥2 + 3𝑥3 = 9
𝑥1 +2(-1) + 3( 3) = 9
𝑥1 − 2 + 9 = 9
x1 = 2
7. Check….
The solution is { 2, -1, 3 }

17
 The Matrix Inverse

• Find matrix  A
1
the inverse of [A], for which

−1
𝐴 𝐴 = 𝐴−1 𝐴 = 𝐼

• The inverse can be computed in a column-by-

column fashion by generating solutions with
unit vectors {B} constants.

18
 1
• The solution of [L][U]{X}={B} with    0
0
. will be the first column of  A1  

0
•The solution of [L][U]{X}={B} with
   1
will be the second column of A1 0
 

•The solution of [L][U]{X}={B} with 0

   0
will be the third column of A1 1
 

19
Example 2:
Use LU decomposition to determine the matrix
inverse for the following system and use it to
find the solution:
3x1 – 0.1x2 – 0.2x3 = 7.85
0.1x1 + 7x2 – 0.3x3 = -19.3
0.3x1 – 0.2x2 + 103 = 71.4

use 6 significant figures in your computation.

20
 Example 2- solution

In matrix form  3  0.1  0.2

A  0.1 7  0.3
0.3  0.2 10 
The triangular factorization of [ A ]
 1 0 0 3  0.1  0.2 
L  0.0333333 1 0 U  0 7.00333  0.293333
   
 0.100000  0.0271300 1 0 0 10.0120 
The first column of of [ A ]-1

 1 0 0 d1  1  1 
0.0333333      
1 0 d 2   0  D   0.03333
 
 0.100000  0.0271300 1    
d3  0
 0.1009 
 

21
3  0.1  0.2   x1  1  0.33249 
0 7.00333  0.293333  x    0.03333  X    0.00518
  2     
0 0 10.0120    
 x3   0.1009 
  0.01008
 

The second column of of [ A ]-1

 1 0 0 d1  0 0 
0.0333333      
1 0 d 2   1   D  1 
 
 0.100000  0.0271300 1 
 3
d  0
 
0.02713
 

3  0.1  0.2   x1  0  0.004944

0 7.00333  0.293333  x   1 
   
 
 2     
X 0.142903

0 0 10.0120     
 x3  0.02713
0.00271 
 

22
 The third column of [ A ]-1
 1 0 0 d1  0 0
0.0333333      
1 0 d 2   0  D  0
 
 0.100000  0.0271300 1   1 
 3  
d 1 
 

3  0.1  0.2   x1  0 0.006798

0 7.00333  0.293333  x   0  X   0.004183
  2     
0 0 10.0120     
 x3  1 
0.09988 
 

The matrix inverse [ A] -1 is

 0.33249 0.004944 0.006798

A1   0.00518 0.142903 0.004183
 
 0.01008 0.00271 0.09988 

23
 • Check your result by verifying that [ A ] [A ]-1 = [I]

• The final solution is

 0.33249 0.004944 0.006798 7.85  3 

X   A1B   0.00518 0.142903 0.004183  19.3   2.50002
 0.01008 0.00271 0.09988  71.4  7 


24
 Extending the Gaussian Elimination Process

If pivoting is required to solve [A]{X}={B}, then there exists a

permutation matrix [P] so that:
[P][A ]=[L][U]
The solution {X} is found in four steps:
• Construct the matrices [L], [U] and [P].
• Compute the column vector [P]{B}.
• Solve [L]{D}=[P]{B} for {D} using forward substitution.
• Solve [U]{X}={D} for {X} using back substitution.

Example 3
Use LU decomposition with permutation to solve the following
system of equations

0.0003 x1 + 3.0000 x2 = 2.0001

1.0000 x1 + 1.0000 x2 = 1.0000
25
Example 3- Solution

• In matrix form [ A] {X} = { B}

0.0003 3  x1  2.0001
 1    
 1 2  
x 1 

• We saw previously that pivoting is required to solve

this system of equations, hence [P][A ]=[L][U]
• The solution {X} is found in four steps:

1. Construct the matrices [L], [U] and [P].

U    
 1 0 1 1
0 1  L  
P     
0 2.9997
1 0 0.0003 1

26
 2. Compute the column vector [P]{B}.

0 1 2.0001 1 
1 0 1  
   2 .0001
3. Solve [L]{D}=[P]{B} for {D} using forward
substitution.
 1 0 d1  1  1 
0.0003 1 d   2.0001  D  1.9998
  2     

4. Solve [U]{X}={D} for {X} using back substitution.

1 1   x1  1  0.33333
0 2.9997  x   1.9998  X   0.66667
  2     

27
THE END

28