Numerické metody
12. přednáška, 10. května 2019
Jiří Zelinka
Jiří Zelinka Numerické metody 12. přednáška, 10. května 20191 / 12
Opakování
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 12. přednáška, 10. května 20192 / 12
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
Konec opakování
Jiří Zelinka Numerické metody 12. přednáška, 10. května 20193 / 12
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 12. přednáška, 10. května 20194 / 12
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 12. přednáška, 10. května 20195 / 12
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.
Jiří Zelinka Numerické metody 12. přednáška, 10. května 20196 / 12
Příklad
A =






2 −1 0 0 0
−1 2 −1 0 0
0 −1 2 −1 0
0 0 −1 2 −1
0 0 0 −1 2






, A−1
=
1
6






5 4 3 2 1
4 8 6 4 2
3 6 9 6 3
2 4 6 8 4
1 2 3 4 5






Příklad
2x1 − x2 = 2
−x1 + 2x2 − x3 = −3
−x2 + 2x3 − x4 = 1
−x3 + 2x4 = 1.5
Jiří Zelinka Numerické metody 12. přednáška, 10. května 20197 / 12
Výpočet inverzní matice a determinantu
Výpočet inverzní matice k matici A je ekvivalentní řešení
systému
AX = E,
Pak řešit systém AX = E znamená řešit n systémů tvaru
A





x11
x21
...
xn1





=





1
0
...
0





, . . . A





x1n
x2n
...
xnn





=





0
0
...
1





.
K řešení lze užít některou z přímých metod (např. maticové
rozklady).
Výpočet inverzní matice je třikrát „dražší“ než řešení systému
Ax = b.
Výpočet determinantu:
GEM – pamatujeme si počet výměn řádků.
Jiří Zelinka Numerické metody 12. přednáška, 10. května 20198 / 12
Výpočet inverzní matice při malé změně A:
Shermanův-Morrisonův vzorec.
Nechť u, v jsou vektory, A ∈ Mn je regulární matice. Pak
(A − uvT
)−1
= A−1
+ α(A−1
uvT
A−1
),
kde
α =
1
(1 − vT A−1u)
,
za předpokladu vT
A−1
u = 1.
Woodburyho vzorec.
Nechť A, U, V ∈ Mn,
(A − UV T
)−1
= A−1
+ A−1
U(E − V T
A−1
U)−1
V T
A−1
,
za předpokladu, že E − V T
A−1
U je regulární.
Jiří Zelinka Numerické metody 12. přednáška, 10. května 20199 / 12
Stabilita, podmíněnost
Definice
Algoritmus pro řešení Ax = b se nazývá stabilní, jestliže
vypočtené řešení ˆx je takové, že
(A + E)ˆx = b + δb,
kde E a δb jsou malé; E se nazývá chybová matice.
Definice
Pro libovolnou přidruženou maticovou normu definujeme číslo
podmíněnosti matice A vztahem
k(A) = A A−1
.
Řekneme, že matice A je dobře podmíněna, jestliže k(A) ≈ 1
a špatně podmíněna, jestliže k(A) je podstatně větší než 1.
Jiří Zelinka
Numerické metody 12. přednáška, 10. května 2019
10 / 12
Příklad
A =
101 10
10 1
⇒ A 1 = 111
A−1
=
1 −10
−10 101
⇒ A−1
1 = 111
Tedy k(A) = 1112
= 12321, A je špatně podmíněna.
Příklad – Hilbertova matice
A =








1 1
2
1
3
· · · 1
n
1
2
1
3
1
4
· · · 1
n+1
...
...
...
...
1
n
1
n+1
1
n+2
· · · 1
2n−1








.
Pro n = 10 vzhledem k normě . 1 je k(A) = 3,5353.1013
.
Jiří Zelinka
Numerické metody 12. přednáška, 10. května 2019
11 / 12
Věta
Jestliže řešíme systém Ax = b v pohyblivé řádové čárce se
zaokrouhlováním na t desetinných míst a k(A) ≈ 10α
, pak
vypočtené řešení ˜x je správné na (t − α − 1) desetinných míst.
A – pozitivně definitní matice
A 2 = (AT A) = (A)
A 2 = max
1≤i≤n
λi
a
A−1
2 = ( min
1≤i≤n
λi )−1
.
k(A) =
max λi
min λi
.
Jiří Zelinka
Numerické metody 12. přednáška, 10. května 2019
12 / 12