Numerické metody
12. přednáška, 9. května 2017
Jiří Zelinka
Jiří Zelinka Numerické metody 12. přednáška, 9. května 2017 1 / 10
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, 9. května 2017 2 / 10
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 12. přednáška, 9. května 2017 3 / 10
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, 9. května 2017 4 / 10
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, 9. května 2017 5 / 10
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, 9. května 2017 6 / 10
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, 9. května 2017 7 / 10
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, 9. května 2017 8 / 10
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, 9. května 2017 9 / 10
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, 9. května 2017 10 / 10