Numerické metody
11. přednáška, 3. května 2018
Jiří Zelinka
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 1 / 17
Řešení systémů lin. rovnic – přímé metody
Opakování – Gaussova eliminační metoda
Úprava soustavy na soustavu s horní trojúhelníkovou maticí R:
(A | b) −→ R | ˜b
Pak provádíme tzv. zpětný chod – počítáme řešení od poslední
složky k první.
Elementární úpravy a matice úprav
Nemění řešení, každá úprava má inverzi.
1. násobení řádku nenulovou konstantou c
Ic =






1 0 · · · · · · · · · 0
0 1 0 · · · · · · 0
.
.
.
.
..
.
.
.
.
.
. c
.
.
.
.
.
.
.
.
.
0 0 · · · · · · · · · 1






, I−1
c =






1 0 · · · · · · · · · 0
0 1 0 · · · · · · 0
.
.
.
.
..
.
.
.
.
.
. 1/c
.
.
.
.
.
.
.
.
.
0 0 · · · · · · · · · 1






Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 2 / 17
2. výměna řádků i, k
Pi,k =






















1 0 · · · 0
0 1 0
...
1 0 0 · · · 0 0 0 · · · 0
0 0 0 · · · 0 1 0 · · · 0
0 0 1 0 0 · · · 0
...
...
...
...
...
...
...
0 0 1 0 0 · · · 0
0 1 0 · · · 0 0 0 · · · 0
0 0 0 · · · 0 0 1
...
...
0 0 1






















, P−1
i,k = Pi,k
Pi,k – permutační matice
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 3 / 17
3. přičtení c násobku i-tého řádku ke k-tému, i < k
Gi,k,c =
i
k














1 0 · · · 0
0 1 · · · 0
...
...
1
...
c 1
...
0 1














.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 4 / 17
G−1
i,k,c =
i
k














1 0 · · · 0
0 1 · · · 0
...
...
1
...
−c 1
...
0 1














.
Ve skutečnosti pro převod na trojúhelníkovou matici stačí 2. a
3. elementární úprava.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 5 / 17
Postup při Gaussově eliminaci
(1) výměna 1. a k-tého řádku (v případě potřeby)
(A | b) −→ A(1)
| b(1)
, A(1)
| b(1)
= P1,k · (A | b)
(1’) vynulování prvního sloupce pod hlavní diagonálou
A(1 )
| b(1 )
= G1· A(1)
| b(1)
, G1 =





1 · · · · · · 0
l21 1
...
...
...
ln1 0 · · · 1





,
lk1 = −
a
(1)
k1
a
(1)
11
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 6 / 17
(i) výměna i-tého. a k-tého řádku (v případě potřeby)
A(i)
| b(i)
= Pi,k · A(i−1 )
| b(i−1 )
(i’) vynulování i-tého sloupce pod hlavní diagonálou
A(i )
| b(i )
= Gi · A(i)
| b(i)
,
Gi =











1 · · · 0
...
... 1
li+1,i
...
...
...
0 ln,i 1











, lki = −
a
(i)
ki
a
(i)
ii
i = 2, . . . , n − 1
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 7 / 17
Gaussova eliminaca bez výměny řádků:
R | ˜b = Gn−1 · . . . G2 · G1 · (A | b)
tedy
R = Gn−1 · . . . G2 · G1 · A
odkud
G−1
1 G−1
2 . . . G−1
n−1R = A.
Matice Gi jsou dolní trojúhelníková, tedy G−i
1 jsou také dolní
trojúhelníkové, takže
A = L · R, L = G−1
1 G−1
2 . . . G−1
n−1.
L – dolní trojúhelníková matice.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 8 / 17
G−1
i =











1 · · · 0
...
... 1
−li+1,i
...
...
...
0 −lni 1











,
pak
L = G−1
1 G−1
2 . . . G−1
n−1 =





1 · · · · · · 0
−l21
...
...
...
...
...
−ln1 · · · −ln,n−1 1





.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 2018 9 / 17
LR rozklad
A = L · R: LR (též LU) rozklad matice A
Použití při řešení soustavy: substituce Rx = y, řešíme
soustavu Ly = b s dolní trojúhelníkovou maticí, pak Rx = y s
horní trojúhelníkovou maticí.
LR rozklad s výměnou řádků
Provádíme LR rozklad matice P · A, kde P je vhodná
permutační matice, která provádí výměnu řádků.
Při praktickém výpočtu, pokud narazíme na potřebu vyměnit
řádky, postupujeme takto:
Pokud bychom vyměnili řádky předem, v už vypočítané části
matice L by tyto řádky byly vyměněny, zbytek by se nezměnil.
Proto můžeme vyměnit řádky ve vypočítané části matice L.
Dále v pomocném vektoru p na začátku nastaveném na
(1, 2, . . . , n)T
zaznamenáme výměnu řádků, tedy vyměníme v
něm stejné řádky.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201810 / 17
Výběr vedoucího prvku (pivota) – částečný
Při úpravě i-tého sloupce najdeme mezi prvky a
(i−1)
ii , . . . , a
(i−1)
ni
prvek s maximální absoulutní hodnotou (např. a
(i−1)
ki ), pak
vyměníme i-tý a k-tý řádek.
Výběr vedoucího prvku (pivota) – úplný
Hledáme prvek s maximální absoultní hodnotou mezi a
(i−1)
jk ,
i ≤ j ≤ n, i ≤ k ≤ n, pak vyměníme příslušný řádek a
spoupec, čímž se změní pořadí proměnných.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201811 / 17
Věta
Nechť všechny hlavní minory matice A ∈ Mn jsou různé od
nuly, tj.
a11 = 0,
a11 a12
a21 a22
= 0,
a11 a12 a13
a21 a22 a23
a31 a32 a33
= 0, . . . det A = 0.
Pak matici A lze rozložit na součin dolní a horní trojúhelníkové
matice.
Důsledky
Nechť matice A je pozitivně definitní. Pak GEM lze
provést bez výměny řádků a sloupců.
Nechť matice A je ryze řádkově diagonálně dominantní.
Pak GEM lze provést bez výměny řádků a sloupců.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201812 / 17
Choleského rozklad
Věta
Nechť matice A je symetrická a její všechny hlavní minory
matice A ∈ Mn jsou různé od nuly, tj.
a11 = 0,
a11 a12
a21 a22
= 0, . . . , det A = 0.
Pak existuje taková horní trojúhelníková matice T ∈ Mn, že
A = TT
T.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201813 / 17
Prvky matice T = (tij ):
t11 =
√
a11, t1j =
a1j
t11
, j = 2, . . . , n,
tii = aii −
i−1
l=1
t2
li , i = 2, . . . , n
tij = 1
tii
(aij −
i−1
l=1
tli tlj ), j > i tij = 0, j < i
Příklad
x1 + 2x2 − x3 = 4
2x1 + 2x2 + 4x3 = 1
−x1 + 4x2 + 8x3 = −8
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201814 / 17
Croutova metoda
Rozklad třídiagonální matice
A =







a11 a12 0 · · · 0
a21 a22 a23 0
0
... ... ...
...
...
... ... an−1,n
0 · · · 0 an,n−1 ann







Jiří Zelinka Numerické metody 11. přednáška, 3. května 201815 / 17
A = LU
L =









l11 0 · · · 0
l21 l22 0 · · · 0
0 l32 l33 :
...
...
... 0
0 · · · 0 ln,n−1 lnn









, U =









1 u12 0 · · · 0
0 1 u23 0
...
...
...
...
... 1 un−1,n
0 · · · · · · 0 1









a11 = l11
ai,i−1 = li,i−1, i = 2, 3, . . . , n
aii = li,i−1ui−1,i + lii , i = 2, 3, . . . , n
ai,i+1 = lii ui,i+1, i = 1, 2, . . . , n − 1.
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201816 / 17
Věta
Nechť A ∈ Mn je třídiagonální matice s vlastnostmi:
ai,i−1ai,i+1 = 0, i = 2, 3, . . . , n − 1,
|a11| > |a12|,
|aii | ≥ |ai,i−1| + |ai,i+1|,
|ann| > |an,n−1|.
i = 2, . . . , n − 1, A – řádkově diagon.
dominantní
Pak matice A je regulární a hodnoty lii , i = 1, . . . , n,
vypočtené ze uvedených vztahů jsou různé od nuly.
Důsledek
Jsou-li splněny předpoklady věty, lze matici A rozložit na
součin dolní a horní trojúhelníkové matice v uvedeném tvaru.
Příklad
2x1 − x2 = 2
−x1 + 2x2 − x3 = −3
−x2 + 2x3 − x4 = 1
−x3 + 2x4 = 1.5
Jiří Zelinka Numerické metody 11. přednáška, 3. května 201817 / 17