Kapitola 7
Numerické řešení ODR – Základní pojmy. Rungeovy–Kuttovy metody
Počáteční a okrajová úloha
Z hlediska numerického je zásadní rozdíl mezi řešením obyčejných diferenciálních rovnic (ODR) s počátečními a s okrajovými podmínkami. Rozlišujeme proto dva typy úloh:
- 1) počáteční úloha (initial value problem) — máme zadánu funkční hodnotu a případně derivace v jednom bodě (typicky v určitém čase) a iteračně hledáme řešení v následných bodech (časech);
- 2) okrajová úloha (boundary value problem) — funkce je zadána v různých bodech a hledáme řešení mezi těmito body. Okrajovou úlohu řešíme obvykle převedením na soustavu lineárních rovnic diskretizací nebo rozvojem do báze.
Zde se budeme zabývat počáteční úlohou; okrajové úlohy budou probírány v letním semestru.
Matematická formulace počáteční úlohy pro ODR
Nalezněte \(u(t) : \langle 0,T\rangle \to \mathbb{C}^d\) splňující rovnici
\begin{equation}\label{eq:06:pocatecni_uloha} u'(t) \equiv \frac{du}{dt} = f(u(t),t) \qquad \text{s poč. podmínkou } u(t=0) = u_0 , \end{equation}kde \(f\) je zadaná funkce (obecně vektorová)
\[ f: \mathbb{C}^d \times \langle 0,T\rangle \to \mathbb{C}^d , \]která může být (a obvykle je) nelineární.
Obecně tedy uvažujeme systém ODR, neboť \(u(t) \in \mathbb{C}^d\).
Díky tomu jsou zahrnuty i počáteční úlohy pro ODR vyšších řádů, neboť stačí zavést proměnné \(u_1(t) = u(t)\), \(u_2(t) = u'(t)\) atd.
Bez újmy na obecnosti pokládáme počáteční čas \(t_0 = 0\); vždy lze posunout.
Pro \(f(u,t) = f(t)\) jde o integraci
\begin{equation}\label{eq:06:integrace} u(t) = u_0 + \int_0^t f(t')\,dt' , \end{equation}proto se můžete setkat i s pojmem numerická integrace ODR.
Existence a jednoznačnost řešení
Otázka existence a jednoznačnosti řešení patří do matematické analýzy, viz příslušnou přednášku. Standardní Cauchyho předpoklady pro existenci a jednoznačnost řešení jsou:
- a) \(f\) je spojitá;
- b) \(f\) je stejnoměrně Lipschitzovská vzhledem k \(u\), tj. existuje konstanta \(L>0\) taková, že
přičemž \(\|\cdot\|\) je vhodná vektorová norma.
Pokud existuje \(\frac{\partial f}{\partial u}\), pak musí být všude omezená konstantou \(L\).
Uvažujme rovnici
\[ u'(t) = u^2 = f(u) , \qquad u(0) = 1 . \]Zde \(f\) není Lipschitzovská, neboť pro
\[ |u^2-v^2| = |u+v|\,|u-v| \]má platit \(|u^2-v^2| \le L\,|u-v|\), a tedy by \(L\) muselo být nekonečné. Řešením je
\[ u(t) = \frac{1}{1-t} , \]které v konečném čase \(t=1\) diverguje, a pro \(t>1\) tedy neexistuje.
Uvažujme rovnici
\[ u'(t) = \sqrt{u} = f(u) , \qquad u(0) = 0 . \]I zde \(f\) není Lipschitzovská, neboť
\[ \frac{\partial f}{\partial u} = \frac{1}{2\sqrt{u}} \to \infty \quad \text{pro } u \to 0 . \]Řešení ovšem existuje, ale není jednoznačné, neboť úlohu splňuje jak \(u(t)=0\), tak \(u(t) = \frac{t^2}{4}\).
Lipschitzova konstanta \(L\) říká, jak moc se řešení pro různé počáteční podmínky rozbíhají, nebo naopak sbíhají. Oba extrémy (velká rozbíhavost, nebo naopak rychlá sbíhavost) způsobují numerické problémy.
Problém špatné podmíněnosti
Existují rovnice, kde libovolně blízké počáteční podmínky mohou vést na dramaticky rozdílná řešení; mnohdy se jedná o chaotické systémy.
Fyzické kyvadlo popsané rovnicí
\begin{equation}\label{eq:06:kyvadlo} \ddot{\varphi}(t) = -\frac{g}{\ell}\sin\varphi(t) \end{equation}má pro počáteční podmínky
\[ \varphi(0) = \pi \pm \varepsilon \quad \text{a} \quad \dot{\varphi}(0) = 0 \]zcela jiné, i když jednoznačné řešení. Lipschitzova konstanta je
\[ L = \max\left(1, \frac{g}{\ell}\right) , \]neboť pro
\[ u = \begin{pmatrix} \varphi \\ \dot{\varphi} \end{pmatrix} \quad \text{splňující} \quad \frac{du}{dt} = \frac{d}{dt}\begin{pmatrix} \varphi \\ \dot{\varphi} \end{pmatrix} = \begin{pmatrix} \dot{\varphi} \\ -\frac{g}{\ell}\sin\varphi \end{pmatrix} = f(u) \]dostaneme (označme si \(v = \begin{pmatrix} \psi \\ \dot{\psi} \end{pmatrix}\))
\begin{align*} \|f(u) - f(v)\|_\infty &= \max\left(|\dot{\varphi} - \dot{\psi}|,\ \frac{g}{\ell}\,|\sin\varphi - \sin\psi|\right) \le \\ &\le \max\left(|\dot{\varphi} - \dot{\psi}|,\ \frac{g}{\ell}\,|\varphi - \psi|\right) \le \\ &\le \max\left(1, \frac{g}{\ell}\right)\max\left(|\dot{\varphi} - \dot{\psi}|,\ |\varphi - \psi|\right) = \\ &= \max\left(1, \frac{g}{\ell}\right)\|u - v\|_\infty . \end{align*}Kružnice opisovaná kyvadlem s ramenem \(\ell\) a úhlem \(\varphi\). Vyneseny jsou dvě blízké polohy odchýlené o \(\varepsilon\) na obě strany od horní úvratě, se šipkami okamžité rychlosti mířícími opačným směrem. Obě řešení se počítají: rovnice \eqref{eq:06:kyvadlo} se integruje metodou RK 4. řádu zvlášť pro \(\varphi(0) = \pi - \varepsilon\) a \(\varphi(0) = \pi + \varepsilon\). Posuvníkem \(\varepsilon\) měňte vzdálenost počátečních podmínek, posuvníkem \(g/\ell\) i Lipschitzovu konstantu \(L = \max(1, g/\ell)\) a tlačítkem přehrajte časový vývoj. Dolní graf ukazuje \(\varphi(t)\) obou řešení: přestože se liší jen o \(2\varepsilon\), jedno spadne doleva (kmitá kolem \(0\)) a druhé doprava (kmitá kolem \(2\pi\)) — to je ona špatná podmíněnost.
Numerické řešení ODR — základní pojmy
Typicky hledáme řešení \(u(t)\) ODR
\[ u'(t) = f(u(t), t) , \qquad u(t_0) = u_0 \]pouze v diskrétních časech \(t_n = t_0 + n k_n\), tj. hledáme přibližné řešení
\begin{equation}\label{eq:06:priblizne_reseni} v^n \simeq u(t_n) , \end{equation}přičemž časový krok \(k_n\) je často konstantní (\(k\)), i když existují např. adaptivní metody, které mění krok pro dosažení vyšší přesnosti.
Jednokrokové a vícekrokové metody
Metody se obvykle dělí na jednokrokové a vícekrokové.
U jednokrokových metod závisí řešení \(v^{n+1}\) v každém kroku pouze na \(v^n\). Výhodou je, že lze snadno změnit krok, a že jsou vhodné pro problémy s nespojitými funkcemi. Nevýhodou je, že pro vyšší přesnost je nutné počítat \(f(u,t)\) i v mezibodech mezi \(t_n\) a \(t_{n+1}\) (víceúrovňové metody). Příkladem jsou Rungeovy–Kuttovy metody.
U vícekrokových metod se \(v^{n+1}\) počítá z předchozích \(s\) kroků (\(s\)-kroková metoda), tj. z hodnot \(v^n, v^{n-1}, \dots, v^{n-s+1}\). Výhodou je, že k výpočtu \(v^{n+1}\) typicky stačí jedno vyčíslení pravé strany \(f(u,t)\), neboť ostatní hodnoty jsou známy z předchozích kroků; tyto metody tedy mohou být rychlejší při vyšší přesnosti. Nevýhodou je náročnější inicializace (potřebujeme na začátku \(s\) počátečních hodnot — lze např. použít Rungeovu–Kuttovu metodu) a obtížná změna kroku. Předpokladem je spojitost vyšších derivací. Příkladem jsou lineární vícekrokové metody.
Explicitní a implicitní metody
Dále dělíme metody na explicitní a implicitní. U explicitních metod nepotřebujeme k nalezení \(v^{n+1}\) hodnotu \(f(v^{n+1}, t_{n+1})\). U implicitních metod závisí \(v^{n+1}\) na \(f(v^{n+1}, t_{n+1})\); je tedy nutné řešit (typicky nelineární) rovnici pro \(v^{n+1}\), k čemuž slouží iterační metody.
Někdy se používají tzv. metody prediktor–korektor, kdy do implicitního schématu dosazujeme za \(v^{n+1}\) v argumentu \(f(v^{n+1}, t_{n+1})\) odhad určený z explicitní metody.
Výhodou implicitních metod je vyšší stabilita (viz později).
Lokální a globální diskretizační chyba
V každém kroku délky \(k\) se dopouštíme lokální chyby, kterou můžeme určit z Taylorova rozvoje. Její první člen bude řádu \(O(k^{p+1})\), kde \(p\) nazýváme řád přesnosti metody.
Nejjednodušší metodou je tzv. explicitní Eulerova metoda, která aproximuje
\begin{equation}\label{eq:06:euler_aprox} \frac{du(t_n)}{dt} \approx \frac{v^{n+1} - v^n}{k} = f(v^n, t_n) , \end{equation}a tedy
\begin{equation}\label{eq:06:euler} v^{n+1} = v^n + k\, f(v^n, t_n) . \end{equation}Lokální diskretizační chybu určíme tak, že za \(v^n\) položíme \(u(t)\) a za \(v^{n+1}\) hodnotu \(u(t+k)\) a určíme z Taylorova rozvoje chybu aproximace \(u(t+k)\) pomocí daného rekurentního vztahu, tj.
\begin{align*} u(t+k) - u(t) - k\, \underbrace{f(u(t),t)}_{u'(t)} &= u(t) + k u'(t) + \frac{k^2}{2} u''(t) + \dots - u(t) - k u'(t) = \\ &= \frac{k^2}{2} u''(t) + O(k^3) = O(k^{p+1}) , \end{align*}neboli \(p = 1\) pro explicitní Eulerovu metodu.
Pokud je lokální chyba řádu \(O(k^{p+1})\), lze za poměrně obecných předpokladů jak pro jednokrokové, tak pro vícekrokové metody ukázat, že globální chyba bude řádu \(O(k^p)\), pokud je daná metoda stabilní (tj. nedochází k růstu chyb v následných iteracích).
Takový výsledek lze očekávat, neboť pro určení \(v^n\) potřebujeme \(\frac{t_n}{k}\) kroků s lokální chybou \(O(k^{p+1})\), a tedy celková chyba by měla být
\[ O\!\left(\frac{t_n}{k}\, k^{p+1}\right) \approx O(k^p) . \]V praxi se samozřejmě projevuje též zaokrouhlovací chyba, a tedy podobně jako u numerické derivace existuje i zde jistá optimální volba kroku \(k\) minimalizující obě chyby zároveň. Opět platí, že pro vyšší přesnost jsou potřeba metody vyšších řádů.
Metoda leap-frog (též midpoint) je dvoukroková metoda druhého řádu. Aproximujeme derivaci v bodě \(t_n\) pomocí centrované diference
\begin{equation}\label{eq:06:leapfrog_aprox} \frac{du(t_n)}{dt} \approx \frac{v^{n+1} - v^{n-1}}{2k} \approx f(v^n, t_n) , \end{equation}neboli
\begin{equation}\label{eq:06:leapfrog} v^{n+1} = v^{n-1} + 2k\, f(v^n, t_n) . \end{equation}A tedy
\[ u(t+k) - u(t-k) - 2k\, f(u(t),t) = \] \begin{align*} &= u(t) + k u'(t) + \frac{k^2}{2} u''(t) + \frac{k^3}{3!} u'''(t) + O(k^4) \\ &\quad - u(t) + k u'(t) - \frac{k^2}{2} u''(t) + \frac{k^3}{3!} u'''(t) + O(k^4) \quad - 2k u'(t) = \\ &= \frac{k^3}{3} u'''(t) + O(k^4) = O(k^{p+1}) \implies p = 2 , \end{align*}neboť se navzájem vykrátí členy \(u(t)\) s \(-u(t)\), členy \(\frac{k^2}{2} u''(t)\) s \(-\frac{k^2}{2} u''(t)\) a členy \(k u'(t) + k u'(t)\) s \(-2k u'(t)\).
Ke metodě leap-frog: rostoucí křivka procházející třemi body nad dělicími body \(t_{n-1}\), \(t_n\), \(t_{n+1}\), sečna spojující krajní dva body, krátký úsek tečny v \(t_n\) a svislé spojnice k osám. Sečna je přesně centrovaná diference \eqref{eq:06:leapfrog_aprox}, čárkovaná zelená je skutečná tečna \(u'(t_n)\). Hodnoty se počítají živě: táhněte úchytem \(t_n\) po ose, měňte krok \(k\) a tlačítkem „půlit k“ si ověřte, že rozdíl sečny a tečny klesá jako \(k^2\), zatímco lokální chyba \(u(t+k)-u(t-k)-2k\,u'(t)\) klesá jako \(k^3/3\cdot u'''(t)\), tedy \(p = 2\).
Jednokrokové metody vyšších řádů
Obecná jednokroková metoda je
\begin{equation}\label{eq:06:obecna_jednokrokova} v^{n+1} = v^n + k\, \Phi(v^n, t_n, k) \end{equation}a její lokální diskretizační chyba je
\begin{equation}\label{eq:06:lokalni_chyba_jednokrokova} u(t+k) - u(t) - k\, \Phi(u(t), t, k) = O(k^{p+1}) . \end{equation}Aby metoda byla alespoň řádu \(p = 1\), musí platit
\begin{equation}\label{eq:06:podminka_p1} \Phi(u(t), t, 0) = f(u(t), t) . \end{equation}Vhodnou volbou \(\Phi\) dostáváme metody vyšších řádů.
Metoda Taylorova rozvoje
U metody Taylorova rozvoje je nutné vyčíslit derivace \(f(u(t),t)\). Plyne přímo dosazením za
\[ u'(t) = f(u(t),t) , \qquad u''(t) = \frac{\partial f}{\partial u}\, u'(t) + \frac{\partial f}{\partial t} \quad \text{atd.} \]do rozvoje
\[ u(t+k) = u(t) + k u'(t) + \frac{k^2}{2} u''(t) + \cdots , \]čímž dostaneme
\begin{equation}\label{eq:06:taylorova_metoda} v^{n+1} = v^n + k\, \overbrace{\left[ f(v^n, t_n) + \frac{k}{2}\left( \frac{\partial f}{\partial t}\Big|_{(v^n, t_n)} + f(v^n, t_n) \frac{\partial f}{\partial u}\Big|_{(v^n, t_n)} \right) + \cdots \right]}^{\Phi(v^n,\, t_n,\, k)} . \end{equation}Rungeovy–Kuttovy metody
Rungeovy–Kuttovy metody jsou lepší v tom, že u nich není nutné počítat derivace \(f\).
Motivace — metoda RK 2. řádu
Nejprve „nastřelíme“ do \(t = t_n + \frac{k}{2}\) pomocí explicitní Eulerovy metody
\begin{equation}\label{eq:06:rk2_nastrel} v^{n+\frac{1}{2}} = v^n + \frac{k}{2} f(v^n, t_n) \end{equation}a pak aproximujeme derivaci v \(t = t_n + \frac{k}{2}\) jako
\begin{equation}\label{eq:06:rk2} \underbrace{\frac{v^{n+1} - v^n}{k}}_{\text{centrovaná diference v bodě } t_n + \frac{k}{2}} = f\!\left(v^{n+\frac{1}{2}}, t_n + \frac{k}{2}\right) = f\!\left(v^n + \frac{k}{2} f(v^n, t_n),\, t_n + \frac{k}{2}\right) . \end{equation}Jeden krok RK metody 2. řádu: křivka řešení s body \(v^n\), \(v^{n+\frac{1}{2}}\) a \(v^{n+1}\), čárkovaná tečna v \(v^n\), sečna se směrnicí ve středním bodě a popisky \(t_n\), \(\frac{k}{2}\), \(t_n + \frac{k}{2}\), \(t_{n+1}\). Šedá křivka je přesné řešení zvolené rovnice procházející bodem \(v^n\), zelená čárkovaná tečna je \(f(v^n,t_n)\), oranžová směrnice v mezibodě je \(f(v^{n+\frac{1}{2}}, t_n+\frac{k}{2})\) podle \eqref{eq:06:rk2_nastrel} a \eqref{eq:06:rk2}. Táhněte bodem \(v^n\), měňte krok \(k\) a přepínejte mezi Eulerem, RK 2. a RK 4. řádu (u RK4 se vykreslí všechny čtyři mezistupně). Sledujte, jak lokální chyba klesá jako \(k^2\), \(k^3\), resp. \(k^5\); přepínač „celý běh“ ukáže globální chybu po mnoha krocích.
Jde o metodu 2. řádu, neboť
\[ u(t+k) - u(t) - k\, f\!\left(u(t) + \frac{k}{2} f(u(t),t),\, t + \frac{k}{2}\right) = \] \begin{align*} &= u(t) + k u'(t) + \frac{k^2}{2} u''(t) + O(k^3) \; - u(t) - k f(u(t),t) \\ &\quad - \frac{k^2}{2}\left( \frac{\partial f}{\partial u} f(u(t),t) + \frac{\partial f}{\partial t} \right) + O(k^3) \;=\; O(k^3) . \end{align*}Výsledný člen \(O(k^3)\) už není nulový, ač jsme to neukázali.
Obecný tvar a Butcherova tabulka
Obecnou metodu s \(r\) mezikroky (úrovněmi) lze psát ve tvaru
\begin{equation}\label{eq:06:rk_obecna_stupne} \left\{ \begin{aligned} y_1 &= v^n + k \sum_{j=1}^{r} a_{1j}\, f(y_j, t_n + c_j k) \\ &\;\;\vdots \\ y_r &= v^n + k \sum_{j=1}^{r} a_{rj}\, f(y_j, t_n + c_j k) \end{aligned} \right. \end{equation}a
\begin{equation}\label{eq:06:rk_obecna_krok} v^{n+1} = v^n + k \sum_{j=1}^{r} b_j\, f(y_j, t_n + c_j k) , \end{equation}což je ekvivalentní zápisu pomocí tzv. Butcherovy tabulky
\[ \begin{array}{c|ccc} c_1 & a_{11} & \dots & a_{1r} \\ \vdots & \vdots & \ddots & \vdots \\ c_r & a_{r1} & \dots & a_{rr} \\ \hline & b_1 & \dots & b_r \end{array} \]Většinou se používají explicitní metody. Pokud je libovolné \(a_{ij} \neq 0\) pro \(j \geq i\), pak jde o implicitní metodu.
Butcherova tabulka pro metodu 2. řádu (viz výše) je
\[ \begin{array}{c|cc} 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ \hline & 0 & 1 \end{array} \]a pro metodu 4. řádu
\[ \begin{array}{c|cccc} 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ \hline & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} & \frac{1}{6} \end{array} \]což je ekvivalentní předpisu
\begin{align*} y_1 &= v^n , \\ y_2 &= v^n + \frac{k}{2} f\!\left(y_1, t_n\right) , \\ y_3 &= v^n + \frac{k}{2} f\!\left(y_2, t_n + \frac{k}{2}\right) , \\ y_4 &= v^n + k\, f\!\left(y_3, t_n + \frac{k}{2}\right) \end{align*}a
\begin{equation}\label{eq:06:rk4} \begin{aligned} v^{n+1} = v^n + \frac{k}{6}\Big[ f\!\left(y_1, t_n\right) &+ 2 f\!\left(y_2, t_n + \frac{k}{2}\right) \\ &+ 2 f\!\left(y_3, t_n + \frac{k}{2}\right) + f\!\left(y_4, t_n + k\right) \Big] . \end{aligned} \end{equation}Podmínky na řád metody
Aby bylo \(p \geq 1\), tj. aby platilo \(\Phi(v^n, t_n, 0) = f(v^n, t_n)\), musí zřejmě platit
\begin{equation}\label{eq:06:podminka_bj} \sum_{j=1}^{r} b_j = 1 . \end{equation}Pro \(p \geq 2\) navíc dostaneme z Taylorova rozvoje (ponecháme pouze členy do \(k^2\))
\[ u(t+k) - u(t) - k \sum_{j=1}^{r} b_j\, f\!\left( u(t) + k \sum_{m=1}^{r} a_{jm} \underbrace{f\left(u(t),t\right)}_{\text{zde zahozeny členy } O(k)} ,\; t + c_j k \right) = \] \begin{align*} ={} & k u'(t) && + \frac{k^2}{2} u''(t) \; + O(k^3) \\ & - k \sum_{j=1}^{r} b_j f(u(t),t) && - k^2 \sum_{j=1}^{r} b_j \left( \sum_{m=1}^{r} a_{jm} \frac{\partial f}{\partial u} f(u(t),t) \; + c_j \frac{\partial f}{\partial t} \right) . \end{align*}Členy \(k u'(t)\) a \(-k\sum_{j=1}^{r} b_j f(u(t),t)\) se navzájem ruší právě tehdy, když
\[ 1 = \sum_{j=1}^{r} b_j , \]a poslední člen \(-k^2\sum_{j=1}^{r} b_j (\dots)\) má být roven členu s druhou derivací, tj.
\[ \frac{u''(t)}{2} = \frac{1}{2}\left( \frac{\partial f}{\partial u} f(u(t),t) + \frac{\partial f}{\partial t} \right) . \]A tedy podmínky pro \(p \geq 2\) jsou
\begin{equation}\label{eq:06:podminky_p2} \sum_{m=1}^{r} a_{jm} = c_j \qquad \text{a} \qquad \sum_{j=1}^{r} b_j c_j = \frac{1}{2} . \end{equation}Obecně existuje více metod určitého řádu (i pro explicitní metody), a proto se přidávají dodatečné podmínky, jako je stabilita, minimální koeficient u lokální chyby apod.
Podrobně viz Butcher: Numerical Methods for ODE, Wiley 2008.