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^{\prime }(\zeta )$ v určitých bodoch medzi $t_i,t_{i+1}$ zodpovedajú deriváciám hľadanej funkcie, $y^{\prime }(\zeta )=f(\zeta ,y(\zeta ))$. Interpolačný polynóm $u^{\prime }$ 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,\dots N_h$. Kolokačný polynóm $u$ je definovaný $\begin{array}{ccc}u(t_i)& =& {\eta }_i,\\ u^{\prime }(t_i+c_{j}h)& =& f(t_i+c_{j}h,u(t_i+c_{j}h)),\end{array}$ nové numerické riešenie je určené ako $\begin{array}{c}{\eta }_{i+1}:=u(t_{i+1}).\end{array}$

---

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,\dots ,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 ℝ$ $n+1$ uzlov $x_0,x_1,\dots ,x_n\in [a,b]$ a hodnoty funkcie $f(x_0),\dots ,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)\text{for}i=0,1,\dots 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{array}{c}{p}_{int}(x)=\sum _{i=0}^{n}f(x_i){\ell }_i(x)\in {\mathbb{P}}^n,\text{mit}\\ {\ell }_i(x)=\prod _{k=1,k\ne i}^n\frac{x-x_k}{x_i-x_k}=\{\begin{array}{ccc}1& & \text{falls}x=x_i,\\ 0& & x=x_j,j\ne i\end{array}(4.16)\end{array}$

''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}\text{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{array}{ccc}& & 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{array}$

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\ne 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 \underset{a}{\overset{b}{\int }}f(s)ds.(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{array}{c}\underset{a}{\overset{b}{\int }}f(s)ds\approx \underset{a}{\overset{b}{\int }}{p}_{int}(s)ds=\underset{a}{\overset{b}{\int }}\sum _{i=0}^{n}f(x_i){\ell }_i(s)=\sum _{i=0}^{n}f(x_i)\underset{:={\alpha }_i}{\underbrace{\underset{a}{\overset{b}{\int }}{\ell }_i(s)ds}}.(4.18)\end{array}$

Newtonova-Cotesova kvadratúra k ľubovoľným, párovo rôznym uzlom $x_0,x_1,\dots ,x_n$ je teda definovaná (4.17) so špeciálnymi váhami $Q[f]:=\sum _{i=0}^n{\alpha }_{i}f(x_i),{\alpha }_i=\underset{a}{\overset{b}{\int }}{\ell }_i(s)ds.(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]=\underset{a}{\overset{b}{\int }}{p}_{int}$ in blau und $\underset{a}{\overset{b}{\int }}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\ne x_1\ne \dots \ne 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 $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,\dots ,c_s$ a nasledujúcimi koeficientmi: $\begin{array}{ccc}{a}_{jm}=\underset{0}{\overset{c_j}{\int }}{\ell }_m(t)dt& & b_m=\underset{0}{\overset{1}{\int }}{\ell }_m(t)dt,m,j=1,\dots ,s,\\ \text{wobei}& & {\ell }_m(t)=\prod _{k=1,k\ne m}^s\frac{t-c_k}{c_m-c_k}\in {\mathbb{P}}^{s-1}\end{array}(4.20)$ Lagrangeov fundamentálny polynóm je.

---

Dôkaz

V (4. 15) označme $u^{\prime }(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^{\prime }$ cez s uzlov $t_i+c_{j}h,j=1,\dots ,s,c_j\in [0,1]$, $u^{\prime }(t)=\sum _{m=1}^s{k}_m{\tilde{\ell }}_m(t),{\tilde{\ell }}_j(t)=\prod _{k=1,k\ne j}^s\frac{t-(t_i+h{c}_k)}{t_i+h{c}_j-(t_i+h{c}_k)}\in {\mathbb{P}}^{s-1}.(4.21)$

Po integrovaní $\underset{t_i}{\overset{t_i+c_{j}h}{\int }}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\underset{t_i}{\overset{t_i+c_{j}h}{\int }}{\tilde{\ell }}_m(t)dt={\eta }_i+h\sum _{m=1}^s{k}_m\underset{0}{\overset{c_j}{\int }}{\ell }_m(c)dc,(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)\mathrm{\%}=u(t_i)+\sum _{m=1}^s{k}_m\underset{t_i}{\overset{t_i+c_{j}h}{\int }}{\tilde{\ell }}_m(t)dt={\eta }_i+h\sum _{m=1}^s{k}_m\underset{0}{\overset{1}{\int }}{\ell }_m(c)dc.(4.23)$

Ak teraz označíme $b_m:=\underset{0}{\overset{1}{\int }}{\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,\dots ,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(t_i+c_{j}h,{\eta }_i+h\sum _{m=1}^s{k}_m\underset{0}{\overset{c_j}{\int }}{\ell }_m(c)dc),$ ktorý je označený $a_{jm}:=\underset{0}{\overset{c_j}{\int }}{\ell }_m(c)dc$

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