Exponentiell integrator

Ej att förväxla med exponentiell integral av exponentialfunktioner .

Exponentialintegratorer är en klass av numeriska metoder för lösning av vanliga differentialekvationer, särskilt initialvärdesproblem . Denna stora klass av metoder från numerisk analys är baserad på den exakta integrationen av den linjära delen av initialvärdesproblemet. Eftersom den linjära delen är integrerad exakt kan detta bidra till att mildra styvheten i en differentialekvation. Exponentiella integratorer kan konstrueras för att vara explicita eller implicita för numeriska vanliga differentialekvationer eller fungera som tidsintegrator för numeriska partiella differentialekvationer .

Bakgrund

Dessa metoder går tillbaka till åtminstone 1960-talet och erkändes av Certaine och Pope. Sedan sent har exponentiella integratörer blivit ett aktivt forskningsområde, se Hochbruck och Ostermann (2010). Ursprungligen utvecklade för att lösa stela differentialekvationer , har metoderna använts för att lösa partiella differentialekvationer inklusive hyperboliska såväl som paraboliska problem som värmeekvationen .

Introduktion

Vi överväger initiala värdeproblem av formen,

$u'(t)=Lu(t)+N(u(t) ),\qquad u(t_{0})=u_{0},\qquad \qquad (1)$

där $L$ är sammansatt av linjära termer och $N$ är sammansatt av de icke-linjära termerna. Dessa problem kan komma från ett mer typiskt initialt värdeproblem

$u'(t)=f(u(t)),\qquad u(t_{0})=u_{ 0},$

efter att ha linjärt lokalt om ett fast eller lokalt tillstånd $u^{*}$ :

$L={\frac {\partial f}{\partial u}}(u^{*});\qquad N=f(u)-Lu.$

Här hänvisar ${\frac {\partial f}{\partial u}}$ till den partiella derivatan av $f$ med avseende på $u$ (jakobian av f ).

Exakt integration av detta problem från tid 0 till en senare tidpunkt $t$ kan utföras med hjälp av matrisexponentialer för att definiera en integralekvation för den exakta lösningen:

$u(t)=e^{Lt}u_{0}+\int _{0}^{t}e^{L(t-\tau )}N\left(u\left( \tau \right)\right)\,d\tau .\qquad (2)$

Detta liknar den exakta integralen som används i Picard–Lindelöfs sats . I fallet med $N\equiv 0$ , är denna formulering den exakta lösningen på den linjära differentialekvationen .

Numeriska metoder kräver en diskretisering av ekvation (2). De kan baseras på Runge-Kutta- diskretiseringar, linjära flerstegsmetoder eller en mängd andra alternativ.

Exponentiella Rosenbrock-metoder

Exponentiella Rosenbrock-metoder visade sig vara mycket effektiva för att lösa stora system av styva vanliga differentialekvationer, vanligtvis ett resultat av rumslig diskretisering av tidsberoende (paraboliska) PDE. Dessa integratorer är konstruerade baserat på en kontinuerlig linjärisering av (1) längs den numeriska lösningen $u_{n}$

$u'(t)=L_{n}u(t)+ N_{n}(u(t)),\qquad u(t_{0})=u_{0},\qquad (3)$

där $L_{n}={\frac {\partial f}{\partial u}}(u_{n}),N_{n}(u)=f(u)-L_{n}u.$ Detta proceduren har fördelen, i varje steg, att ${\frac {\partial N_{n}}{\partial u}}(u_{n})=0 .$ Detta förenklar avsevärt härledningen av ordningsvillkoren och förbättrar stabiliteten vid integration av olinjäriteten $N(u(t))$ . Återigen, genom att tillämpa formeln för variation av konstanter (2) får man den exakta lösningen vid tidpunkten $t_{n+1}$ som

$u(t_{n+1})=e^{h_{n}L_{n}}u(t_{n})+\int _{0}^{h_{n}}e ^{(h_{n}-\tau )L_{n}}N_{n}(u(t_{n}+\tau ))d\tau .\qquad (4)$

Tanken är nu att approximera integralen i (4) med någon kvadraturregel med noder $c_{i}$ och vikter $b_{i}(h_{n} L_{n})$ ( $1\leq i\leq s$ ). Detta ger följande klass av $s-stage$ explicita exponentiella Rosenbrock-metoder, se Hochbruck och Ostermann (2006), Hochbruck, Ostermann och Schweitzer (2009):

$U_{ni}=e^ {c_{i}h_{n}L_{n}}u_{n}+h_{n}\sum _{j=1}^{i-1}a_{ij}(h_{n}L_{n} )N_{n}(U_{nj}),$

${\ displaystyle u_{n+1}=e^{h_{n}L_{n}}u_{n}+h_{n}\sum _{i=1}^{s}b_{i}(h_{n} L_{n})N_{n}(U_{ni})}$

med $u_{n}\approx u(t_{n} ),U_{ni}\approx u(t_{n}+c_{i}h_{n}),h_{n}=t_{n+1}-t_{n}$ . Koefficienterna $a_{ij}(z),b_{i}(z)$ väljs vanligtvis som linjära kombinationer av hela funktionerna ${\displaystyle \varphi _{k}(c_{i}z),\varphi _{k}(z)} ,$ där

$\varphi _{0}(z)=e^{z},\quad \varphi _{k}(z)=\int _{0}^{1}e^ {(1-\theta )z}{\frac {\theta ^{k-1}}{(k-1)!}}d\theta ,\quad k\geq 1.$

Dessa funktioner uppfyller rekursionsrelationen

$\varphi _{k+1}(z)={\frac {\varphi _{k}( z)-\varphi _{k}(0)}{z}},\ k\geq 0.$

Genom att introducera skillnaden $D_{ni}=N_{n}(U_{ni})-N_{n}(u_{n} )$ , kan de omformuleras på ett mer effektivt sätt för implementering (se även ) som

${ \displaystyle U_{ni}=u_{n}+c_{i}h_{n}\varphi _{1}(c_{i}h_{n}L_{n})f(u_{n})+h_{ n}\summa _{j=2}^{i-1}a_{ij}(h_{n}L_{n})D_{nj},}$

$u_{n+1}=u_{n}+h_{n}\varphi _{1}(h_{n}L_{n})f(u_{n})+h_{n}\sum _ {i=2}^{s}b_{i}(h_{n}L_{n})D_{ni}.$

För att implementera detta schema med adaptiv stegstorlek kan man överväga, för lokal feluppskattning, följande inbäddade metoder

${\ bar {u}}_{n+1}=u_{n}+h_{n}\varphi _{1}(h_{n}L_{n})f(u_{n})+h_{n}\ summa _{i=2}^{s}{\bar {b}}_{i}(h_{n}L_{n})D_{ni},$

som använder samma steg $U_{ni}$ men med vikter ${\bar {b}}_{i}$ .

För enkelhetens skull kan koefficienterna för de explicita exponentiella Rosenbrock-metoderna tillsammans med deras inbäddade metoder representeras genom att använda den så kallade reducerade Butcher-tabellen enligt följande:

$c_{2}$
$c_{3}$	$a_{32}$
$\vdots$	$\vdots$		$\ddots$
$c_{s}$	$a_{s2}$	$a_{s3}$	$\cdots$	$a_{s,s-1}$
	$b_{2}$	$b_{3}$	$\cdots$	$b_{s-1}$	$b_{s}$
	${\bar {b}}_{2}$	${\bar {b}}_{3}$	$\cdots$	${\bar {b}}_{s-1}$	${\bar {b}}_{s}$

Styva ordervillkor

Dessutom visas det i Luan och Ostermann (2014a) att omformuleringsmetoden erbjuder ett nytt och enkelt sätt att analysera de lokala felen och därmed härleda villkoren för styv ordning för exponentiella Rosenbrock-metoder upp till ordning 5. Med hjälp av denna nya teknik tillsammans med en förlängning av B-seriekonceptet, en teori för att härleda villkoren för styv ordning för exponentiella Rosenbrock-integratörer av godtycklig ordning har slutligen getts i Luan och Ostermann (2013). Som ett exempel, i det arbetet har villkoren för styv ordning för exponentiella Rosenbrock-metoder upp till ordning 6 härletts, vilka anges i följande tabell:

${\begin{array}{|c|c|c| }\hline Nr.&{\text{Styv ordning}}&{\text{Order}}\\\hline 1&\sum _{i=2}^{s}b_{i}(Z)c_{i }^{2}=2\varphi _{3}(Z)&3\\\hline 2&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{3}= 6\varphi _{4}(Z)&4\\\hline 3&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{4}=24\varphi _{5 }(Z)&5\\4&\summa _{i=2}^{s}b_{i}(Z)c_{i}K\psi _{3,i}(Z)=0&5\\\hline 5& \sum _{i=2}^{s}b_{i}(Z)c_{i}^{5}=120\varphi _{6}(Z)&6\\6&\sum _{i=2} ^{s}b_{i}(Z)c_{i}^{2}M\psi _{3,i}(Z)=0&6\\7&\sum _{i=2}^{s}b_{ i}(Z)c_{i}K\psi _{4,i}(Z)=0&6\\\hline \end{array}}$

Här $Z,K,M.\$ betecknar godtyckliga kvadratiska matriser.

Konvergensanalys

Stabilitets- och konvergensresultaten för exponentiella Rosenbrock-metoder bevisas inom ramen för starkt kontinuerliga semigrupper i vissa Banach-rymden.

Exempel

Alla scheman som presenteras nedan uppfyller villkoren för hård ordning och är därför också lämpliga för att lösa svåra problem.

Andra ordningens metod

Den enklaste exponentiella Rosenbrock-metoden är det exponentiella Rosenbrock–Euler-schemat, som har ordning 2, se till exempel Hochbruck et al. (2009):

$u_{n+1}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n}).$

Tredje ordningens metoder

En klass av tredje ordningens exponentiella Rosenbrock-metoder härleddes i Hochbruck et al. (2009), namngiven som exprb32, ges som:

exprb32:

1
	$2\varphi _{3}$
	0

som lyder som

$U_{n2}=u_{n}+h_{n}\ \varphi _{1}(h_{ n}L_{n})f(u_{n}),$

$u_{n+1}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n})+h_ {n}\ 2\varphi _{3}(h_{n}L_{n})D_{n2},$

där $D_{n2}=N_{n}(U_{n2})-N_{n}(u_{n}).$

För en variabel stegstorleksimplementering av detta schema kan man bädda in det med den exponentiella Rosenbrock–Euler:

${\hat {u}}_{n+1}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n}) .$

Fjärde ordningens ETDRK4-metod av Cox och Matthews

Cox och Matthews beskriver en fjärde ordningens metod för exponentiell tidsskillnad (ETD) som de använde Maple för att härleda.

Vi använder deras notation och antar att den okända funktionen är $u$ , och att vi har en känd lösning $u_{n}$ vid tiden $t_{n}$ . Dessutom kommer vi att explicit använda en möjligen tidsberoende höger sida: ${\mathcal {N}}={\mathcal {N}}(u,t)$ .

Tre stegvärden konstrueras först:

$a_{n}=e^{Lh/2}u_{n} +L^{-1}\left(e^{Lh/2}-I\right){\mathcal {N}}(u_{n},t_{n})$

$b_{n}=e^{Lh/2}u_{n}+L^{- 1}\left(e^{Lh/2}-I\right){\mathcal {N}}(a_{n},t_{n}+h/2)$

$c_{n}=e^{Lh/ 2}a_{n}+L^{-1}\left(e^{Lh/2}-I\right)\left(2{\mathcal {N}}(b_{n},t_{n}+ h/2)-{\mathcal {N}}(u_{n},t_{n})\right)$

Den sista uppdateringen ges av,

$u_{n+1}=e^{Lh}u_{n}+h^{-2}L^{-3}\left\{\left[-4-Lh+e^{Lh}\ left(4-3Lh+(Lh)^{2}\right)\right]{\mathcal {N}}(u_{n},t_{n})+2\left[2+Lh+e^{Lh} \left(-2+Lh\right)\right]\left({\mathcal {N}}(a_{n},t_{n}+h/2)+{\mathcal {N}}(b_{n },t_{n}+h/2)\höger)+\vänster[-4-3Lh-(Lh)^{2}+e^{Lh}\left(4-Lh\höger)\höger]{\ mathcal {N}}(c_{n},t_{n}+h)\right\}.$

Om den implementeras naivt, lider ovanstående algoritm av numeriska instabiliteter på grund av flyttalsavrundningsfel . För att se varför, överväg den första funktionen,

$\varphi _{1}(z)={\frac {e^{z}-1}{z}},$

som finns i första ordningens Euler-metoden, såväl som alla tre stegen av ETDRK4. För små värden på $z$ lider denna funktion av numeriska annulleringsfel. Dessa numeriska problem kan dock undvikas genom att utvärdera $\varphi _{1}$ -funktionen via en konturintegral tillvägagångssätt eller med en Padé approximant .

Ansökningar

Exponentiella integratorer används för simulering av stela scenarier inom vetenskaplig och visuell beräkning, till exempel inom molekylär dynamik , för VLSI- kretssimulering och i datorgrafik . De används också i samband med hybridmonte carlo- metoder. I dessa applikationer visar exponentiella integratörer fördelen med stor tidsstegningskapacitet och hög noggrannhet. För att påskynda utvärderingen av matrisfunktioner i sådana komplexa scenarier kombineras ofta exponentiella integratörer med Krylov subrymdprojektionsmetoder.

Se även

• Allmänna linjära metoder

Anteckningar

•   Berland, Håvard; Owren, Brynjulf; Skaflestad, Bard (2005). "B-serier och beställningsvillkor för exponentiella integratörer". SIAM Journal on Numerical Analysis . 43 (4): 1715–1727. CiteSeerX 10.1.1.216.5645 . doi : 10.1137/040612683 .
•   Berland, Håvard; Skaflestad, Bard; Wright, Will M. (2007). "EXPINT-A MATLAB-paket för exponentiella integratörer" . ACM-transaktioner på matematisk programvara . 33 (1): 4–es. doi : 10.1145/1206040.1206044 . S2CID 1525599 .
• Chao, Wei-Lun; Solomon, Justin; Michels, Dominik L.; Sha, Fei (2015). "Exponentiell integration för Hamiltonian Monte Carlo". Proceedings of the 32nd International Conference on Machine Learning (ICML-15) : 1142–1151.
• Certaine, John (1960). "Lösningen av vanliga differentialekvationer med stora tidskonstanter". Matematiska metoder för digitala datorer . Wiley. s. 128–132.
• Cox, SM; Matthews, PC (mars 2002). "Exponentiell tidsskillnad för styva system". Journal of Computational Physics . 176 (2): 430–455. Bibcode : 2002JCoPh.176..430C . doi : 10.1006/jcph.2002.6995 .
•    Hochbruck, Marlis ; Ostermann, Alexander (maj 2010). "Exponentiella integratörer". Acta Numerica . 19 : 209–286. Bibcode : 2010AcNum..19..209H . CiteSeerX 10.1.1.187.6794 . doi : 10.1017/S0962492910000048 . S2CID 4841957 .
•   Hochbruck, Marlis ; Ostermann, Alexander (2005). "Explicita exponentiella Runge-Kutta-metoder för semilinjära paraboliska problem" . SIAM Journal on Numerical Analysis . 43 (3): 1069–1090. CiteSeerX 10.1.1.561.5501 . doi : 10.1137/040611434 .
• Hochbruck, Marlis ; Ostermann, Alexander (maj 2005). "Exponentiella Runge–Kutta-metoder för paraboliska problem" . Tillämpad numerisk matematik . 53 (2–4): 323–339. doi : 10.1016/j.apnum.2004.08.005 .
• Luan, Vu Thai; Ostermann, Alexander (2014a). "Exponentiella Rosenbrock-metoder för ordningsfem-konstruktion, analys och numeriska jämförelser" . Journal of Computational and Applied Mathematics . 255 : 417–431. doi : 10.1016/j.cam.2013.04.041 .
•   Luan, Vu Thai; Ostermann, Alexander (2014c). "Explicit exponentiella Runge-Kutta-metoder av hög ordning för paraboliska problem". Journal of Computational and Applied Mathematics . 256 : 168–179. arXiv : 1307.0661 . doi : 10.1016/j.cam.2013.07.027 . S2CID 18448807 .
• Luan, Vu Thai; Ostermann, Alexander (2013). "Exponentiell B-serie: Det styva fallet". SIAM Journal on Numerical Analysis . 51 (6): 3431–3445. doi : 10.1137/130920204 .
•   Luan, Vu Thai; Ostermann, Alexander (2014b). Styv ordningsvillkor för exponentiella Runge-Kutta-metoder av ordning fem . Modellering, simulering och optimering av komplexa processer - HPSC 2012 (HG Bock et al. red.) . s. 133–143. doi : 10.1007/978-3-319-09063-4_11 . ISBN 978-3-319-09062-7 .
• Luan, Vu Thai; Ostermann, Alexander (2016). "Parallella exponentiella Rosenbrock-metoder" . Datorer och matematik med applikationer . 71 (5): 1137–1150. doi : 10.1016/j.camwa.2016.01.020 .
• Michels, Dominik L.; Desbrun, Mathieu (2015). "En semi-analytisk metod för molekylär dynamik" . 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). "Exponentiella integratörer för styva elastodynamiska problem". ACM-transaktioner på grafik . 33 : 7:1–7:20. doi : 10.1145/2508462 . S2CID 207207156 .
•   Pope, David A (1963). "En exponentiell metod för numerisk integration av vanliga differentialekvationer" . Kommunikation från ACM . 6 (8): 491–493. doi : 10.1145/366707.367592 . S2CID 18598461 .
• Tokman, Mayya (oktober 2011). "En ny klass av iterativa metoder för exponentiell utbredning av Runge–Kutta-typ (EPIRK)". Journal of Computational Physics . 230 (24): 8762–8778. Bibcode : 2011JCoPh.230.8762T . doi : 10.1016/j.jcp.2011.08.023 .
• Tokman, Mayya (april 2006). "Effektiv integration av stora styva system av ODE med exponentiell utbredning iterativ (EPI) metoder". 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). "Fjärde ordningens tidsstegring för stela PDE:er". SIAM Journal on Scientific Computing . 26 (4): 1214–1233. Bibcode : 2005SJSC...26.1214K . CiteSeerX 10.1.1.15.6467 . doi : 10.1137/S1064827502410633 .
•    Zhuang, Hao; Weng, Shih-Hung; Lin, Jeng-Hau; Cheng, Chung-Kuan (2014). "MATEX" (PDF) . Proceedings of the 51th Annual Design Automation Conference on Design Automation Conference - DAC '14 . s. 1–6. arXiv : 1511.04519 . doi : 10.1145/2593069.2593160 . ISBN 9781450327305 . S2CID 10585362 .
•   Weng, Shih-Hung; Chen, Quan; Cheng, Chung-Kuan (2012). "Tidsdomänanalys av storskaliga kretsar med matrisexponentiell metod med adaptiv kontroll" . IEEE-transaktioner på datorstödd design av integrerade kretsar och system . 32 (8): 1180–1193. doi : 10.1109/TCAD.2012.2189396 . S2CID 14977067 .

externa länkar

• integratörer på GPGPU:er
• kod för en nätfri exponentiell integrator