指数積分器

指数積分器は、常微分方程式、特に初期値問題を解く数値法の一種です。数値解析からのこの大規模な方法のクラスは、初期値問題の線形部分の正確な積分に基づいています。線形部分が正確に積分されるため、微分方程式の硬直性を緩和するのに役立ちます。指数積分器は、数値常微分方程式に対して明示的または暗黙的に構築することも、数値偏微分方程式の時間積分器として機能するように構築することもできます。

少なくとも1960年代に遡るこれらの方法は、Certaine ^[1]とPope ^[2]によって認識されていました。最近、指数積分器は活発な研究分野になっています。HochbruckとOstermann（2010）を参照してください。^{[3]もともとは}硬い微分方程式を 解くために開発されたこの方法は、熱方程式などの双曲型問題と放物型 問題^[4]を含む偏微分方程式を解くために使用されています。

次のような 初期値問題を考える。

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

ここで は線形項で構成され、 は非線形項で構成される。これらの問題は、より典型的な初期値問題から生じる可能性がある。 ${\displaystyle L}$${\displaystyle N}$

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

固定された状態または局所的な状態について局所的に線形化した後： ${\displaystyle u^{*}}$

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

ここで、は(f のヤコビアン) に関するの偏微分を指します。${\displaystyle {\frac {\partial f}{\partial u}}}$${\displaystyle f}$${\displaystyle u}$

この問題の時刻0からそれ以降の時刻までの正確な積分は、行列指数関数を使用して実行でき、正確な解の積分方程式を定義することができます。^[3]${\displaystyle t}$

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

これは、ピカール・リンデレーフの定理で使用される正確な積分に似ています。 の場合、この定式化は線型微分方程式の正確な解です。 ${\displaystyle N\equiv 0}$

数値計算法では方程式(2)の離散化が必要である。数値計算法には ルンゲ・クッタ離散化法、^{[5] [6] [7]} 線形多段階法、あるいはその他のさまざまな方法がある。

指数ローゼンブロック法は、通常、時間依存（放物型）偏微分方程式の空間離散化から生じる、硬い常微分方程式の大規模なシステムを解くのに非常に効率的であることが示されています。これらの積分器は、数値解に沿った（1）の連続線形化に基づいて構築されます。${\displaystyle u_{n}}$

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

ここで、 この手順は、各ステップにおいて、次の利点がある。 これにより、順序条件の導出が大幅に簡素化され、非線形性を積分する際の安定性が向上する。ここでも、定数の変動公式(2)を適用すると、時刻における正確な解が次のように 得られる。${\displaystyle L_{n}={\frac {\partial f}{\partial u}}(u_{n}),N_{n}(u)=f(u)-L_{n}u.}$${\displaystyle {\frac {\partial N_{n}}{\partial u}}(u_{n})=0.}$${\displaystyle N(u(t))}$${\displaystyle t_{n+1}}$

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

ここでの考え方は、(4)の積分をノードと重み( )を持つ求積法で近似することです。これにより、次のクラスの明示的な指数ローゼンブロック法が得られます。HochbruckとOstermann (2006)、Hochbruck、Ostermann、Schweitzer (2009)を参照してください。 ${\displaystyle c_{i}}$${\displaystyle b_{i}(h_{n}L_{n})}$${\displaystyle 1\leq i\leq s}$${\displaystyle s-stage}$

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

となる 。係数は通常、関数全体の線形結合として選ばれる。ここで、 ${\displaystyle u_{n}\approx u(t_{n}),U_{ni}\approx u(t_{n}+c_{i}h_{n}),h_{n}=t_{n+1}-t_{n}}$${\displaystyle a_{ij}(z),b_{i}(z)}$${\displaystyle \varphi _{k}(c_{i}z),\varphi _{k}(z)}$

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

これらの関数は再帰関係を満たす

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

差を導入することで、実装上より効率的な方法で再定式化することができる（^[3]も参照）。 ${\displaystyle D_{ni}=N_{n}(U_{ni})-N_{n}(u_{n})}$

${\displaystyle U_{ni}=u_{n}+c_{i}h_{n}\varphi _{1}(c_{i}h_{n}L_{n})f(u_{n})+h_{n}\sum _{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}\sum _{i=2}^{s}b_{i}(h_{n}L_{n})D_{ni}.}$

この方式を適応ステップサイズで実装するために、局所誤差推定の目的で、以下の組み込み方法を検討することができる。

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

同じステージを使用しますが、重み付けが異なります。 ${\displaystyle U_{ni}}$${\displaystyle {\bar {b}}_{i}}$

便宜上、明示的指数ローゼンブロック法とその埋め込み法の係数は、いわゆる縮小ブッチャー表を使用して次のように表すことができます。

さらに、Luan と Ostermann (2014a) ^[8]では、再定式化アプローチによって、局所誤差を分析し、次数 5 までの指数ローゼンブロック法のスティッフ オーダー条件を導出する新しい簡単な方法が提供されることが示されています。この新しい手法と B シリーズの概念の拡張を組み合わせて、Luan と Ostermann (2013) ^[9]では、任意次数の指数ローゼンブロック積分器のスティッフ オーダー条件を導出する理論が最終的に示されました。例として、その研究では、次数 6 までの指数ローゼンブロック法のスティッフ オーダー条件が導出されており、次の表に示されています。

${\displaystyle {\begin{array}{|c|c|c| }\hline No.&{\text{Stiff order condition}}&{\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&\sum _{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}}}$

ここで 任意の正方行列を表します。 ${\displaystyle Z,K,M.\ }$

指数ローゼンブロック法の安定性と収束の結果は、あるバナッハ空間内の強連続半群の枠組みの中で証明されています。

以下に示すすべてのスキームは、スティフ順序条件を満たしているため、スティフ問題を解決するのにも適しています。

最も単純な指数ローゼンブロック法は、次数が 2 である指数ローゼンブロック-オイラー法です。たとえば、Hochbruck ら (2009) を参照してください。

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

Hochbruck ら (2009) によって導出された 3 次指数 Rosenbrock 法のクラスは、exprb32 と名付けられ、次のように与えられます。

式32:

これは次のように書かれています

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

どこ${\displaystyle D_{n2}=N_{n}(U_{n2})-N_{n}(u_{n}).}$

この方式の可変ステップサイズの実装では、指数関数のローゼンブロック・オイラーを使って埋め込むことができます。

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

CoxとMatthews ^[5]は、 Mapleを使用して導出した4次法指数時間差分(ETD)法について説明しています。

彼らの表記法を使用し、未知の関数が であり、時刻 に既知の解があると仮定します。さらに、時間に依存する可能性のある右辺 を明示的に使用します。 ${\displaystyle u}$${\displaystyle u_{n}}$${\displaystyle t_{n}}$${\displaystyle {\mathcal {N}}={\mathcal {N}}(t,u)}$

最初に 3 つのステージ値が構築されます。

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

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

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

最終更新は、

${\displaystyle 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}}(t_{n},u_{n})+2\left[2+Lh+e^{Lh}\left(-2+Lh\right)\right]\left({\mathcal {N}}(t_{n}+h/2,a_{n})+{\mathcal {N}}(t_{n}+h/2,b_{n})\right)+\left[-4-3Lh-(Lh)^{2}+e^{Lh}\left(4-Lh\right)\right]{\mathcal {N}}(t_{n}+h,c_{n})\right\}.}$

上記のアルゴリズムを単純に実装すると、浮動小数点の丸め誤差による数値不安定性が発生します。 ^[10] 理由を理解するために、最初の関数を考えてみましょう。

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

これは、1次オイラー法とETDRK4の3つのステージすべてに存在します。 の値が小さい場合、この関数は数値的なキャンセルエラーの影響を受けます。ただし、これらの数値的な問題は、関数を輪郭積分ア​​プローチ^[10]またはパデ近似^[11]で評価することで回避できます。${\displaystyle z}$${\displaystyle \varphi _{1}}$

指数積分器は、分子動力学^[12]、 VLSI回路シミュレーション[13]、[ ^{14 ]}、コンピュータグラフィックス^{[15]などの}科学計算やビジュアルコンピューティングにおける硬いシナリオのシミュレーションに使用されます。また、ハイブリッドモンテカルロ法のコンテキストでも適用されています。^[16]これらのアプリケーションでは、指数積分器は大きな時間ステップ機能と高精度の利点を示します。このような複雑なシナリオで行列関数の評価を高速化するために、指数積分器は多くの場合、クリロフ部分空間投影法と組み合わせられます。

• 一般線形法

• Berland, Havard; Owren, Brynjulf; Skaflestad, Bard (2005). 「指数積分器の B シリーズと順序条件」SIAM Journal on Numerical Analysis . 43 (4): 1715–1727. CiteSeerX  10.1.1.216.5645 . doi :10.1137/040612683.
• Berland, Havard; Skaflestad, Bard; Wright, Will M. (2007). 「EXPINT-指数積分器用MATLABパッケージ」ACM Transactions on Mathematical Software . 33 (1): 4–es. doi :10.1145/1206040.1206044. S2CID  1525599.
• Chao, Wei-Lun; Solomon, Justin; Michels, Dominik L.; Sha, Fei (2015). 「ハミルトンモンテカルロの指数積分」。第32回国際機械学習会議 (ICML-15) の議事録: 1142–1151。
• サーティーン、ジョン (1960)。「大きな時定数を持つ常微分方程式の解法」。デジタルコンピュータのための数学的手法。Wiley。pp. 128–132。
• Cox, SM ; Matthews , PC (2002年3 月)。「剛性システムの指数時間差分」。Journal of Computational Physics。176 ( 2): 430–455。Bibcode :2002JCoPh.176..430C。doi :10.1006/jcph.2002.6995。
• Hochbruck, Marlis ; Ostermann, Alexander (2010 年 5 月). 「指数積分器」. 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 (2005a). 「半線形放物線問題に対する明示的指数ルンゲ・クッタ法」SIAM Journal on Numerical Analysis . 43 (3): 1069–1090. CiteSeerX  10.1.1.561.5501 . doi :10.1137/040611434.
• Hochbruck , Marlis ; Ostermann, Alexander (2005b年5 月)。「放物線問題に対する指数ルンゲ・クッタ法」。応用数値数学。53 (2–4): 323–339。doi :10.1016/j.apnum.2004.08.005。
• Luan, Vu Thai; Ostermann, Alexander (2014a). 「指数ローゼンブロック法による 5 次構築、分析、数値比較」。計算および応用数学ジャーナル。255 : 417–431。doi : 10.1016 / j.cam.2013.04.041。
• Luan, Vu Thai; Ostermann, Alexander (2014c). 「放物線型問題に対する高次の明示的指数ルンゲ・クッタ法」.計算および応用数学ジャーナル. 256 : 168–179. arXiv : 1307.0661 . doi :10.1016/j.cam.2013.07.027. S2CID  18448807.
• Luan, Vu Thai; Ostermann, Alexander (2013). 「指数 B シリーズ: 硬いケース」. SIAM Journal on Numerical Analysis . 51 (6): 3431–3445. doi :10.1137/130920204.
• Luan, Vu Thai; Ostermann, Alexander (2014)。「5 次指数ルンゲ・クッタ法のスティフ オーダー条件」。Bock, Hans Georg; Hoang, Xuan Phu; Rannacher, Rolf; Schlöder, Johannes P. (編)。複雑なプロセスのモデリング、シミュレーション、最適化 - HPSC 2012: 第 5 回国際高性能科学計算会議の議事録、2012 年 3 月 5 ～ 9 日、ハノイ、ベトナム。Springer。pp. 133 ～ 143。doi : 10.1007/978-3-319-09063-4_11。ISBN 978-3-319-09062-7。
• Luan, Vu Thai; Ostermann, Alexander (2016). 「並列指数ローゼンブロック法」.コンピュータと数学とその応用. 71 (5): 1137–1150. doi : 10.1016/j.camwa.2016.01.020 .
• Michels, Dominik L.; Desbrun, Mathieu (2015). 「分子動力学への半解析的アプローチ」.計算物理学ジャーナル. 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). 「剛性弾性力学問題のための指数積分器」ACM Transactions on Graphics . 33 : 7:1–7:20. doi :10.1145/2508462. S2CID  207207156.
• Pope, David A (1963). 「常微分方程式の数値積分の指数法」Communications of the ACM . 6 (8): 491–493. doi : 10.1145/366707.367592 . S2CID  18598461.
• Tokman, Mayya (2011 年 10 月)。「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 (2006年4 月)。「指数伝播反復法 (EPI) による大規模で硬い常微分方程式の効率的な積分」。Journal of Computational Physics。213 ( 2): 748–776。Bibcode :2006JCoPh.213..748T。doi :10.1016/j.jcp.2005.08.032 。
• Kassam, Aly-Khan; Trefethen, Lloyd N. (2005). 「スティフ偏微分方程式の 4 次タイムステップ」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 51st Annual Design Automation Conference on Design Automation Conference - DAC '14 . pp. 1–6. arXiv : 1511.04519 . doi :10.1145/2593069.2593160. ISBN 9781450327305. S2CID  10585362。
• Weng, Shih-Hung; Chen, Quan; Cheng, Chung-Kuan (2012)。「適応制御によるマトリックス指数法による大規模回路の時間領域解析」。IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems。32 ( 8): 1180–1193。doi : 10.1109 /TCAD.2012.2189396。S2CID 14977067  。

• GPGPUのインテグレーター
• メッシュフリー指数積分器のコード