Numerika pro teoretické fyziky ← →

Kapitola 8

Numerické řešení ODR – Lineární vícekrokové metody. Stabilita a konvergence

Lineární vícekrokové metody

Obecnou \(s\)-krokovou lineární metodu (anglicky linear multistep method) lze psát ve tvaru

\begin{equation}\label{eq:07:obecna_metoda} \sum_{j=0}^{s} \alpha_j v^{n+j} = k \sum_{j=0}^{s} \beta_j f\left(v^{n+j}, t_{n+j}\right) . \end{equation}

Obvykle se volí \(\alpha_s = 1\) a musí být \(\alpha_0 \neq 0\) nebo \(\beta_0 \neq 0\), aby skutečně šlo o \(s\)-krokovou metodu. Pokud je \(\beta_s = 0\), je metoda explicitní; pro \(\beta_s \neq 0\) je implicitní.

Lokální diskretizační chyba je dána Taylorovým rozvojem

\begin{equation}\label{eq:07:lokalni_chyba} \sum_{j=0}^{s} \left[\alpha_j u(t+jk) - k\,\beta_j\, u'(t+jk)\right] = C_0 u(t) + C_1 k u'(t) + C_2 k^2 u''(t) + \dots \end{equation}

Pokud \(C_0 = C_1 = \dots = C_p = 0\) a \(C_{p+1} \neq 0\), máme metodu řádu \(p\).

Dostaneme tak podmínky

\begin{align*} C_0 &= \alpha_0 + \alpha_1 + \dots + \alpha_s = \sum_{j=0}^{s} \alpha_j = 0 , \\ C_1 &= (\alpha_1 + 2\alpha_2 + \dots + s\,\alpha_s) - (\beta_0 + \beta_1 + \dots + \beta_s) = \sum_{j=0}^{s} (j\alpha_j - \beta_j) = 0 , \end{align*}

což jsou obě nutné podmínky pro \(p \geq 1\). Obecně je podmínka na \(m\)-tý koeficient tvaru

\begin{equation}\label{eq:07:cm} C_m = \sum_{j=0}^{s} \left(\frac{j^m}{m!}\,\alpha_j - \frac{j^{m-1}}{(m-1)!}\,\beta_j\right) = 0 . \end{equation}

Vidíme, že by mohla existovat \(s\)-kroková metoda s řádem přesnosti \(2s\) (volíme \(\alpha_s = 1\) a zbývá \(2s+1\) neznámých), ovšem objeví se problémy se stabilitou, ke kterým se dostaneme později. Dahlquist ukázal, že stabilní \(s\)-krokové lineární metody mohou mít řád přesnosti nejvýše \(s+2\).

Standardní vícekrokové metody

Standardně se používají tři skupiny metod:

  1. 1) explicitní Adamsovy–Bashforthovy metody,
  2. 2) implicitní Adamsovy–Moultonovy metody,
  3. 3) implicitní zpětné diference.

První dvě skupiny vycházejí z integrace interpolačního polynomu \(q(t)\), totiž

\begin{equation}\label{eq:07:adams_integrace} v^{n+s} - v^{n+s-1} = \int_{t_{n+s-1}}^{t_{n+s}} q(t)\,\mathrm{d}t , \end{equation}

kde polynom \(q(t)\) prochází body \(\{t_{n+i}, f_{n+i}\}\), a to pro \(i = 0,\dots, s-1\) v případě Adamsových–Bashforthových metod a pro \(i = 0,\dots, s\) v případě Adamsových–Moultonových metod.

Třetí skupina, tedy implicitní zpětné diference, vychází z aproximace derivace v bodě \(t_{n+s}\) pomocí vztahu \(kD = -\ln(I - \nabla)\).

Interaktivní ukázka · Schéma koeficientů tří rodin metod

Vodorovné časové hladiny \(n\), \(n+1\), …, \(n+s\), na nichž jsou ve třech svislých blocích (Adams–Bashforth, Adams–Moulton, zpětné diference) tečkami vyznačeny nenulové koeficienty \(\alpha_j\) a \(\beta_j\). Elipsa „zde integrace“ mezi hladinami \(n+s-1\) a \(n+s\) a šipka „zde derivace“ k tečce \(\beta_s\) označují, odkud se u které rodiny bere informace. Koeficienty se dopočítávají ze soustavy podmínek \eqref{eq:07:cm} pro zvolenou rodinu a počet kroků \(s\), takže tečky i jejich velikosti odpovídají skutečným hodnotám — pro \(s=2\) u Adamse–Bashfortha dostanete \(\beta = [-\tfrac12, \tfrac32]\), pro zpětné diference \(\alpha = [\tfrac13, -\tfrac43, 1]\), \(\beta_2 = \tfrac23\). Pod plátnem se navíc dopočítá řád přesnosti \(p\) a největší kořen \(\rho(\lambda)\) v absolutní hodnotě. Vyzkoušejte si zpětné diference pro \(s = 7\): max \(|\lambda|\) přeskočí přes jedničku a metoda přestane být stabilní — přesně jak říká poslední věta kapitoly.

Určení koeficientů pomocí operátorového počtu

Koeficienty \(\alpha_j\) a \(\beta_j\) by šlo určit i z podmínek na přesnost metod, tj. z \(c_0 = \alpha_0 + \dots + \alpha_s = 0\) a tak dále. Elegantněji to však lze udělat pomocí Taylorova rozvoje následujícím trikem: použijeme-li operátor posunutí \(E\) a operátor derivace \(D\), můžeme operátor daný lineární vícekrokovou metodou

\begin{equation}\label{eq:07:operator_l} Lu(t_n) = \sum_{j=0}^{r} \alpha_j\, u(t_{n+j}) - k \sum_{j=0}^{r} \beta_j\, u'(t_{n+j}) \end{equation}

psát jako

\begin{equation}\label{eq:07:l_rho_sigma} L = \rho(E) - kD\,\sigma(E), \quad \text{kde } \rho(z) = \sum_{j=0}^{r} \alpha_j z^j \quad \text{a } \sigma(z) = \sum_{j=0}^{s} \beta_j z^j . \end{equation}

Ve členu \(kD\,\sigma(E)\) přitom lze operátory \(E\) a \(D\) libovolně přehazovat, neboť spolu komutují.

Pomocí vztahu \(E = e^{kD}\) pak dostaneme

\begin{equation}\label{eq:07:l_exp} L = \rho(e^{kD}) - kD\,\sigma(e^{kD}) = \rho(e^{x}) - x\,\sigma(e^{x}) = c_0 + c_1 x + \dots , \end{equation}

neboli lineární vícekroková metoda má řád přesnosti \(p\) právě tehdy, pokud Taylorův rozvoj funkce \(\rho(e^{x}) - x\,\sigma(e^{x})\) začíná členem \(x^{p+1}\).

Případně můžeme položit \(e^{x} = z\), neboli \(x = \ln z\) (nyní pro \(x \to 0\) máme \(z \to 1\)), a po vydělení \(\sigma(z)\) lze psát (pokud \(\sigma(1) \neq 0\))

\begin{equation}\label{eq:07:rho_sigma_ln} \frac{\rho(z)}{\sigma(z)} = \ln z + \mathcal{O}\!\left((z-1)^{p+1}\right) \qquad \text{pro } z \to 1 . \end{equation}
Poznámka

Podmínky pro přesnost \(p \geq 1\) lze psát též jako

\[ \rho(1) = \sum_{j=0}^{s} \alpha_j = 0 \qquad \text{a} \qquad \rho'(1) = \sigma(1) . \]
Příklad (Adamsovy–Bashforthovy metody)

Zde je požadavek \(\rho(z) = z^s - z^{s-1}\), a tedy \(\sigma(z)\) lze určit jako Taylorův rozvoj funkce

\[ \frac{\rho(z)}{\ln z} = \frac{z^s - z^{s-1}}{\ln z} \]

v \(z \to 1\) do řádu \(s-1\). Pro Adamsovy–Moultonovy metody se postupuje obdobně, jen se rozvíjí do řádu \(s\).

Stabilita a konvergence

Řekneme, že určitá metoda je konvergentní, pokud se pro časový krok \(k \to 0\) blížíme ke správnému řešení, a že je stabilní, pokud při dané metodě nedochází ke zvětšování lokálních diskretizačních a zaokrouhlovacích chyb.

Přestože metoda může být stabilní a konvergentní pro dostatečně malý časový krok \(k\), nemusí být stabilní pro konečná (a i rozumně velká) \(k\). Proto se zavádějí pojmy jako zero-stability (pro \(k \to 0\)) nebo absolute stability, tedy absolutní stabilita, pro konečná \(k\) a podobně. Některé z nich si definujeme později.

Definice (Konvergence \(s\)-krokové metody)

\(s\)-kroková metoda je konvergentní, pokud pro libovolnou ODR \(u'(t) = f(u,t)\), kde \(f(u,t)\) je spojitá a stejnoměrně Lipschitzovská v \(u\), a pro libovolné počáteční podmínky \(u(t_0) = U_0\) splňující

\begin{equation}\label{eq:07:konv_pocatecni} \lim_{k \to 0} v^i(k) = U_0 \quad \text{pro } i = 0, 1, \dots, s-1 \end{equation}

platí

\begin{equation}\label{eq:07:konv_limita} \lim_{\substack{k \to 0 \\ Nk = T}} v^N = U(T) \end{equation}

pro libovolné \(T > 0\), pro které má ODR jednoznačné řešení.

Poznámka

K této definici se hodí tři poznámky:

  1. 1) Podmínka \eqref{eq:07:konv_pocatecni} je přirozená, máme-li spojité řešení.
  2. 2) Pro pevné \(T\) jde \(N \to \infty\).
  3. 3) Existují i metody, které jsou konvergentní jen pro určité ODR či pro určité počáteční podmínky. My se budeme zabývat jen metodami konvergujícími pro libovolný počáteční problém.

Konvergence explicitních jednokrokových metod

Ač si ukážeme, že za poměrně obecných podmínek jde o konvergentní metody, nemusí být tyto metody nutně stabilní pro konečné \(k\). K oblastem absolutní stability se dostaneme později.

Explicitní Eulerova metoda je konvergentní

Uvažujme nejprve lineární problém

\begin{equation}\label{eq:07:linearni_problem} u'(t) = \lambda u(t) + g(t) , \qquad u(t_0) = u_0 . \end{equation}

Eulerova metoda iteruje

\begin{align*} v^{n+1} &= v^n + k\left[\lambda v^n + g(t_n)\right] = \\ &= (1+k\lambda) v^n + k g(t_n) \end{align*}

a z Taylorova rozvoje máme

\begin{equation}\label{eq:07:euler_taylor} u(t_{n+1}) = (1+k\lambda) u(t_n) + k g(t_n) + \tfrac{1}{2} k^2 u'(t_n) + \mathcal{O}(k^3) , \end{equation}

přičemž poslední dva členy \(\tfrac{1}{2} k^2 u'(t_n) + \mathcal{O}(k^3)\) dohromady tvoří lokální diskretizační chybu \(k\tau^n\), která je vždy přítomna pro konzistentní metodu s \(p \geq 1\).

Odečtením dostaneme

\begin{equation}\label{eq:07:euler_chyba} e^{n+1} = v^{n+1} - u(t_{n+1}) = (1+k\lambda) e^n - k\tau^n , \end{equation}

kde \(e^{n+1}\) je globální chyba v čase \(t_{n+1}\).

Poznámka

Horní index \(n\) u \(e^n\), \(v^n\) či \(\tau^n\) je skutečně index, nikoli mocnina.

Rozepsáním rekurence \eqref{eq:07:euler_chyba} dostaneme

\begin{equation}\label{eq:07:euler_chyba_n} e^n = (1+k\lambda)^n e^0 - k \sum_{m=1}^{n} (1+k\lambda)^{n-m} \tau^{m-1} , \end{equation}

kde \(e^0\) je počáteční zaokrouhlovací chyba.

Interaktivní ukázka · Odhad růstu chyby exponenciálou

Z hodnoty \(1\) na svislé ose vycházejí tři křivky: nejstrmější \(e^{k|\lambda|}\), přímka \(1+k|\lambda|\) a klesající čárkovaná \(1-k|\lambda|\). To je situace pro \(n = 1\); posuvníkem \(n\) přejdete k mocninám \((1\pm k|\lambda|)^n\) a \(e^{n k|\lambda|}\), tedy přesně k odhadu \((1+k\lambda)^{n} \leq e^{n k|\lambda|} \leq e^{|\lambda|T}\), který se používá hned v následujícím odstavci. Křivka \((1+k|\lambda|)^n\) je zesilovací faktor explicitní Eulerovy metody po \(n\) krocích a vyčísluje se spolu s \(e^{n k|\lambda|}\). Táhněte kolečkem po vodorovné ose a sledujte, že poměr obou hodnot nikdy nepřeroste jedničku — a že \(e^{n k|\lambda|} = e^{|\lambda|T}\) pro \(T = nk\).

Využijeme-li odhad (pro kladné \(k\) a libovolné \(\lambda\))

\begin{equation}\label{eq:07:odhad_exp} (1+k\lambda)^{n-m} \leq e^{(n-m)k|\lambda|} \leq e^{nk|\lambda|} \leq e^{|\lambda|T} \end{equation}

platný pro \(nk \leq T\), tedy pro všechny časy \(0 \leq t_n \leq T\), dostaneme

\begin{align*} |e^n| &\leq e^{|\lambda|T} \left[|e^0| + k \sum_{m=1}^{n} |\tau^{m-1}|\right] \leq e^{|\lambda|T} \left(|e^0| + k n \max_{n=1}^{n} |\tau^{m-1}|\right) \leq \\ &\leq e^{|\lambda|T} \left(|e^0| + T \|\tau\|_\infty\right) , \end{align*}

kde \(\|\tau\|_\infty\) je alespoň \(\mathcal{O}(k)\).

Pro \(k \to 0\) jde tedy druhý člen k nule a první závisí na počáteční zaokrouhlovací chybě a na typu úlohy. Pokud \(e^0 = 0\), máme konvergenci pro \(k \to 0\) a jde o metodu řádu 1, neboť globální chyba je \(\mathcal{O}(k)\).

Pro nelineární problém dostaneme obdobně

\begin{equation}\label{eq:07:nelin_chyba} e^{n+1} = e^n + k\left[f(v^n, t_n) - f(u(t_n), t_n)\right] - k\tau^n \end{equation}

a díky stejnoměrné Lipschitzovosti můžeme psát

\begin{equation}\label{eq:07:lipschitz} |f(v^n, t_n) - f(u(t_n), t_n)| \leq L\, |v^n - u(t_n)| = L\, |e^n| . \end{equation}

Máme tedy nyní odhad

\begin{equation}\label{eq:07:nelin_odhad_krok} |e^{n+1}| \leq (1+kL)\, |e^n| + k\, |\tau^n| , \end{equation}

neboli

\begin{equation}\label{eq:07:nelin_odhad_n} |e^n| \leq (1+kL)^n |e^0| + k \sum_{m=1}^{n} (1+kL)^{n-m} |\tau^{m-1}| , \end{equation}

a konečně

\begin{equation}\label{eq:07:nelin_odhad} |e^n| \leq e^{LT} \left(|e^0| + T \|\tau\|_\infty\right) , \end{equation}

kde člen \(T \|\tau\|_\infty\) je \(\mathcal{O}(k)\), stejně jako v předchozím případě.

Explicitní Rungeovy–Kuttovy metody jsou konvergentní

Obecně lze pro tyto metody psát

\begin{equation}\label{eq:07:rk_obecne} v^{n+1} = v^n + k\, \Phi(v^n, t_n, k) , \end{equation}

kde \(\Phi\) závisí na pravé straně \(f(u,t)\) a stejně jako u \(f\) předpokládáme, že je spojitá a stejnoměrně Lipschitzovská, ovšem s jinou konstantou \(L'\).

Příklad (Rungeova–Kuttova metoda 2. řádu)

Rungeova–Kuttova metoda 2. řádu má

\[ \Phi = f\left(v^n + \tfrac{1}{2} k f(v^n, t_n), t_n\right) , \]

z čehož dostaneme \(L' = L + \tfrac{1}{2} k L^2\), a pro \(k \to 0\) je \(L' \to L\).

Pro chybu nyní dostaneme (obdobně jako u Eulerovy metody)

\begin{equation}\label{eq:07:rk_chyba} e^{n+1} = e^n + k\left[\Phi(v^n, t_n, k) - \Phi(u(t_n), t_n, k)\right] - k\tau^n , \end{equation}

a tedy

\begin{equation}\label{eq:07:rk_odhad} |e^{n+1}| \leq |e^n| (1+kL') + k\, |\tau^n| . \end{equation}

Dále už postupujeme stejně jako výše, čímž dostaneme konvergenci.

Řešení homogenních lineárních diferenčních rovnic

Uvažujme diferenční rovnici \(k\)-tého řádu

\begin{equation}\label{eq:07:dif_rovnice} a_k f_{n+k} + \dots + a_1 f_{n+1} + a_0 f_n = 0 , \end{equation}

kde \(a_i\) jsou reálná čísla (\(a_k \neq 0\)) a \(f_n\) je zadána pro \(n = 0, 1, \dots, k-1\).

Obecně, tedy bez počátečních hodnot, existuje \(k\) nezávislých řešení. Jde totiž o \(k\) vektorů tvaru

\[ (f_n, \dots, f_{n+k}) , \]

které jsou kolmé na vektor koeficientů \((a_0, \dots, a_k)\). Bázi tohoto \(k\)-rozměrného prostoru řešení lze dostat následujícím trikem.

S využitím \(f_{n+i} = E^i f_n\) přepíšeme rovnici \eqref{eq:07:dif_rovnice} jako

\begin{equation}\label{eq:07:pE} p(E) f_n = 0 , \end{equation}

kde

\begin{equation}\label{eq:07:charpoly} p(\lambda) = a_k \lambda^k + \dots + a_1 \lambda + a_0 = a_k (\lambda - \lambda_1)^{\alpha_1} \dots (\lambda - \lambda_m)^{\alpha_m} \end{equation}

a kde \(\lambda_1, \dots, \lambda_m\) jsou kořeny polynomu \(p(\lambda)\) s násobnostmi \(\alpha_1, \dots, \alpha_m\) splňujícími \(\alpha_1 + \alpha_2 + \dots + \alpha_m = k\).

Rovnici \eqref{eq:07:dif_rovnice} tedy můžeme psát též jako

\[ p(E) f_n = a_k (E - \lambda_1)^{\alpha_1} \dots (E - \lambda_m)^{\alpha_m} f_n = 0 , \]

a protože \(E\lambda^n = \lambda^{n+1} = \lambda\,\lambda^n\), bude \(f_n = \lambda^n\) řešením rovnice \eqref{eq:07:dif_rovnice}, pokud je \(\lambda\) kořenem charakteristického polynomu \(p(\lambda)\).

Pokud je násobnost všech kořenů \(\alpha_i = 1\), pak máme \(k\) nezávislých řešení. Pro násobné kořeny obecně platí

\begin{equation}\label{eq:07:nasobny_koren} (E-\lambda)^{\alpha_i} q_{\alpha_i - 1}(n)\, \lambda^n = 0 , \end{equation}

kde \(q_N(n)\) je libovolný polynom \(N\)-tého stupně. Platí totiž

\[ (E-\lambda)\, q_N(n) \lambda^n = q_N(n+1) \lambda^{n+1} - q_N(n) \lambda^{n+1} = \tilde{q}_{N-1}(n) \lambda^{n+1} , \]

a tedy postupně snižujeme stupeň \(q\) až na nulu, takže pro \((E-\lambda)^{N+1}\) máme

\begin{equation}\label{eq:07:nasobny_koren_n1} (E-\lambda)^{N+1} q_N(n) \lambda^n = 0 . \end{equation}

Jako \(\alpha_i\) nezávislých řešení pro násobný kořen \(\lambda_i\) tedy můžeme vzít

\begin{equation}\label{eq:07:baze_nasobny} \lambda_i^n,\ n\lambda_i^n,\ \dots,\ n^{\alpha_i-1}\lambda^n . \end{equation}

Řešení rovnice \eqref{eq:07:dif_rovnice} s počátečními podmínkami pro \(n = 0, 1, \dots, k-1\) pak dostaneme jako lineární kombinaci takovýchto bázových funkcí. Koeficienty tohoto rozkladu do báze určíme řešením soustavy lineárních rovnic daných počátečními hodnotami \(f_0, \dots, f_{k-1}\).

Příklad (Fibonacciho posloupnost)

Uvažujme

\begin{equation}\label{eq:07:fib} f_{n+2} = f_{n+1} + f_n , \qquad f_0 = 0 , \quad f_1 = 1 . \end{equation}

Charakteristický polynom je

\[ p(\lambda) = \lambda^2 - \lambda - 1 \qquad \text{s kořeny } \lambda_{1,2} = \frac{1 \pm \sqrt{5}}{2} , \]

a tedy řešení bude mít tvar

\[ f_n = A\lambda_1^n + B\lambda_2^n , \]

kde \(A\) a \(B\) jsou dány rovnicemi

\begin{align*} f_0 &= 0 = A + B , \\ f_1 &= 1 = A\,\frac{1+\sqrt{5}}{2} + B\,\frac{1-\sqrt{5}}{2} , \end{align*}

z nichž plyne \(A = -B = \frac{\sqrt{5}}{5}\). Řešením je tedy

\begin{equation}\label{eq:07:fib_reseni} f_n = \frac{\sqrt{5}}{5}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right] . \end{equation}

Stabilita a konvergence lineárních vícekrokových metod

Zde je situace složitější a ani konzistentní metoda (\(p \geq 1\)) nemusí být stabilní, a tedy konvergentní.

Příklad (Nestabilní dvoukroková metoda)

Explicitní lineární vícekroková metoda s nejvyšším řádem přesnosti \(p = 2s - 1 = 3\) je dána vztahem

\begin{equation}\label{eq:07:nestabilni_metoda} v^{n+2} = -4v^{n+1} + 5v^n + k\left[4f(v^{n+1}, t_{n+1}) + 2f(v^n, t_n)\right] . \end{equation}
Poznámka

Zde máme čtyři neznámé \(\alpha_0, \alpha_1, \beta_0, \beta_1\) a při volbě \(\alpha_2 = 1\) pro ně dostáváme podmínky

\begin{align*} 1 + \alpha_1 + \alpha_0 &= 0 , \\ 2 + \alpha_1 - \beta_0 - \beta_1 &= 0 , \\ 2 + \tfrac{1}{2}\alpha_1 - \beta_1 &= 0 , \\ \tfrac{4}{3} + \tfrac{1}{6}\alpha_1 - \tfrac{1}{2}\beta_1 &= 0 , \end{align*}

z nichž plyne \(\alpha_0 = -5\), \(\alpha_1 = 4\), \(\beta_0 = 2\), \(\beta_1 = 4\).

Použijeme-li tuto metodu na rovnici \(u'(t) = 0\), \(u(0) = 0\), pak pro inicializaci \(v^0 = v^1 = 0\) je řešení v pořádku. Avšak pro \(v^0 = 0\), \(v^1 = k\), což je inicializace splňující podmínku pro konvergenci, dostaneme

\begin{equation}\label{eq:07:nestabilni_reseni} v^n = \frac{k}{6}\left(1 - (-5)^n\right) , \end{equation}

a tedy nepřesnosti z předchozích kroků jsou násobeny faktorem 5, což je exponenciální růst.

Poznámka

Charakteristický polynom je zde \(p(\lambda) = \lambda^2 + 4\lambda - 5\) s kořeny \(\lambda_1 = 1\) a \(\lambda_2 = -5\), takže \(v^n = A\cdot 1^n + B(-5)^n\). Z počátečních podmínek máme rovnice

\begin{align*} v^0 &= 0 = A + B , \\ v^1 &= k = A - 5B , \end{align*}

z nichž plyne \(A = -B = \frac{k}{6}\).

Příklad (Implicitní dvoukroková metoda řádu 3)

Uvažujme metodu

\begin{equation}\label{eq:07:implicitni_metoda} v^{n+2} - 2v^{n+1} + v^n = \frac{k}{2}\left[f(v^{n+2}, t_{n+2}) - f(v^n, t_n)\right] . \end{equation}

Nyní je \(p(\lambda) = \lambda^2 - 2\lambda + 1 = (\lambda - 1)^2\); opět metodu aplikujeme na \(u'(t) = 0\). Obecné řešení má tvar \(v^n = A\cdot 1^n + B n 1^n\) a počáteční podmínky

\begin{align*} v^0 &= 0 = A , \\ v^1 &= k = B \end{align*}

dávají řešení \(v^n = kn\). Metoda je tedy opět nestabilní, ale jen polynomiálně.

Pokud bychom měli vícenásobný kořen \(\lambda_i\), pro který by platilo \(|\lambda_i| < 1\), pak bychom měli stabilní metodu, neboť pro libovolné \(p\) platí

\begin{equation}\label{eq:07:limita_np_lambda} \lim_{n \to \infty} n^p \lambda_i^n = 0 . \end{equation}

Vidíme tedy, že kořeny charakteristického polynomu

\begin{equation}\label{eq:07:rho} \rho(\lambda) = \sum_{j=0}^{s} \alpha_j \lambda^j \end{equation}

lineární vícekrokové metody musí být v absolutní hodnotě menší než jedna pro vícenásobné kořeny, zatímco pro jednonásobné kořeny může být \(|\lambda_i| \leq 1\).

Takto se definuje stabilita lineární vícekrokové metody; jde o tzv. zero-stability.

Definice (Stabilita \(s\)-krokové lineární metody)

\(s\)-kroková lineární metoda je stabilní, pokud je řešení

\[ \rho(E) v^n = 0 \]

omezené pro \(n \to \infty\), neboli pokud \(|\lambda_i| \leq 1\) a pro vícenásobné kořeny \(\rho\) navíc \(|\lambda_i| < 1\).

Příklad (Adamsovy metody)

Adamsovy–Bashforthovy i Adamsovy–Moultonovy metody jsou stabilní v tomto smyslu, neboť obecně

\[ \rho(\lambda) = \lambda^s - \lambda^{s-1} \implies \lambda_1 = 1, \quad \lambda_2 = \lambda_3 = \dots = \lambda_s = 0 , \]

přičemž \(\lambda_1 = 1\) je tzv. principální (hlavní) kořen.

Věta (Dahlquistův teorém ekvivalence)

Lineární vícekroková metoda pro \(u'(t) = f(u(t),t)\) je konvergentní právě tehdy, když je konzistentní (\(p \geq 1\)) a stabilní ve výše uvedeném smyslu.

Stačí tedy zkoumat stabilitu, tj. kořeny \(\rho(\lambda)\), abychom ověřili, že metoda konverguje.

Obecně lze též ukázat (rovněž Dahlquist), že každá stabilní lineární \(s\)-kroková metoda může mít řád \(p\) nejvýše

\begin{equation}\label{eq:07:dahlquist_rad} \begin{aligned} s+2 &\quad \text{pro } s \text{ sudé} , \\ s+1 &\quad \text{pro } s \text{ liché} , \end{aligned} \qquad \text{a } s \text{ pro explicitní metody.} \end{equation}

Zpětné diference jsou stabilní pro \(1 \leq s \leq 6\).