Jump to content

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

Kolokačná metóda

[edit]

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′(ζ) v určitých bodoch medzi ti,ti+1 zodpovedajú deriváciám hľadanej funkcie, y′(ζ)=f(ζ,y(ζ)). Interpolačný polynóm u′ medzi ti,ti+1 sa potom numericky integruje, aby sa získala hodnota u(ti+1) - ktorá aproximuje nové riešenie y(ti+1).


Definícia 4.3 (kolokačná metóda): Nech c1,…cs∈[0,1] s sú kladné, párovo rôzne čísla (body mriežky) medzi 0 a 1, nech i=0,1,…Nh. Kolokačný polynóm u je definovaný u(ti)=ηi,u′(ti+cjh)=f(ti+cjh,u(ti+cjh)), nové numerické riešenie je určené ako ηi+1:=u(ti+1).


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 c1,…,cs. 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

[edit]

Je daný interval [a,b]∈ℝ n+1 uzlov x0,x1,…,xn∈[a,b] a hodnoty funkcie f(x0),…,f(xn).
Hľadáme polynóm pint∈ℙn stupňa n taký, že pint(xi)=!f(xi) for i=0,1,…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 ℓi∈ℙn: pint(x)=∑i=0nf(xi)ℓi(x)∈ℙn, mitℓi(x)=∏k=1,k≠inx−xkxi−xk={1 falls x=xi,0 x=xj,j≠i(4.16)


''Príklad 4.3 (Lagrangeov interpolačný polynóm s dvoma uzlami)
Nech n=1 a uzly interpolácie x0,x1. Lagrangeove polynómy pre tieto uzly sú lineárne funkcie ℓ0(x)=x−x1x0−x1  and  ℓ1(x)=x−x0x1−x0.

Z toho vyplýva, že Lagrangeov interpolačný polynóm pre dva uzly je pint(x)=f(x0)ℓ0(x)+f(x1)ℓ1(x)=f(x0)x−x1x0−x1+f(x1)x−x0x1−x0.

Pre lineárny polynóm pint zodpovedajú uzly x0,x1 funkcii f, ktorá sa má interpolovať, pretože ℓ0(x0)=1,ℓ1(x0)=0 a ℓ1(x1)=1,ℓ0(x1)=0.



Príklad 4.4 („Lagrangeov interpolačný polynóm s tromi uzlami“)
Nech n=2 a x0,x1,x2 sú uzly interpolácie. Lagrangeove fundamentálne polynómy pre tieto uzly sú kvadratické funkcie ℓ0(x)=(x−x1)(x−x2)(x0−x1)(x0−x2), ℓ1(x)=(x−x0)(x−x2)(x1−x0)(x1−x2), ℓ2(x)=(x−x0)(x−x1)(x2−x0)(x2−x1).

Lagrangeov interpolačný polynóm pre tri uzly je kvadratická funkcia pint(x)=f(x0)ℓ0(x)+f(x1)ℓ1(x)+f(x2)ℓ2(x)=f(x0)(x−x1)(x−x2)(x0−x1)(x0−x2)+f(x1)(x−x0)(x−x2)(x1−x0)(x1−x2)+f(x2)(x−x0)(x−x1)(x2−x0)(x2−x1).

V uzloch x0,x1,x2 sa pint zhoduje s f, pretože ℓi(xi)=1,i=1,2,3 a ℓi(xj)=0 ak i≠j.

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

Numerická integrácia

[edit]

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]:=∑i=0nαif(xi)≈∫abf(s)ds.(4.17)

xi sú uzly, α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, ∫abf(s)ds≈∫abpint(s)ds=∫ab∑i=0nf(xi)ℓi(s)=∑i=0nf(xi)∫abℓi(s)ds⏟:=αi.(4.18)

Newtonova-Cotesova kvadratúra k ľubovoľným, párovo rôznym uzlom x0,x1,…,xn je teda definovaná (4.17) so špeciálnymi váhami Q[f]:=∑i=0nαif(xi),αi=∫abℓ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]=∫abpint in blau und ∫abf 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 x0≠x1≠…≠xn∈[a,b] je teda aspoň n. Ak sa uzly xi 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 c1,…,cs a nasledujúcimi koeficientmi: ajm=∫0cjℓm(t)dtbm=∫01ℓm(t)dt, m,j=1,…,s,wobeiℓm(t)=∏k=1,k≠mst−ckcm−ck∈ℙs−1(4.20) Lagrangeov fundamentálny polynóm je.


Dôkaz
V (4. 15) označme u′(ti+cjh)=f(ti+cjh,u(ti+cjh)):=kj a vytvoríme interpolačný polynóm na [ti,ti+h] pre deriváciu u′ cez s uzlov ti+cjh, j=1,…,s, cj∈[0,1], u′(t)=∑m=1skmℓ~m(t),ℓ~j(t)=∏k=1,k≠jst−(ti+hck)ti+hcj−(ti+hck)∈ℙs−1.(4.21)

Po integrovaní ∫titi+cjhdt sa z uvedenej rovnice pomocou u(ti)=ηi získa nasledovné: u(ti+cjh)=u(ti)+∑m=1skm∫titi+cjhℓ~m(t)dt=ηi+h∑m=1skm∫0cjℓm(c)dc,(4.22) kde bola použitá substitúcia premennej c:=t−tih, c∈[0,1] a ℓm je definovaná ako v (4.20). Ak teraz integrujeme v (4.21) až do ti+h, dostaneme s rovnakou substitúciou, u(ti+h)%=u(ti)+∑m=1skm∫titi+cjhℓ~m(t)dt=ηi+h∑m=1skm∫01ℓm(c)dc.(4.23)

Ak teraz označíme bm:=∫01ℓm(c)dc,
nová číselná hodnota ηi+1 sa vypočíta pomocou kolokačnej metódy ako u(ti+h) a teda pomocou (4. 23) ako ηi+1=ηi+h∑m=1skmbm, čo zodpovedá tvaru RK aktualizácie, pozri (4.2).
Aby sme kolokačnú metódu úplne stotožnili s Runge-Kutta metódou, kj:=f(ti+cjh,u(ti+cjh)), j=1,…,s zo začiatku dôkazu s ohodnotením funkcie kj v medzistupňoch (4. 1) (kj vypočítané pomocou matice koeficientov). Na to stačí nahradiť hodnoty u(ti+cjh) v argumente f pomocou (4. 22) a dostaneme kj:=f(ti+cjh,u(ti+cjh))=f(ti+cjh,ηi+h∑m=1skm∫0cjℓm(c)dc), ktorý je označený ajm:=∫0cjℓm(c)dc
kroky kj (implicitnej) Runge-Kutta metódy, (4.1), s definovanou maticou koeficientov (A)jm=ajm. ◻