Numerické metody
10. přednáška, 26. dubna 2018
Jiří Zelinka
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 1/23
Opakování
Iterační metody řešení systémů lineárních rovnic
Systém
Ax = b
převedeme na
x = Tx + g
xk+1
= Txk
+ g, k = 0, 1, . . .
Hlavní věta o konvergenci iteračního procesu
Posloupnost xk ∞
k=0
určená iteračním procesem x = Tx + g
konverguje pro každou počáteční aproximaci x0
∈ Rn
právě
tehdy, když ρ(T) < 1, přičemž
lim
k→∞
xk
= x∗
, x∗
= Tx∗
+ g
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 2/23
Jacobiova iterační metoda
Ax = b, A = D − L − U,
Ax = (D − L − U)x = b
x = D−1
(L + U)x + D−1
b.
xk+1
= D−1
(L + U)xk
+ D−1
b.
Z i-té rovnice vypočteme xi :
xk+1
i = −
n
j=1
j=i
aij
aii
xk
j +
bi
aii
,
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 3/23
Gaussova-Seidelova iterační metoda
xk+1
i = −
i−1
j=1
aij
aii
xk+1
j −
n
j=i+1
aij
aii
xk
j +
bi
aii
, i = 1, . . . , n.
Maticový zápis:
xk+1
= (D − L)−1
Uxk
+ (D − L)−1
b.
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 4/23
Konvergence
Silné řádkové (sloupcové) sumační kriterium:
Nechť matice A je ryze řádkově (sloupcově) diagonálně
dominantní, tj.
|aii | >
n
j=1
j=i
|aij |, i = 1, . . . , n.
Pak Jacobiova i Gaussova-Seidelova iterační metoda
konverguje pro každou počáteční aproximaci x0
∈ Rn
.
Věta
Nechť A je pozitivně definitní matice. Pak Gaussova-Seidelova
metoda konverguje pro každou počáteční aproximaci.
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 5/23
Relaxační metody
Modifikace Gaussovy–Seidelovy metody, ω – relaxační
parametr
xk+1
i = (1 − ω)xk
i +
ω
aii
bi −
i−1
j=1
aij xk+1
j −
n
j=i+1
aij xk
j .
Relaxační metodu lze maticově zapsat takto
xk+1
= (D − ωL)−1
[(1 − ω)D + ωU]xk
+ ω(D − ωL)−1
b
Tω = (D − ωL)−1
[(1 − ω)D + ωU]
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 6/23
Iterační metody pro systémy nelineárních rovnic
f1(x1, . . . , xm) = 0
...
fm(x1, . . . , xm) = 0
F(x) = o, x ∈ Rm
, o = (0, . . . , 0)T
∈ Rm
.
Systém převedeme na ekvivalentní rovnici
x = G(x), x ∈ Rm
x1 = g1(x1, . . . , xm)
...
xm = gm(x1, . . . , xm)
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 7/23
Newtonova metoda pro systémy nelineárních rovnic
F(x) = o, F ∈ C2
(O(ξ))
JF (x) =






∂f1(x)
∂x1
· · ·
∂f1(x)
∂xm
...
...
...
∂fm(x)
∂x1
· · ·
∂fm(x)
∂xm






Taylorův rozvoj:
F(x + h) = F(x) + JF (x) · h + O( h 2
) · (1, . . . , 1)T
x = xk
, xk+1
= xk
+ h ⇒ h = xk+1
− xk
Zanedbáme chybový člen,
F(x + h) = o ⇒ JF (xk
)(xk+1
− xk
) = −F(xk
)
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 8/23
xk+1
= xk
− J−1
F (xk
)F(xk
)
Iterační funkce
G(x) = x − J−1
F (x)F(x)
Věta
Nechť ξ je kořenem rovnice F(x) = o. Nechť JF (x) je
regulární matice se spojitými prvky v okolí O(ξ) bodu ξ,
přičemž
J−1
F (x) ∞
≤ K, K = konst.,
pro všechna x z tohoto okolí. Nechť funkce fi , i = 1, . . . , m,
mají spojité druhé parciální derivace v O(ξ).
Posloupnost xk ∞
k=0
určená Newtonovou metodou konverguje
ke kořenu ξ za předpokladu, že počáteční aproximace x0
leží
dostatečně blízko ξ. Řád metody je roven dvěma.
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 2018 9/23
Řešení systémů lin. rovnic – přímé metody
Základní pojmy
Ax = b, A =



a11 · · · a1n
...
...
an1 · · · ann


, x =



x1
...
xn


, b =



b1
...
bn


.
A – matice soustavy, regulární. Řešení: ˜x = A−1
b
Rozšířená matice soustavy:
(A | b) =





a11 · · · a1n b1
a21 · · · a2n b2
...
...
...
an1 · · · ann bn





Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 201810/23
A – dolní trojúhelníková: aij = 0 pro i < j.
A – horní trojúhelníková: aij = 0 pro i > j.
A – pásová, jestliže existují p, q, 1 < p, q < n taková, že
aij = 0, jestliže i + p ≤ j nebo j + q ≤ i, šířka pásu
w = p + q − 1.
A – třídiagonální pro p = q = 2.
A – ryze řádkově diagonálně dominantní
|aii | >
n
j=1
j=i
|aij |, i = 1, . . . , n.
A – ryze sloupcově diagonálně dominantní – podobně
Věta:
Ryze řádkově (sloupcově) diagonálně dominantní matice, je
regulární.
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 201811/23
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 10. přednáška, 26. dubna 201812/23
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 10. přednáška, 26. dubna 201813/23
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 10. přednáška, 26. dubna 201814/23
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 10. přednáška, 26. dubna 201815/23
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 10. přednáška, 26. dubna 201816/23
(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 10. přednáška, 26. dubna 201817/23
Gaussova eliminace 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 10. přednáška, 26. dubna 201818/23
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 10. přednáška, 26. dubna 201819/23
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 10. přednáška, 26. dubna 201820/23
Příklad
2x1 + 4x2 − x3 = −5
x1 + x2 − 3x3 = −9
4x1 + x2 + 2x3 = 9
Jiří Zelinka Numerické metody 10. přednáška, 26. dubna 201821/23
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 10. přednáška, 26. dubna 201822/23
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 10. přednáška, 26. dubna 201823/23