線形多段階法

線形マルチステップ法は、常微分方程式の数値解法に使用されます。概念的には、数値法は初期点から開始し、次に短い時間ステップを踏んで次の解点を探します。このプロセスは、解をマップするために後続のステップに継続されます。シングルステップ法 (オイラー法など) では、前の 1 つの点とその導関数のみを参照して現在の値を決定します。ルンゲ・クッタなどの方法では、より高次の方法を得るためにいくつかの中間ステップ (たとえば、半ステップ) を実行しますが、2 番目のステップを実行する前に以前の情報をすべて破棄します。マルチステップ法では、前のステップからの情報を破棄するのではなく、保持して使用することで効率を上げようとします。したがって、マルチステップ法では、前の複数の点と導関数値を参照します。線形マルチステップ法の場合、前の点と導関数値の線形結合が使用されます。

定義

常微分方程式の数値解析法は、次のような初期値問題の近似解を求める。 $y'=f(t,y),\quad y(t_{0})=y_{0}.$

結果は、離散時間におけるの値の近似値です。ここで、は時間ステップ ( と呼ばれることもあります) であり、は整数です。 $y(t)$ $t_{i}$ $y_{i}\approx y(t_{i})\quad {\text{where}}\quad t_{i}=t_{0}+ih,$ $h$ $\Delta t$ $i$

マルチステップ法は、前のステップの情報を用いて次の値を計算します。特に、線形マルチステップ法は、との線形結合を用いて、目的の現在のステップにおけるの値を計算します。したがって、線形マルチステップ法は、という形式の方法です。係数とによって、この方法は決定されます。この方法の設計者は、真の解への良好な近似値を得る必要性と、適用しやすい方法を求める要望のバランスを取りながら、係数を選択します。多くの場合、方法を簡素化するために、多くの係数がゼロになります。 $s$ $y_{i}$ $f(t_{i},y_{i})$ $y$ ${\begin{aligned}&y_{n+s}+a_{s-1}\cdot y_{n+s-1}+a_{s-2}\cdot y_{n+s-2}+\cdots +a_{0}\cdot y_{n}\\&\qquad {}=h\cdot \left(b_{s}\cdot f(t_{n+s},y_{n+s})+b_{s-1}\cdot f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}\cdot f(t_{n},y_{n})\right)\\&\Leftrightarrow \sum _{j=0}^{s}a_{j}y_{n+j}=h\sum _{j=0}^{s}b_{j}f(t_{n+j},y_{n+j}),\endaligned}}$ $a_{s}=1$ $a_{0},\dotsc,a_{s-1}$ $b_{0},\dotsc,b_{s}$

明示的法と暗黙的法を区別することができます。の場合、式はを直接計算できるため、この方法は「明示的」と呼ばれます。の場合、の値はの値に依存し、方程式はについて解く必要があるため、この方法は「暗黙的」と呼ばれます。暗黙的式を解くには、ニュートン法などの反復法がよく用いられます。 $b_{s}=0$ $y_{n+s}$ $b_{s}\neq 0$ $y_{n+s}$ $f(t_{n+s},y_{n+s})$ $y_{n+s}$

明示的な多段階法を用いての値を「予測」することがあります。その値は、暗黙的な式で使用され、値を「修正」します。その結果が予測子修正子法です。 $y_{n+s}$

例

例として、問題を考えてみましょう。正確な解はです。 $y'=f(t,y)=y,\quad y(0)=1.$ $y(t)=e^{t}$

ワンステップオイラー

単純な数値法はオイラー法です。オイラー法は、1 ステップの退化ケースに対する明示的なマルチステップ法として考えることができます。 $y_{n+1}=y_{n}+hf(t_{n},y_{n}).$

この方法を問題にステップサイズで適用すると、次の結果が得られます。 $h={\tfrac {1}{2}}$ $y'=y$ ${\begin{aligned}y_{1}&=y_{0}+hf(t_{0},y_{0})=1+{\tfrac {1}{2}}\cdot 1=1.5,\\y_{2}&=y_{1}+hf(t_{1},y_{1})=1.5+{\tfrac {1}{2}}\cdot 1.5=2.25,\\y_{3}&=y_{2}+hf(t_{2},y_{2})=2.25+{\tfrac {1}{2}}\cdot 2.25=3.375,\\y_{4}&=y_{3}+hf(t_{3},y_{3})=3.375+{\tfrac {1}{2}}\cdot 3.375=5.0625\end{aligned}}$

ツーステップ・アダムス・バッシュフォース

オイラー法は1 ステップの手法です。単純なマルチステップ手法は 2 ステップの Adams–Bashforth 法です。この手法では、次の値を計算するためにとの2 つの値が必要です。しかし、初期値問題ではという 1 つの値しか提供されません。この問題を解決する 1 つの方法は、オイラー法で計算されたを 2 番目の値として使用することです。この選択により、Adams–Bashforth 法では次の式が得られます (4 桁に丸められます)。における正確な解はであるため、2 ステップの Adams–Bashforth 法の方がオイラー法よりも正確です。ステップサイズが十分に小さい場合は常にこのようになります。 $y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).$ $y_{n+1}$ $y_{n}$ $y_{n+2}$ $y_{0}=1$ $y_{1}$ ${\begin{aligned}y_{2}&=y_{1}+{\tfrac {3}{2}}hf(t_{1},y_{1})-{\tfrac {1}{2}}hf(t_{0},y_{0})=1.5+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1=2.375,\\y_{3}&=y_{2}+{\tfrac {3}{2}}hf(t_{2},y_{2})-{\tfrac {1}{2}}hf(t_{1},y_{1})=2.375+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5=3.7812,\\y_{4}&=y_{3}+{\tfrac {3}{2}}hf(t_{3},y_{3})-{\tfrac {1}{2}}hf(t_{2},y_{2})=3.7812+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 3.7812-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375=6.0234.\end{aligned}}$ $t=t_{4}=2$ $e^{2}=7.3891\ldots$

多段階法のファミリー

一般的に使用される線形多段階法には、アダムス・バッシュフォース法、アダムス・モールトン法、および後方微分公式(BDF) の 3 つのファミリーがあります。

アダムズ・バッシュフォース法

アダムズ・バッシュフォース法は陽解法です。係数はとであり、はsの位数を持つように選択されます（これにより s の位数が一意に決定されます）。 $a_{s-1}=-1$ $a_{s-2}=\cdots =a_{0}=0$ $b_{j}$

s = 1, 2, 3, 4, 5 の場合の Adams–Bashforth 法は次のとおりです ( Hairer, Nørsett & Wanner 1993 , §III.1; Butcher 2003 , p. 103): ${\begin{aligned}y_{n+1}&=y_{n}+hf(t_{n},y_{n}),\qquad {\text{(This is the Euler method)}}\\y_{n+2}&=y_{n+1}+h\left({\frac {3}{2}}f(t_{n+1},y_{n+1})-{\frac {1}{2}}f(t_{n},y_{n})\right),\\y_{n+3}&=y_{n+2}+h\left({\frac {23}{12}}f(t_{n+2},y_{n+2})-{\frac {16}{12}}f(t_{n+1},y_{n+1})+{\frac {5}{12}}f(t_{n},y_{n})\right),\\y_{n+4}&=y_{n+3}+h\left({\frac {55}{24}}f(t_{n+3},y_{n+3})-{\frac {59}{24}}f(t_{n+2},y_{n+2})+{\frac {37}{24}}f(t_{n+1},y_{n+1})-{\frac {9}{24}}f(t_{n},y_{n})\right),\\y_{n+5}&=y_{n+4}+h\left({\frac {1901}{720}}f(t_{n+4},y_{n+4})-{\frac {2774}{720}}f(t_{n+3},y_{n+3})+{\frac {2616}{720}}f(t_{n+2},y_{n+2})-{\frac {1274}{720}}f(t_{n+1},y_{n+1})+{\frac {251}{720}}f(t_{n},y_{n})\right).\end{aligned}}$

係数は次のように決定できます。多項式補間を使用して、次数の多項式pを求めます。多項式補間のラグランジュの公式から次の式が得られます。多項式pは、解くべき微分方程式の右辺の局所的に良好な近似値であるため、代わりに方程式を検討します。この方程式は正確に解くことができ、解は単にpを積分したものです。これは、次の式を取ることを示唆しています。 p の式を代入すると、Adams–Bashforth 法が発生します。係数は次のように与えられます。補間式pで置き換えると、 h ^sのオーダーの誤差が発生し、sステップの Adams–Bashforth 法は実際にs のオーダーを持つことになります( Iserles 1996、§2.1) $b_{j}$ $s-1$ $p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.$ $p(t)=\sum _{j=0}^{s-1}{\frac {(-1)^{s-j-1}f(t_{n+j},y_{n+j})}{j!(s-j-1)!h^{s-1}}}\prod _{i=0 \atop i\neq j}^{s-1}(t-t_{n+i}).$ $y'=f(t,y)$ $y'=p(t)$ $y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,\mathrm {d} t.$ $b_{j}$ $b_{s-j-1}={\frac {(-1)^{j}}{j!(s-j-1)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s-1}(u+i)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s-1.$ $f(t,y)$

アダムズ・バッシュフォース法は、フランシス・バッシュフォースによる毛細管現象をモデル化する微分方程式を解くために、ジョン・カウチ・アダムズによって考案されました。バッシュフォース（1883）は自身の理論とアダムズの数値解析法（ゴールドスタイン、1977）を発表しました。

アダムス・モールトン法

Adams–Moulton法は、Adams–Bashforth法と同様に、およびを持つという点で類似しています。この場合も、係数bは可能な限り高い次数が得られるように選択されます。しかし、Adams–Moulton法は暗黙的な手法です。という制約を取り除くことで、sステップAdams–Moulton法は次数に到達できますが、sステップAdams–Bashforth法は次数sしかありません。 $a_{s-1}=-1$ $a_{s-2}=\cdots =a_{0}=0$ $b_{s}=0$ $s+1$

s = 0、1、2、3、4 の場合の Adams–Moulton 法がリストされています ( Hairer、Nørsett & Wanner 1993、§III.1; Quarteroni、Sacco & Saleri 2000 )。最初の 2 つの方法は、それぞれ後退オイラー法と台形法( Crank-Nicolson 法とも呼ばれる) です。 ${\begin{aligned}y_{n}&=&y_{n-1}&+hf(t_{n},y_{n}),\\y_{n+1}&=&y_{n}&+h\left({\frac {1}{2}}f(t_{n+1},y_{n+1})+{\frac {1}{2}}f(t_{n},y_{n})\right),\\y_{n+2}&=&y_{n+1}&+h\left({\frac {5}{12}}f(t_{n+2},y_{n+2})+{\frac {8}{12}}f(t_{n+1},y_{n+1})-{\frac {1}{12}}f(t_{n},y_{n})\right),\\y_{n+3}&=&y_{n+2}&+h\left({\frac {9}{24}}f(t_{n+3},y_{n+3})+{\frac {19}{24}}f(t_{n+2},y_{n+2})-{\frac {5}{24}}f(t_{n+1},y_{n+1})+{\frac {1}{24}}f(t_{n},y_{n})\right),\\y_{n+4}&=&y_{n+3}&+h\left({\frac {251}{720}}f(t_{n+4},y_{n+4})+{\frac {646}{720}}f(t_{n+3},y_{n+3})-{\frac {264}{720}}f(t_{n+2},y_{n+2})+{\frac {106}{720}}f(t_{n+1},y_{n+1})-{\frac {19}{720}}f(t_{n},y_{n})\right).\end{aligned}}$

アダムス・モールトン法の導出はアダムス・バッシュフォース法と似ているが、補間多項式では上記の点だけでなく、も用いる。係数は次のように与えられる。 $t_{n-1},\dots ,t_{n-s}$ $t_{n}$ $b_{s-j}={\frac {(-1)^{j}}{j!(s-j)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s}(u+i-1)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s.$

アダムズ・モールトン法は、アダムズ・バッシュフォース法と同様に、ジョン・カウチ・アダムズにのみ由来する。フォレスト・レイ・モールトンの名がこれらの方法と結びついたのは、彼がこれらの方法がアダムズ・バッシュフォース法と予測子・修正子のペアとして併用できることに気づいたためである（Moulton 1926）。ミルン（1926）も同様のアイデアを持っていた。アダムズはニュートン法を用いて陰方程式を解いた（Hairer, Nørsett & Wanner 1993 , §III.1）。

後方微分公式（BDF）

BDF法は、とその他の係数を、次数s （最大次数）に達するように選択した暗黙法です。これらの法は、特にスティッフな微分方程式を解くために使用されます。 $b_{s-1}=\cdots =b_{0}=0$

分析

線形多段階法、そして実際には微分方程式のあらゆる数値解法の解析における中心概念は、収束、順序、および安定性です。

一貫性と秩序

最初の疑問は、この方法に一貫性があるかどうか、つまり差分方程式が微分方程式の良い近似になっているかどうかである。より正確には、h がゼロに近づくにつれて、局所的打ち切り誤差がステップサイズhよりも速くゼロに近づく場合、マルチステップ法は一貫性がある。ここで、局所的打ち切り誤差とは、以前の値がすべて正確であると仮定した方法の結果と、時刻における方程式の正確な解との差として定義される。テイラー級数を使用した計算により、線形マルチステップ法が一貫性を持つのは、次の場合のみであることが示される。上記の方法はすべて一貫性がある ( Hairer、Nørsett、Wanner 1993、§III.2)。 ${\begin{aligned}&a_{s}y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}$ $y'=f(t,y)$ $y_{n+s}$ $y_{n+s-1},\ldots ,y_{n}$ $t_{n+s}$ $\sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad \sum _{k=0}^{s}b_{k}=s+\sum _{k=0}^{s-1}ka_{k}.$

手法が整合的であれば、次に問題となるのは、数値解法を定義する差分方程式が微分方程式をどの程度近似するかです。多段階法は、hがゼロに近づくにつれて局所誤差がp次となる場合、p次を有すると言われます。これは、手法の係数に関する以下の条件と等価です。s ステップAdams–Bashforth法はs次ですが、sステップAdams–Moulton法はp次です（Hairer, Nørsett & Wanner 1993、§III.2）。 $O(h^{p+1})$ $\sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad q\sum _{k=0}^{s}k^{q-1}b_{k}=s^{q}+\sum _{k=0}^{s-1}k^{q}a_{k}{\text{ for }}q=1,\ldots ,p.$ $s+1$

これらの条件は、多くの場合、特性多項式 を使用して定式化されます。これらの多項式を使用すると、メソッドがp次を持つための上記の条件は次のようになります。特に、メソッドが少なくとも 1 次を持つ場合、つまりおよびの場合に、メソッドは一貫しています。 $\rho (z)=z^{s}+\sum _{k=0}^{s-1}a_{k}z^{k}\quad {\text{and}}\quad \sigma (z)=\sum _{k=0}^{s}b_{k}z^{k}.$ $\rho (e^{h})-h\sigma (e^{h})=O(h^{p+1})\quad {\text{as }}h\to 0.$ $\rho (1)=0$ $\rho '(1)=\sigma (1)$

安定性と収束

1ステップ法の数値解は初期条件に依存しますが、 sステップ法の数値解はs 個の開始値すべてに依存します。したがって、数値解が開始値の摂動に対して安定しているかどうかが重要です。線形マルチステップ法は、特定の時間間隔における特定の微分方程式に対してゼロ安定であるとは、サイズ ε の開始値の摂動によって、ステップサイズhに依存しないKの値に対して、その時間間隔での数値解がK ε以下しか変化しない場合を指します。これは、微分方程式の条件を確認すれば十分であるため、「ゼロ安定性」と呼ばれます( Süli & Mayers 2003、p. 332)。 $y_{0}$ $y_{0},y_{1},\ldots ,y_{s-1}$ $y'=0$

特性多項式ρの根がすべて 1 以下の絶対値を持ち、かつ絶対値 1 の根の重複度が 1 であるとき、根条件が満たされるという。線形多段階法が零安定であるのは、根条件が満たされる場合のみである ( Süli & Mayers 2003 , p. 335)。

ここで、十分に滑らかな微分方程式に一貫性のある線形多段階法を適用し、すべての初期値がとして初期値に収束すると仮定します。すると、数値解は、この方法が零安定であるかのように、かつその場合に限り、厳密解に収束します。この結果は、ゲルムント・ダールキストにちなんで名付けられたダールキスト同値定理として知られています。この定理は、有限差分法のラックス同値定理と精神的に類似しています。さらに、この方法がp次を持つ場合、グローバル誤差（固定時刻における数値解と厳密解の差）はです（Süli & Mayers 2003、p. 340）。 $y_{1},\ldots ,y_{s-1}$ $y_{0}$ $h\to 0$ $h\to 0$ $O(h^{p})$

さらに、この方法が収束する場合、が法1の唯一の根であるとき、この方法は強安定であると言われます。この方法が収束し、法1のすべての根が重複していないが、そのような根が複数存在するとき、この方法は相対安定であると言われます。この方法が収束するためには、1が根でなければならないことに注意してください。したがって、収束法は常にこれら2つのいずれかです。 $z=1$

スティッフな方程式に対する線形マルチステップ法のパフォーマンスを評価するために、線形テスト方程式y' = λ yについて考えます。ステップサイズhでこの微分方程式に適用されたマルチステップ法は、特性多項式を持つ線形回帰関係をもたらします。この多項式は、マルチステップ法の安定性多項式 と呼ばれます。その根がすべて 1 未満の係数を持つ場合、マルチステップ法の数値解はゼロに収束し、マルチステップ法はそのh λの値に対して絶対安定していると言われます。実部が負のすべてのh λに対して絶対安定している場合、その方法はA 安定であると言われます。絶対安定領域は、マルチステップ法が絶対安定であるすべてのh λの集合です( Süli & Mayers 2003、pp. 347 & 348)。詳細については、スティッフな方程式とマルチステップ法のセクションを参照してください。 $\pi (z;h\lambda )=(1-h\lambda \beta _{s})z^{s}+\sum _{k=0}^{s-1}(\alpha _{k}-h\lambda \beta _{k})z^{k}=\rho (z)-h\lambda \sigma (z).$

例

アダムズ・バッシュフォースの3段階法を考える。したがって、一つの特性多項式はであり、その根はであり、上記の条件を満たす。は法1の唯一の根であるため、この法は強安定である。 $y_{n+3}=y_{n+2}+h\left({23 \over 12}f(t_{n+2},y_{n+2})-{4 \over 3}f(t_{n+1},y_{n+1})+{5 \over 12}f(t_{n},y_{n})\right).$ $\rho (z)=z^{3}-z^{2}=z^{2}(z-1)$ $z=0,1$ $z=1$

もう一つの特性多項式は $\sigma (z)={\frac {23}{12}}z^{2}-{\frac {4}{3}}z+{\frac {5}{12}}$

第1および第2ダルキスト障壁

これら2つの結果はゲルムント・ダールキストによって証明され、線形多段階法の収束順序とA安定性に関する重要な上界を示している。最初のダールキスト障壁はダールキスト（1956）で、2番目のダールキスト障壁はダールキスト（1963）で証明された。

最初のダルキスト障壁

第一のダールキスト障壁は、零安定かつ線形なqステップ多段階法は、 qが奇数の場合はq + 1を超える収束次数を達成できず、 qが偶数の場合はq + 2を超える収束次数を達成できないことを述べています。この方法が明示的である場合、 qを超える収束次数を達成することはできません（Hairer, Nørsett & Wanner 1993、Thm III.3.5）。

第二ダルキスト障壁

第二のダルキスト障壁は、明示的な線形多段階法はどれもA安定ではないというものです。さらに、（暗黙的な）A安定線形多段階法の最大次数は2です。次数2のA安定線形多段階法の中で、台形則の誤差定数が最も小さいのは台形則です（Dahlquist 1963、Thm 2.1および2.2）。

参照

デジタルエネルギーゲイン

参考文献

バッシュフォース、フランシス（1883）「毛細管現象の理論検証の試み：理論上の液滴形状と実測値の比較による。液滴形状の理論値を示す表を作成する際に用いられた積分法の説明付き」JCアダムズ著、ケンブリッジ{{citation}}: CS1 maint: location missing publisher (link)。
ブッチャー、ジョン・C.（2003）、常微分方程式の数値解析法、ジョン・ワイリー、ISBN 978-0-471-96758-3。
Dahlquist, Germund (1956)、「常微分方程式の数値積分における収束と安定性」、Mathematica Scandinavica、4 : 33– 53、doi : 10.7146/math.scand.a-10454。
Dahlquist, Germund (1963)、「線形多段階法の特殊な安定性問題」、BIT 、 3 : 27–43 、 doi : 10.1007 /BF01963532、ISSN0006-3835 、S2CID120241743 。
ゴールドスタイン、ハーマン H. (1977)、「16世紀から19世紀までの数値解析の歴史」、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-90277-7。
ハイラー、エルンスト。ノーセット、シベール・ポール。 Wanner、Gerhard (1993)、常微分方程式の解法 I: Nonstiff 問題(第 2 版)、ベルリン: Springer Verlag、ISBN 978-3-540-56670-0。
ヘアラー、エルンスト、ワーナー、ゲルハルト（1996年）、常微分方程式の解法II：スティフ問題と微分代数問題（第2版）、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-3-540-60452-5。
Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations , Cambridge University Press, Bibcode : 1996fcna.book.....I , ISBN 978-0-521-55655-2。
ミルン, WE (1926)、「常微分方程式の数値積分」、アメリカ数学月刊誌、33 (9)、アメリカ数学会: 455– 460、doi : 10.2307/2299609、JSTOR 2299609。
モールトン、フォレスト・R.（1926）、『外部弾道学の新手法』、シカゴ大学出版局。
クアルテローニ, アルフィオ;サッコ、リッカルド。サレリ、ファウスト (2000)、Matematica Numerica、Springer Verlag、ISBN 978-88-470-0077-3。
Süli, Endre; Mayers, David (2003), 『数値解析入門』 , Cambridge University Press , ISBN 0-521-00794-1。

外部リンク

ワイスタイン、エリック W. 「アダムス法」。MathWorld 。