Obyčajné differenciálne rovnice/Implicitné Runge-Kutta metódy

4.3 Implicitné Runge-Kutta metódy

edit

Ak je matica koeficientov   v Butcherovej tabuľke Rungeho-Kuttovej metódy plne vyplnenou maticou, výpočet ohodnotení funkcie   pre každé   závisí od ostatných  , najmä tiež od   , pozri (4. 1). Najjednoduchšou iRKV je už známa implicitná Eulerova metóda, ďalšími príkladmi sú implicitný stredový bod a lichobežníkové pravidlo:

Implicitné pravidlo stredového bodu,  :

 


 

Implicitné lichobežníkové pravidlo,  :

 



 

Dôležitou podmnožinou iRKV sú tzv. gaussovské metódy, ktoré umožňujú čo najväčší poriadok vzhľadom na počet krokov. Tieto metódy patria medzi takzvané kolokačné metódy a sú odvodené od Gaussovej kvadratúry, ktorej vďačia za svoj názov. Gaussove metódy, ako aj iné (ale nie všetky) iRKV, majú dobré stabilizačné vlastnosti, ktoré sú dôležité najmä pri „tuhých“ problémoch.

Stiff problémy

edit

Pojem tuhý problém vznikol pri použití numerických metód na riešenie diferenciálnej rovnice, keď sa na získanie použiteľného konvergentného riešenia vyžadujú veľmi malé veľkosti krokov alebo menšie a menšie veľkosti krokov s postupom metódy. V takýchto prípadoch explicitné metódy, ako napríklad Eulerova metóda alebo eRKV vyššieho rádu s pevnou veľkosťou kroku, zlyhávajú; metódy s riadením veľkosti kroku vytvárajú stále menšie veľkosti kroku až po nulu (v rámci presnosti počítača), čo znamená, že v určitom bode sa už nepohybujú, zastavia sa - odtiaľ pochádza termín „tuhý“.

Medzi tuhé problémy patria diferenciálne rovnice s riešeniami s vysokou rýchlosťou zmien alebo systémy so zložkami riešenia, ktoré rastú veľmi rozdielnou rýchlosťou. Tu explicitná metóda generuje aproximáciu riešenia v ďalšom časovom kroku na základe predchádzajúcich, vo vysoko dynamických systémoch už nie aktuálnych, sklonov/informácií náchylných na chyby, a tak explicitná metóda rýchlo prekročí cieľ.

Príkladom tuhých problémov sú systémy lineárnych diferenciálnych rovníc, ktorých matica má veľmi rozdielne vlastné hodnoty, alebo diferenciálne rovnice opisujúce chemické reakcie s látkami, ktoré reagujú rôznymi rýchlosťami. Vďaka dobrým stabilizačným vlastnostiam implicitných jednokrokových metód, ktoré svoj priebeh v aktuálnom kroku prispôsobujú budúcemu (ešte silnejšiemu) gradientu, a tak poskytujú dobré výsledky aj pre väčšie veľkosti krokov  , sú iRKV vhodné najmä pre tuhé problémy.


 

Obrázok 4.1: Komponenty riešenia systému tuhej diferenciálnej rovnice, presné riešenie   a aproximácia explicitnou Eulerovou metódou,  .

Pri implicitných Runge-Kutta metódach sa kroky   počítajú riešením sústavy rovníc (4.1). Existencia riešenia tejto prípadne nelineárnej sústavy rovníc nie je vždy zaručená alebo dosiahnuteľná pomocou iteračných metód. Postačujúcou podmienkou existencie takéhoto riešenia a konvergencie iteračnej metódy pevného bodu je dostatočne malá veľkosť kroku  :


Nastavenie 4.2 (Butcher 1964)

Nech   je spojitý na   a Lipschitzovo spojitý vzhľadom na   s Lipschitzovou konštantou  . Pre prírastok   platí  


Potom sústava rovníc (4.1),  

je jedinečné riešenie, ktoré sa dá vypočítať postupnou substitúciou (iteráciou pevného bodu). Ak  , potom   ako funkcie   sú tiež  -krát spojito diferencovateľné.


Dôkaz. Pre jednoduchosť nech  . Riešenie (nelineárnej) sústavy rovníc (4.1) pre   možno určiť iteračne:  


Ak sústavu rovníc (4.1) prevedieme do vektorového tvaru,  

pričom    

namiesto (4.13) dostaneme iteračné pravidlo  


s počiatočným vektorom  


Podľa Banachovej vety o pevnom bode, pozri vetu 2.1, kapitola 2, existuje jedinečné riešenie, pevný bod  , ak   je samomapovanie a kontrahovanie. Pre funkciu   platí, že  , t. j. vždy je samomapovanie.
Teraz skúmame, či   je kontrakcia. Odhadneme Lipschitzovu spojitosť funkcie   a trojuholníkovú nerovnosť pre absolútnu hodnotu v maximálnej norme:  

Z tohto odhadu vyplýva, že   je kontrakcia v Banachovom priestore  , ak  . Z toho vyplýva, že mapovanie   pre   v   má jedinečný pevný bod,  

Tvrdenie (4.13), (4.14) konverguje k tomuto pevnému bodu. Tvrdenie o p-násobnej spojitej diferencovateľnosti   ponecháme bez dôkazu. ◻



'Poznámka o riešiteľnosti iRKV Remark on the solvability of the iRKV


  1. Obmedzenie veľkosti kroku   môže byť veľmi obmedzujúce pre veľké   konštanty (t. j. pre   s vysokými hodnotami derivácie  ) môžu byť veľmi obmedzujúce a viesť k pomalej konvergencii metódy pevného bodu. Východiskom v týchto prípadoch je použitie inej iteračnej metódy s vyššou rýchlosťou konvergencie na výpočet  , napríklad Newtonovej, sekantovej alebo kvázi-Newtonovej metódy. Tieto metódy konvergujú aj pre väčšie  , pretože majú superlineárnu rýchlosť konvergencie, ak je počiatočná hodnota zvolená priaznivo, v rámci tzv. konvergenčného intervalu.
  2. Ak je funkcia   len lokálne Lipschitzovo spojitá v  , t. j. len v okolí  , potom vyplývajú ďalšie obmedzenia na veľkosť kroku  , aby sa zaručila vlastnosť samomapovania.
  3. Lipschitzova spojitosť procesnej funkcie   eRKV, ako aj iRKV vzhľadom na   vyplýva z Lipschitzovej spojitosti  . To znamená, že iRKV s rádom konzistencie p sú tiež konvergentné s rádom konvergencie p. (pozri vetu 3.1)