Materiály ze cvičení
Kód k vícekrokovým metodám - Adams-Bashforthovy metody
V souboru níže je možné nalézt kód pro řešení SODE pomocí vícekrokového explicitního řešiče. Konkrétně pomocí Adams-Bashforthovy metody 4. řádu a tedy s chybou O(h^4). Součástí tohoto řešiče je i vestavěná metoda Runge-Kutta 4. řádu použitá k nastartování výpočtu.Schéma řešení počáteční úlohy SODE Adams-Bashforthovou metodou k-tého řádu je přibližně:
- Zpracuj vstupní údaje. Vytvoř proměnné pro ukládání řešení.
- Vytvoř pomocnou proměnnou
- Proveď k kroků jednokrokovou metodou a postupně ukládej vyčíslení vektoru pravých stran (přidružené vektorové pole) v každém z těchto kroků do pomocné proměnné.
- Po naplnění pomocné proměnné (už mám všechny údaje, které potřebuji k vyčíslení dalšího kroku k-krokovou metodou). Přestaň pro výpočet dalších kroků řešení používat jednokrokovou metodu, ale začni používat metodu vícekrokovou.
- Vyčísluj jednotlivé body řešení pomocí vícekrokové metody. Je nutné pokaždé aktualizovat pomocnou proměnnou o nově nabyté informace.
- Opakuj bod 5 až do chvíle, než dojdeš na konec intervalu, na kterém aproximuješ řešení.
- Vypiš řešení.
Kód k metodám řešení prediktor-korektor
V případě, že vyžadujeme vyšší přesnost řešení a nejsme ochotni/nemůžeme integrovat s kratším krokem (například případy, kdy integrace s krátkým krokem už interferuje s přesností počítače v některé z prováděných operací), je vhodné použít k řešení SODE některou z metod prediktor-korektor.Tyto metody jsou obvykle (rozumnějme prakticky vždy) kombinací explicitní a implicitní metody.
Jenom pro pořádek, explicitní metoda určuje hodnotu řešení y_N na základě hodnoty předchozího kroku, y_N-1, a vyčíslení pravých stran (vektorového pole) v obecně k předchozích krocích. Implicitní metoda potřebuje vyčíslení vektorového pole i v kroku aktuálním (N-tém).
Prediktor je v této kombinaci tedy explicitní metoda, ze které získáme odhad řešení v N-tém kroku.
Korektor je metoda implicitní. Tedy abychom nalezli y_N, musíme řešit soustavu nelineárních algebraických rovnic
(1) 0 = y_N - y_N-1 - MAP(y_N,knowns),
kde MAP je nějaká lineární kombinace hodnot vektorového pole v k předchozích bodech (knowns) a neznámém y_N.
Jako počáteční nástřel pro numerický řešič této soustavy použijeme hodnotu dopočtenou v prediktoru. Samotný řešič můžeme použít libovolný. V souboru, který máte k dispozici je použita metoda prostých iterací, která konverguje pro dostatečně malý krok metody a dostatečně dobrý odhad získaný z prediktora. Další možností je použít například Newtonovu metodu, která konverguje výrazně rychleji, ale je citlivější na počáteční nástřel. Robustní volbou by bylo startovat řešič pomocí metody půlení intervalu, takto zpřesnit počáteční odhad prediktoru a až tento zpřesněný odhad použít jako počáteční nástřel Newtonovy metody.
Soubor s implementací metody prediktor-korektor naleznete zde. Jako prediktor je použita Adams-Bashforthsova metoda 4. řádu (ta, kterou jsme procházeli posledně na cvičení). Jako korektor potom metoda Adams-Moultonova, také 4. řádu. Jako řešič soustavy (1) je použita metoda prostých iterací.
Jelikož je hlavní integrátor vícekrokový, je třeba jej startovat. Zde je k nastartování metody použita metoda Runge-Kutta 4. řádu, bez korektoru.
Pozn: Dalším velmi důležitým uplatněním metod prediktor-korektor jsou takzvané kontinuační algoritmy. Tyto algoritmy slouží ke studiu závislosti kořenů (soustav) nelineárních algebraických rovnic na parametrech. Informace o kontinuačních algoritmech je možné nalézt v monografii Z: Holodniok M., Klíč A., Kubíček M., Marek M.: Metody analýzy nelineárních dynamických modelů. Academia Praha 1986. ISBN 21-010-86. Anglicky, ale zato online dostupná je monografie Allgower, E. Kurt, G. Introduction to Numerical Continuation Methods.
Kód k metodám numerického řešení okrajové úlohy pro SODE
V případě počátečních úloh SODE se můžeme opřít o větu o existenci a jednoznačnosti řešení. I když řešení nemůžeme nalézt přesně (analyticky), víme, že existuje a známe právě jeden bod ze stavového prostoru, kterým prochází. Můžeme tedy (teoreticky) řešení aproximovat s libovolně velkou přesností postupem z tohoto známého bodu.V případě úloh okrajových neexistije žádný ekvivalent věty o existenci a jednoznačnosti. Navíc ani nemáme žádný z bodů stavového prostoru, kterými řešení prochází určený jednoznačně.
Prezentovaný algoritmus je založen na takzvané metodě střelby. Ta spočívá v dotipování neznámých souřadnic řešení v jedné z okrajových podmínek a v následné minimalizaci vzdálenosti mezi bodem, do kterého se dostaneme integrací z naší tipované počáteční podmínky a známými souřadnicemi bodu, do kterého bychom se dostat měli (okrajová podmínka).
Algoritmus má dvě úrovně, vnitřní a vnější řešič. Vnitřní řešič se stará o integraci řešeného systému, vnější řešič o minimalizaci (nulování) vzdálenosti od požadovaného konečného bodu. Vnější řešič je tedy nějaká metoda schopná řešit soustavu nelineárních rovnic.
Algoritmus je možné nalézt zde. Jako vnitřní řešič je použita metoda Runge-Kutta 4. řádu. Jako řešič vnější potom Newtonova metoda.
Proč je řešení nepřesné i přesto, že Newton konverguje? Jak bychom se mohli této nepřesnosti zbavit? Pro jaké problémy jsou metody střelby vhodné a pro jaké naopak nikoliv?