Pokročilé numerické metody II
5. přednáška
Vícekrokové metody:
D–stabilita a konvergence
Jiří Zelinka
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 1 / 16
Vícekrokové metody – opakování
y′
= f (x, y), y(x0) = y0
y(xi+1) = y(xi ) +
xi+1
xi
f (x, y(x))dx
Adamsova–Bashforthova metoda
Funkci f aproximujeme interpolačním polynomem v bodech
xi−s, xi−s+1, . . . , xi
Adamsův extrapolační vzorec:
yi+1 = yi + h[fi + b1∆fi−1 + b2∆2
fi−2 + · · · + bs∆s
fi−s]
Koeficienty bj :
j 1 2 3 4 5
bj 1/2 5/12 3/8 251/720 95/288
bj nezávisí na s, b0 = 1.
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 2 / 16
Při použití Lagrangeova interpolačního polynomu dostaneme
formuli
yi+1 = yi + h[bs,0fi + bs,1fi−1 + bs,2fi−2 + · · · + bs,sfi−s]
s bs,0 bs,1 bs,2 bs,3 bs,4
0 1
1 3/2 -1/2
2 23/12 -16/12 5/12
3 55/24 -59/24 37/24 -9/24
4 1901/720 -2774/720 2616/720 -1274/720 521/720
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 3 / 16
Adamsova–Multonova metoda
Funkci f aproximujeme interpolačním polynomem v bodech
xi−s, xi−s+1, . . . , xi , xi+1
Adamsův interpolační vzorec:
yi+1 = yi + h[fi+1 + c1∆fi + c2∆2
fi−1 + · · · + cs+1∆s+1
fi−s]
Koeficienty cj :
j 1 2 3 4 5
cj -1/2 -1/12 -1/24 -19/720 -3/160
cj nezávisí na s, c0 = 1.
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 4 / 16
Použití Lagrangeova interpolačního polynomu:
s cs,−1 cs,0 cs,1 cs,2 cs,3
-1 1
0 1/2 1/2
1 5/12 8/12 -1/12
2 9/24 19/24 -5/24 1/24
3 251/720 646/720 -264/720 106/720 -19/720
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 5 / 16
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
Formule se nazývá řádu r, jestliže je přesná pro polynomy do
stupně r.
Podmínky řádu: s
j=0
aj = 1
−
s
j=0
jaj +
s
j=−1
bj = 1
s
j=0
(−j)k
aj + k
s
j=−1
(−j)k−1
bj = 1, k = 2, . . . , r
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 6 / 16
Metoda, která splňuje první dvě rovnice se nazývá
konzistentní.
Lokální diskretizační chyba:
y(xi+1) =
s
j=0
aj y(xi−j ) + h
s
j=−1
bj y′
(xi−j ) + ltei
ltei =
1
r!
xi+1
xi−s
G(t)y(r+1)
(t)dt
G se nazývá účinková funkce
G(t) = (xi+1 − t)
r
− rhb−1(xi+1 − t)
r−1
+
+
s
j=1
[aj (xi−j − t)
r
+ rhbj (xi−j − t)
r−1
]
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 7 / 16
Pokud G nemění znaménko na [xi−s, xi+1] pak podle věty o
střední hodnotě integrálu
ltei =
y(r+1)
(η)
r!
xi+1
xi−s
G(t)dt xi−s < η < xi+1.
Pak
ltei = Chr+1
y(r+1)
(η)
Pokud G mění znaménko na [xi−s, xi+1], pak platí
|ltei | ≤
|y(r+1)
(ξ)|
r!
xi+1
xi−s
|G(t)|dt
kde ξ je bod z [xi−s, xi+1], v němž nabývá |y(r+1)
| svého
maxima.
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 8 / 16
Lineární diferenční rovnice s konstantními
koeficienty
akyn+k + ak−1yn+k−1 + · · · + a0yn = bn
k je řád rovnice, ak ̸= 0.
Pro bn = 0 dostaneme homogenní rovnici.
Pro každé počáteční hodnoty y0,. . . ,yk−1 dostaneme
jednoznačně určené řešení.
Řešení homogenního systému tvoří k-rozměrný vektorový
prostor, jeho báze se nazývá fundamentální systém řešení,
její prvky označíme y1n,. . . ,ykn.
Obecné řešení homogenní rovnice je lineární kombinace prvků
FSŘ, obecné řešení nehomogenní rovnice je součet
partikulárního řešení a obecného řešení homogenní rovnice.
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 9 / 16
Prvky FSŘ jsou definovány pomocí řešení charakteristické
rovnice
akzk
+ ak−1zk−1
+ · · · + a1z + a0 = 0,
resp. pomocí kořenů charakteristického polynomu. Je-li kořen
zl reálný, násobnosti r, pak FSŘ obsahuje prvky
zn
l , nzn
l , n2
zn
l ,. . . ,nr−1
zn
l .
Je-li kořen zl komplexní násobnosti r, zl = ρ(cos φ ± i sin φ),
obsahuje FSŘ prvky
ρn
cos nφ, nρn
cos nφ,. . . , nr−1
ρn
cos nφ,
ρn
sin nφ, nρn
sin nφ,. . . , nr−1
ρn
sin nφ.
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 10 / 16
Konvergence metody
Definice
Nechť počáteční hodnoty y0, . . . , ys splňují podmínku
lim
h→0+
yj = y0, j = 1, . . . , s.
Metoda se nazývá konvergentní v bodě x, jestliže
lim
h→0+
yn = y(x), nh = x − x0.
Metoda se nazývá konvergentní na intervalu [a, b], jestliže
je konvergentní ∀x ∈ [a, b].
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 11 / 16
D–stabilita
Definice
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, 5. přednáška 12 / 16
Řá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, 5. přednáška 13 / 16
Stabilita
Testovácí úloha: y′
= λy, y(0) = 1
Obecná s + 1 kroková formule:
yi+1(1 − hλb−1) =
s
j=1
(aj + hλbj )yi−j
Charakteristická rovnice:
(1 − hλb−1)zs+1
=
s
j=1
(aj + hλbj )zs−j
Buď z0 řešení charakteristické rovnice, pro které lim
h→0
z0 = 1,
z1, . . . , zs ostatní řešení. Oblast stability je množina
komplexních čísel z = hλ, pro které
| zl
z0
| ≤ 1, l = 1, . . . , s, přičemž pro |zl | = |z0| je |zl |
jednoduchý kořen.
Jiří Zelinka Pokročilé numerické metody II, 5. přednáška 14 / 16
Explicitní vícekrokové metody nemoou 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, 5. přednáška 15 / 16
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, 5. přednáška 16 / 16