ルンゲ＝クッタ法
数値解析においてルンゲ=クッタ法(Runge–Kutta method)とは、初期値問題に対して近似解を与える常微分方程式の数値解法に対する総称である。この技法は1900年頃に数学者カール・ルンゲとマルティン・クッタによって発展を見た。
一連のルンゲ=クッタ公式の中で最も広く知られているのが、古典的ルンゲ=クッタ法 (RK4、もしくは単に狭義の ルンゲ=クッタ法、the (classical) Runge–Kutta method) などと呼ばれる4次の公式である。
次の初期値問題を考える。
y' = f(t, y), \quad y(t_0) = y_0.
但し、y(t) が近似的に求めたい未知関数であり、その t における勾配は f(t, y) によって t 及び y(t) の関数として与えられている。時刻 t0 における初期値は y0 で与えられている。
今、時刻 tn における値 yn = y(tn) が既知のとき、十分に小さなステップ幅 h に対して yn+1, tn+1 を以下の式で与えると、yn+1 は y(tn+1) の 4次精度の近似になっている。このステップを逐次的に繰り返すことによって、初期値 y0 から任意の時刻 tn における近似値 yn が求められる。
\begin{align}
y_{n+1} &= y_n + {h \over 6} (k_1 + 2k_2 + 2k_3 + k_4), \\
t_{n+1} &= t_n + h.
\end{align}
ここで、
\begin{align} k_1 &= f \left( t_n, y_n \right), \\
k_2 &= f \left( t_n + {h \over 2}, y_n + {h \over 2} k_1 \right), \\
k_3 &= f \left( t_n + {h \over 2}, y_n + {h \over 2} k_2 \right), \\
k_4 &= f \left( t_n + h, y_n + hk_3 \right) \end{align}
である。次の値 (yn+1) は、現在の値 (yn) に増分を加えたものであり、増分は勾配の推定値に間隔 h を乗じたものになっている。勾配の推定値は、k1, ..., k4 の4つの勾配の重み付け平均で求める。k1, ..., k4 のそれぞれの勾配は、特定の (t, y) に対する f によって与えられ、以下のように解釈できる。
k1 は区間の最初 tn における勾配である (オイラー法で用いる勾配に一致する)。
k2 は区間の中央 tn + h/2 における勾配の近似値である (中点法で用いる勾配)。計算に用いる中央の y の値は、初期位置の勾配 k1 を用いてオイラー法で推定する。
k3 は区間の中央における勾配のもう一つの近似値である。中央の y を k2 の値から推定して用いる。
k4 は区間の最後 tn + h における勾配の近似値であり、k3 の値から推定された最後の点の y の値を用いる。
重み付き平均では、中央の勾配に対して大きな重みを用いる。シンプソン則を用いた平均と同等の形になる。
\mbox{slope} = \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}.
RK4は4次の方法である。厳密解とRK4のテイラー展開が4次の項まで一致し、1ステップの推定誤差は O(h^5) のオーダーになる。目的の時刻の y を求めるのに必要なステップ数は O(h^{-1}) になるので、全体の推定誤差は O(h^4) になる。
前述の RK4 の一般化として、以下の形式を持つ s 段のルンゲ゠クッタ法を構成することができる。整数 s をそのルンゲ゠クッタ法の段数 (stage) という。
y_{n+1} = y_n + h\sum_{i=1}^s b_i k_i,
但し、
k_i = f\left(t_n + hc_i, y_n + h\sum_{j=1}^s a_{ij} k_j\right), \quad i = 1,\ldots,s.
(文献によって、等価であるが上と異なる定義の仕方をしているものがあることに注意する)。
具体的なルンゲ゠クッタ公式は、解ができるだけ高い精度を持つように適切に選ばれた係数 aij (ルンゲ゠クッタ行列)、bi (重み)、cj (節点) で指定される ( i,j \le s )。特に  i \le j に対して  a_{ij} = 0 を満たす方法が広く用いられ、総称して 陽的ルンゲ゠クッタ法 (ERK、explicit Runge–Kutta methods) と呼ぶ。そうでないものを 陰的ルンゲ゠クッタ法 (IRK、implicit Runge–Kutta methods) と呼ぶ。
近似値 yn を yn+1 から計算するときに発生する誤差の大きさが O(h^{p+1}) のとき、そのルンゲ゠クッタ公式は p 次精度を持つといい、p を次数 (または位数) と呼ぶ。p 次のルンゲ゠クッタ公式は、誤差の大きさの条件に誤差の表式を代入し、係数の条件を求めることによって得られる。例えば、2段の陽的方法が2次精度を持つための係数に対する条件は、 b_1 + b_2 =1 ,  b_2c_2 = 1/2 , かつ  b_2a_{21} = 1/2 である。この条件を満たす範囲内で様々な方法を考え得る。
これらの係数を分かりやすく表記する方法として、以下のような形式のブッチャー配列 (Butcher tableau) が知られている:
\begin{align}
\begin{array}{c|ccccc}
c_1 & a_{11} & a_{12} & \cdots & a_{1s} \\
c_2 & a_{21} & a_{22} & \cdots & a_{2s} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
c_s & a_{s1} & a_{s2} & \cdots & a_{ss} \\ \hline
& b_1 & b_2 & \cdots & b_s
\end{array} &= \begin{array}{c|c} \mathbf{c} & A \\ \hline & \mathbf{b}^\mathrm{T} \end{array}
\end{align}
実際には、それぞれのルンゲ゠クッタ法について各要素に具体的な値を入れて用いる。陽的な方法ではルンゲ゠クッタ行列の上三角成分は常に 0 になるので表記を省略する。例えば RK4 はブッチャー配列を用いて以下のように表現される。
\begin{align}
\begin{array}{c|ccccc}
0   & \\
1/2 & 1/2 \\
1/2 & 0 & 1/2 \\
1   & 0 & 0 & 1 \\ \hline
& 1/6 & 1/3 & 1/3 & 1/6
\end{array}
\end{align}
ルンゲ゠クッタ法が一貫しているためには、次の条件が満たされている必要がある。
\sum_{j=1}^{s} a_{ij} = c_i, \; i=1, \ldots, s.
ルンゲ=クッタ法は、数値積分における求積法 (quadrature) と深く繋がる。時刻 tn での値から tn+1 = tn + h での値を求めるときの方程式は以下のように定める。
y' = f(t,y), \; y(t_n) = y_n.
求積法は、与えられた区間での定積分の値を被積分関数の値の線型結合として近似する方法である。簡単のために、区間を [0, 1] とする。よって求積法の公式は
\int_0^1 f(t)dt \approx \sum_{i=1}^{s} b_i f(c_i)
となる。ここで、bi と ci は先に選ばれた定数であり、前述の重みと節点に対応する。上記式に対し、等式がすべての p − 1 次以下の多項式に成立するとき(すなわち、誤差が0のとき)、その求積法は p 次精度であり、p を次数と呼ぶ。節点が s 個の時、最大次数は 2s であり、その方法は s 次ガウス・ルジャンドル公式と呼ばれる。
そして上記の方程式を積分形式に変形し、求積法を用いると次の公式となる。
y(t_{n+1}) = y_n + \int_{y_n}^{y_{n+1} f(t,y(t)) dt = y_n + h\int_0^1 y(t_n+h\tau, y(t_n+h\tau))d\tau = y_n + h\sum_{i=1}^s b_if(t_n + c_i h, y(t_n + c_i h))
k_i = f(t_n + c_i h, y(t_n + c_i h))  とおく。ki あるいは y(tn + ci h) を適切に(線型結合として)近似することでルンゲ=クッタ法の公式となる。その上、係数をテイラー展開より正しく選択すると、方法の収束性も求積法の収束性より保証される。しかし、局所誤差のオーダーや上界は、方法によって大きく異なるので、方法別に計算しなければならない。
陽的ルンゲ゠クッタ法では a_{ij}=0 ( i \le j ) が満たされるので、ブッチャー配列は以下の形になる。
この時、各勾配 k1, ..., ks を以下のように逐次的に求めることができる。
\begin{align} k_1 &= f(t_n, y_n), \\
k_2 &= f(t_n+c_2h, y_n+a_{21}hk_1), \\
k_3 &= f(t_n+c_3h, y_n+a_{31}hk_1+a_{32}hk_2), \\
&\vdots\\
k_s &= f(t_n+c_sh, y_n+a_{s1}hk_1+a_{s2}hk_2+\cdots+a_{s,s-1}hk_{s-1}). \end{align}
(文献によって、等価であるが上と異なる定義の仕方をしているものがあることに注意する)。
陽的ルンゲ゠クッタ法が目的の精度 p になる係数を持つためには、十分に大きな段数 s が必要になる。少なくとも次数以上の段数が必要 ( s \ge p ) であり、更に5次以上の場合には段数は次数よりも大きく取らなければならない ( s > p ) ことが知られている。各次数 p に対する最低段数 s の一般式は未解決問題である。具体的な値が幾つか知られている:
\begin{array}{c|cccccccc}
p & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\hline
\min s & 1 & 2 & 3 & 4 & 6 & 7 & 9 & 11
\end{array}
最も単純なルンゲ゠クッタ法が 1段1次 の方法であり、一意に定まる。(前進) オイラー法と等価になる。
y_{n+1} = y_n + hf(t_n,y_n).
以下のブッチャー配列で表現される。
2段2次の方法は1パラメータの自由度 α を持ち、以下のブッチャー配列で与えられる。
y_{n+1} = y_n + h\bigl( (1-\tfrac1{2\alpha}) f(t_n, y_n) + \tfrac1{2\alpha} f(t_n + \alpha h, y_n + \alpha h f(t_n, y_n)) \bigr).
である。 \alpha = 1/2  の場合が 中点法 (または修正オイラー法, modified Euler method)
y_{n+1} = y_n + hf\left(t_n+\frac{h}{2},y_n+\frac{h}{2}f(t_n, y_n)\right)
に対応し、以下のブッチャー配列で与えられる。
\alpha = 1  の場合は ホイン法(または改良オイラー法, improved Euler method)として知られ、ブッチャー配列は以下の通りである。
古典的ルンゲ゠クッタ法 (RK4) は既に述べた通り以下のブッチャー配列で与えられる:
修正版としてクッタの3/8公式 (Kutta's 3/8-rule) が知られている。
他に使われている方法は、ルンゲ=クッタ法のリストに参照。
前述の通り、2段の陽的方法が2次精度を持つための係数に対する条件は、 b_1 + b_2 =1 ,  b_2c_2 = 1/2 , かつ  b_2a_{21} = 1/2 である。例として、それらの条件の導出を見てみよう。
一般的に2段陽的ルンゲ=クッタ法に対応する配列は以下の通りである(一貫性を用いて c_1 = 0 がわかる)。
\begin{array}{c|cc}
0 & &\\
c_2 & a_{21}&\\
\hline
&  b_1&b_2\\
\end{array}
公式から k_2 = f(t_n + c_2h, y_n + ha_{21} f(t_n,y_n)) の f(tn,yn) に関するテイラー展開を考える
k_2 = f(t_n,y_n) + c_2h f_t(t_n,y_n) + ha_{21}f(t_n,y_n)f_y(t_n,y_n) + O(h^2)
ここで、ft は f  の t に関する偏微分である。それを  y_{n+1} = y_n + h(b_1k_1 + b_2k_2)  に代入し、 k_1 = f(t_n,y_n)  を用いて整理すると
y_{n+1} = y_n + h(b_1 + b_2)f(t_n,y_n) + h^2b_2(c_2f_t(t_n,y_n) + a_{21}f(t_n,y_n)f_y(t_n,y_n)) + O(h^3)
となる。同時に、方程式  y'(t) = f(t,y)  の t に関する微分を取って y' を f(t,y) に置き換えると
y(t) = f_t(t,y) + f(t,y)f_y(t,y)
となる。厳密解を y(t) とする。上記式を用いて y(tn+1) の tn に関するテイラー展開を考える
y(t_{n+1}) = y(t_n) + hf(t_n,y_n) + \frac{1}{2}h^2(f_t(t_n,y_n) + f(t_n,y_n)f_y(t_n,y_n)) + O(h^3)
2次精度を持つ条件は、局所誤差  e_{n+1,h} = y(t_{n+1}) - y_{n+1} = O(h^3)  である。二つの展開式の係数を比較すると、その条件が b_1 + b_2 =1 ,  b_2c_2 = 1/2 , かつ  b_2a_{21} = 1/2 であることがわかる。
ルンゲ=クッタ法の局所誤差を精確に計算することが難しいので、実践では誤差を一定の範囲にコントロールするのが望ましいである。そのために開発されたのが 埋め込み型ルンゲ=クッタ法(Embedded Runge-Kutta method)である。適応型ルンゲ=クッタ法 (adaptive Runge–Kutta method) とも呼ばれる。線型多段法にもミルンデバイスと呼ばれる相似の方法が存在する。
埋め込み方法は陽的ルンゲ=クッタ法二つを利用する(下の方法を上の方法に埋め込むように見えるので埋め込み型と呼ばれる)。ブッチャー配列の以下のように拡張する。
ここで、bi は p 次陽的方法に対応し、b は p-1 次陽的方法に対応する。二つの方法は係数 aij と ci を共用する。正しく係数を選ぶと、二つの方法をともに収束させることができる。そのとき、埋め込み方法の時刻 tn での相対(局所)誤差 en は次の公式で与えられる。
e_{n} = y_n - y^*_n = h \sum_{i=1}^s (b_i - b^*_i)k_i = O(h^p)
ルンゲ=クッタ法の収束性から、相対誤差も0に収束することがわかる。埋め込みルンゲ=クッタ法は、アルゴリズムを用いて一時刻ごと(自動的)に刻み幅 h を調整し、誤差をコントロールすることができる(故に適応型と呼ばれる)。よって絶対誤差を計算せずに刻み幅を正しく設定することができる。そのアルゴリズムは、大体以下の通りである。
誤差の許容値を δ とする。刻み幅 h の近似値 yn+1 と y をルンゲ=クッタ法で計算する。二つの値に対し、 \|e_{n+1}\| \ge h\delta  が成立するとき、h が大きすぎて小さくする必要がある。よって新しい刻み幅 h' = \frac{1}{2}h と設定し再び近似値を計算する。代わりに  \|e_{n+1}\| \le \frac{1}{10}h\delta  が成立するとき、h が小さすぎて大きくするほうが効率が良い。よって新しい刻み幅 h' = 2h と設定し、次の時刻での近似値を計算する(この場合、誤差が許容値より小さいので今の近似値を二度と計算する必要はない)。二つの不等式ともが成立しないとき、そのままの刻み幅で次の時刻での近似値を計算してよい。
ただし、使用したスカラー(1/2他)は方程や方法によって変更することも可能である。また、実践では h を小さくしすぎないようにするため、下界 hmin を先に設定することもある。 h < h_{\mathrm{min}  のときにアルゴリズムを停止し、代わりにもっと高い次数を持つ方法を使う。
もっとも単純な埋め込み型ルンゲ=クッタ法は、ホイン法(2次)とオイラー法(1次)を組み合わせる方法である。以下の拡張ブッチャー配列で与えられる。
そして実践でよく使われているのが5次と4次の陽的方法を組み合わせる ルンゲ=クッタ=フェールベルグ法 である。対応する拡張ブッチャー配列は以下の通りである。
他に使われている方法は、Bogacki–Shampine法(次数3と2)、Cash–Karp法 と ドルマン=プリンス法(両方次数5と4)である。
いままでに述べた方法はすべて陽公式である。陽的ルンゲ=クッタ方法の絶対安定性領域(region of absolute stability)が小さくて有界であるため、硬い方程式の解を計算する場合、方法は不適切である。この問題は特に偏微分方程式の解を計算するときに重要である。
陽的方法の不安定さは陰的ルンゲ=クッタ法の開発の動機となる。陰的ルンゲ=クッタ法は上述の一般的な公式と同じく、以下の形で与えられる
y_{n+1} = y_n + h\sum_{i=1}^s b_i k_i,
但し、
k_i = f\left(t_n + hc_i, y_n + h\sum_{j=1}^s a_{ij} k_j\right), \quad i = 1,\ldots,s.
であり、対応するルンゲ=クッタ行列は厳密な下三角行列ではない。結果として、一時刻ごとに代数方程式系を解かなければならなくなる。応じて、計算コストもかなり上がる。s 段法を使って m 個の成分からなる微分方程式系(すなわち \vec{y} = (y_1, \ldots, y_m) のとき)に適用する場合に対応する代数方程式の数は ms となる。これは陰的線型多段法とも比較できる:s 段陰的線型多段法を使って同じ方程式系に適用する場合に対応する代数方程式の数は m であり、段数 s に依存しない。
一番単純な陰的ルンゲ=クッタ法は、後退オイラー法
y_{n+1} = y_n + hf(t_{n+1},y_{n+1})
である。対応するブッチャー配列も単純に以下の通りである。
\begin{array}{c|c}
1 & 1 \\
\hline
& 1 \\
\end{array}
他の例として、台形公式と呼ばれる方法は以下の公式で与えられる。
y_{n+1} = y_n + \frac{1}{2}h(f(t_n,y_n) + f(t_{n+1},y_{n+1}))
対応する配列は以下の通りである。
\begin{array}{c|cc}
0 & 0& 0\\
1 & \frac{1}{2}& \frac{1}{2}\\
\hline
&  \frac{1}{2}&\frac{1}{2}\\
\end{array}
その対応は、 y_{n+1} = y_n + \frac{1}{2}k_1 + \frac{1}{2}k_2  を覚えてて、公式を以下のように書き換えると明らかになる。
y_{n+1} = y_n + \frac{1}{2}f(t_n,y_n) + \frac{1}{2}f\left(t_n + h, y_n + \frac{1}{2}k_1 + \frac{1}{2}k_2\right)
台形公式は、選点法である。選点法はすべて陰的ルンゲ=クッタ法であるけど、陰的ルンゲ=クッタ法がすべて選点法であるわけではない。
選点法の中では、ガウス求積に基づいたガウス・ルジャンドル法が一番次数の高い方法である。s 段ガウス・ルジャンドル法の次数は 2s となる(よって、任意に高い次数を持つ方法を構造できるようになる)。例として、2段ガウス・ルジャンドル法は次の配列で与えられる。
\begin{array}{c|cc}
\frac12 - \frac16 \sqrt3 & \frac14                  & \frac14 - \frac16 \sqrt3 \\
\frac12 + \frac16 \sqrt3 & \frac14 + \frac16 \sqrt3 & \frac14 \\
\hline
& \frac12                  & \frac12 \\
\end{array}
== 安定性 ==
数値分析における安定性は、それぞれ異なる定義が複数存在する。ルンゲ=クッタ法の安定性を反映できる概念は、主に以下の二つである。
線型テスト方程式  y' = \lambda y  を考える。一つのルンゲ=クッタ法を使ってこの方程式に適用すると  y_{n+1} = r(h\lambda)y_n  となる。ここで、
r(z) = 1 + zb^T(I-zA)^{-1}e = \frac{\det (I-zA+zeb^T)}{\det(I-zA)}
は安定性関数と呼ばれる C 上の有理関数である(e はすべての成分が 1 のベクトルである)。s 段法の場合、行列式の展開によって r(z) は二つの s 次多項式の商となる。陽的方法の場合、対応するルンゲ=クッタ行列が狭義下三角行列であるため、\det(I-zA) = 1 がわかる。したがって、r(z) は s 次多項式となる。
ルンゲ=クッタ法による上記の方程式の数値解がゼロに減衰する条件が |r(z)| < 1 (z = h\lambda) である。上記の条件を満たす z の集合は方法に対する 絶対安定性領域 (region of absolute stability) である。 特に、絶対安定性領域が左複素数平面を含むとき、その方法は A-安定 (A-stable) という。陽的ルンゲ=クッタ法は、安定性関数が多項式であるため、A-安定な方法になれない。
もっと一般的に、方法の次数が p のときに、安定性関数に対し r(z) = e^z + O(z^{p+1}) が成立する。ゆえに、指数関数 ez の、与えられた次数の多項式の商からなる有理関数の中での最善近似が重要だと考えられる。そのような有理関数はパデ近似と呼ばれる。分子の次数が m で分母の次数が n のパデ近似式がA-安定性の条件 |r(z)| < 1,  \mathrm{Re}(z) \le 0 を満足するための必要十分条件は、m \le n \le m+2 である。
s 段ガウス・ルジャンドル法の次数は前述通り 2s である。よって安定性関数の分子と分母は同じく s 次多項式となる。すなわち、 m = n = s である。上記の条件が満たされるので、ガウス・ルジャンドル法はA-安定であることがわかる。故に任意に高い次数を持つ、A-安定なルンゲ=クッタ法が存在する。比べて、A-安定性を持つ線型多段法の次数は2以下である。
以上のことから、陰的ルンゲ=クッタ法は陽的方法より優れる安定性を持つこともわかる。
A-安定性という概念は線型自励方程式  y' = \lambda y  を考える結果である。 ダールキストは、数値的方法を使って、とある単調性条件を満たす非線型方程式系に適用するときの安定性を主張した。対応する安定性は、線型多段法の場合に G-安定性 (G-stability)で、ルンゲ=クッタ法の場合に B-安定性 (B-stability) と呼ぶ。 一般的なテスト方程式 y' = f(x,y) と単調性条件 \langle f(x,y) - f(x,z), y-z \rangle \le 0 を満足する f を考える。もしすべての h \ge 0 に対し、 不等式 \|y_{n+1} - z_{n+1}\| \le \|y_n - z_n\| が成立するとき、そのルンゲ=クッタ法は B-安定 という。 ここで、yn と zn はそれぞれの初期値に対する数値解である。 f(x,y) = \lambda y に方法を適用することで、B-安定性はA-安定性より強い条件であることがわかる。