Obyčajné differenciálne rovnice/Kolokačná metóda

Kolokačná metóda

Termín kolokácia pochádza zo slova kolokovať - súhlasiť a je elegantným spôsobom konštrukcie implicitných Runge-Kutta metód vyššieho rádu konzistencie. Základnou myšlienkou kolokačnej metódy je konštrukcia polynómu (kolokačný polynóm $u(t)$), ktorého derivácie $u'(\zeta )$ v určitých bodoch medzi $t_{i},t_{i+1}$ zodpovedajú deriváciám hľadanej funkcie, $y'(\zeta )=f(\zeta ,y(\zeta ))$. Interpolačný polynóm $u'$ medzi $t_{i},t_{i+1}$ sa potom numericky integruje, aby sa získala hodnota $u(t_{i+1})$ - ktorá aproximuje nové riešenie $y(t_{i+1})$.

---

Definícia 4.3 (kolokačná metóda): Nech $c_{1},\dots c_{s}\in [0,1]$ s sú kladné, párovo rôzne čísla (body mriežky) medzi 0 a 1, nech $i=0,1,\ldots N_{h}$. Kolokačný polynóm $u$ je definovaný ${\begin{aligned}u(t_{i})&=&\eta _{i},\qquad \qquad \qquad \qquad \qquad \\u'(t_{i}+c_{j}h)&=&f(t_{i}+c_{j}h,u(t_{i}+c_{j}h)),\end{aligned}}$ nové numerické riešenie je určené ako ${\begin{aligned}\eta _{i+1}:=u(t_{i+1}).\end{aligned}}$

---

V kolokačnej metóde sa polynóm $u$ v praxi explicitne nevypočítava, ale realizuje sa ako interpolačná úloha (4.15) spojená s následnou numerickou integráciou (intepolačná kvadratúra). Výsledkom tohto postupu s použitím Lagrangeovho interpolačného polynómu v (4.15) a po integrácii tohto interpolačného polynómu je numerická metóda, ktorú možno formulovať ako Runge-Kutta metódu s interpolačnými bodmi s $c_{1},\ldots ,c_{s}$. Táto realizácia umožňuje praktickú implementáciu kolokačnej metódy ako (implicitnej) Runge-Kutta metódy a neskôr je formulovaná ako veta a dokázaná konštrukčne. Tým sa stáva jasným spojenie kolokačnej metódy s iRKV, v ktorej je kolokačná metóda prevedená na Runge-Kutta metódu so špeciálnymi váhami a koeficientmi. Kolokačnú metódu možno teda považovať za spôsob konštrukcie špeciálnych iRKV.

Skôr ako sformulujeme a dokážeme vetu o praktickej realizácii kolokačnej metódy, urobíme exkurz o princípoch numerickej interpolácie a integrácie.

Interpolácia

Je daný interval $[a,b]\in {\mathbb {R} }$ $n+1$ uzlov $x_{0},x_{1},\ldots ,x_{n}\in [a,b]$ a hodnoty funkcie $f(x_{0}),\ldots ,f(x_{n})$.
Hľadáme polynóm $p_{int}\in {\mathbb {P} }^{n}$ stupňa $n$ taký, že $p_{int}(x_{i}){\stackrel {!}{=}}f(x_{i})\ {\mbox{for}}\ i=0,1,\ldots n.$ Najznámejším interpolačným polynómom je Lagrangeov interpolačný polynóm, ktorý je zložený ako kombinácia Lagrangeových fundamentálnych polynómov $\ell _{i}\in {\mathbb {P} }^{n}$: ${\begin{aligned}p_{int}(x)=\sum _{i=0}^{n}f(x_{i})\ell _{i}(x)\in {\mathbb {P} }^{n},\ \qquad {\mbox{mit}}\qquad \\\ell _{i}(x)=\prod _{k=1,k\neq i}^{n}{\frac {x-x_{k}}{x_{i}-x_{k}}}=\left\{{\begin{matrix}1&&\ {\mbox{falls}}\ x=x_{i},\\0&&\ x=x_{j},\;j\neq i\end{matrix}}\right.\qquad \qquad (4.16)\end{aligned}}$

''Príklad 4.3 (Lagrangeov interpolačný polynóm s dvoma uzlami)
Nech $n=1$ a uzly interpolácie $x_{0},x_{1}$. Lagrangeove polynómy pre tieto uzly sú lineárne funkcie $\ell _{0}(x)={\frac {x-x_{1}}{x_{0}-x_{1}}}\ \ {\mbox{and}}\ \ \ell _{1}(x)={\frac {x-x_{0}}{x_{1}-x_{0}}}.$

Z toho vyplýva, že Lagrangeov interpolačný polynóm pre dva uzly je $p_{int}(x)=f(x_{0})\ell _{0}(x)+f(x_{1})\ell _{1}(x)=f(x_{0}){\frac {x-x_{1}}{x_{0}-x_{1}}}+f(x_{1}){\frac {x-x_{0}}{x_{1}-x_{0}}}.$

Pre lineárny polynóm $p_{int}$ zodpovedajú uzly $x_{0},x_{1}$ funkcii $f$, ktorá sa má interpolovať, pretože $\ell _{0}(x_{0})=1,\ell _{1}(x_{0})=0$ a $\ell _{1}(x_{1})=1,\ell _{0}(x_{1})=0$.

Príklad 4.4 („Lagrangeov interpolačný polynóm s tromi uzlami“)
Nech $n=2$ a $x_{0},x_{1},x_{2}$ sú uzly interpolácie. Lagrangeove fundamentálne polynómy pre tieto uzly sú kvadratické funkcie $\ell _{0}(x)={\frac {(x-x_{1})(x-x_{2})}{(x_{0}-x_{1})(x_{0}-x_{2})}},\ \ell _{1}(x)={\frac {(x-x_{0})(x-x_{2})}{(x_{1}-x_{0})(x_{1}-x_{2})}},\ \ell _{2}(x)={\frac {(x-x_{0})(x-x_{1})}{(x_{2}-x_{0})(x_{2}-x_{1})}}.$

Lagrangeov interpolačný polynóm pre tri uzly je kvadratická funkcia ${\begin{aligned}&&p_{int}(x)=f(x_{0})\ell _{0}(x)+f(x_{1})\ell _{1}(x)+f(x_{2})\ell _{2}(x)=\\&&f(x_{0}){\frac {(x-x_{1})(x-x_{2})}{(x_{0}-x_{1})(x_{0}-x_{2})}}+f(x_{1}){\frac {(x-x_{0})(x-x_{2})}{(x_{1}-x_{0})(x_{1}-x_{2})}}+f(x_{2}){\frac {(x-x_{0})(x-x_{1})}{(x_{2}-x_{0})(x_{2}-x_{1})}}.\end{aligned}}$

V uzloch $x_{0},x_{1},x_{2}$ sa $p_{int}$ zhoduje s $f$, pretože $\ell _{i}(x_{i})=1,i=1,2,3$ a $\ell _{i}(x_{j})=0$ ak $i\neq j$.

Obrázok 4.2: Interpolácia v intervale $[a,b]$ s tromi uzlami: Lagrangeove fundamentálne polynómy $\ell _{0},\ \ell _{1},\ \ell _{2}$ a interpolovaná funkcia $f$.

Numerická integrácia

Numerická integrácia - kvadratúra - je spôsob, ako aproximovať určitý integrál funkcie súčtom, t. j. lineárnou kombináciou určitých hodnôt funkcie, a tak ho algoritmicky vypočítať, $Q[f]:=\sum _{i=0}^{n}\alpha _{i}f(x_{i})\approx \int _{a}^{b}f(s)ds.\qquad \qquad (4.17)$

$x_{i}$ sú uzly, $\alpha _{i}$ sú váhy kvadratúry.
Prirodzeným spôsobom aproximácie integrálu súčtom je interpolačná kvadratúra: integrácia interpolačného polynómu. Príkladom interpolačnej kvadratúry je Newtonova-Cotesova kvadratúra, kde sa vytvorí a integruje Lagrangeov interpolačný polynóm pre integrovanú funkciu, ${\begin{aligned}\int _{a}^{b}f(s)ds\approx \int _{a}^{b}p_{int}(s)ds=\int _{a}^{b}\sum _{i=0}^{n}f(x_{i})\ell _{i}(s)=\sum _{i=0}^{n}f(x_{i})\underbrace {\int _{a}^{b}\ell _{i}(s)ds} _{:=\alpha _{i}}.\quad (4.18)\end{aligned}}$

Newtonova-Cotesova kvadratúra k ľubovoľným, párovo rôznym uzlom $x_{0},x_{1},\ldots ,x_{n}$ je teda definovaná (4.17) so špeciálnymi váhami $Q[f]:=\sum _{i=0}^{n}\alpha _{i}f(x_{i}),\quad \alpha _{i}=\int _{a}^{b}\ell _{i}(s)ds.\quad (4.19)$

Obrázok 4.3: Interpolačná kvadratúra $f$ v intervale $[a,b]$ ako integrál Lagrangeovho interpolačného polynómu (príklad 4.4). Tu $Q[f]=\int _{a}^{b}p_{int}$ in blau und $\int _{a}^{b}f$ v červených pruhoch.

Exaktheitsgrad stupňa kvadratúry

je stupeň polynómov, pre ktoré kvadratúra ešte presne vypočíta integrál.

V prípade interpolačnej kvadratúry exaktnosť kvadratúry priamo súvisí s exaktnosťou interpolácie. Pre $n+1$ uzly je interpolačný polynóm $n$-tého stupňa určený jednoznačne, a preto sú všetky polynómy $n$-tého stupňa, ktoré sa zhodujú v $n+1$ uzloch, identické. Napríklad lineárna funkcia je jednoznačne a presne (bez chyby) reprezentovaná interpolačným polynómom s dvoma uzlami, pozri príklad 4.3, kvadratická funkcia je jednoznačne a presne určená interpolačným polynómom s tromi uzlami, pozri príklad 4.4 atď. Keďže interpolačná kvadratúra je následná (presná) integrácia, stupeň presnosti tejto kvadratúry pre voľne voliteľné uzly $x_{0}\neq x_{1}\neq \ldots \neq x_{n}\in [a,b]$ je teda aspoň $n$. Ak sa uzly $x_{i}$ interpolačnej kvadratúry špeciálne vyberú, možno dosiahnuť ešte vyšší stupeň presnosti. To je prípad Gaussovej kvadratúry, ktorá dosahuje maximálny stupeň presnosti $2n+1$ pre ${\textstyle n+1}$ špeciálne vybrané uzly, viac informácií o Gaussovej kvadratúre nájdete napríklad v [3].

Použitie numerickej interpolácie a Newtonovej-Cotesovej (interpolačnej) kvadratúry (4.17)-(4.19) na odvodenie kolokačného polynómu $u$ vedie k nasledujúcej vete o praktickom použití kolokačnej metódy, ako už bolo oznámené.

---

Veta 4.3 (kolokačná metóda ako iRKV): Kolokačná metóda (4.15) je ekvivalentná s-krokovej Runge-Kutta metóde s interpolačnými bodmi $c_{1},\ldots ,c_{s}$ a nasledujúcimi koeficientmi: ${\begin{aligned}a_{jm}=\int _{0}^{c_{j}}\ell _{m}(t)dt&&b_{m}=\int _{0}^{1}\ell _{m}(t)dt,\ m,j=1,\ldots ,s,\\{\mbox{wobei}}&&\ell _{m}(t)=\prod _{k=1,k\neq m}^{s}{\frac {t-c_{k}}{c_{m}-c_{k}}}\in {\mathbb {P} }^{s-1}\end{aligned}}\qquad (4.20)$ Lagrangeov fundamentálny polynóm je.

---

Dôkaz

V (4. 15) označme $u'(t_{i}+c_{j}h)=f(t_{i}+c_{j}h,u(t_{i}+c_{j}h)):=k_{j}$ a vytvoríme interpolačný polynóm na $[t_{i},t_{i}+h]$ pre deriváciu $u'$ cez s uzlov $t_{i}+c_{j}h,\ j=1,\ldots ,s,\ c_{j}\in [0,1]$, $u'(t)=\sum _{m=1}^{s}k_{m}{\tilde {\ell }}_{m}(t),\quad {\tilde {\ell }}_{j}(t)=\prod _{k=1,k\neq j}^{s}{\frac {t-(t_{i}+hc_{k})}{t_{i}+hc_{j}-(t_{i}+hc_{k})}}\in {\mathbb {P} }^{s-1}.\quad (4.21)$

Po integrovaní $\int _{t_{i}}^{t_{i}+c_{j}h}dt$ sa z uvedenej rovnice pomocou $u(t_{i})=\eta _{i}$ získa nasledovné: $u(t_{i}+c_{j}h)=u(t_{i})+\sum _{m=1}^{s}k_{m}\int _{t_{i}}^{t_{i}+c_{j}h}{\tilde {\ell }}_{m}(t)dt=\eta _{i}+h\sum _{m=1}^{s}k_{m}\int _{0}^{c_{j}}\ell _{m}(c)dc,\qquad (4.22)$ kde bola použitá substitúcia premennej $c:={\frac {t-t_{i}}{h}},\ c\in [0,1]$ a $\ell _{m}$ je definovaná ako v (4.20). Ak teraz integrujeme v (4.21) až do $t_{i}+h$, dostaneme s rovnakou substitúciou, $u(t_{i}+h)\%=u(t_{i})+\sum _{m=1}^{s}k_{m}\int _{t_{i}}^{t_{i}+c_{j}h}{\tilde {\ell }}_{m}(t)dt=\eta _{i}+h\sum _{m=1}^{s}k_{m}\int _{0}^{1}\ell _{m}(c)dc.\qquad (4.23)$

Ak teraz označíme $b_{m}:=\int _{0}^{1}\ell _{m}(c)dc,$

nová číselná hodnota $\eta _{i+1}$ sa vypočíta pomocou kolokačnej metódy ako $u(t_{i}+h)$ a teda pomocou (4. 23) ako $\eta _{i+1}=\eta _{i}+h\sum _{m=1}^{s}k_{m}b_{m},$ čo zodpovedá tvaru RK aktualizácie, pozri (4.2).

Aby sme kolokačnú metódu úplne stotožnili s Runge-Kutta metódou, $k_{j}:=f(t_{i}+c_{j}h,u(t_{i}+c_{j}h)),\ j=1,\ldots ,s$ zo začiatku dôkazu s ohodnotením funkcie $k_{j}$ v medzistupňoch (4. 1) ($k_{j}$ vypočítané pomocou matice koeficientov). Na to stačí nahradiť hodnoty $u(t_{i}+c_{j}h)$ v argumente $f$ pomocou (4. 22) a dostaneme $k_{j}:=f(t_{i}+c_{j}h,u(t_{i}+c_{j}h))=f{\Big (}t_{i}+c_{j}h,\eta _{i}+h\sum _{m=1}^{s}k_{m}\int _{0}^{c_{j}}\ell _{m}(c)dc{\Big )},$ ktorý je označený $a_{jm}:=\int _{0}^{c_{j}}\ell _{m}(c)dc$

kroky $k_{j}$ (implicitnej) Runge-Kutta metódy, (4.1), s definovanou maticou koeficientov $(A)_{jm}=a_{jm}$. ◻