線形多段階法

単純な数値計算法としては、オイラー法がある。 $${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n}).}$$ オイラー法は、1ステップという退化したケースに対する明示的な多段階法と見なすことができる。

この方法は、ステップサイズで適用されます。${\displaystyle h={\tfrac {1}{2}}}$問題について${\displaystyle y'=y}$すると、以下の結果が得られます。 $${\displaystyle {\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段階のアダムス・バッシュフォース法がある。 $${\displaystyle y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).}$$ このメソッドには2つの値が必要です。${\displaystyle y_{n+1}}$そして${\displaystyle y_{n}}$次の値を計算するには、${\displaystyle y_{n+2}}$しかし、初期値問題は1つの値しか提供しない。${\displaystyle y_{0}=1}$この問題を解決する一つの方法は、${\displaystyle y_{1}}$オイラー法で計算された2番目の値。この選択により、アダムス・バッシュフォース法では（4桁に丸めて）次の値が得られる。 $${\displaystyle {\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}}}$$ 正確な解決策は${\displaystyle t=t_{4}=2}$は${\displaystyle e^{2}=7.3891\ldots }$したがって、2段階のアダムス・バッシュフォース法はオイラー法よりも精度が高い。これは、ステップサイズが十分に小さい場合、常に当てはまる。

アダムス・バッシュフォース法は陽解法です。係数は${\displaystyle a_{s-1}=-1}$そして${\displaystyle a_{s-2}=\cdots =a_{0}=0}$一方で、${\displaystyle b_{j}}$メソッドの次数がsになるように選択されます（これによりメソッドが一意に決定されます）。

s = 1, 2, 3, 4, 5 の場合の Adams–Bashforth 法は次のとおりです ( Hairer, Nørsett & Wanner 1993 、§III.1 ; Butcher 2003 、p. 103 ):  $${\displaystyle {\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}}}$$

係数${\displaystyle b_{j}}$は次のように決定できます。多項式補間を使用して次数 の多項式p を求めます。${\displaystyle s-1}$そのため $${\displaystyle p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.}$$多項式補間の ラグランジュ公式は、$${\displaystyle 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}).}$$ 多項式pは、微分方程式の右辺を局所的に良好に近似する。${\displaystyle y'=f(t,y)}$それは解決すべき問題なので、方程式を考えてみましょう。${\displaystyle y'=p(t)}$代わりに。この方程式は厳密に解くことができ、解は単にpの積分です。これは、 $${\displaystyle y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,\mathrm {d} t.}$$ アダムス・バッシュフォース法は、pの式を代入したときに得られる。係数${\displaystyle b_{j}}$結果は以下の通り $${\displaystyle 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.}$$ 交換する${\displaystyle f(t,y)}$その補間関数pによってh ^sのオーダーの誤差が生じ、したがってsステップ Adams–Bashforth 法は確かにs のオーダーを持つことになる( Iserles 1996 、§2.1)

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

アダムス・モールトン法は、アダムス・バッシュフォース法と同様に、${\displaystyle a_{s-1}=-1}$そして${\displaystyle a_{s-2}=\cdots =a_{0}=0}$。ここでも、 b係数は可能な限り高い次数を得るように選択されます。ただし、アダムス・モールトン法は陰解法です。${\displaystyle b_{s}=0}$sステップのアダムス・モールトン法は次数に達することができる${\displaystyle s+1}$一方、sステップのアダムス・バッシュフォース法はsのオーダーしか持ちません。

s = 0、1、2、3、4 の場合の Adams–Moulton 法は、 ( Hairer、Nørsett & Wanner 1993 、§III.1 ; Quarteroni、Sacco & Saleri 2000 ) に列挙されており、最初の 2 つの方法はそれぞれ後退オイラー法と台形公式( Crank-Nicolson 法としても知られる) である。 $${\displaystyle {\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}}}$$

アダムス・モールトン法の導出はアダムス・バッシュフォース法と同様ですが、補間多項式は点だけでなく${\displaystyle t_{n-1},\dots ,t_{n-s}}$上記の通りだが、${\displaystyle t_{n}}$係数は次のように与えられる。 $${\displaystyle 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.}$$

アダムス・モールトン法は、アダムス・バッシュフォース法と同様に、ジョン・カウチ・アダムスのみによるものです。フォレスト・レイ・モールトンの名前がこれらの方法と結びついたのは、彼がこれらの方法をアダムス・バッシュフォース法と予測子・修正子のペアとして併用できることに気づいたためです（モールトン 1926 ）。ミルン（1926）も同じ考えを持っていました。アダムスは陰方程式を解くためにニュートン法を使用しました（ヘアラー、ノーセット、ワナー 1993 、§III.1）。

BDF メソッドは暗黙的なメソッドであり、${\displaystyle b_{s-1}=\cdots =b_{0}=0}$そして、他の係数は、この方法が次数s (可能な限り最大) を達成するように選択されます。これらの方法は、特に硬い微分方程式の解法に用いられます。

最初の質問は、その方法が一貫しているかどうかです。差分方程式は $${\displaystyle {\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}}}$$ 微分方程式の良い近似${\displaystyle y'=f(t,y)}$より正確には、多段階法は、h がゼロに近づくにつれて局所打ち切り誤差がステップサイズ h よりも速くゼロに近づく場合に一貫性があると言えます。ここで、局所打ち切り誤差は、結果とステップサイズhの差として定義されます。${\displaystyle y_{n+s}}$この方法の、これまでの値がすべて${\displaystyle y_{n+s-1},\ldots ,y_{n}}$は正確であり、時刻における方程式の正確な解は${\displaystyle t_{n+s}}$テイラー級数を用いた計算により、線形多段階法が整合的であるのは 、$${\displaystyle \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}.}$$ 上記の方法はすべて一貫している（Hairer、Nørsett & Wanner 1993 、§III.2）。

方法が一貫している場合、次の問題は、数値解法を定義する差分方程式が微分方程式をどの程度正確に近似しているかである。多段階法は、局所誤差がオーダー p である場合にオーダーpであると言われる。${\displaystyle O(h^{p+1})}$hがゼロに近づくとき。これは、各手法の係数に関する以下の条件と同等です。 $${\displaystyle \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ステップアダムス・バッシュフォース法の次数はsであり、sステップアダムス・モールトン法の次数は${\displaystyle s+1}$( Hairer、Nørsett & Wanner 1993 、§III.2)。

これらの条件は、特性多項式を用いて定式化されることが多い。$${\displaystyle \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}.}$$ これらの多項式に関して、メソッドが次数pを持つための上記の条件は次のようになる。 $${\displaystyle \rho (e^{h})-h\sigma (e^{h})=O(h^{p+1})\quad {\text{as }}h\to 0.}$$ 特に、この方法は少なくとも1のオーダーを持つ場合に一貫性があり、それは次の場合に当てはまります。${\displaystyle \rho (1)=0}$そして${\displaystyle \rho '(1)=\sigma (1)}$。

1段階法の数値解は初期条件に依存する${\displaystyle y_{0}}$しかし、 sステップ法の数値解はs個の初期値すべてに依存し、${\displaystyle y_{0},y_{1},\ldots ,y_{s-1}}$したがって、数値解が初期値の摂動に対して安定しているかどうかは興味深い点である。線形多段階法は、ある微分方程式に対して、与えられた時間間隔でゼロ安定である。これは、初期値にεの大きさの摂動を加えたときに、その時間間隔における数値解が、ステップサイズhに依存しないある値Kに対して、 Kε以下しか変化しない場合に成り立つ。これは、微分方程式の条件をチェックするだけで十分であるため、「ゼロ安定性」と呼ばれる。${\displaystyle y'=0}$( Süli & Mayers 2003 、p. 332)。 

特性多項式ρの根の絶対値が1以下であり、絶対値1の根の重複度が1である場合、根条件が満たされていると言います。線形多段階法は、根条件が満たされている場合に限り、ゼロ安定です（Süli & Mayers 2003 、p. 335）。 

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

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

硬い方程式に対する線形多段階法の性能を評価するために、線形テスト方程式y' = λ yを考えます。ステップサイズhでこの微分方程式に多段階法を適用すると、特性多項式を持つ 線形漸化式が得られます。$${\displaystyle \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).}$$ この多項式は、多段階法の安定性多項式と呼ばれます。そのすべての根の絶対値が 1 未満であれば、多段階法の数値解はゼロに収束し、そのh λの値に対して多段階法は絶対安定であると言われます。実部が負のすべてのh λに対して絶対安定である場合、この方法は A-安定であると言われます。絶対安定領域は、多段階法が絶対安定であるすべてのh λの集合です( Süli & Mayers 2003 、pp. 347 & 348) 。詳細については、硬い方程式と多段階法のセクションを参照してください。 

アダムス・バッシュフォースの3段階法について考えてみよう $${\displaystyle 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).}$$ したがって、特性多項式は $${\displaystyle \rho (z)=z^{3}-z^{2}=z^{2}(z-1)}$$ 根源を持つ${\displaystyle z=0,1}$、そして上記の条件が満たされている。${\displaystyle z=1}$は法1の唯一の根であり、この方法は非常に安定している。

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

第一のダールクイスト障壁は、ゼロ安定かつ線形なqステップ多段階法は、 qが奇数の場合はq + 1より大きい収束次数を達成できず、qが偶数の場合はq + 2より大きい収束次数を達成できないと述べている。また、この方法が陽解法である場合は、 qより大きい次数を達成することはできない（Hairer、Nørsett & Wanner 1993 、定理 III.3.5）。

2番目のダールクイスト障壁は、明示的な線形多段階法はA安定ではないと述べている。さらに、（暗黙的な）A安定な線形多段階法の最大次数は2である。次数2のA安定な線形多段階法の中で、台形公式は最小の誤差定数を持つ（ダールクイスト1963 、定理2.1および2.2）。