Wykładniczy integrator

Nie mylić z całką wykładniczą funkcji wykładniczych .

Integratory wykładnicze to klasa metod numerycznych służących do rozwiązywania równań różniczkowych zwyczajnych , w szczególności problemów z wartościami początkowymi . Ta duża klasa metod analizy numerycznej opiera się na dokładnym całkowaniu części liniowej problemu wartości początkowej. Ponieważ część liniowa jest całkowana , może to pomóc złagodzić sztywność równania różniczkowego. Integratory wykładnicze można skonstruować tak, aby były jawne lub niejawne dla numerycznych równań różniczkowych zwyczajnych lub służyły jako integrator czasu dla numerycznych równań różniczkowych cząstkowych .

Tło

Metody te, sięgające co najmniej lat 60. XX wieku, zostały uznane przez Certaine i Pope'a. Od późnych czasów integratory wykładnicze stały się aktywnym obszarem badań, zob. Hochbruck i Ostermann (2010). Metody te , pierwotnie opracowane do rozwiązywania sztywnych równań różniczkowych , były wykorzystywane do rozwiązywania równań różniczkowych cząstkowych, w tym problemów hiperbolicznych i parabolicznych , takich jak równanie ciepła .

Wstęp

Rozważamy problemy z wartością początkową postaci,

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

gdzie $składa$$.$ z terminów liniowych a składa się z terminów nieliniowych Te problemy mogą wynikać z bardziej typowego problemu z wartością początkową

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

po lokalnej linearyzacji względem ustalonego lub lokalnego stanu ${\ displaystyle u ^ {*}}$ :

${\ Displaystyle L = {\ Frac {\ częściowe f} {\ częściowe u}} (u ^ {*}); \ qquad N = f (u) -Lu.}$

Tutaj $} {\ częściowe u}}}$$displaystyle f$ odnosi się do pochodnej cząstkowej względem ( jakobianu f ) $}$ ).

Dokładną integrację tego problemu od czasu 0 do czasu późniejszego można przeprowadzić za pomocą wykładniczych macierzy w celu zdefiniowania równania całkowego dla dokładnego rozwiązania: ${\ displaystyle t}$

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

Jest to podobne do całki dokładnej użytej w twierdzeniu Picarda-Lindelöfa . W przypadku $różniczkowego$ sformułowanie jest dokładnym rozwiązaniem równania .

Metody numeryczne wymagają dyskretyzacji równania (2). Mogą one opierać się na Runge-Kutty , liniowych metodach wieloetapowych lub wielu innych opcjach.

Wykładnicze metody Rosenbrocka

Wykładnicze metody Rosenbrocka okazały się bardzo skuteczne w rozwiązywaniu dużych układów sztywnych równań różniczkowych zwyczajnych, zwykle wynikających z przestrzennej dyskretyzacji zależnych od czasu (parabolicznych) PDE. Te integratory są konstruowane w oparciu o ciągłą linearyzację (1) wzdłuż rozwiązania numerycznego ${\ displaystyle u_ {n}}$

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

gdzie ${\ Displaystyle L_ {n} = {\ Frac {\ częściowe f} {\ częściowe u}} (u_ {n}), N_ {n} (u) = f (u) -L_ {n} u.}$ To ∂ ${\ Displaystyle {\ Frac {\ częściowe N_ {n}} {\ częściowe u}} (u_ {n}) =$ This considerably simplifies the derivation of the order conditions and improves the stability when integrating the nonlinearity $N(u(t))$. Again, applying the variation-of-constants formula (2) gives the exact solution at time $t_{n+1}$ as

${\ Displaystyle 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)}$

Pomysł polega teraz na przybliżeniu całki w (4) za pomocą pewnej reguły kwadraturowej z węzłami $n} L_ {n})}$$($ { ( ${\ Displaystyle 1 \ równoważnik ja \ równoważnik s}$ ). Daje to następującą klasę $2009$ , patrz Hochbruck i Ostermann (2006), Hochbruck, Ostermann i Schweitzer

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

${\ styl wyświetlania u_{n+1}=e^{h_{n}L_{n}}u_{n}+h_{n}\suma _{i=1}^{s}b_{i}(h_{n} L_{n})N_{n}(U_{ni})}$

z ${\ Displaystyle u_ {n} \ około u (t_ {n} ),U_{ni}\około u(t_{n}+c_{i}h_{n}),h_{n}=t_{n+1}-t_{n}}$ . Współczynniki są zwykle wybierane jako kombinacje liniowe całych funkcji ${\ Displaystyle \ varphi _ {k} (c_ {i} z), \ varphi _ {k} (z)}$${\ Displaystyle a_ {ij} (z), b_ {i}$ , gdzie

${\ Displaystyle \ 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.}$

Funkcje te spełniają relację rekurencji

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

Wprowadzając różnicę ${\ Displaystyle D_ {ni} = N_ {n} (U_ {ni}) -N_ {n} (u_ {n} )}$ , można je przeformułować w bardziej efektywny sposób w celu wdrożenia (zobacz także ) jako

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

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

Aby zaimplementować ten schemat z adaptacyjnym rozmiarem kroku, można rozważyć, w celu oszacowania błędu lokalnego, następujące metody wbudowane

${\ Displaystyle {\ słupek {u}}_{n+1}=u_{n}+h_{n}\varphi_{1}(h_{n}L_{n})f(u_{n})+h_{n}\ suma _{i=2}^{s}{\bar {b}}_{i}(h_{n}L_{n})D_{ni},}$

$ale$ same etapy z wagami $i}}$ .

Dla wygody współczynniki jawnych wykładniczych metod Rosenbrocka wraz z ich osadzonymi metodami można przedstawić za pomocą tak zwanego zredukowanego obrazu Butchera w następujący sposób:

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

Sztywne warunki zamówienia

Co więcej, w Luan i Ostermann (2014a) wykazano, że podejście przeformułowania oferuje nowy i prosty sposób analizy błędów lokalnych, a tym samym wyprowadzenia warunków sztywnego rzędu dla wykładniczych metod Rosenbrocka do rzędu 5. Z pomocą tego nowego wraz z rozszerzeniem koncepcji serii B, teoria wyprowadzania warunków sztywnego porządku dla wykładniczych integratorów Rosenbrocka dowolnego rzędu została ostatecznie podana w Luan i Ostermann (2013). Na przykład w tej pracy wyprowadzono warunki sztywnego porządku dla wykładniczych metod Rosenbrocka do rzędu 6, które przedstawiono w poniższej tabeli:

${\ Displaystyle {\ rozpocząć {tablica} {| c | c | c | }\hline nr&{\text{Warunek sztywnego porządku}}&{\text{kolejność}}\\\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&\suma _{i=2}^{s}b_{i}(Z)c_{i}K\psi _{3,i}(Z)=0&5\\\hlinia 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&\suma _{i=2}^{s}b_{ i}(Z)c_{i}K\psi _{4,i}(Z)=0&6\\\hlinia \end{tablica}}}$

Tutaj ${\ displaystyle Z, K, M. \}$ oznaczają dowolne macierze kwadratowe.

Analiza konwergencji

Wyniki stabilności i zbieżności dla wykładniczych metod Rosenbrocka są udowodnione w ramach silnie ciągłych półgrup w pewnej przestrzeni Banacha.

Przykłady

Wszystkie przedstawione poniżej schematy spełniają sztywne warunki porządku, a zatem nadają się również do rozwiązywania sztywnych problemów.

Metoda drugiego rzędu

Najprostszą wykładniczą metodą Rosenbrocka jest wykładniczy schemat Rosenbrocka – Eulera, który ma rząd 2, patrz np. Hochbruck i in. (2009):

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

Metody trzeciego rzędu

Klasa wykładniczych metod Rosenbrocka trzeciego rzędu została wyprowadzona w Hochbruck i in. (2009), nazwany jako exrb32, jest podany jako:

wyrażenie32:

1
	${\ Displaystyle 2 \ varphi _ {3}}$
	0

co brzmi jak

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

${\ Displaystyle 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},}$

gdzie ${\ Displaystyle D_ {n2} = N_ {n} (U_ {n2}) -N_ {n} (u_ {n}).}$

W przypadku implementacji tego schematu o zmiennej wielkości kroku można go osadzić za pomocą wykładniczego Rosenbrocka – Eulera:

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

Metoda ETDRK4 czwartego rzędu Coxa i Matthewsa

Cox i Matthews opisują metodę wykładniczego różnicowania czasu (ETD) czwartego rzędu, którą wykorzystali do wyprowadzenia Maple .

Używamy ich notacji i zakładamy, że nieznaną funkcją jest $}$$n$ \ displaystyle $n}$ . Ponadto wyraźnie wykorzystamy prawą stronę, która może być zależna od czasu: ${\ Displaystyle {\ mathcal {N}} = {\ mathcal {N}} (u, t)}$ .

Najpierw konstruowane są trzy wartości etapowe:

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

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

${\ Displaystyle 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)}$

Ostateczną aktualizację podaje m.in.

${\ Displaystyle u_ {n + 1} = e ^ {Lh} u_ {n} + h ^ {-2} L ^ {-3} \ lewo \ {\ lewo [-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)\right)+\left[-4-3Lh-(Lh)^{2}+e^{Lh}\left(4-Lh\right)\right]{\ mathcal {N}}(c_{n},t_{n}+h)\right\}.}$

W przypadku implementacji naiwnej powyższy algorytm cierpi na niestabilności numeryczne z powodu błędów zaokrągleń zmiennoprzecinkowych . Aby zobaczyć, dlaczego, rozważ pierwszą funkcję,

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

który jest obecny w metodzie Eulera pierwszego rzędu, jak również we wszystkich trzech etapach ETDRK4. $W przypadku$ wartości ta funkcja ma numeryczne błędy anulowania. Jednak tych problemów liczbowych można uniknąć, oceniając funkcję za pomocą podejścia całkowego konturu $lub$ Padé

Aplikacje

Integratory wykładnicze są używane do symulacji sztywnych scenariuszy w obliczeniach naukowych i wizualnych , na przykład w dynamice molekularnej , w symulacji obwodów VLSI oraz w grafice komputerowej . Są one również stosowane w kontekście hybrydowych metod Monte Carlo . W tych zastosowaniach integratory wykładnicze wykazują zaletę w postaci dużych skoków czasowych i wysokiej dokładności. Aby przyspieszyć ocenę funkcji macierzowych w tak złożonych scenariuszach, integratory wykładnicze są często łączone z metodami projekcji podprzestrzennej Kryłowa.

Zobacz też

• Ogólne metody liniowe

Notatki

•   Berland, Havard; Owren, Brynjulf; Skaflestad, Bard (2005). „Seria B i warunki zamówienia dla integratorów wykładniczych”. SIAM Journal o analizie numerycznej . 43 (4): 1715–1727. CiteSeerX 10.1.1.216.5645 . doi : 10.1137/040612683 .
•   Berland, Havard; Skaflestad, Bard; Wright, Will M. (2007). „EXPINT-A Pakiet MATLAB dla integratorów wykładniczych” . Transakcje ACM dotyczące oprogramowania matematycznego . 33 (1): 4–es. doi : 10.1145/1206040.1206044 . S2CID 1525599 .
• Chao, Wei-Lun; Salomon, Justyn; Michels, Dominik L.; Sha, Fei (2015). „Całkowanie wykładnicze dla Hamiltona Monte Carlo”. Materiały z 32. Międzynarodowej Konferencji na temat uczenia maszynowego (ICML-15) : 1142–1151.
• Pewnie, John (1960). „Rozwiązanie równań różniczkowych zwyczajnych z dużymi stałymi czasowymi”. Metody matematyczne dla komputerów cyfrowych . Wiley'a. s. 128–132.
• Cox, SM; Matthews, PC (marzec 2002). „Wykładnicze różnicowanie czasu dla sztywnych systemów”. Journal of Computational Physics . 176 (2): 430–455. Bibcode : 2002JCoPh.176..430C . doi : 10.1006/jcph.2002.6995 .
•    Hochbrück, Marlis ; Ostermann, Alexander (maj 2010). „Inteligentne integratory”. Acta Numerica . 19 : 209–286. Bibcode : 2010AcNum..19..209H . CiteSeerX 10.1.1.187.6794 . doi : 10.1017/S0962492910000048 . S2CID 4841957 .
•   Hochbrück, Marlis ; Ostermann, Aleksander (2005). „Jawne wykładnicze metody Runge-Kutty dla półliniowych problemów parabolicznych” . SIAM Journal o analizie numerycznej . 43 (3): 1069–1090. CiteSeerX 10.1.1.561.5501 . doi : 10.1137/040611434 .
• Hochbrück, Marlis ; Ostermann, Alexander (maj 2005). „Wykładnicze metody Runge-Kutty dla problemów parabolicznych” . Stosowana matematyka numeryczna . 53 (2–4): 323–339. doi : 10.1016/j.apnum.2004.08.005 .
• Luan, Vu Thai; Ostermann, Aleksander (2014a). „Wykładnicze metody Rosenbrocka konstrukcji piątego rzędu, analiza i porównania numeryczne” . Journal of Computational and Applied Mathematics . 255 : 417–431. doi : 10.1016/j.cam.2013.04.041 .
•   Luan, Vu Thai; Ostermann, Aleksander (2014c). „Jawne wykładnicze metody Runge-Kutty wysokiego rzędu dla problemów parabolicznych”. Journal of Computational and Applied Mathematics . 256 : 168–179. ar Xiv : 1307.0661 . doi : 10.1016/j.cam.2013.07.027 . S2CID 18448807 .
• Luan, Vu Thai; Ostermann, Aleksander (2013). „Wykładnicza seria B: sztywna obudowa” . SIAM Journal o analizie numerycznej . 51 (6): 3431–3445. doi : 10.1137/130920204 .
•   Luan, Vu Thai; Ostermann, Aleksander (2014b). Sztywne warunki porządku dla wykładniczych metod Runge-Kutty rzędu piątego . Modelowanie, symulacja i optymalizacja złożonych procesów - HPSC 2012 (HG Bock i in. Red.) . s. 133–143. doi : 10.1007/978-3-319-09063-4_11 . ISBN 978-3-319-09062-7 .
• Luan, Vu Thai; Ostermann, Aleksander (2016). „Równoległe wykładnicze metody Rosenbrocka” . Komputery i matematyka z aplikacjami . 71 (5): 1137–1150. doi : 10.1016/j.camwa.2016.01.020 .
• Michels, Dominik L.; Desbrun, Mathieu (2015). „Półanalityczne podejście do dynamiki molekularnej” . 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). „Wykładnicze integratory dla sztywnych problemów elastodynamicznych”. Transakcje ACM na grafice . 33 : 7:1-7:20. doi : 10.1145/2508462 . S2CID 207207156 .
•   Papież, David A (1963). „Wykładnicza metoda numerycznego całkowania równań różniczkowych zwyczajnych” . Komunikaty ACM . 6 (8): 491–493. doi : 10.1145/366707.367592 . S2CID 18598461 .
• Tokman, Mayya (październik 2011). „Nowa klasa iteracyjnych metod propagacji wykładniczej 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 (kwiecień 2006). „Wydajna integracja dużych sztywnych systemów ODE z metodami iteracyjnymi propagacji wykładniczej (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). „Przechodzenie w czasie czwartego rzędu dla sztywnych PDE” . SIAM Journal o obliczeniach naukowych . 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) . Materiały z 51. dorocznej konferencji Design Automation na konferencji Design Automation Conference - DAC '14 . s. 1–6. ar Xiv : 1511.04519 . doi : 10.1145/2593069.2593160 . ISBN 9781450327305 . S2CID 10585362 .
•   Weng, Shih-Hung; Chen, Quan; Cheng, Chung-Kuan (2012). „Analiza w dziedzinie czasu obwodów wielkoskalowych metodą wykładniczą macierzy ze sterowaniem adaptacyjnym” . Transakcje IEEE dotyczące wspomaganego komputerowo projektowania układów scalonych i systemów . 32 (8): 1180–1193. doi : 10.1109/TCAD.2012.2189396 . S2CID 14977067 .

Linki zewnętrzne

• integratorów na GPGPU
• kod wykładniczego integratora bez siatki