CS计算机代考程序代写 LU Decomposition

LU Decomposition
CS/SE 4X03
Ned Nedialkov McMaster University January 29, 2021

Outline
LU decomposition Why needed Example
General derivation

LU decomposition Why needed Example General derivation LU decomposition
• Decompose A as A = LU, O(n3) work, where ◦ L is unit lower-triangular
◦ U is upper-triangular
• Then
Ly = b ◦ Ly=bfory: O(n2)work
• Solve
◦ Ux = y for x: O(n2) work
Ax = b L(Ux) = b,
set y = Ux
Copyright © 2021 N. Nedialkov. All rights reserved. 3/11

LU decomposition Why needed Example General derivation Why needed
• Assume we have an n × n matrix and want to solve m systems Ax = b(i), for i = 1,…,m
• If we solve each using GE, then the work is O(mn3) If m = n, O(n4)
• Suppose we solve as
◦ LU decomposition: O(n3) ◦ Solve
Ly = b(i), Ux = y, for i = 1,…,m
• The work is O(n3) + O(mn2) = O(n3 + mn2)
• Ifm=n,O(n3)
Copyright © 2021 N. Nedialkov. All rights reserved. 4/11

LU decomposition Why needed Example General derivation Example
􏰠1 −1 3􏰡×1 ×3 A=110↓
3−21 ↓ • multipliers l2,1 = 1, l3,1 = 3
1 0 01 −1 3 1 −1 3 M1A=−1 1 01 1 0= 0 2 −3 =A(1)
−3 0 1 3 −2 1 0 1 −8 • multiplier l3,2 = 1/2
Copyright © 2021 N. Nedialkov. All rights reserved.
5/11

LU decomposition
Why needed Example General derivation
We have
1 0 01 −1 3 M2A(1)=0 1 00 2 −3
0 −1 1 0 1 −8 2
1−1 3
= 0 2 −3 =A(2) =U
0 0 −6.5
M2A(1) = (M2M1)A = U
A = (M−1M−1)U 12
􏰎 􏰍􏰌 􏰏
L
To compute M−1, M−1 flip the signs of nonzero entries below the 12
main diagonal
Copyright © 2021 N. Nedialkov. All rights reserved. 6/11

LU decomposition Why needed Example General derivation
Then
100100 100 L=M−1M−1=1 1 00 1 0=1 1 0
301011 311 22
1 0 01 −1 3  1 −1 3
1 1 00 2 −3=1 1 0
3 1 1 0 0 −6.5 3 −2 1 2
􏰎 􏰍􏰌 􏰏􏰎 􏰍􏰌 􏰏 􏰎 􏰍􏰌 􏰏
LUA
12
Copyright © 2021 N. Nedialkov. All rights reserved. 7/11

LU decomposition Why needed Example General derivation General derivation
• Let li,1 = ai,1/a1,1 for l = 2,…n
 1 0 0 ··· 0a1,1 a1,2 a1,3 ··· −l2,1 1 0 ··· 0a2,1 a2,2 a2,3 ··· −l3,1 0 1 ··· 0a3,1 a3,2 a3,3 ···  .  .
a1,n
a2,n
a3,n 
 .  . 
−ln,1 0 ··· 1 an,1 an,2 an,3 ··· 􏰎 􏰍􏰌 􏰏􏰎 􏰍􏰌
M1 A
a1,1 a1,2 a1,3 ···
0 a(1) a(1) ···  2,2 2,3
an,n
􏰏
a1,n  a(1)
2,n a(1) 
.
(1) (1) (1) 0 an,2 an,3 ··· an,n
􏰎 􏰍􏰌 􏰏
A(1)
Copyright © 2021 N. Nedialkov. All rights reserved. 8/11
 0 a(1) a(1) ··· = 3,2 3,3
3,n . 

LU decomposition Why needed Example General derivation • Let li,2 = a(1)/a(1) for l = 3,…n
i,2 2,2
1 0 0 ··· 0a1,1 a1,2 a1,3 ··· 010···00a(1) a(1) ···
a1,n a(1)
2,n
a(1) 
..
 2,2 2,3
0 −l3,2 1 ··· 0 0 a(1) a(1) ···
  3,2 3,3 3,n
..
..
0 −ln,2 ··· 1
􏰎 􏰍􏰌 􏰏􏰎 􏰍􏰌
M2 A(1)
a1,1 a1,2 a1,3 ···
0 a(1) a(1) ···  2,2 2,3
(1) (1) (1) 0 an,2 an,3 ··· an,n
􏰏
a1,n  a(1)
2,n a(2) 
.
(2) (2) (2) 0 an,2 an,3 ··· an,n
􏰎 􏰍􏰌 􏰏
A(2)
 0 a(2) a(2) ··· = 3,2 3,3
3,n . 
Copyright © 2021 N. Nedialkov. All rights reserved. 9/11

LU decomposition Why needed Example General derivation
• M2A(1) = M2M1A = A(2) • Continuing in this way
Mn−1 ···M2M1A = A(n−1) = U which is upper triangular
• Multiplying by M−1 both sides i
A = 􏰁M−1M−1 ···M−1 􏰂U 1 2 n−1
􏰎 􏰍􏰌 􏰏
L
Copyright © 2021 N. Nedialkov. All rights reserved.
10/11

LU decomposition Why needed Example
• Mi is of the form 1
 …
1 
−l1  Mi =  i+1,i 
 −l …   i+2,i 
. .. ..
−ln,i 1
 …
1 M−1 =  li+1,i 1
1

   
i 
General derivation
.. ..
ln,i 1 Copyright © 2021 N. Nedialkov. All rights reserved.
 li+2,i . 
. ..
 
11/11