Pokročilé numerické metody II
6. přednáška
Metody zpětného derivování
Tuhé problémy
Jiří Zelinka
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 1 / 14
Opakování
Obecná vícekroková metoda
yi+1 =
s
j=0
aj yi−j + h
s
j=−1
bj y′
i−j ,
y0, . . . , ys – počáteční hodnoty.
b−1 = 0: explicitní metoda, b−1 ̸= 0: implicitní metoda
Konzistence:
s
j=0
aj = 1
−
s
j=0
jaj +
s
j=−1
bj = 1
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 2 / 14
D–stabilita
Metoda se nazývá D–stabilní (stabilní podle Dahlquista,
’zero stability’), jestliže pro všechna řešení zl charakteristické
rovnice (kořeny charakteristického polynomu)
zs+1
=
s
j=1
aj zs−j
platí |zl | ≤ 1 a pokud |zl | = 1, je zl jednoduchý.
Věta
Metoda je konvergentní právě tehdy, když je konzistentní a
D–stabilní.
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 3 / 14
Řád konvergence D–stabilních metod
Pro k–krokové D–stabilní metody platí pro jejich řád
konvergence p (tzv. první Dahlquistova bariéra):
p ≤ k pro explicitní metody
p ≤ k + 1 pro implicitní metody, k liché
p ≤ k + 2 pro implicitní metody, k sudé
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 4 / 14
Stabilita
Testovací úloha: y′
= λy, y(0) = 1, řešení: y(x) = eλx
.
Obecná s + 1 kroková formule:
yi+1(1 − hλb−1) =
s
j=0
(aj + hλbj )yi−j
Charakteristická rovnice:
(1 − hλb−1)zs+1
=
s
j=0
(aj + hλbj )zs−j
Řešení charakteristické rovnice: zj = zj (h), j = 0, . . . s, pro
jednoduchost předpokládejme, že jsou jednoduchá.
Numerické řešení:
yi =
s
j=0
cj zi
j , cj = cj (h)
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 5 / 14
Pro h → 0 má charakteristická rovnice tvar zs+1
=
s
j=0
aj zs−j
,
vzhledem k 1. podmínce konzistence je jedno řešení rovno 1,
označme ho z0.
Z 2. podmínky konzistence dostaneme z0(h) = 1+λh +O(h2
).
Protože 1 + λh = eλh
+ O(h2
), platí
zi
0 = (1 + λh + O(h2
))i
= eλhi
+ O(h2
) = eλxi
+ O(h2
).
Takže pro malá h výraz c0zi
0 aproximuje přesné řešení, platí
c0(h) → 1.
Ostatní řešení pro z1, . . . , zs jsou tzv. parazitní řešení,
cj (h) → 0 pro j = 1, . . . , s.
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 6 / 14
Protože je řešení lineární kombinací zi
j , musí platit |zj | < 1 pro
všechna řešení a parazitní řešení nesmí převážit z0.
Oblast stability:
Oblast stability je množina komplexních čísel ˜h = hλ, pro které
|zj | < 1, j = 0, . . . , s a |
zj
z0
| ≤ 1, j = 1, . . . , s, přičemž pro
|zj | = |z0| je zj jednoduchý kořen.
Absolutně stabilní metoda je taková, jejíž oblast stability
obsahuje všechna komplexní čísla se zápornou reálnou složkou.
(Někdy se požaduje, aby obsahovala zápornou část reálné osy.)
Explicitní vícekrokové metody nemohou být absolutně stabilní,
implicitní vícekrokové metody, které jsou absolutně stabilní
mají řád přesnosti maximálně 2 (tzv. druhá Dahlquistova
bariéra).
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 7 / 14
Metody prediktor–korektor
Kombinace explicitní (prediktor) a implicitní (korektor) metody
stejných řádů přesnosti.
Příklad 1:
prediktor y
(0)
i+1 = yi + h
2
(3fi − fi−1) AB metoda
korektor y
(r+1)
i+1 = yi + h
2
(f
(r)
i+1 + fi ) LM
Příklad 2:
prediktor y
(0)
i+1 = yi + h
24
(55fi − 59fi−1 + 37fi−2 − 9fi−3) AB
korektor y
(r+1)
i+1 = yi + h
24
(9f
(r)
i+1 + 19fi − 5fi−1 + fi−2) AM
Metody prediktor–korektor se zpravidla používají s proměnnou
délkou kroku, který se mění na základě odhadu lokální chyby.
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 8 / 14
Metody zpětného derivování (BDF)
V rovnici y′
(xi+1) = f (xi+1, y(xi+1)) nahradíme derivaci funkce
y v bodě xi+1 derivací interpolačního polynomu v bodech
[xi+1, yi+1], [xi , yi ],. . . ,[xi−s, yi−s].
Příklady: s = 0, s = 1.
Obecný tvar:
αs,−1yi+1 + αs,0yi + αs,1yi−1 + · · · + αs,syi−s = hf (xi+1, yi+1)
Tabulka koeficientů:
s αs,−1 αs,0 αs,1 αs,2 αs,3 αs,4
0 1 -1
1 3/2 -2 1/2
2 11/6 -3 3/2 -1/3
3 25/12 -4 3 -4/3 1/4
4 137/60 -5 5 -10/3 5/4 -1/5
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 9 / 14
Alternativní formule:
yi+1 =
s
j=0
aj yi−j + hb−1f (xi+1, yi+1)
Tabulka koeficientů:
s as,0 as,1 as,2 as,3 as,4 bs,−1
0 1 1
1 4/3 -1/3 2/3
2 18/11 -9/11 2/11 6/11
3 48/25 -36/25 16/25 -3/25 12/25
4 300/137 -300/137 200/137 -75/137 12/137 60/137
Konzistence, řád metody, D–stabilita, stabilita?
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 10 / 14
Označení BDFk: k-kroková metoda zpětného derivování,
k = s + 1
Vztahy mezi koeficienty αs,j a as,j , b−1:
as,j = −
αs,j
αs,−1
, b−1 = 1
αs,−1
bj = 0 pro j ≥ 0
První podmínka konzistence:
s
j=−1
αs,j = 0
Druhá podmínka konzistence:
s
j=−1
jαs,j = −1
Charakteristická rovnice pro D-stabilitu:
αs,−1zs+1
+ αs,0zs
+ · · · + αs,s = 0
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 11 / 14
Tuhé problémy
Charakteristika 1.
Počáteční problém je tuhý, když počet kroků potřebných
k jeho vyřešení metodou s omezenou oblastí absolutní stability
je podstatně větší než počet kroků, který k jeho vyřešení
potřebuje metoda s neomezenou oblastní absolutní stability.
Příklad 1:
y′
1 = y2
y′
2 = −1000y1 − 1001y2
y1(0) = −1
y2(0) = 1
Řešení: y1(x) = −e−x
, y2(x) = e−x
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 12 / 14
Stabilní problém
Počáteční problém y′
= f (x, y), y(x0) = y0 (může být i
systém) se nazývá stabilní, jestliže malá změna f a y0 způsobí
malou změnu řešení.
Poznámka: Neplést si se stabilitou metody.
Pro lineární rovnice y′
= Ay hrají rozhodující roli vlastní čísla
matice A (spektrální poloměr ρ(A)), pro nelineární rovnice je
jejich lineární složka dána Jacobiovou maticí fy .
Charakteristika 2.
Počáteční stabilní problém je tuhý, jestliže součin spektrálního
poloměru Jacobiovy matice fy a délky intervalu, na němž
hledáme řešení je velký.
max
x∈[a,b]
ρ(fy (x, y(x)))(b − a) >> 1
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 13 / 14
Charakteristika 3.
Tuhost problému se projevuje tím, že při numerickém řešení
omezuje délku kroku spíš stabilita než přesnost.
Numerické řešení tuhých problémů: absolutně stabilní
metody.
Příklad 2:
Při použití běžné metody může numerické řešení oscilovat
y′
= y2
− y3
, y(0) = δ, x ∈ [0, 2/δ]
Jiří Zelinka Pokročilé numerické metody II, 6. přednáška 14 / 14