線形多段法

同義語:線形多段階法linear multistep method

概要

線形多段法(linear multistep method)とは、常微分方程式の初期値問題の近似解を、直前の $k$ 個の近似値とそこでの右辺の値の 1 次結合で次の値を定めて進める数値解法で、Adams 法や BDF がその例である。次数は係数の簡単な 1 次式で判定でき、収束は整合性と 0 安定性(第 1 特性多項式の根の条件)が合わさることと同値である(Dahlquist の同値定理)。0 安定な $k$ 段の方法の次数は $k+2$ 以下、$k$ が奇数なら $k+1$ 以下、陽的なら $k$ 以下に制限される(Dahlquist の第 1 障壁)。

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

前提知識: 常微分方程式の数値解法, 初期値問題, Lagrange補間, Euler法

線形多段法(linear multistep method)とは、常微分方程式の初期値問題 $x'=f(t,x)$ の近似解を、直前の $k$ 個の近似値と、そこでの $f$ の値の 1 次結合で次の値を決めて進める方法である。Runge–Kutta法 が 1 歩の中で $f$ を何度も評価するのに対し、線形多段法は過去に計算した値を使い回すので、1 歩あたりの $f$ の評価が 1 回(陰的な方法でも反復の分だけ)で済む。その代わり、係数を勝手に選ぶと、局所的にはいくら精度が高くても、刻み幅を小さくするほど誤差が爆発する方法ができてしまう。
この記事では、線形多段法の次数の条件と 0 安定性(根の条件)を述べ、Adams 法と BDF(後退差分公式)の作り方と次数を示す。収束が「整合的かつ 0 安定」と同値であるという Dahlquist の同値定理(thm-lmm-equivalence)を述べ、主定理として、0 安定な $k$ 段の方法の次数は $k+2$ を超えられないという Dahlquist の第 1 障壁(thm-lmm-barrier1)を完全に証明する。安定領域・A 安定性・硬い方程式の扱いと、A 安定な方法の次数が $2$ 以下であるという第 2 障壁は 常微分方程式の数値解法 の主題で、この記事では引いて使う。

定義

$f\colon[t_0,t_0+T]\times\mathbb{R}^d\to\mathbb{R}^d$ は連続で、$x$ について大域的な Lipschitz 条件を定数 $L$ で満たすとする。刻み幅を $h=T/N$、$t_n:=t_0+nh$ とし、$f_n:=f(t_n,x_n)$ と書く。このとき初期値問題の解 $x$ は $[t_0,t_0+T]$ でただ 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_{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\alpha_j\zeta^j$、$\sigma(\zeta):=\sum_j\beta_j\zeta^j$ を 第 1・第 2 特性多項式 という。

陰的な方法でも、$hL\lvert\beta_k\rvert< 1$ なら $x_{n+k}$ は縮小写像の不動点としてただ 1 つに定まる。条件 $\lvert\alpha_0\rvert+\lvert\beta_0\rvert>0$ は、実際には $k-1$ 段の方法であるものを除くためである。

次数と誤差定数

$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=\dots=C_p=0$ となる最大の $p$ を方法の 次数 といい、$p\ge1$ のとき方法は 整合的 であるという。$\sigma(1)\ne0$ のとき $C_{p+1}/((p+1)!\,\sigma(1))$ を 誤差定数 という。

$C_0=\rho(1)$、$C_1=\rho'(1)-\sigma(1)$ なので、整合的であることは $\rho(1)=0$ かつ $\rho'(1)=\sigma(1)$ と同値である。

根の条件と 0 安定性

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

$h=0$ とおいた差分方程式 $\sum_j\alpha_jx_{n+j}=0$ の一般解は、$\rho$ の根 $\zeta$(重複度 $m$)ごとの $n^i\zeta^n$($0\le i< m$)の 1 次結合である。根の条件は、この解がすべて有界であることにほかならない。

収束

線形多段法が 収束する とは、上の条件を満たすすべての $f$(すべての次元 $d$)と、$\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$)となることをいう。

次数の判定

次数の言い換え

整数 $p\ge0$ について次は同値である。
(R1) $C_0=\dots=C_p=0$。
(R2) 次数 $p$ 以下のすべての多項式 $y$ と $t\in\mathbb{R}$、$h>0$ について $\sum_j\alpha_jy(t+jh)=h\sum_j\beta_jy'(t+jh)$(方法は次数 $p$ 以下の多項式解を厳密に再現する)。
(R3) $w\to0$ で $\rho(e^w)-w\,\sigma(e^w)=O(w^{p+1})$。

$y(s)=s^q$ を代入する

$y(s)=(s-t)^q/h^q$ を (ii) の両辺の差に代入すると、ちょうど $C_q$ になる。$q\le p$ の $(s-t)^q$ は次数 $p$ 以下の多項式の基底なので、(i) と (ii) は同値である。また $e^{jw}=\sum_q(jw)^q/q!$ を代入して $w^q$ の係数を集めると
$$ \rho(e^w)-w\sigma(e^w)=\sum_{q\ge0}\frac{C_q}{q!}w^q $$
なので、(i) と (iii) は同値である。$\square$

条件 (ii) から、$C^{p+2}$ 級の解を方法の式に代入したときの残り(局所打ち切り誤差)は、Taylor 展開により $h^{p+1}C_{p+1}x^{(p+1)}(t_n)/(p+1)!+O(h^{p+2})$ である。誤差定数は、これを $\sigma(1)$ で割って 1 歩あたりの量に直したものである。

Adams 法と BDF

方法の作り方は 2 通りある。
Adams 法. $x(t_{n+k})-x(t_{n+k-1})=\int_{t_{n+k-1}}^{t_{n+k}}x'(s)\,ds$ の被積分関数を、$f_n,\dots,f_{n+k-1}$ を通る Lagrange補間 の多項式(次数 $k-1$ 以下)で置き換えたものが陽的な Adams–Bashforth 法、$f_{n+k}$ も含めた次数 $k$ 以下の補間で置き換えたものが陰的な Adams–Moulton 法 である。どちらも $\rho(\zeta)=\zeta^k-\zeta^{k-1}$ で、根は $1$ と $0$ だけなので、どの $k$ でも 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}$ で、$\sigma(\zeta)=\beta_k\zeta^k$ である。

Adams 法と BDF の次数

$k$ 段の Adams–Bashforth 法の次数は $k$ 以上、$k$ 段の Adams–Moulton 法の次数は $k+1$ 以上、$k$ 段の BDF の次数は $k$ 以上である。

補間が厳密になる多項式

prop-lmm-order の (ii) を確かめる。$y$ が次数 $k$ 以下の多項式なら $y'$ は次数 $k-1$ 以下なので、$y'(t+jh)$($0\le j\le k-1$)を通る次数 $k-1$ 以下の補間多項式は $y'$ 自身であり、Adams–Bashforth 法の式は $y(t+kh)-y(t+(k-1)h)=\int y'$ という恒等式になる。Adams–Moulton 法では $k+1$ 点の補間なので、次数 $k+1$ 以下の $y$ で同じことが起こる。BDF では、$y$ が次数 $k$ 以下なら $k+1$ 点の補間多項式は $y$ 自身なので、その微分係数は $y'(t+kh)$ に等しい。$\square$

$k$ 段の陽的な方法には未知の係数が $2k$ 個あるので、0 安定性を気にしなければ $C_0=\dots=C_{2k-1}=0$ を課すことができ、次数を $2k-1$ まで上げられる場合がある。$k=2$ では次の方法が次数 $3$ をもつ:
$$ x_{n+2}+4x_{n+1}-5x_n=h(4f_{n+1}+2f_n). $$
実際 $C_0=1+4-5=0$、$C_1=6-6=0$、$C_2=8-8=0$、$C_3=12-12=0$、$C_4=20-16=4$ である。しかし $\rho(\zeta)=(\zeta-1)(\zeta+5)$ は根 $-5$ をもち、0 安定でない。$x'=-x$、$x(0)=1$ に正確な出発値で使うと、時刻 $1$ での誤差は $h=0.1,\ 0.05,\ 0.025$ で約 $7.0$、$4.7\times10^6$、$2.9\times10^{19}$ と、$h$ を小さくするほど爆発する。丸め誤差や打ち切り誤差の成分が毎歩 $-5$ 倍されるためで、次数だけでは方法の良し悪しが決まらないことを示す例である。

代表的な方法の次数と誤差定数

係数から $C_q$ を計算した結果である。「AB$k$」「AM$k$」は $k$ 段の Adams–Bashforth 法・Adams–Moulton 法である。

方法$\rho(\zeta)$$\sigma(\zeta)$次数誤差定数0 安定
AB1(Euler 法)$\zeta-1$$1$1$\frac12$可
AB2$\zeta^2-\zeta$$\frac12(3\zeta-1)$2$\frac5{12}$可
AB3$\zeta^3-\zeta^2$$\frac1{12}(23\zeta^2-16\zeta+5)$3$\frac38$可
AB4$\zeta^4-\zeta^3$$\frac1{24}(55\zeta^3-59\zeta^2+37\zeta-9)$4$\frac{251}{720}$可
AM1(台形則)$\zeta-1$$\frac12(\zeta+1)$2$-\frac1{12}$可
AM2$\zeta^2-\zeta$$\frac1{12}(5\zeta^2+8\zeta-1)$3$-\frac1{24}$可
AM3$\zeta^3-\zeta^2$$\frac1{24}(9\zeta^3+19\zeta^2-5\zeta+1)$4$-\frac{19}{720}$可
BDF2$\zeta^2-\frac43\zeta+\frac13$$\frac23\zeta^2$2$-\frac13$可
中点則(leapfrog)$\zeta^2-1$$2\zeta$2$\frac16$可(根 $\pm1$)
Milne–Simpson 法$\zeta^2-1$$\frac13(\zeta^2+4\zeta+1)$4$-\frac1{180}$可(根 $\pm1$)
上の陽的 2 段法$\zeta^2+4\zeta-5$$4\zeta+2$3$\frac1{36}$否(根 $-5$)

$k$ 段の BDF の次数はちょうど $k$ で、誤差定数は $-\frac1{k+1}$ である($k\le12$ で計算した)。$\rho$ の $1$ 以外の根の絶対値の最大値は、$k=1,\dots,6$ で $0,\ 0.333,\ 0.426,\ 0.561,\ 0.709,\ 0.863$ と $1$ 未満だが、$k=7$ で $1.022$ になり、$k=7,\dots,12$ ではどれも $1$ を超えて 0 安定でない。

収束:Dahlquist の同値定理

Dahlquist の同値定理

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

同じ定理は 常微分方程式の数値解法 の定理「Dahlquistの同値定理」で、根の条件を同伴行列のべき乗の有界性に言い換えて証明されている。ここでは、差分方程式を母関数で解く別の証明を与える。

差分方程式の基本解の有界性

要点:$1/(\zeta^k\rho(1/\zeta))$ のべき級数の係数 $\gamma_m$ が、根の条件のもとで有界になる。誤差の差分方程式を $\gamma_m$ で解くと、誤差は出発値の誤差と局所打ち切り誤差の和で押さえられ、離散版の Grönwall の議論で閉じる。

詳しい証明を開く

基本解。$\tilde\rho(w):=w^k\rho(1/w)=\sum_j\alpha_jw^{k-j}$ とおくと $\tilde\rho(0)=1$ なので、べき級数 $1/\tilde\rho(w)=\sum_{m\ge0}\gamma_mw^m$ が定まる。$\rho$ の $0$ でない根を $\zeta_i$(重複度 $m_i$)とすると、部分分数分解により $1/\tilde\rho(w)=\sum_i\sum_{r\le m_i}c_{ir}(1-\zeta_iw)^{-r}$ で、$\gamma_m=\sum_{i,r}c_{ir}\binom{m+r-1}{r-1}\zeta_i^m$ である。根の条件のもとでは、$\lvert\zeta_i\rvert< 1$ の項は $0$ に収束し、$\lvert\zeta_i\rvert=1$ の項は $r=1$ だけで絶対値一定なので、$\Gamma:=\sup_m\lvert\gamma_m\rvert< \infty$ である。

誤差の表示。$e_n:=x(t_n)-x_n$、$d_n:=\sum_j\alpha_jx(t_{n+j})-h\sum_j\beta_jx'(t_{n+j})$ とおくと $\sum_j\alpha_je_{n+j}=g_n$、$g_n:=h\sum_j\beta_j\bigl(f(t_{n+j},x(t_{n+j}))-f_{n+j}\bigr)+d_n$ である。母関数 $E(w):=\sum_ne_nw^n$、$G(w):=\sum_ng_nw^n$ について、$w^{n+k}$ を掛けて足すと $\tilde\rho(w)E(w)=P(w)+w^kG(w)$ となる。ここで $P(w)=\sum_j\alpha_jw^{k-j}\sum_{i< j}e_iw^i$ は次数 $k-1$ 以下の多項式で、係数は $A\max_{i< k}\lvert e_i\rvert$($A:=\sum_j\lvert\alpha_j\rvert$)以下である。係数を比べると $e_n=\sum_{i< k}P_i\gamma_{n-i}+\sum_{m=0}^{n-k}\gamma_{n-k-m}g_m$ であり、

$$\lvert e_n\rvert\le\Gamma kA\max_{i< k}\lvert e_i\rvert+\Gamma\sum_{m=0}^{n-k}\lvert g_m\rvert .$$

十分性。$b:=\sum_j\lvert\beta_j\rvert$、$a_n:=\max_{i\le n}\lvert e_i\rvert$ とおくと $\lvert g_m\rvert\le hLb\,a_{m+k}+\lvert d_m\rvert$ である。$D:=\sum_m\lvert d_m\rvert$ とし、$h\Gamma Lb\le\frac12$ とすると、$a_n$ を含む項を左辺に移して $a_n\le B+2h\Gamma Lb\sum_{i< n}a_i$、$B:=2\Gamma(kAa_{k-1}+D)$ を得る。帰納法で $a_n\le B(1+2h\Gamma Lb)^n\le Be^{2\Gamma LbT}$ である。整合的なら $\rho(1)=0$、$\rho'(1)=\sigma(1)$ を使って $d_n=\sum_j\alpha_j\bigl(x(t_{n+j})-x(t_n)-jhx'(t_n)\bigr)-h\sum_j\beta_j\bigl(x'(t_{n+j})-x'(t_n)\bigr)$ と書け、$x'$ の一様連続性から $\lvert d_n\rvert=o(h)$($n$ について一様)、よって $D=o(1)$ である。次数 $p$ で $x\in C^{p+1}$ なら、prop-lmm-order の (ii) と Taylor の定理から $\lvert d_n\rvert\le ch^{p+1}$、$D\le cTh^p$ である。

必要性。$f\equiv0$、$x\equiv0$ とする。$\rho$ が $\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^{T/h}\to\infty$ である。$\lvert\zeta\rvert=1$ の重根があれば、$x_n:=\sqrt h\,n(\operatorname{Re}\zeta^n,\operatorname{Im}\zeta^n)$ が同じ役をする。よって 0 安定である。$f\equiv0$、$x\equiv1$、出発値 $1$ から $\rho(1)=0$ を得る。$f\equiv1$、$x(t)=t-t_0$ とし $c:=\sigma(1)/\rho'(1)$ とおくと(0 安定性から $\rho'(1)\ne0$)、$x_n:=nhc$ は方法の解で出発値は真の値に近づくので、$x_N=Tc\to T$ から $c=1$、すなわち $\rho'(1)=\sigma(1)$ である。$\square$

定理は「整合性(1 歩のずれが小さい)と安定性(ずれが増幅されない)を合わせると収束する」という形をしている。0 安定でない ex-lmm-table の陽的 2 段法の爆発は、必要性の証明の $h\lvert\zeta\rvert^{T/h}$ そのものである。

主定理:Dahlquist の第 1 障壁

$k$ 段の方法の係数は $\alpha_k=1$ を除いて $2k+1$ 個あるので、0 安定性を問わなければ次数は $2k$ まで上げられる見込みがある。0 安定性はこれを大きく制限する。
証明には、次の補題を使う。$\operatorname{artanh}z=\sum_{n\ge0}z^{2n+1}/(2n+1)$ である。

$z/\operatorname{artanh}z$ の係数の符号

形式的べき級数として
$$ \frac{z}{\operatorname{artanh}z}=1-\sum_{j\ge1}\gamma_jz^{2j} $$
と書くと、すべての $j\ge1$ で $\gamma_j>0$ である($\gamma_1=\frac13$、$\gamma_2=\frac4{45}$、$\gamma_3=\frac{44}{945}$)。

係数の比が増えることを使う帰納法

$a_n:=\frac1{2n+1}$ とおくと $\operatorname{artanh}z/z=\sum_na_nz^{2n}$ である。$c_0:=1$ とし、$\sum_nc_nz^{2n}$ をその逆数とすると、$n\ge1$ で $\sum_{i=0}^nc_ia_{n-i}=0$ である。示すべきことは $c_n< 0$($n\ge1$)である。$c_1=-a_1=-\frac13< 0$ である。$r_m:=a_{m+1}/a_m=\frac{2m+1}{2m+3}$ は $m$ について狭義に増加する。$c_1,\dots,c_n< 0$ と仮定すると、
$$ -c_{n+1}=\sum_{i=0}^nc_ia_{n+1-i}=\sum_{i=0}^nc_ia_{n-i}r_{n-i}=\sum_{i=0}^nc_ia_{n-i}(r_{n-i}-r_n) $$
である(最後の等号は $\sum_{i=0}^nc_ia_{n-i}=0$ の $r_n$ 倍を引いた)。$i=0$ の項は $0$ で、$1\le i\le n$ の項は $c_i< 0$、$a_{n-i}>0$、$r_{n-i}-r_n< 0$ なので正である。よって $c_{n+1}< 0$ である。$\gamma_j:=-c_j$ とおけばよい。$\square$

Dahlquist の第 1 障壁

0 安定な $k$ 段の線形多段法の次数 $p$ について、次が成り立つ。

  1. $p\le k+2$ である。
  2. $k$ が奇数なら $p\le k+1$ である。陽的な方法なら、$k$ の偶奇によらず $p\le k$ である。
  3. $p=k+2$ なら(このとき $k$ は偶数)、$\rho$ の根はすべて単位円 $\lvert\zeta\rvert=1$ の上にある。
Cayley 変換で根を左半平面に移し、係数の符号を比べる

1・2 は $p\ge k+2$ の場合、陽的な方法の主張は $p\ge k+1$ の場合だけを考えればよいので、$p\ge k+1$(とくに $p\ge2$ で方法は整合的)とする。0 安定性と整合性から、$\zeta=1$ は $\rho$ の単根である。
変換。 $\zeta=\frac{1+z}{1-z}$ とおく。この 1 次分数変換は、左半平面 $\operatorname{Re}z< 0$ を単位円板 $\lvert\zeta\rvert< 1$ に、虚軸を単位円から $-1$ を除いたものに、$z=0$ を $\zeta=1$ に写す。
$$ r(z):=\Bigl(\frac{1-z}2\Bigr)^k\rho\Bigl(\frac{1+z}{1-z}\Bigr)=2^{-k}\sum_j\alpha_j(1+z)^j(1-z)^{k-j},\qquad s(z):=2^{-k}\sum_j\beta_j(1+z)^j(1-z)^{k-j} $$
は次数 $k$ 以下の多項式である。$r(1)=\alpha_k=1\ne0$ なので、$r$ の根は $\rho$ の $-1$ でない根に対応し、$\rho$ の根の条件から $r$ の根はすべて $\operatorname{Re}z\le0$ にある。$z=0$ は単根で、ほかの根 $z_i$ は $0$ でない。よって $r(z)=cz\prod_i(z-z_i)$ と書け、実根の因子 $z-z_i$($z_i< 0$)と共役な対の因子 $z^2-2(\operatorname{Re}z_i)z+\lvert z_i\rvert^2$ はどれも係数が $0$ 以上で定数項が正である。$\rho,\sigma$ を同時に $-1$ 倍しても次数と根は変わらないので $c>0$ としてよく、$r(z)=\sum_{i=1}^ka_iz^i$ と書くと、すべての $a_i\ge0$ かつ $a_1>0$ である。
次数の条件の言い換え。 $\ell(z):=\log\frac{1+z}{1-z}=2\operatorname{artanh}z$ とおくと $e^{\ell(z)}=\zeta$ である。prop-lmm-order の (iii) に $w=\ell(z)=2z+O(z^3)$ を代入して $w$ で割り、$\bigl(\frac{1-z}2\bigr)^k$ を掛けると
$$ \frac{r(z)}{\ell(z)}-s(z)=O(z^p)\qquad(z\to0) $$
を得る($r(0)=0$ なので左辺の第 1 項は $z=0$ で正則である)。
係数の比較。 lem-lmm-kaluza により
$$ \frac{r(z)}{\ell(z)}=\frac{r(z)}z\cdot\frac z{2\operatorname{artanh}z}=\frac12\Bigl(\sum_{i=1}^ka_iz^{i-1}\Bigr)\Bigl(1-\sum_{j\ge1}\gamma_jz^{2j}\Bigr) $$
である。$m\ge k$ のとき右辺の $z^m$ の係数は、第 1 の因子の $z^{i-1}$ と第 2 の因子の $-\gamma_jz^{2j}$ の積からだけ来て、
$$ -\frac12\sum_{\substack{1\le i\le k\\ i-1+2j=m,\ j\ge1}}a_i\gamma_j $$
である。$s$ の次数は $k$ 以下なので、$k+1\le m\le p-1$ ではこの係数が $0$ でなければならない。各項は $0$ 以上なので、$i\equiv m+1\pmod2$ のすべての $i\le k$ について $a_i=0$ である($m\ge k+1$ なら $i\le k\le m-1$ で、対応する $j=\frac{m+1-i}2\ge1$ がある)。
1・2。 $k$ が奇数で $p\ge k+2$ なら、$m=k+1$ について $i\equiv k+2\equiv1$ なので $a_1=0$ となり、$a_1>0$ に反する。よって $p\le k+1$ である。$k$ が偶数で $p\ge k+3$ なら、$m=k+2$ について $i\equiv1$ なので同じく矛盾し、$p\le k+2$ である。
3。 $p=k+2$ なら $k$ は偶数で、$m=k+1$ から偶数の $i$ について $a_i=0$、すなわち $r$ は奇関数である。$z_i$ が $r$ の根なら $-z_i$ も根なので、$\operatorname{Re}z_i< 0$ の根があれば $\operatorname{Re}z>0$ の根もあることになり矛盾する。よって $r$ の根はすべて虚軸の上にあり、$\rho$ の根はすべて単位円の上にある($\zeta=-1$ の根も単位円の上にある)。陽的な方法。 $p\ge k+1$ とし、$r(z)/\ell(z)=\sum_md_mz^m$ と書く。$s$ の次数は $k$ 以下なので $s(z)=\sum_{m\le k}d_mz^m$ である。lem-lmm-kaluza の証明の漸化式から $0< \gamma_j\le\frac1{2j+1}$ なので、$\sum_j\gamma_jz^{2j}$ は $\lvert z\rvert< 1$ で収束して $1-\frac z{\operatorname{artanh}z}$ に等しく、$z\to1-0$ で $\frac z{\operatorname{artanh}z}\to0$ となることから $\sum_j\gamma_j=1$ で、係数の級数は絶対収束して $\sum_md_m=\frac12r(1)\bigl(1-\sum_j\gamma_j\bigr)=0$ である。よって $\beta_k=s(1)=-\sum_{m>k}d_m=\frac12\sum_{i-1+2j>k}a_i\gamma_j\ge\frac12a_1\gamma_j>0$($2j>k$ の $j$)となり、陽的であることに反する。$\square$

証明の要は、0 安定性が「$r$ の係数がすべて同じ符号」に、高い次数が「$r$ と $z/\operatorname{artanh}z$ の積の高次の係数が消える」に翻訳され、lem-lmm-kaluza の符号と両立しないことである。

上界に達する方法

Milne–Simpson 法 $x_{n+2}-x_n=\frac h3(f_{n+2}+4f_{n+1}+f_n)$ は $k=2$、$p=4=k+2$ で、thm-lmm-barrier1 の上界に達する。実際 $r(z)=z$ で、奇関数である。$\rho(\zeta)=\zeta^2-1$ の根は $\pm1$ で、3 のとおり単位円の上にある。

3 は、最大の次数をもつ方法が「ぎりぎり 0 安定」であることを意味する。Milne–Simpson 法を $x'=-x$ に $h=0.1$ で使うと、$\pi(\zeta)=\rho(\zeta)+h\sigma(\zeta)$ の根は $0.9048\approx e^{-h}$(主根)と $-1.0339$(寄生根)で、寄生根の成分が毎歩符号を変えながら約 $1.034$ 倍される。正確な出発値から始めても、誤差は $t=5$ で $1.6\times10^{-7}$、$t=10$ で $7.2\times10^{-7}$、$t=20$ で $2.0\times10^{-5}$ と増え、$t=15$ と $t=20$ の近似値は負になる(真の解 $e^{-t}$ は正)。0 安定でも、$h$ を固定して長い時間を計算するときの安定性は別に調べる必要がある。これが安定領域の考え方である(常微分方程式の数値解法 の定義「安定領域とA安定性」)。

第 2 障壁

整合的で 0 安定な線形多段法について、A 安定な(安定領域が左半平面を含む)方法の次数は $2$ 以下であり、陽的な方法は A 安定でない。これが Dahlquist の第 2 障壁で、証明は 常微分方程式の数値解法 の定理「A安定な線形多段法の次数(Dahlquistの第2障壁)」にある。そこでも thm-lmm-barrier1 と同じ変換 $\zeta=\frac{1+z}{1-z}$ と、$\log$ の展開の係数の符号が使われる。次数 $2$ の台形則と BDF2 は A 安定で、この上界に達する。

反例:条件を外すと成り立たないこと

主張外す条件例成り立たなくなること
thm-lmm-equivalence(十分性)0 安定$x_{n+2}+4x_{n+1}-5x_n=h(4f_{n+1}+2f_n)$(次数 3)収束しない。$x'=-x$ で時刻 $1$ の誤差が $h\to0$ で発散する(ex-lmm-table の前の段落)
thm-lmm-equivalence(十分性)整合性$x_{n+1}=x_n+2hf_n$($\rho(1)=0$ だが $\rho'(1)=1\ne2=\sigma(1)$)0 安定だが、$x'=1$ に使うと $x_n=x_0+2nh$ で、$x'=2$ の解に収束する
thm-lmm-barrier1 の 1・20 安定$k=3$ で $C_0=\dots=C_6=0$ を解いた $x_{n+3}+\frac{27}{11}x_{n+2}-\frac{27}{11}x_{n+1}-x_n=\frac{3h}{11}(f_{n+3}+9f_{n+2}+9f_{n+1}+f_n)$次数は $6>k+1$ だが、$\rho$ は根 $-3.136$ をもち 0 安定でない
thm-lmm-barrier1 の 3 の逆—中点則 $x_{n+2}=x_n+2hf_{n+1}$根は $\pm1$ で単位円上だが、次数は $2< k+2=4$。根が単位円上にあっても最大次数とは限らない
0 安定なら $h$ を固定しても安定—Milne–Simpson 法、$x'=-x$、$h=0.1$寄生根 $-1.034$ の成分が増え、減衰する解を正しく追えない(ex-lmm-simpson の後の段落)

3 行目の係数は $C_0=\dots=C_6=0$ を解いて得たもので、根は数値で求めた値である。2 行目の方法は $\rho$ が根の条件を満たすので有界な誤差の増幅しか起こさないが、$f$ の重みが 2 倍なので別の方程式を解いてしまう。

歴史と出典

線形多段法の一般論と収束・安定性の同値定理、次数の上界(第 1 障壁)は G. Dahlquist による(Dah56)。同値定理にあたるのは Theorem 1(p. 43)で、収束の定義がこの記事と異なり、摂動を含めた収束(converge stably)と根の条件(条件 D・E)の同値の形で述べられている。第 1 障壁は Theorem 4a(p. 51)である。Dahlquist は $z/\log\frac{1+z}{1-z}$ の係数の符号を、$\log$ の分枝の切れ目に沿う積分表示から導いている(Dah56 (2.21)、p. 51)。この記事の lem-lmm-kaluza の証明は、係数の比の単調性を使う帰納法による書き下ろしである。thm-lmm-equivalence の証明も、母関数による書き下ろしである。Theorem 4a は、$p=k+2$ となるのが $R(z)$(この記事の $r$ に対応する多項式)が奇関数であるときに限ることと、そのとき $R(z)$ の根がすべて虚軸の上にあることも述べており、thm-lmm-barrier1 の 3 はこれにあたる($\rho$ の根がすべて単位円の上にあることは同じ頁の Theorem 4b)。陽的な方法の上界 $p\le k$ の証明は、この記事の書き下ろしである。
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、Theorem 1(p. 43)、(2.21)・Theorem 4a・4b(p. 51)

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