4. Trojúhelníkový rozklad
4. Trojúhelníkový rozklad ­ p. 1/20
Trojúhelníkový rozklad
1. Permutační matice
2. Trojúhelníkové matice
3. Trojúhelníkový (LU) rozklad
4. Výpočet LU rozkladu
5. Řešení soustav pomocí LU rozkladu
6. Použití LU rozkladu
4. Trojúhelníkový rozklad ­ p. 2/20
4.1 Permutační matice
DEFINICE 1
Matice P se nazývá permutační matice, je-li možno P
získat z jednotkové matice I stejného typu postupnou
výměnou řádků.
Výměnu i-tého a j-tého řádku dané matice můžeme
provést tak, že tuto matici vynásobíme zleva elementární
permutační maticí Pij, je možno každou permutační
matici P zapsat ve tvaru
P = Pikjk
   Pi1j1
I = Pikjk
   Pi1j1
.
4. Trojúhelníkový rozklad ­ p. 3/20
4.1 Permutační matice
P ŘÍKLAD 1
I =
1 0 0
0 1 0
0 0 1
r3
r1

0 0 1
0 1 0
1 0 0
r2
r1 
0 1 0
0 0 1
1 0 0
= P,
takže P můžeme zapsat ve tvaru
P = P12P13I = P12P13.
LEMMA 1 Pro libovolnou permutační matici P platí P-1
= P
D ŮKAZ: Zřejmě platí Pij = P
ij. Pak z P-1
ij = Pij plyne
PP
= Pikjk
   Pi1j1 (Pikjk
   Pi1j1 )
= Pikjk
   Pi1j1 P
i1j1
   P
ikjk
= Pikjk
   Pi1j1 Pi1j1    Pikjk
= P-1
ikjk
   P-1
i1j1
Pi1j1    Pikjk
= I
4. Trojúhelníkový rozklad ­ p. 4/20
4.1 Permutační matice
Elementární permutační matice Pij můžeme také použít k výměně
i-tého a j-tého sloupce. K tomu stačí násobit maticí Pij zprava.
P ŘÍKLAD 2 Například vynásobíme-li matici A = [aij] řádu 2
maticí P12 zprava, dostaneme
AP12 =
a11 a12
a21 a22
0 1
1 0 =
a12 a11
a22 a21
= sA
2 , sA
1 .
K odvození obecného pravidla pro permutaci sloupců můžeme
použít transponování.
4. Trojúhelníkový rozklad ­ p. 5/20
4.2 Trojúhelníkové matice
DEFINICE 2
Čtvercová matice L(U) se nazývá dolní (horní) trojúhelníková matice,
jestliže má nad (pod) diagonálou všechny prvky nulové. Pro
prvky lij dané dolní trojúhelníkové matice L tedy platí lij = 0 pro
i < j, zatímco pro prvky uij dané horní trojúhelníkové matice U
platí uij = 0 pro i > j.
LEMMA 2 Součin dvou trojúhelníkových matic stejného typu je
trojúhelníková matice téhož typu.
D ŮKAZ: Jsou-li například L = [lij] a M = [mij] dvě dolní trojúhelníkové matice
a i < j, pak
[LM]ij = li1m1j +  +linmnj = li10+  +lii0+0mi i+1+  +0min = 0,
takže LM je také dolní trojúhelníková matice.
4. Trojúhelníkový rozklad ­ p. 6/20
4.2 Trojúhelníkové matice
V ĚTA 1
Nechť L = [lij] je čtvercová dolní trojúhelníková matice
s nenulovými diagonálními prvky. Pak L je regulární a L-1
je dolní
trojúhelníková matice.
D ŮKAZ: Je-li L dolní trojúhelníková matice s nenulovými prvky na diagonále,
pak existují matice elementárních operací Tp = Gipjp
(p) s ip < jp, případně
Tp = Mip
(l-1
ipip
) tak, že pro matici T = Tk    T1 platí
T L|I = I|B .
Porovnáním levých částí příslušných matic dostaneme TL = I. Odtud tedy platí
L = T-1
, odkud dle definice inverzní matice je LT = I a T = L-1
. Jelikož
všechny matice Ti jsou dolní trojúhelníkové, je také matice
L-1
= T = Tk    T1
dolní trojúhelníková matice.
4. Trojúhelníkový rozklad ­ p. 7/20
4.3 Trojúhelníkový (LU) rozklad
V ĚTA 2
Nechť A je regulární čtvercová matice. Pak existuje
dolní trojúhelníková matice L, horní trojúhelníková matice
U a permutační matice P tak, že
AP = LU.
Matice L, U jsou regulární.
D ŮKAZ: Nechť A = [aij] je čtvercová matice řádu n.
Z regulárnosti matice A plyne, že existuje i1 tak, že a1i1 = 0.
Takže A = AP1i1 má v levém horním rohu nenulový prvek
a11 = a1i1 .
4. Trojúhelníkový rozklad ­ p. 8/20
4.3 Trojúhelníkový (LU) rozklad
D ŮKAZ: Pokračování
První krok úpravy matice A, který známe z Gaussovy eliminace,
můžeme zapsat ve tvaru
L1AP1i1 = A1,
kde
A1 =




a11 a12 . . . a1n
0 a1
22 . . . a1
2n
...
...
...
...
0 a1
n2 . . . a1
nn



 =




a1
11 a1
12 . . . a1
1n
0 a1
22 . . . a1
2n
...
...
...
...
0 a1
n2 . . . a1
nn




a
L1 = G1n(-an1/a11)    G12(-a21/a11)
je dolní trojúhelníková matice, neboť je vyjádřena jako součin
dolních trojúhelníkových matic.
4. Trojúhelníkový rozklad ­ p. 9/20
4.3 Trojúhelníkový (LU) rozklad
D ŮKAZ: Pokračování
Matice A1 je zřejmě součinem regulárních matic, takže je A1 také
regulární a existuje i2  2 tak, že a1
2i2
= 0. Matice A1 = A1P2i2 má
tedy nenulový prvek a22 a stejný první sloupec jako matice A1.
Opakováním tohoto postupu dosáhneme toho, že
LAP = U,
kde
U =




an-1
11 an-1
12 . . . an-1
1n
0 an-1
22 . . . an-1
2n
...
...
...
...
0 0 . . . an-1
nn



 = An-1
a
P = P1i1    Pn-1 in-1 , L = Ln-1    L1.
4. Trojúhelníkový rozklad ­ p. 10/20
4.3 Trojúhelníkový (LU) rozklad
D ŮKAZ: Pokračování
P je zřejmě permutační matice a L je dolní trojúhelníková matice,
neboť každá matice Li je součinem dolních trojúhelníkových matic
Gij(-ai-1
ji /ai-1
ii ) s i < j. Přenásobíme-li rovnici LAP = U zleva
maticí L = L-1
, dostaneme
AP = LU.
Matice L je regulární dolní trojúhelníková matice, neboť je inverzní
k dolní trojúhelníkové matici L. Jelikož jsou matice A, P, L
regulární, je také matice U = LAP regulární.
Vyjádření matice ve tvaru součinu AP = LU se nazývá LU rozklad
podle počátečních písmen anglických slov Lower (dolní) a Upper
(horní). Matice L, U a P nejsou určeny jednoznačně.
4. Trojúhelníkový rozklad ­ p. 11/20
4.4 Výpočet LU rozkladu
Dle důkazu předchozí věty lze LU rozklad matice A nalézt
následovně:
1. Úprava A|I  U|L
Nesmíme přičítat násobky řádků s vyšším indexem k
řádkům s indexem nižším.
Nesmíme vyměňovat řádky
Pokud to je nutné, můžeme vyměnit sloupce a tyto výměny
budeme zaznamenávat stejnými úpravami jednotkové
matice t.j. I  P, kde P je hledaná permutační matice.
2. Vypočteme L = L-1
úpravou L|I  I|L .
K této úpravě opět nesmíme použít elementární řádkové
operace popsané v 1.
4. Trojúhelníkový rozklad ­ p. 12/20
4.4 Výpočet LU rozkladu
P ŘÍKLAD 3 Úprava A|I  U|L :
A|I =
0 -1 2 1 0 0
-1 2 -1 0 1 0
2 -1 0 0 0 1
s3  s1

2 -1 0 1 0 0
-1 2 -1 0 1 0
0 -1 2 0 0 1
2 + r1 

2 -1 0 1 0 0
0 3 -2 1 2 0
0 -1 2 0 0 1 3 + r2

2 -1 0 1 0 0
0 3 -2 1 2 0
0 0 4 1 2 3
=
= U|L
Sledování výměn sloupců:
I =
1 0 0
0 1 0
0 0 1
s3  s1

0 0 1
0 1 0
1 0 0
= P
4. Trojúhelníkový rozklad ­ p. 13/20
4.4 Výpočet LU rozkladu
P ŘÍKLAD 3 Pokračování
Výpočet L = L-1
úpravou L|I  I|L :
L|I =
1 0 0 1 0 0
1 2 0 0 1 0
1 2 3 0 0 1
-r1
-r1

1 0 0 1 0 0
0 2 0 -1 1 0
0 2 3 -1 0 1 -r2




1 0 0 1 0 0
0 2 0 -1 1 0
0 0 3 0 -1 1

1
2
1
3



1 0 0 1 0 0
0 1 0 -1
2
1
2
0
0 0 1 0 -1
3
1
3

 =
= I|L
L =


1 0 0
-1
2
1
2
0
0 -1
3
1
3

 , U =
2 -1 0
0 3 -2
0 0 4
, P =
0 0 1
0 1 0
1 0 0
.
Přímým výpočtem si můžeme ověřit, že platí AP = LU. 4. Trojúhelníkový rozklad ­ p. 14/20
4.4 Výpočet LU rozkladu
Uvedený postup výpočtu LU rozkladu je spíše vhodný pro ruční
výpočet. Pro počítačové nalezení LU rozkladu bychom využili
následujících poznatků.
Předpokládejme, že provádíme úpravu A|I  U|L a máme
upraveno k - 1 sloupců. Pak
Ak-1 =










ak-1
1,k
...
ak-1
k,k
ak-1
k+1,k
...
ak-1
n,k










Lk










ak
1,k
...
ak
k,k
0
...
0









, Lk =








1 . . . 0 0 . . . 0
...
...
...
...
...
0 . . . 1 0 . . . 0
0 . . . -lk+1,k1 . . . 0
...
...
...
...
...
0 . . . -ln,k 0 . . . 1








kde li,k = ak-1
i,k /ak-1
k,k , i = k + 1, . . . , n. 4. Trojúhelníkový rozklad ­ p. 15/20
4.4 Výpočet LU rozkladu
Po n - 1 úpravách obdržíme U = LA, kde L = Ln-1    L1. Pro
hledanou matici L ovšem platí
L = L-1
= L-1
1    L-1
n-1.
Pak se dá snadno dokázat, že
L-1
k =








1 . . . 0 0 . . . 0
...
...
...
...
...
0 . . . 1 0 . . . 0
0 . . . lk+1,k1 . . . 0
...
...
...
...
...
0 . . . ln,k 0 . . . 1








a L =








1 . . . 0 0 . . . 0
...
...
...
...
...
lk,1 . . . 1 0 . . . 0
lk+1,1 . . . lk+1,k 1 . . . 0
...
...
...
...
...
ln1 . . . ln,k ln,k+1. . . 1








Případné výměny sloupců se budou opět zaznamenávat do I čímž
obdržíme permutační matici P.
4. Trojúhelníkový rozklad ­ p. 16/20
4.4 Výpočet LU rozkladu
S použitím výše uvedených poznatků můžeme navrhnout algoritmus
pro přímé nalezení LU rozkladu matice A:
Algoritmus
U = A, L = I
for k = 1 to n - 1 do
for i = k + 1 to n do
li,k = ui,k/uk,k
ui,k:n = ui,k:n - li,kuk,k:n
end for
end for
4. Trojúhelníkový rozklad ­ p. 17/20
4.5 Řešení soustav pomocí LU rozkladu
Přenásobíme-li AP = LU zprava maticí P = P
, dostaneme
vyjádření A ve tvaru
A = LUP
s permutační maticí P.
Místo soustavy Ax = b pak budeme řešit soustavu
L U Px = b
tak, že postupně vyřešíme
1. Lz = b tzv. dopřednou substitucí
2. Uy = z tzv. zpětnou substitucí
3. Px = y permutací složek řešení.
4. Trojúhelníkový rozklad ­ p. 18/20
4.5 Řešení soustav pomocí LU rozkladu
P ŘÍKLAD 4 Využijte LU rozkladu z příkladu 3 k řešení soustavy:
-x2 + 2x3 = 1
-x1 + 2x2 - x3 = 1
2x1 - x2 = 1
ŘEŠENÍ: Nejprve řešíme soustavu Lz = b, tedy
z1 = 1
-1
2 z1 + 1
2 z2 = 1
- 1
3 z2 + 1
3 z3 = 1
odkud z1 = 1, z2 = 3, z3 = 6. Potom vyřešíme soustavu Uy = z, tedy
2y1 - y2 = 1
3y2 - 2y3 = 3
4y3 = 6
Odtud y1 = 3
2 , y2 = 2, y3 = 3
2 .
Konečně určíme x řešením Px = y nebo z x = Py, takže
x1 = 3
2 ,x2 = 2,x3 = 3
2 . 4. Trojúhelníkový rozklad ­ p. 19/20
4.6 Použití LU rozkladu
LU rozklad je základním prostředkem pro řešení
soustav lineárních rovnic
Výpočetní náročnost je řádově stejná jako u
Gaussovy eliminace, tj.  1
3n3
LU rozklad je velmi efektivní nástroj pro řešení
soustav s více pravými stranami (pro různé pravé
strany stačí pouze řešit dopřednou a zpětnou
substituci)
LU rozkladu je možné využít i k nalezení inverzní
matice neboť
A = LUP  A-1
= PU-1
L-1
LU rozklad je taktéž velmi důležitý teoretický
nástroj 4. Trojúhelníkový rozklad ­ p. 20/20