差分法

同義語:有限差分法finite difference methodFDM

概要

差分法(finite difference method)とは、微分方程式の導関数を格子点の値の差の比で置き換え、連立 1 次方程式や漸化式に直して数値解を求める方法である。誤差は打切り誤差と安定性で決まり、2 点境界値問題の中心差分は、解が滑らかなら離散の最大値原理により $O(h^2)$ で収束する。熱方程式の陽解法は $\kappa\Delta t/\Delta x^2\le\tfrac12$ で安定で、移流方程式の風上差分には CFL 条件が要る。熱伝導・拡散・波動・Poisson 方程式などの数値計算に使う。

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

前提知識: Taylorの定理, 偏微分方程式, 連立1次方程式, 固有値

差分法(finite difference method)は、微分方程式の導関数を格子点の値の差の比(差分商)で置き換え、連立 1 次方程式や漸化式に直して数値解を求める方法である。たとえば
$$ -u''(x)=f(x)\quad(0< x< 1),\qquad u(0)=u(1)=0 $$
の解は、一般の $f$ では閉じた形に書けない。そこで $[0,1]$ を幅 $h$ に等分し、格子点での値 $U_j\approx u(jh)$ を未知数として
$$ \frac{-U_{j-1}+2U_j-U_{j+1}}{h^2}=f(jh) $$
を立てると、3 重対角の連立 1 次方程式になる。これを解けば、解が滑らかなら、$h$ を半分にするごとに誤差がおよそ $1/4$ になる近似解が得られる。
計算そのものは単純だが、差分法には次の 3 つの問いがつきまとう。

  • 差分商は導関数をどれだけ正確に近似するか(整合性、打切り誤差)。
  • 小さな誤差が計算の途中で増えないか(安定性)。
  • $h\to0$ で近似解は本当の解に近づくか(収束)。
    この記事では、差分公式の表を示し、2 点境界値問題と熱方程式で誤差の上界を証明する。熱方程式の陽解法の安定条件 $\kappa\Delta t/\Delta x^2\le\tfrac12$ と、移流方程式の CFL 条件も導く。手順と数値まで計算した例題を置き、条件を外すと何が成り立たなくなるかを反例の表で見る。

定義と使える条件

等間隔の格子を考える。区間 $[0,1]$ を $N$ 等分し、$h=1/N$、$x_j=jh$($j=0,\dots,N$)とおく。関数 $u$ の格子点での値を $u_j=u(x_j)$ と書く。

差分商

関数 $u$ と $h>0$ に対し、次の量を点 $x$ での 差分商 という。
$$ \delta^+u(x)=\frac{u(x+h)-u(x)}{h},\qquad \delta^-u(x)=\frac{u(x)-u(x-h)}{h},\qquad \delta^0u(x)=\frac{u(x+h)-u(x-h)}{2h}, $$
$$ \delta^2u(x)=\frac{u(x+h)-2u(x)+u(x-h)}{h^2}. $$
順に 前進差分、後退差分、中心差分、2 階中心差分 と呼ぶ。

打切り誤差・整合性・安定性・収束

微分方程式 $Lu=f$ を、格子上の線形方程式 $L_hU=f_h$($U$ は格子点の値の列)で近似する。$u_h$ を厳密解 $u$ の格子点での値の列とする。

  • $\tau_h=L_hu_h-f_h$ を 打切り誤差 という。適当なノルムで $\|\tau_h\|\to0$($h\to0$)のとき 整合している といい、$\|\tau_h\|=O(h^p)$ のとき $p$ 次の精度 をもつという。
  • $L_h$ が正則で、$h$ によらない定数 $M$ があって $\|L_h^{-1}\|\le M$ のとき 安定 という。
  • $\|u_h-U\|\to0$ のとき 収束する という。

ここでのノルムは格子上の関数のノルムで、この記事では最大値ノルム $\|V\|_\infty=\max_j\lvert V_j\rvert$ と、ベクトルの Euclid ノルムを使う。打切り誤差は「厳密解を差分式に代入した残り」であり、解の誤差 $u_h-U$ とは別の量である。 この 2 つをつなぐのが安定性で、$L_h(u_h-U)=\tau_h$ から
$$ \|u_h-U\|\le\|L_h^{-1}\|\,\|\tau_h\| $$
が出る。「整合性+安定性=収束」という見取り図は、この 1 行にある。
公式を使ってよい条件は次のとおり。
(i) 滑らかさ:$p$ 次の精度の評価には、方程式の階数より高い階の導関数の有界性が要る。2 階中心差分の $O(h^2)$ には $u\in C^4$ を使う。
(ii) 格子:表の公式は等間隔の格子のものである。不等間隔なら係数が変わる。
(iii) 方程式の型に合った差分:楕円型の方程式には符号の条件($q\ge0$ など)、熱方程式の陽解法には刻みの比の制限、移流方程式には風上側の差分と CFL 条件が要る。

公式の表

次の表の「誤差の主要項」は、差分商から真の導関数を引いた値の、$h$ の最低次の項である。

近似するもの差分公式誤差の主要項条件根拠
$u'(x)$前進 $\dfrac{u(x+h)-u(x)}{h}$$\dfrac h2u''(x)$$u\in C^2$計算(畳んだ導出)
$u'(x)$後退 $\dfrac{u(x)-u(x-h)}{h}$$-\dfrac h2u''(x)$$u\in C^2$計算(畳んだ導出)
$u'(x)$中心 $\dfrac{u(x+h)-u(x-h)}{2h}$$\dfrac{h^2}6u'''(x)$$u\in C^3$計算(畳んだ導出)
$u'(x)$片側 3 点 $\dfrac{-3u(x)+4u(x+h)-u(x+2h)}{2h}$$-\dfrac{h^2}3u'''(x)$$u\in C^3$計算(畳んだ導出)
$u'(x)$5 点 $\dfrac{-u(x+2h)+8u(x+h)-8u(x-h)+u(x-2h)}{12h}$$-\dfrac{h^4}{30}u^{(5)}(x)$$u\in C^5$計算(畳んだ導出)
$u''(x)$中心 $\dfrac{u(x+h)-2u(x)+u(x-h)}{h^2}$$\dfrac{h^2}{12}u^{(4)}(x)$$u\in C^4$prop-fd-second-difference
$u''(x)$5 点 $\dfrac{-u(x+2h)+16u(x+h)-30u(x)+16u(x-h)-u(x-2h)}{12h^2}$$-\dfrac{h^4}{90}u^{(6)}(x)$$u\in C^6$計算(畳んだ導出)
$(au')'(x)$$\dfrac{a_{+}(u(x+h)-u(x))-a_{-}(u(x)-u(x-h))}{h^2}$、$a_\pm=a(x\pm\tfrac h2)$$O(h^2)$$a\in C^3$、$u\in C^4$証明しない。Saa03 (2.16)(p. 52)
$u''(x)$(不等間隔)$\dfrac2{h_1+h_2}\Bigl(\dfrac{u(x+h_2)-u(x)}{h_2}-\dfrac{u(x)-u(x-h_1)}{h_1}\Bigr)$$\dfrac{h_2-h_1}3u'''(x)$$u\in C^3$計算(畳んだ導出)
$\Delta u(x,y)$5 点 $\dfrac{u(x+h,y)+u(x-h,y)+u(x,y+h)+u(x,y-h)-4u(x,y)}{h^2}$$\dfrac{h^2}{12}(u_{xxxx}+u_{yyyy})$$u\in C^4$prop-fd-second-difference を各変数に
表の導出を開く

$u(x\pm h)=\sum_{k=0}^{m}(\pm h)^ku^{(k)}(x)/k!+O(h^{m+1})$ を代入し、低い階の項が消えるように係数を組む。前進差分は $u'+\tfrac h2u''+O(h^2)$。中心差分は偶数階の項が打ち消し合い $u'+\tfrac{h^2}6u'''+O(h^4)$。片側 3 点は $-3u(x)+4u(x+h)-u(x+2h)$ の $h^2$ の項が $(4-4)\tfrac{h^2}2u''=0$ となり、$h^3$ の項が $(4-8)\tfrac{h^3}6u'''=-\tfrac23h^3u'''$ で、$2h$ で割って $-\tfrac{h^2}3u'''$。1 階の 5 点公式は中心差分 $D_h$ と $D_{2h}$ の組み合わせ $(4D_h-D_{2h})/3$ で $h^2$ の項を消したもので、$h^4$ の項の係数は $(4-16)/3\cdot\tfrac1{120}=-\tfrac1{30}$。2 階の 5 点公式は $\delta^2_h$ と $\delta^2_{2h}$ の組み合わせ $(4\delta^2_h-\delta^2_{2h})/3$ で、$\delta^2_h$ の $u^{(6)}$ の項が $\tfrac{2h^4}{720}$ なので、係数は $(4-16)/3\cdot\tfrac2{720}=-\tfrac1{90}$。不等間隔の式は、$(u(x+h_2)-u(x))/h_2=u'+\tfrac{h_2}2u''+\tfrac{h_2^2}6u'''+\cdots$ と $(u(x)-u(x-h_1))/h_1=u'-\tfrac{h_1}2u''+\tfrac{h_1^2}6u'''-\cdots$ の差が $\tfrac{h_1+h_2}2u''+\tfrac{h_2^2-h_1^2}6u'''+\cdots$ であることから出る。

時間発展の方程式の代表的なスキームは次の表のとおり。打切り誤差の列は、厳密解を式に代入して Taylor 展開する計算で得られる(thm-fd-heat の証明の計算と同じである)。根拠の列は安定の条件の根拠を示す。以下、$\Delta x=1/J$、$U_j^n\approx u(x_j,t_n)$、$t_n=n\Delta t$ とし、$\delta^2$ は $h=\Delta x$ の 2 階中心差分を添字 $j$ について働かせたものとする。

方程式スキーム式打切り誤差安定の条件根拠
熱 $u_t=\kappa u_{xx}$陽解法$U_j^{n+1}=U_j^n+\kappa\Delta t\,\delta^2U_j^n$$O(\Delta t+\Delta x^2)$$r=\kappa\Delta t/\Delta x^2\le\tfrac12$thm-fd-heat、prop-fd-heat-necessary
同上陰解法$U_j^{n+1}=U_j^n+\kappa\Delta t\,\delta^2U_j^{n+1}$$O(\Delta t+\Delta x^2)$なし(無条件)prop-fd-theta
同上Crank–Nicolson 法$U_j^{n+1}=U_j^n+\tfrac12\kappa\Delta t\,\delta^2(U_j^{n+1}+U_j^n)$$O(\Delta t^2+\Delta x^2)$なし(無条件)prop-fd-theta
移流 $u_t+au_x=0$($a>0$)風上差分$U_j^{n+1}=U_j^n-\nu(U_j^n-U_{j-1}^n)$$O(\Delta t+\Delta x)$$\nu=a\Delta t/\Delta x\le1$prop-fd-upwind
同上時間前進・空間中心$U_j^{n+1}=U_j^n-\tfrac\nu2(U_{j+1}^n-U_{j-1}^n)$$O(\Delta t+\Delta x^2)$不安定($\nu>0$ のどの値でも)prop-fd-upwind
波動 $u_{tt}=c^2u_{xx}$2 階中心$U_j^{n+1}=2U_j^n-U_j^{n-1}+c^2\Delta t^2\,\delta^2U_j^n$$O(\Delta t^2+\Delta x^2)$$C=c\Delta t/\Delta x\le1$計算(畳んだ導出)
波動方程式の安定条件の導出を開く

$U_j^n=g^ne^{ij\xi}$ を代入すると、$s=\sin^2(\xi/2)$ として $g^2-2(1-2C^2s)g+1=0$ を得る。2 根の積は $1$ である。$\lvert1-2C^2s\rvert\le1$ なら 2 根は共役な複素数か重根で絶対値 $1$、そうでなければ実の 2 根で片方の絶対値が $1$ を超える。$\lvert1-2C^2s\rvert\le1$ がすべての $s\in[0,1]$ で成り立つ条件は $C\le1$ である。同じ条件は LL17 §2.10.3 の (2.89)(p. 160)にある。

打切り誤差の評価

差分法のすべての誤差評価は、次の不等式から始まる。

2 階中心差分の誤差

$u\in C^4[x-h,x+h]$ で $\lvert u^{(4)}\rvert\le M_4$ とすると
$$ \bigl\lvert\delta^2u(x)-u''(x)\bigr\rvert\le\frac{h^2}{12}M_4 . $$

Taylorの定理 より、ある $\xi_\pm$ が $x$ と $x\pm h$ のあいだにあって
$$ u(x\pm h)=u(x)\pm hu'(x)+\frac{h^2}2u''(x)\pm\frac{h^3}6u'''(x)+\frac{h^4}{24}u^{(4)}(\xi_\pm) $$
となる。2 式を足すと奇数階の項が消え、
$$ u(x+h)-2u(x)+u(x-h)=h^2u''(x)+\frac{h^4}{24}\bigl(u^{(4)}(\xi_+)+u^{(4)}(\xi_-)\bigr). $$
$h^2$ で割って $\lvert u^{(4)}(\xi_\pm)\rvert\le M_4$ を使うと、誤差は $\dfrac{h^2}{24}\cdot2M_4=\dfrac{h^2}{12}M_4$ 以下である。

2 点境界値問題

$q,f\in C[0,1]$、$q\ge0$ とする。境界値問題
$$ -u''+qu=f,\qquad u(0)=\alpha,\quad u(1)=\beta $$
を、内部の格子点で 2 階中心差分に置き換える。
$$ L_hU_j:=-\delta^2U_j+q_jU_j=f_j\quad(j=1,\dots,N-1),\qquad U_0=\alpha,\quad U_N=\beta . $$
未知数は $U_1,\dots,U_{N-1}$ で、係数行列は対角が $2/h^2+q_j$、その隣が $-1/h^2$ の 3 重対角行列である。3 重対角なら Gauss の消去法は帯を保つので、LU分解 を使って $O(N)$ 回の演算で解ける。
安定性は次の離散の最大値原理から出る。連続の場合の 最大値原理(楕円型偏微分方程式) と同じ形をしている。

離散の最大値原理

$q_j\ge0$ とし、$V_0,\dots,V_N$ が $L_hV_j\le0$($j=1,\dots,N-1$)を満たすとする。このとき
$$ \max_{0\le j\le N}V_j\le\max\{V_0,V_N,0\}. $$

$M=\max_jV_j$ とし、$M>\max\{V_0,V_N,0\}$ と仮定して矛盾を導く。$V_j=M$ となる $j$ の最小のものを取ると、$V_0< M$、$V_N< M$ より $1\le j\le N-1$ で、$V_{j-1}< M$、$V_{j+1}\le M$ である。また $M>0$ なので $q_jM\ge0$。したがって
$$ h^2L_hV_j=(2+h^2q_j)M-V_{j-1}-V_{j+1}\ge2M-V_{j-1}-V_{j+1}>0 $$
となり、$L_hV_j\le0$ に反する。

2 点境界値問題の誤差の上界

$q\ge0$ とする。差分方程式の解 $U$ はただ 1 つ存在する。$u\in C^4[0,1]$ が境界値問題の解で $\lvert u^{(4)}\rvert\le M_4$ なら、
$$ \lvert u(x_j)-U_j\rvert\le\frac{h^2}{24}M_4\,x_j(1-x_j)\le\frac{h^2}{96}M_4\qquad(j=0,\dots,N). $$

一意存在。 差分方程式は未知数と同じ個数の 1 次方程式である。$\alpha=\beta=0$、$f=0$ の解 $V$ に prop-fd-discrete-maximum-principle を $V$ と $-V$ に使うと $V=0$ なので、係数行列は単射、よって正則である。
安定性。 $\psi_j=x_j(1-x_j)/2$ とおく。$\psi$ は 2 次式なので 2 階中心差分は厳密で、$-\delta^2\psi_j=1$ である。また $\psi_j\ge0$。$E_0=E_N=0$ を満たす $E$ に対し $T=\max_j\lvert L_hE_j\rvert$ とおき、$V_j=\pm E_j-T\psi_j$ を考えると
$$ L_hV_j=\pm L_hE_j-T(1+q_j\psi_j)\le T-T=0 $$
であり、$V_0=V_N=0$ なので最大値原理から $V_j\le0$、すなわち $\lvert E_j\rvert\le T\psi_j$ である。
結論。 $E_j=u(x_j)-U_j$ とする。$-u''+qu=f$ を $x_j$ で使うと
$$ L_hE_j=-\delta^2u(x_j)+q_ju(x_j)-f_j=-\delta^2u(x_j)+u''(x_j). $$
prop-fd-second-difference より $T\le\tfrac{h^2}{12}M_4$ で、$E_0=E_N=0$ である。安定性の不等式に入れて
$$ \lvert E_j\rvert\le\frac{h^2}{12}M_4\cdot\frac{x_j(1-x_j)}2, $$
最後に $x(1-x)\le\tfrac14$ を使う。

$\psi$ を比較の相手に使う部分が安定性の証明で、$\|L_h^{-1}\|_\infty\le\tfrac18$ を示している。定数は $h$ によらない。
2 次元の Poisson 方程式 $-\Delta u=f$ を正方形の上で 5 点公式に置き換えた場合も、同じ議論で最大値原理が成り立つ。行列は $(N-1)^2$ 元で、各行の非零要素は高々 5 個の 疎 な行列になる。

安定なら収束する

時間発展の問題では、1 ステップの更新を繰り返す。整合性と安定性から収束が出るという見取り図は、ここでも 1 行の計算で確かめられる。

安定性と整合性から収束が従う

格子上のベクトル $U^n$ の更新を $U^{n+1}=CU^n+\Delta t\,F^n$ とし、厳密解の格子点の値 $u^n$ が
$$ u^{n+1}=Cu^n+\Delta t\,F^n+\Delta t\,\tau^n $$
を満たすとする。$n\Delta t\le T$ の範囲で $\|C^n\|\le M$ なら、$n\Delta t\le T$ に対し
$$ \|u^n-U^n\|\le M\Bigl(\|u^0-U^0\|+T\max_{k< n}\|\tau^k\|\Bigr). $$

$e^n=u^n-U^n$ とおくと $e^{n+1}=Ce^n+\Delta t\,\tau^n$ である。これを繰り返して
$$ e^n=C^ne^0+\Delta t\sum_{k=0}^{n-1}C^{n-1-k}\tau^k . $$
ノルムを取り、$\|C^m\|\le M$ と $n\Delta t\le T$ を使う。

逆に「整合したスキームが収束するなら安定である」ことは、一様有界性原理 を使って示される。定常な近似の枠組みでの同値(Lax の同値定理)は HN01 Theorem 5.53(p. 115)にあり、発展方程式でも類似の結果(Lax同値定理)があることが同じ箇所で注意されている。この記事では逆向きは証明しない。線形でない方程式では、このような一般の同値は成り立つとは限らない。

熱方程式の差分法

$u_t=\kappa u_{xx}$($0< x< 1$、$0< t\le T$)、$u(0,t)=u(1,t)=0$、$u(x,0)=u_0(x)$ を考える(熱方程式)。陽解法は、$r=\kappa\Delta t/\Delta x^2$ として
$$ U_j^{n+1}=rU_{j-1}^n+(1-2r)U_j^n+rU_{j+1}^n . $$
$r$ はこの方法のすべてを決める数である。

陽解法の誤差の上界

$r\le\tfrac12$ で、厳密解 $u$ は $u_{tt}$、$u_{xxxx}$ が連続で $\lvert u_{tt}\rvert\le A$、$\lvert u_{xxxx}\rvert\le B$ とする。$U_j^0=u_0(x_j)$ なら、$n\Delta t\le T$ に対し
$$ \max_j\lvert u(x_j,t_n)-U_j^n\rvert\le T\Bigl(\frac{\Delta t}2A+\frac{\kappa\Delta x^2}{12}B\Bigr). $$

内部の格子点の値のベクトルに対し、更新は $U^{n+1}=CU^n$ と書ける。$C$ の成分は $r$ と $1-2r$ で、$r\le\tfrac12$ よりすべて $0$ 以上、各行の和は $1$ 以下である。よって最大値ノルムの作用素ノルムは $\|C\|_\infty\le1$ で、$\|C^n\|_\infty\le1$ である。
打切り誤差を評価する。時間の Taylorの定理 と $u_t=\kappa u_{xx}$ より
$$ \tau_j^n=\frac{u_j^{n+1}-u_j^n}{\Delta t}-\kappa\delta^2u_j^n =\Bigl(u_t+\frac{\Delta t}2u_{tt}(x_j,\theta)\Bigr)-\kappa\delta^2u_j^n =\frac{\Delta t}2u_{tt}(x_j,\theta)+\kappa\bigl(u_{xx}-\delta^2u\bigr)(x_j,t_n) $$
($\theta$ は $t_n$ と $t_{n+1}$ のあいだの点)。prop-fd-second-difference から $\lvert\tau_j^n\rvert\le\tfrac{\Delta t}2A+\tfrac{\kappa\Delta x^2}{12}B$ である。$e^0=0$ なので、prop-fd-lax を $M=1$ として使えば結論を得る。

条件 $r\le\tfrac12$ を外すと、この証明の「成分が $0$ 以上」が成り立たない。証明が通らないだけでなく、結論も成り立たない。

陽解法の不安定性

内部の格子点の値のベクトル $v^{(k)}=(\sin k\pi x_j)_{j=1}^{J-1}$($k=1,\dots,J-1$)は陽解法の更新の固有ベクトルで、固有値は
$$ g_k=1-4r\sin^2\frac{k\pi\Delta x}2 $$
である。$r>\tfrac12$ を固定すると、$\Delta x$ が十分小さいとき $\lvert g_{J-1}\rvert>1$ で、初期値の $v^{(J-1)}$ の成分は 1 ステップごとに $\lvert g_{J-1}\rvert$ 倍に増える。

加法定理より
$$ \sin k\pi x_{j+1}+\sin k\pi x_{j-1}=2\cos(k\pi\Delta x)\sin k\pi x_j $$
で、境界の格子点では $\sin k\pi x_0=\sin k\pi x_J=0$ だから、$v^{(k)}$ に対して
$$ rv_{j-1}^{(k)}+(1-2r)v_j^{(k)}+rv_{j+1}^{(k)}=\bigl(1-2r(1-\cos k\pi\Delta x)\bigr)v_j^{(k)}=g_kv_j^{(k)} . $$
$k=J-1$ のとき $k\pi\Delta x=\pi-\pi\Delta x$ なので $g_{J-1}=1-4r\cos^2(\pi\Delta x/2)$ である。$\Delta x\to0$ で $g_{J-1}\to1-4r<-1$ だから、$\Delta x$ が十分小さければ $g_{J-1}<-1$ である。

$\Delta x$ を小さくしながら $r$ を固定すると、時刻 $T$ までのステップ数 $T/\Delta t$ は増えるので、$\lvert g_{J-1}\rvert^{T/\Delta t}$ は爆発する。厳密な計算なら $v^{(J-1)}$ の成分が $0$ の初期値もあるが、丸め誤差があればこの成分は必ず入る。一方 $r\le\tfrac12$ なら $-1\le g_k\le1$ である。
陰解法と Crank–Nicolson 法は、次の $\theta$ 法にまとめられる。
$$ \frac{U_j^{n+1}-U_j^n}{\Delta t}=\kappa\bigl(\theta\,\delta^2U_j^{n+1}+(1-\theta)\,\delta^2U_j^n\bigr)\qquad(0\le\theta\le1). $$
$\theta=0$ が陽解法、$\theta=1$ が陰解法、$\theta=\tfrac12$ が Crank–Nicolson 法である。$\theta>0$ では、各ステップで 3 重対角の連立 1 次方程式を解く。

$\theta$ 法の増幅率と安定性

$\theta$ 法の更新は $v^{(k)}$ を固有ベクトルにもち、$s_k=\sin^2(k\pi\Delta x/2)$ として固有値は
$$ g_k=\frac{1-4(1-\theta)rs_k}{1+4\theta rs_k} $$
である。$\tfrac12\le\theta\le1$ なら、どの $r>0$ でも Euclid ノルムで $\|U^{n+1}\|\le\|U^n\|$ である。$0\le\theta<\tfrac12$ なら、$r\le\dfrac1{2(1-2\theta)}$ のとき同じ不等式が成り立つ。

prop-fd-heat-necessary の計算から、$\Delta x^2\delta^2v^{(k)}=-4s_kv^{(k)}$ である。$U^n=v^{(k)}$、$U^{n+1}=gv^{(k)}$ を $\theta$ 法に入れると $g-1=-4rs_k(\theta g+1-\theta)$ となり、これを解いて表示式を得る。
$v^{(1)},\dots,v^{(J-1)}$ は実対称行列 $\Delta x^2\delta^2$ の相異なる固有値の固有ベクトルなので直交基底をなす。よって $\|U^{n+1}\|\le\|U^n\|$ は、すべての $k$ で $\lvert g_k\rvert\le1$ であることから従う。$g_k\le1$ は分子が分母以下であることから明らかで、$g_k\ge-1$ は
$$ 1-4(1-\theta)rs_k\ge-1-4\theta rs_k\iff2rs_k(1-2\theta)\le1 $$
と同値である。$\theta\ge\tfrac12$ なら左辺は $0$ 以下で成り立ち、$\theta<\tfrac12$ なら $s_k<1$ より $r\le1/(2(1-2\theta))$ で成り立つ。

安定性の議論のこの形は、Fourier 成分 $e^{ij\xi}$ を代入して増幅率を調べる方法(von Neumann の方法)である。陽解法の増幅率と安定の条件は LL17 §3.3((3.54) p. 234、(3.57) p. 235)にある。この方法は、定数係数で周期境界か、上のように固有ベクトルが分かる場合に完全な証明になる。
図: 陽解法を r=0.4(左)と r=0.6(右)で計算した結果。左は厳密解に沿って減衰し、右は格子ごとに符号が反転する成分が増える 図: 陽解法を r=0.4(左)と r=0.6(右)で計算した結果。左は厳密解に沿って減衰し、右は格子ごとに符号が反転する成分が増える

移流方程式と CFL 条件

$a>0$ とし、$u_t+au_x=0$、$u(x,0)=u_0(x)$ を考える。厳密解は $u(x,t)=u_0(x-at)$ で、情報は右へ速さ $a$ で運ばれる。$\nu=a\Delta t/\Delta x$ とおく。

風上差分の安定性と中心差分の不安定性

$U_j^n=g(\xi)^ne^{ij\xi}$($\xi\in\mathbb{R}$)を代入すると、増幅率は次のとおりである。

  1. 風上差分:$g=1-\nu+\nu e^{-i\xi}$、$\lvert g\rvert^2=1-2\nu(1-\nu)(1-\cos\xi)$。特に、すべての $\xi$ で $\lvert g\rvert\le1$ となることと $\nu\le1$ は同値である。
  2. 時間前進・空間中心:$g=1-i\nu\sin\xi$、$\lvert g\rvert^2=1+\nu^2\sin^2\xi$。$\nu>0$ なら $\sin\xi\ne0$ の成分は必ず増える。
    また $0\le\nu\le1$ の風上差分は $U_j^{n+1}=(1-\nu)U_j^n+\nu U_{j-1}^n$ と凸結合で書けるので、$\max_j\lvert U_j^{n+1}\rvert\le\max_j\lvert U_j^n\rvert$ である。

代入すると、1. は $g=1-\nu(1-e^{-i\xi})$、2. は $g=1-\tfrac\nu2(e^{i\xi}-e^{-i\xi})=1-i\nu\sin\xi$ である。1. の絶対値は
$$ \lvert g\rvert^2=(1-\nu)^2+\nu^2+2\nu(1-\nu)\cos\xi=1-2\nu(1-\nu)(1-\cos\xi). $$
$1-\cos\xi\ge0$ なので、すべての $\xi$ で $\lvert g\rvert\le1$ となるのは $\nu(1-\nu)\ge0$ のときに限る。$\xi=\pi$ で $\lvert g\rvert=\lvert1-2\nu\rvert$ であることからも確かめられる。残りの主張は式から明らかである。

次の命題は安定性解析によらず、解の情報が届かない ことから収束を否定する。

CFL 条件の必要性

実数直線上の格子で、比 $\lambda=\Delta t/\Delta x$ を固定して $\Delta x\to0$ とする風上差分を考える。$a\lambda>1$ なら、滑らかな初期値 $u_0$ で、ある点で近似解が厳密解に収束しないものがある。

更新の式から、$U_j^n$ は $u_0(x_j),u_0(x_{j-1}),\dots,u_0(x_{j-n})$ だけで決まる。これらの点は区間 $[x_j-n\Delta x,x_j]$ にある。$t>0$ を固定し、$(x_j,t_n)=(0,t)$ となるように格子を取ると、$n\Delta x=t/\lambda$ である。したがって $U_j^n$ が見るのは $[-t/\lambda,0]$ の中の $u_0$ の値だけである。
一方、厳密解は $u(0,t)=u_0(-at)$ で、$a\lambda>1$ より $-at<-t/\lambda$ である。そこで $u_0$ を、$[-t/\lambda,0]$ で $0$、点 $-at$ で $1$ となる滑らかな関数に取る。このときすべての格子で $U_j^n=0$ だが、$u(0,t)=1$ である。

同じ議論から、陽解法で計算の依存領域が厳密解の依存領域を含むこと が収束の必要条件になる。これが CFL条件(Courant–Friedrichs–Lewy 条件)の考え方である。熱方程式の解は時刻 $t>0$ で初期値全体に依存するので、この議論だけでも陽解法には $\Delta t/\Delta x\to0$ が要る。実際の制限はさらに強い $\Delta t=O(\Delta x^2)$ である。風上差分の説明は LL17 §4.1.4(p. 331)、時間前進・空間中心の不安定な振る舞いは同書 §4.1(p. 327)にある。

計算の手順

微分方程式を差分法で解く標準の手順は次のとおり。

  1. 方程式の型を確かめる:楕円型(楕円型偏微分方程式、境界値問題)か、放物型(放物型偏微分方程式、熱方程式)か、双曲型(双曲型偏微分方程式、移流・波動)か。型で下の表の分岐が決まる。
  2. 格子を決める:$\Delta x$(2 次元なら $\Delta y$ も)、時間発展なら $\Delta t$。無次元の比 $r$、$\nu$、$C$ を計算する。
  3. 差分公式を当てる:内部の格子点で公式の表の式に置き換える。$(au')'$ の形は保存形の式を使う。
  4. 境界条件を入れる:下の表による。
  5. 解く・進める:楕円型は連立 1 次方程式(1 次元は 3 重対角の LU分解、2 次元以上は反復法か疎行列の直接法)。時間発展は 1 ステップずつ進める。
  6. 収束を確かめる:$h$ を半分にして誤差か差分の比を見る。$\log_2$(誤差の比)が理論の次数 $p$ に近いことを確かめる。

止める判定と失敗の見分け方。 楕円型の連立方程式を反復法で解くときは、残差 $\|f_h-L_hU^{(k)}\|$ が右辺のノルムの許容誤差倍(たとえば $10^{-8}$ 倍)以下になったら止め、反復の上限を置く。ただし離散の解の誤差 $O(h^2)$ より小さくしても得るものはない。時間発展では、値が急に大きくなる、格子ごとに符号が反転する、という症状が不安定の兆候である。

方程式の型差分の選び方刻みの制限連立方程式
楕円型 $-u''+qu=f$2 階中心差分なし($q\ge0$)毎回 1 回解く
放物型(陽解法)時間前進・空間 2 階中心$r\le\tfrac12$不要
放物型(陰解法・Crank–Nicolson 法)prop-fd-theta安定性の制限はなし各ステップで解く
双曲型(移流)風上差分$\nu\le1$不要
移流拡散 $-au''+bu'=0$中心差分はセル Péclet 数 $\lvert b\rvert h/(2a)$ が $1$ 未満のとき風上差分なら制限なし(精度は 1 次)毎回 1 回解く
境界条件差分での入れ方精度
:--:--:--
Dirichlet $u(1)=\beta$$U_N=\beta$ を右辺へ移す内部の式と同じ 2 次
Neumann $u'(1)=g$、仮想点仮想の点 $U_{N+1}$ を置き、$(U_{N+1}-U_{N-1})/(2h)=g$ と $x_N$ での内部の式から消去する2 次
Neumann $u'(1)=g$、片側差分$(U_N-U_{N-1})/h=g$1 次
周期$U_{J+m}=U_m$ と番号をつなぐ内部の式と同じ

仮想の点を使う方法は LL17 §2.6.2(p. 126)と §2.6.6(p. 132)にある。

例題

$-u''=\pi^2\sin\pi x$、$u(0)=u(1)=0$

使う公式:thm-fd-bvp。答え:厳密解は $u=\sin\pi x$。$h=\tfrac14$ で $U_2\approx1.05303$($u(\tfrac12)=1$)。誤差の上界は $\tfrac{h^2}{96}\pi^4\approx0.0634$ で、実際の誤差は $0.0530$ である。

$N$$U(\tfrac12)$最大誤差上界 $\pi^4h^2/96$次数
41.0530295.303e−26.342e−2—
81.0129511.295e−21.585e−22.03
161.0032193.219e−33.964e−32.01
321.0008048.036e−49.909e−42.00
途中の計算を開く

$v_j=\sin\pi x_j$ は prop-fd-heat-necessary の $k=1$ の固有ベクトルで、$-\delta^2v=\lambda v$、$\lambda=\tfrac4{h^2}\sin^2\tfrac{\pi h}2$ である。よって離散の解は $U_j=\tfrac{\pi^2}\lambda\sin\pi x_j$ と閉じた形で書ける。$h=\tfrac14$ では $\lambda=64\sin^2\tfrac\pi8\approx9.37258$ で、$U_2=\pi^2/\lambda\approx1.05303$。

仮想の点と片側差分の比較

$-u''=\tfrac{\pi^2}4\sin\tfrac{\pi x}2$、$u(0)=0$、$u'(1)=0$(厳密解 $u=\sin\tfrac{\pi x}2$)を解く。使う公式:境界条件の表。答え:$N=32$ の最大誤差は、仮想の点で $2.01\times10^{-4}$、片側差分で $3.84\times10^{-2}$ である。$N$ を 2 倍にしたときの次数は、それぞれ $2.00$、$0.99$ である。境界の 1 か所の精度が全体の精度を決める。

途中の計算を開く

仮想の点の場合:$(U_{N+1}-U_{N-1})/(2h)=0$ から $U_{N+1}=U_{N-1}$ で、$x_N$ の内部の式は $(-2U_{N-1}+2U_N)/h^2=f_N$ となる。$N$ 元の 3 重対角方程式を解く。片側差分の場合:最後の式を $U_N-U_{N-1}=0$ に替える。$N=4,8,16,32,64$ の誤差は、仮想の点で $1.295\times10^{-2}$、$3.219\times10^{-3}$、$8.036\times10^{-4}$、$2.008\times10^{-4}$、$5.020\times10^{-5}$、片側差分で $0.2955$、$0.1510$、$0.0763$、$0.0384$、$0.0192$。

図: 最大誤差と刻み幅の両対数グラフ。Dirichlet 条件と仮想の点は傾き 2、片側差分は傾き 1 図: 最大誤差と刻み幅の両対数グラフ。Dirichlet 条件と仮想の点は傾き 2、片側差分は傾き 1

単位正方形の Poisson 方程式

$-\Delta u=1$($(0,1)^2$ の上)、境界で $u=0$ を 5 点公式で解く。答え:中心の値は $h=\tfrac12$ で $\tfrac1{16}=0.0625$、$h=\tfrac14$ で $\tfrac9{128}\approx0.070313$、$h=\tfrac18$ で $0.072783$、$h=\tfrac1{64}$ で $0.073657$ である。Fourier の 2 重正弦級数の和による値は $0.07367$ で、中心の値の差は $h=\tfrac1{16}$ のあたりから $h$ を半分にするごとに約 $1/4$ になる。

途中の計算を開く

$h=\tfrac14$ では内部の点が 9 個ある。対称性から、角の隣の $a$、辺の中央の $b$、中心の $c$ の 3 種類に減り、$4a-2b=h^2$、$4b-2a-c=h^2$、$4c-4b=h^2$ を解いて $a=\tfrac{11}{256}$、$b=\tfrac7{128}$、$c=\tfrac9{128}$。比較の級数は $u(\tfrac12,\tfrac12)=\sum_{m,n\ \text{奇数}}\dfrac{16\sin(m\pi/2)\sin(n\pi/2)}{\pi^4mn(m^2+n^2)}$。この問題では解が正方形の角で滑らかでないので、thm-fd-bvp と同じ形の評価を仮定なしに当てはめることはできない。

陽解法の $r=0.4$、$0.5$、$0.6$

$u_t=u_{xx}$、$u(0,t)=u(1,t)=0$、$u(x,0)=\min(x,1-x)$ を $\Delta x=\tfrac1{20}$ で、$t\approx0.1$ まで計算する。使う公式:thm-fd-heat、prop-fd-heat-necessary。

$r$ステップ数$t$$U(\tfrac12)$厳密解 $u(\tfrac12,t)$増幅率 $g_{19}$
0.41000.10000.1509370.151059−0.5902
0.5800.10000.1516850.151059−0.9877
0.6670.1005$-7.65\times10^6$0.150315−1.3852

答え:$r=0.6$ だけ計算が破綻する。$r=0.5$ は破綻しないが、増幅率が $-1$ に近い成分がほとんど減らず、$r=0.4$ より誤差が大きい。

途中の計算を開く

厳密解は $u(x,t)=\sum_{k\ \text{奇数}}\dfrac{4\sin(k\pi/2)}{k^2\pi^2}\sin(k\pi x)e^{-k^2\pi^2t}$。$r=0.6$ の値の大きさは最高波数の成分で説明できる。初期値の $v^{(19)}$ の成分は約 $-0.002515$ で、$g_{19}^{67}$ 倍すると大きさ約 $7.63\times10^6$ となり、計算された値の大きさとほぼ一致する。増幅率の値は prop-fd-heat-necessary の式による。

熱方程式の 3 つの方法の次数

$u_t=u_{xx}$、$u(x,0)=\sin\pi x$、$T=0.1$(厳密解 $e^{-\pi^2t}\sin\pi x$、$u(\tfrac12,0.1)\approx0.372708$)を解く。使う公式:prop-fd-theta。陽解法と陰解法は $r=0.1$ に固定し、Crank–Nicolson 法は $\Delta t=0.1\,\Delta x$($r=\tfrac{1}{10}J$)とする。

$J$陽解法の誤差陰解法の誤差Crank–Nicolson 法の誤差
101.220e−34.820e−32.734e−3
203.032e−41.209e−36.821e−4
407.567e−53.025e−41.705e−4
801.891e−57.563e−54.261e−5

答え:どれも $J$ を 2 倍にすると誤差は約 $1/4$ になる。ただし陽解法と陰解法は $\Delta t$ を $1/4$ にしてそうなるのに対し、Crank–Nicolson 法は $\Delta t$ を $1/2$ にするだけでよい。$J=80$ で必要なステップ数は、順に $6400$、$6400$、$80$ である。

途中の計算を開く

初期値が $v^{(1)}$ なので、数値解は $g_1^n\sin\pi x_j$ と閉じた形で書ける($g_1$ は prop-fd-theta の式)。陽解法の誤差の上界は thm-fd-heat で $A=B=\pi^4$ として、$J=10$ で $1.30\times10^{-2}$、$J=40$ で $8.12\times10^{-4}$ で、実際の誤差はその約 $1/10$ である。

周期境界の移流方程式

$u_t+u_x=0$、$u(x,0)=\sin2\pi x$、周期 $1$、$\Delta x=\tfrac1{50}$、$T=1$ で計算する。厳密解は $T=1$ で初期値に戻る。使う公式:prop-fd-upwind。

スキーム$\nu$最大の $\lvert U\rvert$最大誤差$\max_\xi\lvert g\rvert$
風上0.50.81910.17891
風上10.998$0$(丸め誤差を除く)1
風上1.251.1020.10351.5
時間前進・空間中心0.51.2160.21791.118

答え:$\nu=1$ の風上差分は $U_j^{n+1}=U_{j-1}^n$ で、格子点の上では厳密である。$\nu=0.5$ は安定だが振幅が減る。これは 1 次のスキームの数値的な拡散で、$\lvert g\rvert<1$ による。

途中の計算を開く

初期値の波数は $\xi=2\pi\Delta x$ である。$\nu=0.5$ では $\lvert g(\xi)\rvert^{100}\approx0.8208$ で、計算の振幅に合う(格子の上の初期値の最大値が $0.998$ なので、$0.998\times0.8208\approx0.819$)。$\nu=1$ の最大の $\lvert U\rvert$ が $1$ でなく $0.998$ なのは、格子点に $\sin2\pi x$ の最大の点がないためである。

使える条件と反例

thm-fd-bvp・thm-fd-heat・prop-fd-upwind の条件と、公式の表・手順の表の条件を 1 つずつ外すと、次のようになる。

外す条件反例成り立たなくなること
$u\in C^4$$-u''=f$、$u=x^{3/2}-x$打切り誤差が $x_1$ で $O(h^{-1/2})$ に増え、誤差の次数が 2 に届かない
$q\ge0$$h=\tfrac14$、$q=-\lambda_1$($\lambda_1\approx9.3726$)差分方程式の係数行列が特異になり、逆行列のノルムの上界 $\tfrac18$ も成り立たない
$r\le\tfrac12$ex-fd-heat-stability の $r=0.6$誤差の上界が成り立たず、安定性が失われ、計算が発散する
風上の向き$a>0$ で $U_j^{n+1}=U_j^n-\nu(U_{j+1}^n-U_j^n)$$\lvert g\rvert$ の最大値が $1+2\nu$ となり、どの $\nu>0$ でも不安定
セル Péclet 数 $c< 1$$-0.01u''+u'=0$、$u(0)=0$、$u(1)=1$、$N=10$ の中心差分厳密解は単調なのに、数値解が振動する
等間隔間隔が $h$、$2h$ と交互の格子に $(u_{j+1}-2u_j+u_{j-1})/\bar h^2$ を使う整合性が失われ、$u=x^2$ でも差分商が $O(1/h)$ で発散する
滑らかさを外す

$u=x^{3/2}-x$ は $u(0)=u(1)=0$、$-u''=-\tfrac34x^{-1/2}=:f$ を満たすが、$u''$ は $x=0$ で有界でない。$x_1=h$ での打切り誤差は $h^{-1/2}$ に比例し、$N=16$ で $0.314$、$N=256$ で $1.255$ と増える。それでも誤差は減るが、最大誤差の次数は $N=1024\to2048$ で $1.47$ で、2 次には届かない($N=2048$ の誤差は $1.55\times10^{-6}$)。これは thm-fd-bvp の仮定 $u\in C^4$ が満たされていないことによる。

符号の条件を外す

$h=\tfrac14$ のとき $-\delta^2$ の固有値は $\lambda_k=64\sin^2\tfrac{k\pi}8$ で、最小は $\lambda_1\approx9.3726$ である。$q\equiv-\lambda_1$ なら $L_h$ は特異で、$f$ によっては解がない。$q\equiv-9$ なら正則だが、$f\equiv1$ の解は $(U_1,U_2,U_3)\approx(2.294,3.235,2.294)$ で、$\|L_h^{-1}\|_\infty\approx3.24$ と $\tfrac18$ を大きく超える。

移流が強い問題の中心差分

$-au''+bu'=0$、$u(0)=0$、$u(1)=1$ の厳密解は $u=(1-e^{Rx})/(1-e^R)$($R=b/a$)で、単調である。$a=0.01$、$b=1$、$N=10$ とすると、セル Péclet 数は $c=Rh/2=5$ である。中心差分の解は $\sigma=(1+c)/(1-c)=-1.5$ として $U_j=(1-\sigma^j)/(1-\sigma^N)$ で、$U_1,\dots,U_9\approx-0.0441,\,0.0221,\,-0.0772,\,0.0717,\,-0.1517,\,0.1834,\,-0.3192,\,0.4346,\,-0.6961$ と符号が交互に変わる。$u'$ を後退差分(風上)に替えると $U_9\approx0.0909$ で、$U_j$ は単調になる。厳密解は $u(0.9)\approx4.5\times10^{-5}$ であり、風上差分の解は境界層(特異摂動)の近くで広がっている。式は Saa03 §2.2.4(pp. 54–55)による。

不等間隔の格子に等間隔の式を使う

$x_{j+1}-x_j=2h$、$x_j-x_{j-1}=h$ の点で、平均の間隔 $\bar h=\tfrac32h$ を使った $(u_{j+1}-2u_j+u_{j-1})/\bar h^2$ を $u=x^2$ に当てる。計算すると $\tfrac{8x_j}{9h}+\tfrac{20}9$ となり、$x_j=1$、$h=0.01$ で約 $91.1$ である。真の値は $2$ で、$h\to0$ で発散する。公式の表の不等間隔の式なら、$u=x^2$ に対して $h$ によらず $2$ である。

よくある誤り

誤り正しくはなぜ
打切り誤差が小さいので解も正確と思う安定性も確かめる打切り誤差は $L_h^{-1}$ のノルムの倍率で解の誤差になる(prop-fd-lax、ex-fd-heat-stability)
$\Delta x$ を半分にして $\Delta t$ はそのままにする陽解法では $\Delta t$ を $1/4$ にする$r$ が 4 倍になる(thm-fd-heat)
陰解法なら $\Delta t$ はいくら大きくてもよい安定でも精度は $\Delta t$ で決まる陰解法の時間の誤差は $O(\Delta t)$。Crank–Nicolson 法でも大きな $r$ の高波数の成分は $g\approx-1$ でほとんど減らない
境界だけ片側差分のままにする仮想の点か片側 3 点の公式を使う全体の次数が 1 に落ちる(ex-fd-neumann)
$(au')'$ を $au''+a'u'$ に直して $a$ の跳びを無視する保存形の式を使う$a$ が不連続だと展開が使えない
移流項に中心差分を使って振動を見逃すセル Péclet 数を確かめるex-fd-peclet

補足

Crank–Nicolson 法の高波数。 $s=1$ のとき $g=(1-2r)/(1+2r)$ で、$r=10$ で $-0.905$、$r=100$ で $-0.990$ である。無条件に安定だが、大きな $r$ では格子ごとに振動する成分がほとんど減らない。
有限要素法との関係。 等間隔の 1 次元格子で区分 1 次の 有限要素法 を使うと、$-u''$ の行列は差分法と $h$ 倍の違いしかない。差が出るのは右辺の扱いと、不規則な領域での格子の作り方である。
名前の似た別のもの。 差分商の方法 は偏微分方程式の解の正則性を示す解析の道具で、数値計算の方法ではない。差分作用素そのものの計算は 数列の和と差分 が扱う。高校の範囲の差分商は 差分近似(高校数学) にある。
参考文献の所在。 差分公式と 1 次元の問題の行列は Saa03 §2.2(pp. 50–55)、熱・波動・移流方程式の差分スキームの計算は LL17 第 2〜4 章にある。Lax の同値定理の抽象的な形は HN01 §5.5(pp. 114–115)にある。

関連項目

参考文献

[1]
John K. Hunter, Bruno Nachtergaele, Applied Analysis, World Scientific, 2001, §5.5、Theorem 5.53(Lax equivalence、pp. 114–115)(番号と頁は著者公開版)
[2]
Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, §2.2(pp. 50–55、差分公式 (2.8)–(2.17)、(2.16) の保存形、1 次元の行列、§2.2.4 風上差分)
[3]
Hans Petter Langtangen, Svein Linge, Finite Difference Computing with PDEs: A Modern Software Approach, Texts in Computational Science and Engineering 16, Springer, 2017, §2.6.2(p. 126、仮想の点の消去)、§2.6.6(p. 132、仮想の点の実装)、§2.10.3 (2.89)(p. 160、波動方程式の安定条件)、§3.3((3.54) p. 234、(3.57) p. 235)、§4.1(p. 327、§4.1.4 p. 331)

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