College of Engineering and Computer Science

Department of IT/CE
Lebanese French University

Numerical Analysis
Lesson #: 3
Title: LU factorization/decomposition

Fall Semester 2023 – 2024

Instructor: Dr. Mohammed Fadhil Hama
Why use LU
factorization/decomposition?
If you need to solve multiple systems of the form:

Where the matrix A remains the same, but the right-hand

side vectors b1,b2,b3​,… change.
So we can use this formula:
𝐿∙ 𝑈= 𝐴

[ ]
1 0 0 =original matrix
𝑆. 𝐹1 1 0∙
𝑆. 𝐹2 𝑆. 𝐹3 1
Lower triangular Upper triangular
 𝐿∙ 𝑈= 𝐴
How to calculate
Perform Gauss Multiply both
elimination sides by L
A ∙ 𝑥 =𝑏 U ∙ 𝑥=c 𝐋 ∙U ∙ 𝑥=c ∙ 𝐋

𝑨 ∙ 𝑥=c ∙ 𝐋 𝐋 ∙𝑐=𝑏 L=
Simple steps:
[Link] U
[Link] L Lower triangular
𝐋c∙𝑐=𝑏
[Link] L . c = b, find matrix
[Link] U . x = c, find
Ux∙ 𝑥=c
 [ ]
1 0 0
𝐿= 𝑆 . 𝐹 1 1 0

Example 1
𝑆 . 𝐹2 𝑆. 𝐹3 1

A ∙ 𝑥 =𝑏 𝑈

[ ][ ] [ ] [ ]
2 4 1 𝑥 1 Perform Gauss 2 4 1
0 1 2 𝑦 = 4 elimination
0 1 2
3 2 1 𝑧 2 0 0 15 / 2

𝐿 𝐿∙ 𝑈= 𝐴

[ ]
1 0 0
0 1 0
3
−4 1
2
 A ∙ 𝑥 =𝑏 L=
Example 1 [ ][ ] [ ]
2 4 1 𝑥 1
0 1 2 𝑦 = 4
3 2 1 𝑧 2

𝐋 ∙𝑐=𝑏

[ ][ ] [ ]
1 0 0 To find x,
𝑐1 1 𝒄𝟏 =𝟏
0 1 0 use:
3
𝑐2 = 4 𝒄𝟐=𝟒 𝐔 ∙ 𝑥=𝑐
−4 1 𝑐3 2 𝒄 𝟑=𝟑𝟑 /𝟐
2
 A ∙ 𝑥 =𝑏 U=

Example 1 [ ][ ] [ ]
2 4 1 𝑥 1
0 1 2 𝑦 = 4
3 2 1 𝑧 2 𝐋 ∙𝑐=𝑏
𝒄𝟏 =𝟏

[ ][ ] [ ]
1 0 0
𝑐1 1
0 1 0
𝑐2 = 4 𝒄𝟐=𝟒
3
2
−4 1 𝑐3 2 𝒄 𝟑=𝟑𝟑 /𝟐

𝐔 ∙ 𝑥=𝑐 (15/2) z = (33/2)(from row 3)

z = 33/15

[ ][ ] [ ]
y + 2z = 4 (from row 2)
2 4 1 𝑥 1
y + 2(33/15) = 4
0 1 2 𝑦 = 4 y = (-6/15)
0 0 15 / 2 𝑧 33/ 2 2x + 4y + z = 1 (from row 1)
2x + 4(-6/15) + (33/15) = 1
x = 3/15
Example 2

Find x and y by using LU

decomposition method:
2x + 3y = 4
9y +4x = 6
 Simple steps:
1. Find U
STEP
Solution
2. Make L
3. By L . c = b, 3

STEP 1 & A ∙ 𝑥 =𝑏 find c

4. By U . x = c, 𝐋 ∙𝑐=𝑏

[ ][ ] [ ]
2

[ ][
find x
2 3 𝑥 4 1 0 𝒄 𝟏 =𝟒
4 9 𝑦
=
6 4
2
1
𝑐1
𝑐2][]
=
4
6 𝒄 𝟐 =− 𝟐
¿
[4 – 2x(4/2)] = 0 L=
[9 – 3x(4/2)] = 3 𝐔 ∙ 𝑥=𝑐 STEP
4

U= [ 2
0
3
3 ][ ] [ ]
𝑥
𝑦
=
4 (from row
−2
2)
y = -2/3
(from row
1)
Classwork question. solve the
matrix using LU decomposition

[ ][ ] [ ]
1 3 2 𝑥 1
3 2 6 𝑦 = 2
2 4 8 𝑧 3
Solution 1. Make all numbers below diagonal to
zero to make matrix U

[ ][ ] [ ]
2. Put the scaling factors in matrix L
1 3 2 𝑥 1
Column 1 Column 2 3 2 6 𝑦 = 2
• Make 3 zero • Make -2 2 4 8 𝑧 3
3 – 1(3/1) = 0 zero
2 – 3(3/1) = -7 -2 –(-7)(-2/-7) U=
6 – 2(3/1) = 0 =0
• Make 2 zero 4 – 0(-2/-7) =
2 – 1(2/1) = 0 4
L= Simple steps:
4 – 3(2/1) = -2
U= [Link] U
8 – 2(2/1) = 4 [Link] L
3. By L . c = b,
find c
 Solution
A ∙ 𝑥 =𝑏

[ ][ ] [ ]
1 3 2 𝑥 1 L= U=
3 2 6 𝑦 = 2
2 4 8 𝑧 3

𝐋 ∙𝑐=𝑏
𝒄 𝟏=𝟏

[ ][ ] [ ]
1 0 0
𝑐1 1
3 1 0
𝑐2 = 2 𝒄 𝟐=−𝟏 Simple steps:
2
2 1 𝑐3 3 𝒄 𝟑=𝟏 . 𝟐𝟖𝟓𝟕 1. Find U
7
2. Make L
[Link] L . c = b,
find c
 Solution
A ∙ 𝑥 =𝑏

[ ][ ] [ ]
1 3 2 𝑥 1 L= U=
3 2 6 𝑦 = 2
2 4 8 𝑧 3
𝒄 𝟏=𝟏
𝐔 ∙ 𝑥=𝑐 𝒄 𝟐=−𝟏

[ ][ ] [ ]
1 3 2 𝑥 1 z = 0.3214 𝒄 𝟑=𝟏 . 𝟐𝟖𝟓𝟕
0 −7 0 𝑦 = −1 y = 0.14286 Simple steps:
x = -0.07138 1. Find U
0 0 4 𝑧 1.2857 2. Make L
3. By L . c = b,
Now you can validate your
find c
answers
Classwork question solve the matrix
using LU decomposition
 1. Make all numbers below diagonal to
Solution zero to make matrix U
2. Put the scaling factors in matrix L

[ ][ ] [ ]
1 2 3 𝑥 6
Column 1 Column 2 2 −3 2 𝑦 = 14
• Make 2 zero • Make -5 zero
3 1 −1 𝑧 −2
2 – 1(2/1) = 0 -5 –(-7)(-5/-7) = 0
-3 – 2(2/1) = -7
-10 – (-4)(-5/-7) = -
2 – 3(2/1) = -4 7.143
U=
• Make 3 zero
3 – 1(3/1) = 0
1 – 2(3/1) = -5 L= Simple steps:
-1 –3(3/1) = - U= [Link] U
10 [Link] L
3. By L . c = b,
find c
 Solution
A ∙ 𝑥 =𝑏
L=

[ ][ ] [ ]
1 2 3 𝑥 6 U=
2 −3 2 𝑦 = 14
3 1 −1 𝑧 −2

𝐋 ∙𝑐=𝑏

[ ][ ] [
1 0 0

]
𝑐1 6 𝒄 𝟏=𝟔 Simple steps:
2 1 0
𝑐 2 = 14 𝒄 𝟐=𝟐 1. Find U
5 2. Make L
3 1 𝑐3 −2 𝒄 𝟑=−𝟔 . 𝟒𝟑
7 [Link] L . c = b,
find c
 Solution
A ∙ 𝑥 =𝑏
L=

[ ][ ] [ ]
1 2 3 𝑥 6 U=
2 −3 2 𝑦 = 14
3 1 −1 𝑧 −2
𝒄 𝟏=𝟔
𝐔 ∙ 𝑥=𝑐 𝒄 𝟐=𝟐

[ ][ ] [ ]
1 2 3 𝑥 6 z=3 𝒄 𝟑=−𝟔 . 𝟒𝟑
0 −7 −4 𝑦 = 2 y = -2 Simple steps:
1. Find U
0 0 − 7.143 𝑧 − 6.43 x=1 2. Make L
3. By L . c = b,
Now you can validate your
find c
answers
Homework question solve the
matrix using LU decomposition
 End of Class

Thank you, Any questions?