常微分方程式の数値解法

同義語:ODEの数値解法numerical methods for ordinary differential equationsnumerical solution of ordinary differential equations

概要

常微分方程式の数値解法(numerical methods for ordinary differential equations)とは、初期値問題の解の近似値を刻み幅ごとに有限回の計算で求める方法の総称で、Euler 法、Runge–Kutta 法、線形多段法(Adams 法・BDF)などがある。線形多段法は、整合的かつ 0 安定であるとき、そのときに限り収束する(Dahlquist の同値定理)。与えられた刻み幅でのふるまいは安定領域で判定し、硬い方程式には陰的な方法を使う。力学系、化学反応、回路などの時間発展の計算に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 初期値問題, Euler法, Runge–Kutta法, 固有値

ロジスティック方程式 $x'=x(1-x)$ は解を式で書けるが、右辺が少し複雑になると解の式は期待できない。そこで、時刻 $t$ を刻み幅 $h$ ごとに進め、解の値を順に計算する。常微分方程式の数値解法(numerical methods for ordinary differential equations)は、このように初期値問題 $x'=f(t,x)$、$x(t_0)=x_0$ の解の近似値を、有限回の計算で求める方法の総称である。
方法は数多いが、選ぶときの問いは次の 3 つに集約される。

問い答えを決めるものこの記事の箱
$h\to0$ で真の解に近づくか整合性と 0 安定性(Dahlquist の同値定理)thm-ode-dahlquist
どの速さで近づくか次数 $p$(誤差 $\sim h^p$)prop-ode-order
与えられた $h$ で暴れないか安定領域、とくに A 安定性def-ode-abs、thm-ode-astable

1 歩の方法の基本は Euler法 と Runge–Kutta法 が扱う。この記事は入口として、前の数歩の値を使う 線形多段法 の一般論を証明し、硬い方程式 で陽的な方法が使えなくなる理由と、方法の選び方を述べる。

定義と使える条件

以下、$\lvert u\rvert$ は $\mathbb{R}^d$(または $\mathbb{C}^d$)のベクトルの長さである。使える条件は次のとおりとする。

  1. $f\colon[t_0,t_0+T]\times\mathbb{R}^d\to\mathbb{R}^d$ は連続である。
  2. $f$ は $x$ について大域的な Lipschitz 条件を定数 $L$ で満たす。
  3. 刻み幅は $h=T/N$($N$ は正の整数)で、$t_n:=t_0+nh$ とする。
    このとき解 $x$ は $[t_0,t_0+T]$ の上にただ 1 つあり、$C^1$ 級である(初期値問題 の定理「初期値問題の適切性」、大域的な存在は Picard–Lindelöfの定理)。
線形多段法と特性多項式

正の整数 $k$ と実数 $\alpha_0,\dots,\alpha_k$、$\beta_0,\dots,\beta_k$($\alpha_k=1$、$\lvert\alpha_0\rvert+\lvert\beta_0\rvert>0$)を与える。出発値 $x_0,\dots,x_{k-1}$ から
$$ \sum_{j=0}^k\alpha_jx_{n+j}=h\sum_{j=0}^k\beta_jf(t_{n+j},x_{n+j})\qquad(0\le n\le N-k) $$
で $x_k,\dots,x_N$ を順に定める方法を $k$ 段の線形多段法 という。$\beta_k=0$ なら 陽的、$\beta_k\ne0$ なら 陰的 である。多項式
$$ \rho(\zeta):=\sum_{j=0}^k\alpha_j\zeta^j,\qquad\sigma(\zeta):=\sum_{j=0}^k\beta_j\zeta^j $$
を 第 1・第 2 特性多項式 という。

陰的な方法でも $hL\lvert\beta_k\rvert< 1$ なら、$x_{n+k}$ は縮小写像の不動点としてただ 1 つに定まる。$k=1$ の方法は 1 段法である。$k\ge2$ では出発値を別の方法で作る必要がある。

整合性と次数

$q=0,1,2,\dots$ に対して $C_q:=\sum_jj^q\alpha_j-q\sum_jj^{q-1}\beta_j$ とおく($0^0=1$、$q=0$ の第 2 項は $0$)。$C_0=\cdots=C_p=0$ となる最大の $p$ を方法の 次数 といい、次数が $1$ 以上のとき方法は 整合的 であるという。整合的であることは $\rho(1)=0$ かつ $\rho'(1)=\sigma(1)$ と同値である。

根の条件と0安定性

多項式 $\pi$ の根がすべて $\lvert\zeta\rvert\le1$ にあり、$\lvert\zeta\rvert=1$ の根がすべて単根であるとき、$\pi$ は 根の条件 を満たすという。$\rho$ が根の条件を満たす方法を 0 安定 という。

名前の「0」は、$h=0$ とおいた差分方程式 $\sum_j\alpha_jx_{n+j}=0$ の解が有界であることを表す。

収束

線形多段法が 収束する とは、すべての $d$、上の条件を満たすすべての $f$ と解 $x$、$\max_{j< k}\lvert x_j-x(t_j)\rvert\to0$($h\to0$)となるすべての出発値について、$\max_{0\le n\le N}\lvert x_n-x(t_n)\rvert\to0$($h\to0$)となることをいう。

$h\to0$ の性質とは別に、与えられた $h$ でのふるまいを、減衰する方程式で測る。$\lambda$ を複素数として $x'=\lambda x$ に方法を使う($\mathbb{C}$ 値の方程式にも同じ式で定める)。$\mu:=h\lambda$ とおくと、線形多段法は $\sum_j(\alpha_j-\mu\beta_j)x_{n+j}=0$ になる。

安定領域とA安定性

線形多段法の 安定領域 $S$ とは、$\mu\beta_k\ne1$ で、$\pi_\mu(\zeta):=\rho(\zeta)-\mu\sigma(\zeta)$ が根の条件を満たす複素数 $\mu$ の全体である。$x_{n+1}=R(h\lambda)x_n$ の形になる 1 段法(Runge–Kutta 法など)では $S:=\{\mu\mid\lvert R(\mu)\rvert\le1\}$ とする。$S$ が開左半平面 $\{\operatorname{Re}\mu< 0\}$ を含むとき、方法は A 安定 であるという。1 段法で A 安定かつ $\lim_{\lvert\mu\rvert\to\infty}R(\mu)=0$ のとき、L 安定 であるという。

$\mu\in S$ なら近似値は有界で、$\pi_\mu$ の根がすべて $\lvert\zeta\rvert< 1$ なら $x_n\to0$ である(lem-ode-power)。$x'=Ax$ で $A$ が対角化できるなら、すべての固有値 $\lambda_i$ で $h\lambda_i$ が $S$ に入るかを調べる。

硬い方程式

解の主な部分はゆっくり変化するのに、速く減衰する成分(絶対値の大きい負の固有値)をもつため、刻み幅が精度ではなく安定性で決まってしまう方程式を 硬い(stiff)方程式という。数学的に 1 つに決まった定義はなく、方法と精度の要求に対する相対的な性質である。線形の系では固有値の実部の比 $\max\lvert\operatorname{Re}\lambda_i\rvert/\min\lvert\operatorname{Re}\lambda_i\rvert$ が目安になる。非線形の方程式では、解の近くの Jacobi 行列 $\partial f/\partial x$ の固有値で判断する。

公式の表

$f_j:=f(t_j,x_j)$ と書く。「実軸の安定区間」は $S\cap(-\infty,0]$ である。

方法式次数実軸の安定区間A 安定根拠
Euler 法$x_{n+1}=x_n+hf_n$1$[-2,0]$否Euler法
後退 Euler 法$x_{n+1}=x_n+hf_{n+1}$1$(-\infty,0]$L 安定Euler法
台形則$x_{n+1}=x_n+\frac h2(f_{n+1}+f_n)$2$(-\infty,0]$可thm-ode-astable
Heun 法Runge–Kutta法 の例の表2$[-2,0]$否計算
古典的 Runge–Kutta 法Runge–Kutta法 の例の表4$[-2.785,0]$否Runge–Kutta法
Adams–Bashforth 2 次$x_{n+2}=x_{n+1}+\frac h2(3f_{n+1}-f_n)$2$[-1,0]$否計算
Adams–Bashforth 3 次$x_{n+3}=x_{n+2}+\frac h{12}(23f_{n+2}-16f_{n+1}+5f_n)$3$[-\frac6{11},0]$否計算
Adams–Moulton 3 次$x_{n+2}=x_{n+1}+\frac h{12}(5f_{n+2}+8f_{n+1}-f_n)$3$[-6,0]$否計算
BDF2$x_{n+2}-\frac43x_{n+1}+\frac13x_n=\frac23hf_{n+2}$2$(-\infty,0]$可thm-ode-astable
BDF3$x_{n+3}-\frac{18}{11}x_{n+2}+\frac9{11}x_{n+1}-\frac2{11}x_n=\frac6{11}hf_{n+3}$3$(-\infty,0]$否計算
中点則(leapfrog)$x_{n+2}=x_n+2hf_{n+1}$2$\{0\}$否ex-ode-leapfrog
Simpson 則$x_{n+2}=x_n+\frac h3(f_{n+2}+4f_{n+1}+f_n)$4$\{0\}$否計算

表の線形多段法はすべて 0 安定である。線形多段法の A 安定の欄の「否」は thm-ode-astable から従い、陽的な Runge–Kutta 法の「否」は Runge–Kutta法 の命題「陽的な方法の安定性関数」から従う。

方法の作り方を開く

Adams 法。$x(t_{n+k})-x(t_{n+k-1})=\int_{t_{n+k-1}}^{t_{n+k}}f(s,x(s))\,ds$ の被積分関数を、既知の点 $f_n,\dots,f_{n+k-1}$ の補間多項式で置き換えると陽的な Adams–Bashforth 法、$f_{n+k}$ も含めると陰的な Adams–Moulton 法になる。$\rho(\zeta)=\zeta^k-\zeta^{k-1}$ なので根は $1$ と $0$ だけで、どの段数でも 0 安定である。

BDF(後退差分公式)。$x_n,\dots,x_{n+k}$ を通る補間多項式の $t_{n+k}$ での微分を $f_{n+k}$ に等しいとおく。$\nabla x_m:=x_m-x_{m-1}$ として $\sum_{j=1}^k\frac1j\nabla^jx_{n+k}=hf_{n+k}$ である(これを $\alpha_k=1$ に正規化したものが表の式)。$\rho$ の根を計算すると $k=1,\dots,6$ で根の条件を満たし、$k=7$ では絶対値 $1.0222$ の根が現れて 0 安定でなくなる。

主定理と証明

次数の判定

次数の 3 つの言い換え

線形多段法と整数 $p\ge0$ について、次は同値である。
(R1) $C_0=\cdots=C_p=0$。
(R2) $z\to0$ で $\rho(e^z)-z\sigma(e^z)=O(z^{p+1})$。
(R3) ある定数 $K$ があって、$C^{p+1}$ 級のすべての関数 $y$ について
$$ \Bigl\lvert\sum_j\alpha_jy(t+jh)-h\sum_j\beta_jy'(t+jh)\Bigr\rvert\le Kh^{p+1}\max_{[t,t+kh]}\lvert y^{(p+1)}\rvert . $$

Taylor 展開で係数を比べる

(i)⇔(ii):$e^{jz}$ を展開して $z^q$ の係数を集めると
$$ \rho(e^z)-z\sigma(e^z)=\sum_j\alpha_j\sum_{q\ge0}\frac{(jz)^q}{q!}-\sum_j\beta_j\sum_{q\ge1}\frac{j^{q-1}z^q}{(q-1)!}=\sum_{q\ge0}\frac{C_q}{q!}z^q $$
である。
(i)⇒(iii):$y(t+jh)$ を $p$ 次まで、$y'(t+jh)$ を $p-1$ 次まで積分形の剰余つきで Taylor 展開する($p=0$ なら第 2 の展開は $y'(t+jh)$ のままとし、$\lvert y'\rvert$ の最大値で評価する)。$h^q y^{(q)}(t)/q!$ の係数はちょうど $C_q$ で、$0$ になる。剰余は $\frac{(jh)^{p+1}}{(p+1)!}\max\lvert y^{(p+1)}\rvert$ と $h\cdot\frac{(jh)^p}{p!}\max\lvert y^{(p+1)}\rvert$ で押さえられるので、$K:=\sum_j\bigl(\lvert\alpha_j\rvert\frac{j^{p+1}}{(p+1)!}+\lvert\beta_j\rvert\frac{j^p}{p!}\bigr)$ でよい。
(iii)⇒(i):$y(s)=s^q$($q\le p$)は $y^{(p+1)}=0$ なので、$t=0$、$h=1$ として左辺の $C_q$ が $0$ になる。$\square$

Dahlquist の同値定理

根の条件は、差分方程式の解の有界性と同じことである。

根の条件とべき乗の有界性

$\pi(\zeta)=\zeta^k+a_{k-1}\zeta^{k-1}+\cdots+a_0$ の同伴行列を
$$ C:=\begin{pmatrix}-a_{k-1}&-a_{k-2}&\cdots&-a_0\\1&0&\cdots&0\\&\ddots&\ddots&\vdots\\&&1&0\end{pmatrix} $$
とする。$\pi$ が根の条件を満たすことと、$\Gamma:=\sup_{m\ge0}\|C^m\|_\infty< \infty$ は同値である($\|\cdot\|_\infty$ は行の絶対値の和の最大値)。根がすべて $\lvert\zeta\rvert< 1$ なら $C^m\to0$ である。

Jordan 標準形で見る

$C$ の固有多項式は $\pi$ で、固有値 $\zeta$ の固有ベクトルは $(\zeta^{k-1},\dots,\zeta,1)^\top$ の定数倍に限る。よって各固有値の Jordan ブロックは 1 つで、サイズは根の重複度 $m$ に等しい。サイズ $m$ のブロックの $n$ 乗の成分は $\binom n{i}\zeta^{n-i}$($0\le i< m$)である。$\lvert\zeta\rvert< 1$ なら $0$ に収束し、$\lvert\zeta\rvert=1$ かつ $m=1$ なら絶対値 $1$ であり、$\lvert\zeta\rvert>1$ または($\lvert\zeta\rvert=1$ かつ $m\ge2$)なら非有界である。$\square$

Dahlquistの同値定理

線形多段法について、収束することと、整合的かつ 0 安定であることは同値である。
さらに、方法が 0 安定で次数 $p\ge1$ をもち、解 $x$ が $C^{p+1}$ 級なら、$h$ によらない定数 $C$ があって、十分小さい $h$ について
$$ \max_{0\le n\le N}\lvert x_n-x(t_n)\rvert\le C\Bigl(\max_{j< k}\lvert x_j-x(t_j)\rvert+h^p\Bigr) $$
である。

誤差の差分方程式を同伴行列で解く

十分性. $e_n:=x(t_n)-x_n$ とし、真の解の残り $d_n:=\sum_j\alpha_jx(t_{n+j})-h\sum_j\beta_jx'(t_{n+j})$ を評価する。$\omega(\delta):=\max\{\lvert x'(s)-x'(t)\rvert\mid\lvert s-t\rvert\le\delta\}$ は $\delta\to0$ で $0$ に近づき、$\lvert x(t+jh)-x(t)-jhx'(t)\rvert\le jh\,\omega(jh)$、$\lvert x'(t+jh)-x'(t)\rvert\le\omega(jh)$ である。整合性 $\rho(1)=0$、$\rho'(1)=\sigma(1)$ から $x(t_n)$ と $hx'(t_n)$ の係数が消え、$h$ によらない定数 $c$ で
$$ \lvert d_n\rvert\le ch\,\omega(kh) $$
となる。$C^{p+1}$ 級なら prop-ode-order の (iii) から $\lvert d_n\rvert\le ch^{p+1}$ である($c$ は $x$ によって変わる)。したがって $D:=\sum_n\lvert d_n\rvert$ は、$h\to0$ で $0$ に近づくか、$cTh^p$ 以下である。
真の解の式と方法の式を引くと、
$$ \sum_{j=0}^k\alpha_je_{n+j}=g_n,\qquad g_n:=h\sum_j\beta_j\bigl(f(t_{n+j},x(t_{n+j}))-f(t_{n+j},x_{n+j})\bigr)+d_n $$
である。$E_n:=(e_{n+k-1},\dots,e_n)$、$G_n:=(g_n,0,\dots,0)$ とおくと、$\rho$ の同伴行列 $C$ の各成分を $\mathbb{R}^d$ のスカラー倍として作用させて $E_{n+1}=CE_n+G_n$ であり、
$$ E_n=C^nE_0+\sum_{m=0}^{n-1}C^{n-1-m}G_m $$
である。$a_n:=\max_{0\le i\le n+k-1}\lvert e_i\rvert$、$b:=\sum_j\lvert\beta_j\rvert$ とおくと、Lipschitz 条件から $\lvert g_m\rvert\le hLb\,a_{m+1}+\lvert d_m\rvert$ である。lem-ode-power の $\Gamma$($\ge1$)を使い、$K:=\Gamma Lb$ とすると
$$ a_n\le\Gamma(a_0+D)+hK\sum_{m=1}^na_m $$
を得る($E_n$ の成分の最大値は右辺以下で、右辺は $n$ について増加し、$a_n$ はそれまでの最大値である)。$hK\le\frac12$ のとき、$a_n$ の項を左辺に移して
$$ a_n\le A+2hK\sum_{m=0}^{n-1}a_m,\qquad A:=2\Gamma(a_0+D) $$
となる。右辺を $S_n$ とおくと $S_{n+1}=S_n+2hKa_n\le(1+2hK)S_n$、$S_0=A$ なので、$a_n\le S_n\le Ae^{2Knh}\le Ae^{2KT}$ である。これが両方の主張を与える。
必要性. 方法が収束するとする。$T=1$、$t_0=0$ としてよい。まず 0 安定性を示す。$f\equiv0$、$x\equiv0$ とする。$\rho$ の根 $\zeta$ で $\lvert\zeta\rvert>1$ のものがあれば、$\mathbb{R}^2$ 値の列 $x_n:=h(\operatorname{Re}\zeta^n,\operatorname{Im}\zeta^n)$ は差分方程式を満たし、出発値は $0$ に近づくが、$\lvert x_N\rvert=h\lvert\zeta\rvert^{1/h}\to\infty$ である。$\lvert\zeta\rvert=1$ の重根があれば、$\sum_j\alpha_j(n+j)\zeta^{n+j}=\zeta^n(n\rho(\zeta)+\zeta\rho'(\zeta))=0$ なので、$x_n:=\sqrt h\,n(\operatorname{Re}\zeta^n,\operatorname{Im}\zeta^n)$ が差分方程式を満たし、出発値は $0$ に近づくが、$\lvert x_N\rvert=1/\sqrt h\to\infty$ である。どちらも収束に反する。
次に整合性を示す。$f\equiv0$、$x\equiv1$、出発値を $1$ とすると、収束から $x_n\to1$(一様)なので、$0=\sum_j\alpha_jx_{N-k+j}\to\rho(1)$ である。$\rho(1)=0$ で、0 安定性から $\rho'(1)\ne0$ である。$f\equiv1$、$x(t)=t$ とし、$\mu:=\sigma(1)/\rho'(1)$ とおくと、$x_n:=nh\mu$ は $\sum_j\alpha_j(n+j)h\mu=h\mu(n\rho(1)+\rho'(1))=h\sigma(1)$ を満たす方法の解で、出発値は $0$ に近づく。$x_N=\mu\to1$ より $\mu=1$、すなわち $\rho'(1)=\sigma(1)$ である。$\square$

この定理は「整合性(1 歩のずれが小さい)+安定性(ずれが増幅されない)=収束」の形をしている。同じ形が偏微分方程式の差分法にも現れる(差分法 の命題「安定性と整合性から収束が従う」)。
次数をいくらでも上げられるわけではない。$k$ 段の線形多段法の係数は $2k+1$ 個あるので次数 $2k$ まで作れるが、0 安定性がこれを止める。

Dahlquistの第1障壁

0 安定な $k$ 段の線形多段法の次数は $k+2$ 以下であり、$k$ が奇数なら $k+1$ 以下である。

証明の所在

この記事では証明しない。証明は 線形多段法 の定理「Dahlquist の第 1 障壁」にあり、そこでは陽的な方法の次数が $k$ 以下であることも示している。原典は Dah56 Theorem 4a(p. 51)である。同じ論文の Theorem 1(p. 43)は、摂動を含めた収束と安定性の同値を、解が $C^{p+1}$ 級の方程式の族について述べたものである。Simpson 則($k=2$、$p=4$)は上界に達する。

安定性と次数の上限

A安定な線形多段法の次数(Dahlquistの第2障壁)

整合的で 0 安定な線形多段法について、次が成り立つ。
(R1) 陽的な方法は A 安定でない。
(R2) A 安定な方法の次数は 2 以下である。
(R3) 台形則と BDF2 は A 安定である。

右半平面で実部が負にならない有理関数を調べる

要点:$R:=\rho/\sigma$ とする。$\pi_\mu(\zeta)=0$ は $\mu=R(\zeta)$ のことなので、A 安定なら $\lvert\zeta\rvert>1$ で $\operatorname{Re}R\ge0$ である。一方、次数 $p$ なら $\zeta=1$ の近くで $R(\zeta)=\log\zeta+O((\zeta-1)^{p+1})$ である。$\lvert\zeta\rvert>1$ を右半平面に写すと、(i) は $\zeta=\infty$ の極から、(ii) は $\log$ の展開の係数の符号から矛盾が出る。

詳しい証明を開く

準備。0 安定性から $\rho$ の根は $\lvert\zeta\rvert\le1$ にあり、$\rho'(1)\ne0$ なので $\sigma(1)=\rho'(1)\ne0$ である。A 安定とし、$\lvert\zeta_0\rvert>1$ で $\sigma(\zeta_0)\ne0$ とする。$\operatorname{Re}R(\zeta_0)< 0$ なら、$\mu=R(\zeta_0)$ について $\zeta_0$ は $\pi_\mu$ の絶対値 $1$ より大きい根である。$\mu\beta_k=1$ のときも含めて、これは $\mu\in S$ に反する。よって $\sigma\ne0$ の点で $\operatorname{Re}R\ge0$ である。$\sigma(\zeta_0)=0$($\lvert\zeta_0\rvert>1$)なら $\rho(\zeta_0)\ne0$ で $R$ は $\zeta_0$ に極をもち、その近くで実部が負の値をとるので矛盾する。同じことが $\zeta=\infty$ でも言える:$\beta_k=0$ なら $\deg\sigma< k=\deg\rho$ なので $R$ は $\infty$ に極をもち、十分大きい $\lvert\zeta\rvert$ で実部が負の値をとる。これが (i) である。

(ii)。$p\ge3$ と仮定する。$\zeta=(1+w)/(1-w)$ で $\lvert\zeta\rvert>1$ は $\operatorname{Re}w>0$ に写り、$q(w):=R\bigl(\frac{1+w}{1-w}\bigr)$ は有理関数である。(i) から $\beta_k\ne0$ なので $R$ は $\zeta=\infty$($w=1$)でも有限で、$q$ は $\operatorname{Re}w>0$ で正則、$\operatorname{Re}q\ge0$ である。prop-ode-order の (ii) で $z=\log\zeta$ とおき $\sigma(1)\ne0$ で割ると、$w=0$ の近くで $R(\zeta)=\log\zeta+O(w^{p+1})$ であり、$\log\zeta=2\operatorname{artanh}w$ なので $q(w)=2w+\frac23w^3+O(w^4)$ である。$q$ は定数でないので、開写像定理から $\operatorname{Re}w>0$ で $\operatorname{Re}q>0$ であり、$F:=1/q$ も $\operatorname{Re}w>0$ で正則で $\operatorname{Re}F>0$ である。展開から $F(w)=\frac1{2w}\bigl(1-\frac{w^2}3+O(w^3)\bigr)=\frac1{2w}-\frac w6+O(w^2)$ である。

$F$ の虚軸上の点 $w_0$ の極は 1 位で、留数は正である。実際、位数 $m$、主要項 $c(w-w_0)^{-m}$ とし $w-w_0=\varepsilon e^{i\theta}$($\lvert\theta\rvert< \pi/2$)と動かすと、$\operatorname{Re}F\ge0$ からすべての $\theta$ で $\cos(\arg c-m\theta)\ge0$ でなければならず、$m=1$、$c>0$ に限る。同様に $\infty$ の極も 1 位で、主要項は $aw$($a>0$)である。$\infty$ に極がないときは $a=0$ とする。部分分数に分けると $F(w)=aw+\sum_l\frac{c_l}{w-iy_l}+H(w)$($a\ge0$、$c_l>0$)で、$H$ は $\operatorname{Re}w\ge0$ と $\infty$ で正則な有理関数である。虚軸の上では $aw$ と $c_l/(w-iy_l)$ の実部は $0$ なので、$\operatorname{Re}H=\operatorname{Re}F\ge0$(極の点と $\infty$ では連続性による)である。調和関数 $\operatorname{Re}H$ に最小値の原理を使うと、$\operatorname{Re}w>0$ で $\operatorname{Re}H\ge0$ である。また $\operatorname{Re}w>0$ で $\operatorname{Re}(aw)\ge0$、$\operatorname{Re}\frac{c_l}{w-iy_l}>0$ である。$w_0=0$ の項は $\frac1{2w}$ なので、これを除いた $F(w)-\frac1{2w}$ の実部は $\operatorname{Re}w>0$ で $0$ 以上である。ところが展開から、小さい実数 $w>0$ で $F(w)-\frac1{2w}=-\frac w6+O(w^2)< 0$ となり、矛盾する。

(iii)。台形則の $\pi_\mu$ の根は $\zeta=\frac{1+\mu/2}{1-\mu/2}$ で、$\operatorname{Re}\mu< 0$ なら $\lvert1+\mu/2\rvert< \lvert1-\mu/2\rvert$ である。BDF2 は $\sigma(\zeta)=\frac23\zeta^2$ なので、$u:=1/\zeta$ として $R=P(u):=\frac32-2u+\frac12u^2$ である。$u=e^{i\theta}$ で $\operatorname{Re}P=\frac32-2\cos\theta+\frac12\cos2\theta=(1-\cos\theta)^2\ge0$ なので、最小値の原理から $\lvert u\rvert\le1$ で $\operatorname{Re}P\ge0$ である。よって $\operatorname{Re}\mu< 0$ の $\pi_\mu$ は $\lvert\zeta\rvert\ge1$ に根をもたず、根はすべて $\lvert\zeta\rvert< 1$ である。$\square$

thm-ode-astable の (ii) により、線形多段法で硬い方程式を A 安定に解こうとすると次数 2 が上限になる。この壁は線形多段法の壁であり、陰的な Runge–Kutta 法には当てはまらない(rem-ode-gauss)。

硬い方程式と陰的な方法

陽的な方法の安定領域は有界で(Runge–Kutta 法は Runge–Kutta法 の命題「陽的な方法の安定性関数」)、$h\lvert\lambda\rvert$ が定数以下という制限が付く。固有値 $-1000$ の成分は解にほとんど寄与しなくても、$h$ を $10^{-3}$ 程度に強いる。陰的な方法は 1 歩の手間は大きいが、$h$ を精度だけで決められる。
ただし A 安定だけでは足りないことがある。速い成分を $\mu\to-\infty$ の極限でどう扱うかが、方法によって違う。

大きな負の $\mu$ での増幅率

$\mu$ を負の実数とする。
(R1) 後退 Euler 法の増幅率は $R(\mu)=\frac1{1-\mu}$ で、$\mu\to-\infty$ で $0$ に近づく。
(R2) 台形則の増幅率は $R(\mu)=\frac{1+\mu/2}{1-\mu/2}$ で、$\mu\to-\infty$ で $-1$ に近づく。
(R3) $k$ 段の BDF では、$\sigma(\zeta)=\beta_k\zeta^k$ なので、$\mu\to-\infty$ で $\pi_\mu$ の根はすべて $0$ に近づく。

(i)(ii) は $x'=\lambda x$ に代入して解いた式から明らかである。(iii):$\pi_\mu(\zeta)/(-\mu)=\beta_k\zeta^k-\rho(\zeta)/\mu$ の係数は $\mu\to-\infty$ で $\beta_k\zeta^k$ の係数に近づき、根は係数に連続に依存する。$\square$

したがって台形則では、大きな $h\lvert\lambda\rvert$ の成分はほとんど減らず、符号を変えながら残る(ex-ode-stiff)。BDF と後退 Euler 法は速い成分を 1 歩で消す。
1 歩の方程式の解き方. 陰的な方法では、各歩で $G(u):=u-h\beta_kf(t_{n+k},u)-b=0$($b$ は既知の値)を解く。不動点反復 $u\mapsto h\beta_kf(t_{n+k},u)+b$ は $h\lvert\beta_k\rvert L< 1$ のときしか保証がなく(非線形方程式の数値解法 の定理「不動点反復の収束」)、硬い方程式では $L$ が大きいのでこの条件が陽的な方法の制限と同じ大きさになる。そこで Newton 法 $(I-h\beta_kJ)\Delta=-G(u)$($J:=\partial f/\partial x$)を使う。初期値には前の歩の値か陽的な方法の予測値を使う。系が大きいときの連立方程式は Krylov部分空間法 で解く。

長時間の計算と保存量

減衰のない振動では、安定領域の虚軸の部分が問題になる。

調和振動子のエネルギー

$y=(x,x')$、$y'=Ay$、$A=\begin{pmatrix}0&1\\-1&0\end{pmatrix}$ を刻み幅 $h$ で解き、$E_n:=\lvert y_n\rvert^2$ とおく。
(R1) Euler 法:$E_{n+1}=(1+h^2)E_n$。
(R2) 古典的 Runge–Kutta 法:$E_{n+1}=\bigl(1-\frac{h^6}{72}+\frac{h^8}{576}\bigr)E_n$。
(R3) 台形則:$E_{n+1}=E_n$。

$A$ は固有値 $\pm i$ の正規行列で、ユニタリ行列で対角化できるので、$y_{n+1}=R(hA)y_n$ のとき $E_{n+1}=\lvert R(ih)\rvert^2E_n$ である($R$ は実係数なので $\lvert R(ih)\rvert=\lvert R(-ih)\rvert$)。$R$ はそれぞれ $1+z$、$\sum_{j\le4}z^j/j!$、$\frac{1+z/2}{1-z/2}$ である。(ii) は $\lvert R(iy)\rvert^2=\bigl(1-\frac{y^2}2+\frac{y^4}{24}\bigr)^2+\bigl(y-\frac{y^3}6\bigr)^2$ の展開である。(iii) は分母と分子が共役であることによる。$\square$

prop-ode-energy の (ii) から、古典的 Runge–Kutta 法の虚軸の安定区間は $\lvert y\rvert\le2\sqrt2$ である。各種の方法でのエネルギーの比較の数値は LL17 §1.6.2(pp. 39–40)に、振動の方程式に向く Euler–Cromer 法は同書 §1.7 にある。

刻み幅の制御

実用の計算では $h$ を固定せず、1 歩の誤差の推定値が許容誤差 $\varepsilon$ 以下になるように変える。推定には 2 通りの近似値の差を使う。

刻みを 2 分割した誤差の推定

次数 $p$ の陽的 Runge–Kutta 法で、$f$ が $C^\infty$ 級とする。点 $(t,u)$ から刻み $h$ で 1 歩進んだ値を $\hat x$、刻み $h/2$ で 2 歩進んだ値を $\tilde x$、同じ点から出発する解を $x$ とすると、
$$ x(t+h)-\tilde x=\frac{\tilde x-\hat x}{2^p-1}+O(h^{p+2})\qquad(h\to0) $$
である。

局所誤差の主要項を消す

局所打ち切り誤差は $h$ の滑らかな関数なので(Runge–Kutta法 の定義「局所打ち切り誤差と次数」のあとの注意)、$h^{p+1}$ の係数を $c(t,u)$ として $x(t+h)-\hat x=c(t,u)h^{p+1}+O(h^{p+2})$ である。前半の $h/2$ 歩の誤差は $c(t,u)(h/2)^{p+1}+O(h^{p+2})$ で、後半の 1 歩はこの誤差を $1+O(h)$ 倍して運び、新しく $c(t+\frac h2,\cdot)(h/2)^{p+1}+O(h^{p+2})$ を加える。$c$ は滑らかなので
$$ x(t+h)-\tilde x=2c(t,u)(h/2)^{p+1}+O(h^{p+2})=2^{-p}c(t,u)h^{p+1}+O(h^{p+2}) $$
である。2 式を引くと $\tilde x-\hat x=(1-2^{-p})c(t,u)h^{p+1}+O(h^{p+2})$ であり、これを $2^p-1$ で割ったものが上の式の主要項に一致する。$\square$

もう 1 つの方法は、段の評価を共有する次数 $p$ と $p+1$ の組(埋め込み Runge–Kutta 法)である。最も簡単な組は Euler 法と Heun 法で、$k_1=f(t,x)$、$k_2=f(t+h,x+hk_1)$ から
$$ \text{誤差の推定値}=\Bigl\lvert\frac h2(k_2-k_1)\Bigr\rvert $$
を得る。1 歩の誤差が $h^{p+1}$ に比例するので、推定値 $e$ が得られたら、次の刻みを
$$ h_{\text{new}}:=h\cdot\min\Bigl\{2,\ \max\bigl\{0.2,\ 0.9(\varepsilon/e)^{1/(p+1)}\bigr\}\Bigr\} $$
とする($0.9$・$0.2$・$2$ は過度の増減を避ける経験的な値である)。$e>\varepsilon$ の歩はやり直す。

計算の手順

  1. 標準形にする:高階の方程式を 1 階の系 $y'=F(t,y)$ に直す(常微分方程式 の命題「高階の方程式と 1 階の連立方程式」)。
  2. 硬さを調べる:Jacobi 行列の固有値の大きさと、解く時間の長さの積を見る。$T\max\lvert\lambda_i\rvert$ が大きいのに解が滑らかなら硬い。分からなければ、陽的な方法で許容誤差を緩めても刻みが極端に小さくなるかを見る。
  3. 方法を下の表から選ぶ。
  4. 出発値を作る(多段法):次数 $p$ の方法には誤差 $O(h^p)$ の出発値を与える(thm-ode-dahlquist)。Runge–Kutta 法で作るか、段数の低い方法から立ち上げる。
  5. 進める:刻み幅を制御し、陰的な方法では各歩で Newton 法を使う。不連続点(入力の切り替えなど)では刻みの端をその時刻に合わせる。
  6. 止める判定と失敗の検出:刻みが丸め誤差の水準($\lvert t\rvert$ の $10^{-15}$ 倍程度)まで小さくなったら止めて報告する。解の爆発か、不連続か、硬さの見落としが疑われる。反復と刻みの回数に上限を置く。
  7. 確かめる:許容誤差を 10 分の 1 にして結果の変化を見る。変化が許容誤差と同程度なら受け入れる。
    問題の性質方法の例理由と注意
    滑らかで硬くない古典的 Runge–Kutta 法、埋め込み Runge–Kutta 法自己出発で刻みを変えやすい。1 歩に 4 回以上の $f$ の評価
    $f$ の評価が高価、高い精度が要るAdams 法の予測子修正子1 歩の $f$ の評価が少ない。刻みの変更に手間
    硬いBDF(次数 2 までが A 安定)、後退 Euler 法速い成分を消す。Jacobi 行列と連立方程式が要る
    硬く、高い次数が要る陰的 Runge–Kutta 法(rem-ode-gauss)1 歩の連立方程式が大きい
    エネルギーが保たれる振動、長時間台形則、Euler–Cromer 法エネルギーの増減を抑える(prop-ode-energy)。位相の誤差は残る
    $f$ が不連続不連続点で区間を分けて上のどれか次数が落ちるのを防ぐ(ex-ode-counterexamples)
    境界条件を 2 点で与える問題この記事の対象外:差分法、有限要素法初期値問題に直すと不安定になることがある
    刻み幅と方法の選択で考えるべき要素(計算時間、丸め誤差、安定性)は LebDQ26 §1.7(p. 60)にも述べられている。

例題

次数と $f$ の評価回数:$x'=x(1-x)$、$x(0)=0.1$

使う公式:thm-ode-dahlquist(次数)。AB2 の出発値 $x_1$ は Heun 法で作る。
答え:解は $x(t)=\frac1{1+9e^{-t}}$、$x(5)\approx0.942826$ である。$t=5$ の誤差は次のとおり。

$h$Euler 法Heun 法AB2古典的 Runge–Kutta 法
$0.2$$2.96\times10^{-3}$$9.23\times10^{-4}$$7.39\times10^{-5}$$1.19\times10^{-6}$
$0.1$$1.43\times10^{-3}$$2.26\times10^{-4}$$1.56\times10^{-5}$$7.27\times10^{-8}$
$0.05$$7.02\times10^{-4}$$5.59\times10^{-5}$$3.55\times10^{-6}$$4.50\times10^{-9}$
$0.025$$3.48\times10^{-4}$$1.39\times10^{-5}$$8.43\times10^{-7}$$2.80\times10^{-10}$

$h$ を半分にすると誤差はそれぞれおよそ $1/2$、$1/4$、$1/4$、$1/16$ になる。$f$ の評価が約 $100$ 回の組で比べると、Euler 法($h=0.05$)$7.0\times10^{-4}$、Heun 法($h=0.1$)$2.3\times10^{-4}$、AB2($h=0.05$)$3.5\times10^{-6}$、古典的 Runge–Kutta 法($h=0.2$)$1.2\times10^{-6}$ である。

硬い方程式:$x'=-1000(x-\cos t)-\sin t$、$x(0)=2$

使う公式:def-ode-abs、prop-ode-limit。BDF2 の 1 歩目は後退 Euler 法とする。
答え:解は $x(t)=\cos t+e^{-1000t}$、$x(1)\approx0.540302$ である。$t=0.01$ を過ぎると第 2 項は事実上消える。$t=1$ の値の誤差(RK4 は古典的 Runge–Kutta 法)は次のとおり。

$h$$h\lambda$RK4後退 Euler 法台形則BDF2
$0.1$$-100$$1.1\times10^{66}$$2.8\times10^{-5}$$6.7\times10^{-1}$$2.7\times10^{-6}$
$0.01$$-10$$2.5\times10^{246}$$2.7\times10^{-6}$$7.0\times10^{-9}$$2.8\times10^{-8}$
$0.002$$-2$$2.7\times10^{-7}$$5.4\times10^{-7}$$2.8\times10^{-10}$$1.1\times10^{-9}$

RK4 は $h\le2.785\times10^{-3}$ でないと発散する。$h=0.1$ の台形則では、速い成分が毎歩 $\frac{1-50}{1+50}\approx-0.9608$ 倍にしかならず、$10$ 歩後にも $(-0.9608)^{10}\approx0.670$ が残る。これが表の誤差 $0.67$ である。同じ $h$ の後退 Euler 法の増幅率は $1/101$ で、BDF2 も初期の過渡を速やかに消す。$h$ が小さく速い成分が解けている範囲では、台形則の次数 2 の精度が効いて後退 Euler 法より良い。

0 安定でも暴れる方法:中点則と $x'=-x$

使う公式:def-ode-abs。
答え:$\pi_\mu(\zeta)=\zeta^2-2\mu\zeta-1$ の根は $\zeta=\mu\pm\sqrt{\mu^2+1}$ で、積は $-1$ である。実数 $\mu\ne0$ では 2 根が実数で絶対値が異なるので、一方は絶対値が $1$ より大きい。したがって $S\cap\mathbb{R}=\{0\}$ である($\mu=iy$、$\lvert y\rvert< 1$ では 2 根とも絶対値 $1$ の異なる根である)。$x'=-x$、$h=0.1$、$x_0=1$、$x_1=e^{-0.1}$ で計算すると

$t$$5$$10$$15$$20$
近似値$0.01779$$1.618$$238.2$$35058.7$
真の値$0.00674$$4.54\times10^{-5}$$3.06\times10^{-7}$$2.06\times10^{-9}$

である。根 $\zeta\approx-1.10499$ の成分が $t$ の単位あたり約 $e$ 倍で増え、符号を変えながら育つ。$h=0.05$ でも $x(20)$ の近似値は $4756.2$ である。整合的で 0 安定なので $h\to0$ で各時刻の値は収束するが、固定した $h$ では減衰する方程式に使えない。Simpson 則でも、$\mu< 0$ では $\pi_\mu(-1)=\frac23\mu< 0$ から $-1$ より小さい根があり、同じ現象が起こる。

調和振動子の長時間計算

使う公式:prop-ode-energy。
答え:$x''=-x$、$x(0)=1$、$x'(0)=0$ を $h=0.1$ で $t=100$ まで($1000$ 歩)解くと、$E_{1000}$ は Euler 法で $1.01^{1000}\approx20959$、古典的 Runge–Kutta 法で $0.999986$、台形則で $1$ である。ただし台形則も完全ではなく、1 歩の回転角が $h$ でなく $2\arctan(h/2)$ なので、$t=100$ で位相が約 $0.0832$ だけ遅れ、$x\approx0.8173$(真の値 $\cos100\approx0.8623$)となる。

誤差の推定:$x'=x(1-x)$ の 1 歩

使う公式:prop-ode-richardson($p=4$)。
答え:$x(0)=0.1$ から古典的 Runge–Kutta 法で 1 歩進む。推定値 $(\tilde x-\hat x)/15$ と実際の誤差 $x(h)-\tilde x$ は次のとおりで、$h$ が小さいほど比が $1$ に近づく。

$h$推定値実際の誤差比
$0.8$$7.75\times10^{-6}$$9.96\times10^{-6}$$0.778$
$0.4$$2.65\times10^{-7}$$3.03\times10^{-7}$$0.874$
$0.2$$8.58\times10^{-9}$$9.20\times10^{-9}$$0.933$

同じ方程式を Euler 法と Heun 法の組で $[0,5]$ を $h_0=0.1$ から解き、推定値 $\le\varepsilon$ の歩を受理して上の式で刻みを更新し、受理した歩は Heun 法の値で進むと、$\varepsilon=10^{-3},10^{-4},10^{-5},10^{-6}$ に対して受理した歩数は $34$、$104$、$326$、$1025$、$x(5)$ の誤差は $5.1\times10^{-4}$、$5.7\times10^{-5}$、$5.9\times10^{-6}$、$6.6\times10^{-7}$ である。歩数は $\varepsilon^{-1/2}$ に比例して増えている。

左:安定領域の境界。Euler 法・古典的 Runge–Kutta 法・AB2 は曲線の内側、BDF2 は曲線の外側が安定領域で、台形則の安定領域は左半平面である。右:例題のロジスティック方程式の誤差と刻み幅の両対数グラフ 左:安定領域の境界。Euler 法・古典的 Runge–Kutta 法・AB2 は曲線の内側、BDF2 は曲線の外側が安定領域で、台形則の安定領域は左半平面である。右:例題のロジスティック方程式の誤差と刻み幅の両対数グラフ

使える条件と反例

各行は、対応する主張の仮定を 1 つだけ外したものである。

外す条件反例成り立たなくなること
整合性(thm-ode-dahlquist)$x_{n+1}=x_n+2hf_n$ を $x'=x$、$x(0)=1$ に別の方程式 $x'=2x$ の解に収束する
0 安定性(thm-ode-dahlquist)$x_{n+2}+4x_{n+1}-5x_n=h(4f_{n+1}+2f_n)$ を $x'=x$ に$h$ を小さくするほど発散する
Lipschitz 条件(thm-ode-dahlquist)AB2 を $x'=2\sqrt{\lvert x\rvert}$、$x_0=x_1=0$ に解 $t^2$ に収束しない
解の滑らかさ(次数の評価)古典的 Runge–Kutta 法を $x'=\lvert t-1/\sqrt2\rvert$ に次数 4 の速さが出ない
安定領域に入ること古典的 Runge–Kutta 法を ex-ode-stiff の $h=0.1$ で発散する
$R(\infty)=0$(L 安定性)台形則を ex-ode-stiff の $h=0.1$ で速い成分が残る
反例の確かめ

1 行目:$\rho(\zeta)=\zeta-1$、$\sigma(\zeta)=2$ なので $\rho(1)=0$ だが $\rho'(1)=1\ne2=\sigma(1)$ である。根の条件は満たす。近似値は $x_N=(1+2h)^{1/h}$ で、$h=10^{-4}$ で $7.3876$、極限は $e^2\approx7.3891$ で、真の値 $e$ でない。
2 行目:$\rho(\zeta)=\zeta^2+4\zeta-5=(\zeta-1)(\zeta+5)$ は根 $-5$ をもつ。prop-ode-order の条件を計算すると次数は 3 で、$k=2$ の陽的な方法の最高の次数である。$x_1=e^h$ として $x(1)$ の近似値を計算すると、$h=0.1$ で $-0.127$、$h=0.05$ で $-1.62\times10^6$、$h=0.025$ で $-9.34\times10^{18}$ となる。これらの値は有理数の演算でも同じで、丸め誤差のためではない。同じ方法の 6 桁の計算の例は Dah56 §1.2(pp. 37–38)にある。
3 行目:$f(x)=2\sqrt{\lvert x\rvert}$ は $0$ の近くで Lipschitz 条件を満たさない。初期値問題 $x'=f(x)$、$x(0)=0$ には解 $x\equiv0$ と $x=t^2$ がある。出発値の誤差 $\lvert x_1-h^2\rvert=h^2$ は $0$ に近づくのに、AB2 の値はすべて $0$ で、$x=t^2$ との差は $t=1$ で $1$ である。
4 行目:$x''$ は $t=1/\sqrt2$ で跳び、解は $C^1$ 級だが $C^2$ 級でない。$[0,1]$ を $N$ 等分したときの $x(1)$ の誤差は $N=10,40,160,320$ で $1.86\times10^{-4}$、$8.72\times10^{-6}$、$1.05\times10^{-6}$、$1.58\times10^{-7}$ で、誤差$/h^2$ はこの範囲で $0.05$ 以下にとどまり、減り方は不規則で、$h^4$ の速さは出ない。$t=1/\sqrt2$ を刻みの端に合わせて区間を分ければ、それぞれの区間で解は多項式で、誤差は $0$ になる。
5・6 行目:ex-ode-stiff の表による。

よくある誤り

誤り正しくはなぜ
次数の高い多段法ほどよいと考えて係数だけで作る0 安定性を $\rho$ の根で確かめるthm-ode-barrier1、ex-ode-counterexamples の 2 行目
0 安定なら固定の $h$ で安全とする0 安定性は $h\to0$ の性質で、$h$ を固定した性質は安定領域で見るex-ode-leapfrog
A 安定なら硬い方程式はどれも同じとする$\mu\to-\infty$ の増幅率を確かめるprop-ode-limit
陰的な方法の方程式を単純な反復で解くNewton 法を使う反復の収束に $h\lvert\beta_k\rvert L< 1$ が要る
多段法の出発値を低い次数のまま使う誤差 $O(h^p)$ の出発値を使うthm-ode-dahlquist の評価の第 1 項
刻みを小さくすれば必ず精度が上がるとする丸め誤差があり、ある刻み幅より下では悪くなるEuler法 の定理「Euler法の大域誤差」のあとの説明

補足

陰的な Runge–Kutta 法

thm-ode-astable は線形多段法についての主張である。2 段の Gauss 法(Butcher 表が $c_{1,2}=\frac12\mp\frac{\sqrt3}6$、$a_{11}=a_{22}=\frac14$、$a_{12}=\frac14-\frac{\sqrt3}6$、$a_{21}=\frac14+\frac{\sqrt3}6$、$b_1=b_2=\frac12$)の増幅率は
$$ R(z)=\frac{1+\frac z2+\frac{z^2}{12}}{1-\frac z2+\frac{z^2}{12}}=e^z-\frac{z^5}{720}+O(z^6) $$
である。分母の根 $3\pm\sqrt3\,i$ は右半平面にあり、虚軸の上で分子と分母は共役なので $\lvert R(iy)\rvert=1$、$\lvert z\rvert\to\infty$ で $R\to1$ である。最大値の原理から $\operatorname{Re}z\le0$ で $\lvert R\rvert\le1$ となり、この方法は A 安定で、線形の方程式では次数 4 である。代わりに 1 歩で $2d$ 元の連立方程式を解く。

用語の注意. Dah56 では $p$ を degree、$k$ を order と呼ぶ。この記事の「次数 $p$」「$k$ 段」と入れ替わっているので、文献を読むときに注意する。
関連する主題. 偏微分方程式の空間を離散化すると、大きな常微分方程式の系になる。その系の時間積分に、この記事の安定領域がそのまま効く(偏微分方程式の数値解法)。

関連項目

参考文献

[1]
Germund Dahlquist, Convergence and stability in the numerical integration of ordinary differential equations, Mathematica Scandinavica, 1956, pp. 33–53、§1.2(pp. 37–38)、Theorem 1(p. 43)、Theorem 4a(p. 51)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する