Exponenciální integrátor - Exponential integrator
Exponenciální integrátoři jsou třídou numerické metody pro řešení obyčejné diferenciální rovnice konkrétně problémy s počáteční hodnotou. Tato velká třída metod z numerická analýza je založen na přesné integraci lineární část problému počáteční hodnoty. Protože lineární část je integrovaný přesně to může pomoci zmírnit ztuhlost diferenciální rovnice. Exponenciální integrátory mohou být konstruovány tak, aby byly explicitní nebo implicitní pro obyčejné numerické diferenciální rovnice nebo sloužit jako integrátor času pro numerické parciální diferenciální rovnice.
Pozadí
Od roku 1960, tyto metody byly Certainem uznány[1] a papež.[2] Jak pozdní exponenciální integrátoři se stali aktivní oblastí výzkumu, viz Hochbruck a Ostermann (2010).[3] Původně vyvinut pro řešení tuhé diferenciální rovnice, metody byly použity k řešení parciální diferenciální rovnice počítaje v to hyperbolický stejně jako parabolický problémy[4] tak jako rovnice tepla.
Úvod
Zvažujeme problémy s počáteční hodnotou formuláře,
kde se skládá z lineární výrazy, a se skládá z nelineární Tyto problémy mohou pocházet z typičtějšího problému počáteční hodnoty
po místní linearizaci o pevném nebo místním stavu :
Tady, Odkazuje na parciální derivace z s ohledem na (jakobián z f).
Přesná integrace tohoto problému od času 0 do pozdějšího času lze provést pomocí maticové exponenciály definovat integrální rovnici pro přesné řešení:[3]
To je podobné přesnému integrálu použitému v Picard – Lindelöfova věta. V případě , tato formulace je přesným řešením lineární diferenciální rovnice.
Numerické metody vyžadují a diskretizace rovnice (2). Mohou být založeny na Runge-Kutta diskretizace,[5][6][7]lineární vícestupňové metody nebo řadu dalších možností.
Exponenciální Rosenbrockovy metody
Ukázalo se, že exponenciální Rosenbrockovy metody jsou velmi účinné při řešení velkých systémů tuhých obyčejných diferenciálních rovnic, které jsou obvykle výsledkem prostorové diskretizace časově závislých (parabolických) PDE. Tyto integrátory jsou konstruovány na základě spojité linearizace (1) podél numerického řešení
kde Tento postup má v každém kroku tu výhodu, žeTo značně zjednodušuje odvození podmínek řádu a zlepšuje stabilitu při integraci nelinearity Opět platí, že použití vzorce variace konstant (2) poskytuje přesné řešení v čase tak jako
Myšlenkou je nyní aproximovat integrál v (4) pomocí nějakého pravidla kvadratury s uzly a váhy (). Tím se získá následující třída explicitní exponenciální Rosenbrockovy metody, viz Hochbruck a Ostermann (2006), Hochbruck, Ostermann a Schweitzer (2009):
s . Koeficienty se obvykle volí jako lineární kombinace celých funkcí kde
Tyto funkce uspokojují relaci rekurze
Zavedením rozdílu , mohou být přeformulovány efektivnějším způsobem pro implementaci (viz také [3]) tak jako
Aby bylo možné implementovat toto schéma s velikostí adaptivního kroku, lze pro účely místního odhadu chyb zvážit následující vložené metody
které používají stejné fáze ale s váhami .
Pro usnadnění lze koeficienty explicitní exponenciální Rosenbrockovy metody spolu s jejich vloženými metodami reprezentovat pomocí takzvaného redukovaného Butcherova tabla takto:
Přísné podmínky objednávky
Navíc je zobrazen v Luan and Osterman (2014a)[8] že reformulační přístup nabízí nový a jednoduchý způsob, jak analyzovat lokální chyby, a tak odvodit podmínky přísného řádu pro exponenciální Rosenbrockovy metody až do řádu 5. S pomocí této nové techniky spolu s rozšířením konceptu řady B, teorie pro odvození podmínek přísného řádu pro exponenciální Rosenbrockovy integrátory libovolného řádu byla konečně uvedena v Luan a Osterman (2013).[9] Jako příklad lze uvést, že v této práci byly odvozeny podmínky přísného řádu pro exponenciální metody Rosenbrock až do řádu 6, které jsou uvedeny v následující tabulce:
Tady označit libovolné čtvercové matice.
Konvergenční analýza
Výsledky stability a konvergence pro exponenciální Rosenbrockovy metody jsou prokázány v rámci silně spojitých poloskupin v nějakém Banachově prostoru.
Příklady
Všechna níže uvedená schémata splňují podmínky přísného řádu, a proto jsou také vhodná pro řešení náročných problémů.
Metoda druhého řádu
Nejjednodušší exponenciální Rosenbrockovou metodou je exponenciální Rosenbrock – Eulerovo schéma, které má řád 2, viz například Hochbruck et al (2009):
Metody třetího řádu
Třída exponenciálních Rosenbrockových metod třetího řádu byla odvozena v Hochbruck et al. (2009), pojmenovaný jako exprb32, je uveden jako:
exprb32:
1 0
který zní jako
kde
Pro implementaci tohoto schématu s variabilní velikostí kroku je možné jej vložit do exponenciální Rosenbrock – Euler:
Metoda čtvrtého řádu ETDRK4 od Coxe a Matthewse
Cox a Matthews[10] popsat metodu exponenciálního časového rozdílu (ETD) metody čtvrtého řádu, kterou použili Javor odvodit.
Používáme jejich zápis a předpokládáme, že neznámá funkce je , a že máme známé řešení v čase Dále explicitně využijeme časově závislou pravou stranu: .
Nejprve jsou vytvořeny tři stupně:
Konečná aktualizace je dána,
Pokud je implementován naivně, výše uvedený algoritmus trpí numerickou nestabilitou kvůli plovoucí bod chyby zaokrouhlování.[11] Chcete-li zjistit proč, zvažte první funkci,
který je přítomen v Eulerově metodě prvního řádu, stejně jako ve všech třech fázích ETDRK4. Pro malé hodnoty , tato funkce trpí chybami numerického zrušení. Těmto číselným problémům se však lze vyhnout hodnocením funkce prostřednictvím konturového integrálního přístupu [11] nebo a Padé přibližný.[12]
Aplikace
Exponenciální integrátoři se používají pro simulaci náročných scénářů v vědecký a vizuální výpočetní technika, například v molekulární dynamika,[13] pro VLSI simulace obvodu,[14][15] a v počítačová grafika.[16] Používají se také v kontextu hybridní monte carlo metody.[17] V těchto aplikacích ukazují exponenciální integrátoři výhodu velké schopnosti krokování času a vysoké přesnosti. K urychlení vyhodnocení funkcí matice v takových složitých scénářích se exponenciální integrátoři často kombinují s metodami projekce Krylovského podprostoru.
Viz také
Poznámky
- ^ Jistý (1960)
- ^ Papež (1963)
- ^ A b C Hochbruck & Ostermann (2010)
- ^ Hochbruck & Ostermann (2006)
- ^ Cox & Matthews (2002)
- ^ Tokman (2006)
- ^ Tokman (2011)
- ^ Luan & Osterman (2014a)
- ^ Luan & Osterman (2013)
- ^ Cox & Matthews (2002)
- ^ A b Kassam & Trefethen (2005)
- ^ Berland (2007)
- ^ Michels & Desbrun (2015)
- ^ Zhuang (2014)
- ^ Weng (2012)
- ^ Michels (2014)
- ^ Chao (2015)
Reference
- Berland, Havard; Owren, Brynjulf; Skaflestad, Bard (2005). "Série B a podmínky objednávky pro exponenciální integrátory". Časopis SIAM o numerické analýze. 43 (4): 1715–1727. CiteSeerX 10.1.1.216.5645. doi:10.1137/040612683.
- Berland, Havard; Skaflestad, Bard; Wright, Will M. (2007). „Balíček EXPINT-A MATLAB pro exponenciální integrátory“. Transakce ACM na matematickém softwaru. 33 (1): 4 – es. doi:10.1145/1206040.1206044.
- Chao, Wei-Lun; Solomon, Justin; Michels, Dominik L .; Sha, Fei (2015). "Exponenciální integrace pro Hamiltonian Monte Carlo". Sborník z 32. mezinárodní konference o strojovém učení (ICML-15): 1142–1151.
- Jistý, John (1960). Řešení obyčejných diferenciálních rovnic s velkými časovými konstantami. Wiley. str. 128–132.
- Cox, S. M .; Matthews, P.C. (Březen 2002). Msgstr "Exponenciální časové rozdíly pro tuhé systémy". Journal of Computational Physics. 176 (2): 430–455. Bibcode:2002JCoPh.176..430C. doi:10.1006 / jcph.2002.6995.
- Hochbruck, Marlis; Ostermann, Alexander (květen 2010). "Exponenciální integrátoři". Acta Numerica. 19: 209–286. Bibcode:2010AcNum..19..209H. CiteSeerX 10.1.1.187.6794. doi:10.1017 / S0962492910000048.
- Hochbruck, Marlis; Ostermann, Alexander (2005). „Explicitní exponenciální metody Runge-Kutta pro semilineární parabolické problémy“. Časopis SIAM o numerické analýze. 43 (3): 1069–1090. CiteSeerX 10.1.1.561.5501. doi:10.1137/040611434.
- Hochbruck, Marlis; Ostermann, Alexander (květen 2005). „Exponenciální metody Runge – Kutta pro parabolické problémy“. Aplikovaná numerická matematika. 53 (2–4): 323–339. doi:10.1016 / j.apnum.2004.08.005.
- Luan, Vu Thai; Ostermann, Alexander (2014a). „Exponenciální Rosenbrockovy metody konstrukce pátého řádu, analýza a numerická srovnání“. Journal of Computational and Applied Mathematics. 255: 417–431. doi:10.1016 / j.cam.2013.04.041.
- Luan, Vu Thai; Ostermann, Alexander (2014c). "Explicitní exponenciální Runge-Kuttovy metody vysokého řádu pro parabolické problémy". Journal of Computational and Applied Mathematics. 256: 168–179. arXiv:1307.0661. doi:10.1016 / j.cam.2013.07.027.
- Luan, Vu Thai; Ostermann, Alexander (2013). "Exponenciální řada B: tuhý případ". Časopis SIAM o numerické analýze. 51 (6): 3431–3445. doi:10.1137/130920204.
- Luan, Vu Thai; Ostermann, Alexander (2014b). Přísné podmínky pořadí pro exponenciální metody Runge-Kutta řádu pět. Modelování, simulace a optimalizace složitých procesů - HPSC 2012 (H.G. Bock et al. Eds.). 133–143. doi:10.1007/978-3-319-09063-4_11. ISBN 978-3-319-09062-7.
- Luan, Vu Thai; Ostermann, Alexander (2016). „Paralelní exponenciální Rosenbrockovy metody“. Počítače a matematika s aplikacemi. 71 (5): 1137–1150. doi:10.1016 / j.camwa.2016.01.020.
- Michels, Dominik L .; Desbrun, Mathieu (2015). „Semi-analytický přístup k molekulární dynamice“. Journal of Computational Physics. 303: 336–354. Bibcode:2015JCoPh.303..336M. doi:10.1016 / j.jcp.2015.10.009.
- Michels, Dominik L .; Sobottka, Gerrit A .; Weber, Andreas G. (2014). "Exponenciální integrátoři pro tuhé elastodynamické problémy". Transakce ACM v grafice. 33: 7:1–7:20. doi:10.1145/2508462.
- Papež, David A (1963). "Exponenciální metoda numerické integrace obyčejných diferenciálních rovnic". Komunikace ACM. 6 (8): 491–493. doi:10.1145/366707.367592.
- Tokman, Mayya (říjen 2011). "Nová třída iterativních metod exponenciálního šíření typu Runge – Kutta (EPIRK)". Journal of Computational Physics. 230 (24): 8762–8778. Bibcode:2011JCoPh.230.8762T. doi:10.1016 / j.jcp.2011.08.023.
- Tokman, Mayya (duben 2006). "Efektivní integrace velkých tuhých systémů ODR s metodami iterativní exponenciální propagace (EPI)". Journal of Computational Physics. 213 (2): 748–776. Bibcode:2006JCoPh.213..748T. doi:10.1016 / j.jcp.2005.08.032.
- Trefethen, Lloyd N .; Aly-Khan Kassam (2005). "Časový krok čtvrtého řádu pro tuhé PDE". SIAM Journal on Scientific Computing. 26 (4): 1214–1233. CiteSeerX 10.1.1.15.6467. doi:10.1137 / S1064827502410633.
- Zhuang, Hao; Weng, Shih-Hung; Lin, Jeng-Hau; Cheng, Chung-Kuan (2014). "MATEX" (PDF). Sborník z 51. výroční konference Design Automation Conference on Design Automation Conference - DAC '14. s. 1–6. arXiv:1511.04519. doi:10.1145/2593069.2593160. ISBN 9781450327305.
- Weng, Shih-Hung; Chen, Quan; Cheng, Chung-Kuan (2012). „Analýza časových domén obvodů velkého rozsahu pomocí maticové exponenciální metody s adaptivním řízením“. Transakce IEEE na počítačově podporovaném návrhu integrovaných obvodů a systémů. 32 (8): 1180–1193. doi:10.1109 / TCAD.2012.2189396.