Numerické metody
11. přednáška, 2. května 2017
Jiří Zelinka
Jiří Zelinka Numerické metody 11. přednáška, 2. května 2017 1 / 13
Ř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, 2. května 2017 2 / 13
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, 2. května 2017 3 / 13
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, 2. května 2017 4 / 13
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, 2. května 2017 5 / 13
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, 2. května 2017 6 / 13
(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, 2. května 2017 7 / 13
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, 2. května 2017 8 / 13
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, 2. května 2017 9 / 13
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, 2. května 2017 10 / 13
Příklad
2x1 + 4x2 − x3 = −5
x1 + x2 − 3x3 = −9
4x1 + x2 + 2x3 = 9
Jiří Zelinka Numerické metody 11. přednáška, 2. května 2017 11 / 13
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.
Příklad:
LR rozklad matice
A =
0, 0001 1
1 1
.
se zaokrouhlováním na 3 platné číslice.
Jiří Zelinka Numerické metody 11. přednáška, 2. května 2017 12 / 13
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, 2. května 2017 13 / 13
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, 2. května 2017 14 / 13
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, 2. května 2017 15 / 13