06. 時間対称スキーム, Runge-Kutta法
Photo by James Cheung on Unsplash
Euler 法よりも良い方法は?
単純な常微分方程式を Euler 法「以外」で計算しようとすると、一般にはどんな技術が必要になるだろうか?:
Euler 法は簡単で扱いやすいんだけれども、パラメータを少し変えると不安定になっていたし、 時間方向の対称性を捨てているから近似精度も悪い. それに、近似解の挙動が「真の解の挙動よりも常に遅れる」というのは偏りが強い、悪い特徴だ.
そこで、もう少し良い近似解法が考えられないか、検討してみよう.
対象の微分方程式
対象として、前回扱った小型人工衛星の温度 $u(t)$ の変化のモデル方程式 \begin{equation} \frac{du}{dt} = 1 + \frac{1}{2} \sin(t) - u^4 . \label{eq:tvmas} \end{equation} を考えよう. ただし初期値 $u(0)$ については $(1/2)^{1/4} \leq u(0) \leq ( 3/2 )^{1/4}$ としておく.
まずは、「対称な」スキームを扱ってみよう
対称なスキームとは
時間刻み幅 $\Delta t$ を一定にして、微分を含め、全体を「時間方向に対称に」近似する, いいかえれば、Taylor 展開の中心点を $t = (n + 1 / 2)\Delta t$ にとることがもっとも素直になるような近似をする、ということで近似計算式(スキーム)を作ることを考えよう.
以降、$u_n \cong u(n\Delta t)$ と想定した近似値 $u_n$ を用いて話を進めよう.
こうした時間方向に対称なスキームは無数に作れる. が、ここではなるべくシンプルに近似を作ってみよう.
つまり、時間微分項 $du / dt$ を時間 $t = (n+ 1 / 2)\Delta t$ で中心対称な差分 $(u_{n+1} - u_n) / \Delta t$ で近似し、 他の部分に出てくる $u(t)$ は時間方向の平均 $(u_{n+1} + u_n) / 2$ などで近似するという感じだ.
今回の対象としている微分方程式にこうしたシンプルな対称な近似を行ってみると、例えば
\begin{equation} \frac{u_{n+1} - u_n}{\Delta t} = 1 + \frac{1}{2} \sin\left( (n + \frac{1}{2})\Delta t \right) - \left( \frac{u_{n+1} + u_n}{2} \right)^4 \label{eq:symm-scheme} \end{equation}
というような近似式が得られる.
この近似式を採用したとしよう. さて、どうやって $u_{n+1}$ を計算しようか. $u_n$ は既知という状況で $u_{n+1}$ は未知とすると、この未知量をどう求めたら良いかを考える必要がある.
これには,以前の授業
の知識が使える. そのつもりで少し丁寧に議論を続けよう.
$\def\up{u^{+}}$ $\def\u{u}$ まず、分かりやすいように未知量を $u_{n+1} = \up$, 既知量を $u_n = \u$ と表記して上の近似式を整理しよう. この問題では時間 $t = n\Delta t$ が式に陽に含まれている為に時間ステップ数 $n$ を明示して、
\begin{equation} f(\up, \u, n) := \up - \u - \Delta t \left( 1 + \frac{1}{2} \sin\left( (n+\frac{1}{2})\Delta t\right) - \left(\frac{ \up + \u }{2}\right)^4 \right) \label{eq:symm-scheme-zero-func} \end{equation}
と定義すれば、
与えられた $\u$, $n$ に対して $f(\up, \u, n)$ がゼロになるような $\up$ を求める
ことで、$\u$ から $\up$ へと近似解の時間ステップを 1つ進められる、ことになる.
あとは既知である初期値 $u_0 = u(0)$ を最初の情報として、上の考え方で $u_1, u_2, \cdots$ と順番に求めていけば好きなだけ先の近似値を計算できる.
そして、この計算方法で数値計算をすすめていけると見込めたので、近似式 $(\ref{eq:symm-scheme})$ を今回の問題に対する「対称な」数値計算スキームと呼んでおこう.
式 $(\ref{eq:symm-scheme-zero-func})$ を満たす $\up$ を求める方法として Newton 法を用いてみる
復習を兼ねて、この問題を対象として Newton法を丁寧に適用してみよう.
まず、$f(\up,\u, n)$ の $\up$ に関する微分を求めよう. これは簡単で、
\begin{equation} \frac{df}{d\up} = 1 + 2 \,\Delta t \left( \frac{\up+\u}{2} \right)^3 \end{equation}
となる.
これで Newton 法を適用できる. まず,準備段階は以下のようになるだろう.
1# 定数の設定
2Δt = 0.1
3
4# 関数 f(up,u,n). 時間に依存する.
5f(up, u, n) = up - u - Δt * ( 1 + (1/2)*sin( (n+(1/2))*Δt ) - ( (up+u)/2 )^4 )
6
7# 微分 df/d(up). たまたまだが時間に依存しない.
8df(up, u) = 1 + 2 * Δt * ( (up+u)/2 )^3
そして,Newton 法で今の近似値 $\u$ から新しい時間ステップの近似値 $\up$ を求める関数を次のように定義する.
1# Newton 法で、u_old (← uのこと.紛れないように old という添字をつけておく)
2# から up を求める
3#
4function newton(u_old, n)
5 up = u_old # とりあえず、初期値を古い値 u_old と一致させておいて…
6
7 for i in 1:100 # この繰り返しの変数 i には特に意味はない
8 if abs( f(up,u_old,n) ) < 1.0e-8 # 8桁あってれば
9 break # ループ(この場合は for )から脱出する.
10 end
11 up = up - f(up,u_old,n)/df(up,u_old) # Newton 法で up を改善する.
12 end
13
14 return up # f が十分にゼロに近くなったら、近似値 up を返す
15end
これで準備が整ったので、実際に数値計算をして時間発展をさせてみよう.
1u0 = 0.9 # 初期値は前回と同じもの
2u = u0 # 「今」の値は、もちろん最初は初期値そのもの.
3u_sq = [ u ] # 記録をとっておく.初期値を最初に配列に入れておく.
4
5for n in 0:99 # n が時間ステップを表す.つまり、式の中に出てくるので丁寧に考える.
6 u = newton(u, n) # Newton 法で新しい時間ステップの値が求まって出てくるはず.
7 push!(u_sq, u) # その値を配列に追加していく.
8end
計算がスムーズに終わっているようなので、早速、グラフにしてみてみよう.
1using Plots
2
3t_range = 0:Δt:100Δt # 時間の範囲.初期値 0 から 100Δt まで 101点になる.
4
5plot(t_range, u_sq, marker = :circle,
6 xlabel = "t", ylabel = "u", legend = false)
どうやら無事に計算がうまくいっているようだ.まずはめでたしめでたし.
Euler 法は不安定だったけどこの「対称なスキーム using Newton法」はどうかな?
前回みたように、Euler 法はパラメータの値によっては数値計算としては失敗した. この数値スキームはどうだろうか?
Euler スキームでは数値計算に失敗したパラメータ $\Delta t = 0.5$ に設定して、今回のスキームでもう一度計算してみよう.
1Δt = 0.5
2u = u0 # 「今」の値は、もちろん最初は初期値そのもの.
3u_sq = [ u ] # 記録をとっておく.初期値を最初に配列に入れておく.
4
5for n in 0:99 # n が時間ステップを表す.つまり、式の中に出てくるので丁寧に考える.
6 u = newton(u, n) # Newton 法で新しい時間ステップの値が求まって出てくるはず.
7 push!(u_sq, u) # その値を配列に追加していく.
8end
9
10t_range = 0:Δt:100Δt # 時間範囲.初期値 0 から 100Δt まで 101点になる.
11plot(t_range, u_sq, marker = :circle,
12 xlabel = "t", ylabel = "u", legend = false)
おお、これはきちんと動作するぞ. ちょっとばかり手間だけれども、「対称なスキーム using Newton法」は Euler 法より安心して使えそうだ.
式 $(\ref{eq:symm-scheme-zero-func})$ を満たす $\up$ を求める方法としてライブラリを用いてみる
これまた復習を兼ねて、以前学習した、NLsolve パッケージを使ってみよう. まず、このパッケージを用いる際のルーチン的な手続きは以下の通りだった.これを実行しよう.
1using NLsolve
2
3function nls(func, params...; ini = [0.0])
4 if typeof(ini) <: Number
5 r = nlsolve((vout,vin)->vout[1]=func(vin[1],params...), [ini])
6 v = r.zero[1]
7 else
8 r = nlsolve((vout,vin)->vout .= func(vin,params...), ini)
9 v = r.zero
10 end
11 return v, r.f_converged
12end
あとは前やったように、以下のようにすれば良いはずだ.
1Δt = 0.1 # 時間刻み幅を元に戻しておいて、
2
3u = u0 # 「今」の値は、もちろん最初は初期値そのもの.
4u_sq = [ u ] # 初期値を配列に入れておいて…
5
6for n in 0:99 # n が時間ステップを表す.つまり、式の中に出てくるので丁寧に考える.
7 u = nls(f, u, n, ini = u)[1] # 関数 nls で新しい値をいきなり求める.
8 push!(u_sq, u) # その値を配列に追加していく.
9end
ふむ、無事に動いたようだ.グラフにしてみてみよう.
1t_range = 0:Δt:100Δt # 時間範囲.初期値 0 から 100Δt まで 101点になる.
2plot(t_range, u_sq, marker = :circle,
3 xlabel = "t", ylabel = "u", legend = false)
グラフを見ると、Newton法を用いた結果とほぼ同じなようだ.問題ないと見て良いだろう.
Euler 法は不安定だったけどこの「対称なスキーム using ライブラリ」はどうかな?
先と同じように、$\Delta t = 0.5$ として挙動を見てみよう.
1Δt = 0.5 # 時間刻み幅を危ない数字にして…
2
3u = u0 # 「今」の値は、もちろん最初は初期値そのもの.
4u_sq = [ u ] # 初期値を配列に入れておいて…
5
6for n in 0:99 # n が時間ステップを表す.つまり、式の中に出てくるので丁寧に考える.
7 u = nls(f, u, n, ini = u)[1] # 関数 nls で新しい値をいきなり求める.
8 push!(u_sq, u) # その値を配列に追加していく.
9end
10
11t_range = 0:Δt:100Δt # 時間も記録.初期値 0 から 100Δt まで 101点になる.
12plot(t_range, u_sq, marker = :circle,
13 xlabel = "t", ylabel = "u", legend = false)
おお、これもきちんと動作する. 「対称なスキーム using ライブラリ」は Euler 法より安心して使えそうと言える. プログラムの手間もかなり少なくて、これは良い方法と言えそうだ.
(一般に非対称だが) 速くて精度も高い Runge-Kutta 法
さて,さらに新しい解法を紹介しよう.
ここで紹介する Runge-Kutta 法とは常微分方程式
\begin{equation} \frac{du}{dt} = r(u,t) \end{equation}
に対して $u(t)$ から $u(t+Δt)$ の近似値を計算する手法の一つで、 $t$ から $t + Δt$ の間の $u$ の 時間変化を表す右辺 $r$ の近似値をいくつか計算して、それを使って $u(t+Δt)$ の近似値を作るもの、だな.
その中でも有名なのは、以下の「古典的 4次 Runge-Kutta 法」と呼ばれるもので、なかなか「頑丈 = 安定して計算できる」ことと、代入計算だけで済むので「計算が速い」ことが知られている. ただし、時間方向の対称性とかは失われてしまうのでそのあたりはバーターだね.
古典的 4段 4次 Runge-Kutta 法
古典的 4段 4次 Runge-Kutta 法というものでは,まず, 時間 $t$ での $u(t)$ の値を $u$ として、
\begin{equation} \left\{\begin{array}{rcl} r_1 & = & r(u, t), \cr r_2 & = & r(u + (\Delta t / 2) \, r_1, \, t+\Delta t / 2), \cr r_3 & = & r(u + (\Delta t / 2) \, r_2, \, t+\Delta t / 2), \cr r_4 & = & r(u + \Delta t \, r_3, \, t+\Delta t) \end{array} \right. \end{equation}
と順番に $r_k$ を 4つ計算する. そしてこれらを用いて、
\begin{equation} u(t + \Delta t) \, \text{ の近似値} := u(t) + \Delta t \left( \frac{r_1 + 2r_2 + 2r_3 + r_4}{6} \right) \end{equation}
として、時間ステップを 1つ進める近似解法がこの方法だ.
早速、プログラムしてみよう. まず、この問題の場合は、常微分方程式の右辺 $r(u,t)$ は次のようになる.
1r(u,t) = 1 + sin(t)/2 - u^4
そして、Runge-Kutta 法で 1ステップすすめる関数をプログラムで書くと次のような感じだな.
1function RK(u,t)
2 r1 = r(u,t)
3 r2 = r(u + Δt/2 * r1, t + Δt/2)
4 r3 = r(u + Δt/2 * r2, t + Δt/2)
5 r4 = r(u + Δt * r3, t + Δt)
6 return u + Δt * (r1 + 2*r2 + 2*r3 + r4)/6
7end
早速使ってみよう! まずは安全そうなパラメータで.
1Δt = 0.1
2
3u0 = 0.9
4u = u0 # 最初の値はもちろん初期値
5u_sq = [ u ] # 初期値を配列に入れておいて…
6
7for n in 0:99
8 u = RK(u, n*Δt) # Runge-Kutta 法で新しい値をいきなり求める.
9 push!(u_sq, u) # その値を配列に追加していく.
10end
で、動いているようなのでプロットだ.
1t_range = 0:Δt:100Δt # 時間も記録.初期値 0 から 100Δt まで 101点になる.
2plot(t_range, u_sq, marker = :circle,
3 xlabel = "t", ylabel = "u", legend = false)
ふむふむ、うまくいっている.
$\Delta t$ を大きくしてみて、Runge-Kutta 法がうまく動くかチェックしよう
1Δt = 0.5 # この値を大きくした.
2
3u0 = 0.9
4u = u0 # 最初の値はもちろん初期値
5u_sq = [ u ] # 初期値を配列に入れておいて…
6
7for n in 0:99
8 u = RK(u, n*Δt) # Runge-Kutta 法で新しい値をいきなり求める.
9 push!(u_sq, u) # その値を配列に追加していく.
10end
今回も大丈夫なようなので、プロットしよう.
1t_range = 0:Δt:100Δt # 時間も記録.初期値 0 から 100Δt まで 101点になる.
2plot(t_range, u_sq, marker = :circle,
3 xlabel = "t", ylabel = "u", legend = false)
Runge-Kutta 法も、少し大きめの $\Delta t$ に対してきちんと動作する.安心できそうだ.
いまのところどの解法も良さそうだ.さらに比較したい.
いまのところ、今回紹介している方法は Euler法なら失敗するパラメータでも十分問題なく動作する. さらに違いはあるだろうか.実際に調べてみよう.
まずは近似解の精度で比べてみよう
前回、time $t = 10$ での $u$ の値として相当誤差が小さそうな値: \begin{equation} u_\text{approx}(t=10) = 0.9594159419736648865 \end{equation} を得ていたので、これを真値の代わりに使って近似解の誤差相当を測定し、解法による違いを比較しよう. なお、以降、$\tilde{u} := u_\text{approx}(t=10)$ と表記する.
まず,様々な $\Delta t$ に対して計算して $t = 10$ のときの誤差がどうなるのか,記録を取ろう. まずは 時間$T$ までそれぞれの解法で計算する関数を定義しておこう.上記のプログラムを動かしてきたという前提で、下記のようにする.
1### 1. Euler 法
2Euler(u, n) = u + Δt * ( 1 + sin(n*Δt)/2 - u^4 )
3
4function Euler_all() # すべてのパラメータは外部にあるものと仮定して楽をする.
5 u = u0
6 for n in 0:N-1
7 u = Euler(u, n) # Euler スキームで新しい値を求める.
8 end
9 return u
10end
11
12### 2. 対称解法 using Newton法
13function Sym_Newton_all() # すべてのパラメータは外部にあるものと仮定して楽をする.
14 u = u0
15 for n in 0:N-1
16 u = newton(u, n) # 新しい値を求める.
17 end
18 return u
19end
20
21### 3. 対称解法 using ライブラリ
22function Sym_NLsolve_all() # すべてのパラメータは外部にあるものと仮定して楽をする.
23 u = u0
24 for n in 0:N-1
25 u = nls(f, u, n, ini = u)[1] # 関数 nls で新しい値をいきなり求める
26 end
27 return u
28end
29
30### 4. Runge-Kutta法
31function RK_all() # すべてのパラメータは外部にあるものと仮定して楽をする.
32 u = u0
33 for n in 0:N-1
34 u = RK(u, n*Δt) # Runge-Kutta 法で新しい値をいきなり求める.
35 end
36 return u
37end
38
39### 5. 全体の誤差計算
40u_exact = 0.9594159419736648865 # 厳密解もどき.
41function errors()
42 [ Euler_all() Sym_Newton_all() Sym_NLsolve_all() RK_all() ] .- u_exact
43end
うまく動くかどうか、下記のように確認しておこう.
1T = 10.0
2N = 100
3Δt = T/N
4u0 = 0.9
5
6Euler_all(), Sym_Newton_all(), Sym_NLsolve_all(), RK_all(), errors()
結果は以下のように出力されるはずだ.
(0.959650776373918, 0.959433000731827, 0.9594330007318271, 0.9594155982720675, [0.00023483440025318103 1.7058758162158405e-5 1.7058758162269427e-5 -3.437015974050439e-7])
さて、各関数が上手く動作するようなので、下記のようなプログラムで $\Delta t$ と各解法での誤差の関係を調べることができるだろう.
1# 全体条件: 変更しないパラメータ
2u0 = 0.9 # 初期値
3T = 10.0 # 最終時刻
4u_exact = 0.9594159419736648865 # 厳密解もどき.
5ratio = 1.5 # 計算回数を毎回 1.5倍する <=> Δt を毎回 2/3 に.
6N_iter = 15 # 何回 Δt を小さくするか
7
8# 初期化: 変更していくパラメータ
9N = 100
10Δt = T/N
11
12err = errors() # 誤差を一回計算しておく.こうすると記録開始しやすい.
13println("iter, Δt, errors") # 画面表示
14println("0, $Δt, $err") # 画面表示
15
16# 記録をとりはじめる.
17sq_dt = [ Δt ] # Δt の記録
18sq_errors = err # 誤差の記録
19
20# Δt を小さくしていったときの近似解をそれぞれ求める.
21for i in 1:N_iter
22 N = round(Int, ratio * N) # N を ratio 倍する.
23 Δt = T / N # Δt も変更される.
24 err = errors() # 誤差を計算
25 println("$i, $Δt, $err") # 画面表示
26
27 push!( sq_dt, Δt ) # Δt の記録
28 sq_errors = vcat(sq_errors, err) # 誤差の記録
29end
すると次のように次々と表示され,だんだん誤差が小さくなっていることや,対称解法に Newton法を組み合わせてもライブラリを組み合わせても誤差はほとんど変わらないことや、他の解法との違いが見えてくる.
iter, Δt, errors
0, 0.1, [0.00023483440025318103 1.7058758162158405e-5 1.7058758162269427e-5 -3.437015974050439e-7]
1, 0.06666666666666667, [0.0001618831577113733 7.56147702318799e-6 7.5614770232990125e-6 -6.014084463767944e-8]
2, 0.044444444444444446, [0.00011029081935520768 3.3566750670122047e-6 3.3566750670122047e-6 -1.0940763850442181e-8]
3, 0.029585798816568046, [7.447305806651539e-5 1.4866625780429743e-6 1.4866625780429743e-6 -2.0317409976655654e-9]
4, 0.01972386587771203, [5.0115424536256725e-5 6.606040989787232e-7 6.606040989787232e-7 -3.8659575540833657e-10]
5, 0.013157894736842105, [3.3639577645905305e-5 2.9411813584623303e-7 2.9411813573521073e-7 -7.467015894491169e-11]
6, 0.008771929824561403, [2.2518712307073585e-5 1.3909466667350046e-7 1.390946641199875e-7 -1.4503842571400583e-11]
7, 0.005847953216374269, [1.5053510717955021e-5 2.2877105165797218e-7 2.2877116656605523e-7 -2.832956091936012e-12]
8, 0.003898635477582846, [1.005391240027631e-5 1.0166398023425671e-7 1.0166409514233976e-7 -5.552225346150408e-13]
9, 0.002598752598752599, [6.70984456307977e-6 4.516872742499345e-8 4.5168852547128324e-8 -1.0935696792557792e-13]
10, 0.0017325017325017325, [4.476831548361204e-6 2.007395571990145e-8 2.0074085504973027e-8 -2.0761170560490427e-14]
11, 0.001155001155001155, [2.986155194339979e-6 8.921454019983344e-9 8.921575700426843e-9 -4.218847493575595e-15]
12, 0.00077000077000077, [1.991481612506618e-6 3.965590633647764e-9 3.9657140904481025e-9 -1.1102230246251565e-15]
13, 0.000513347022587269, [1.328004692768836e-6 1.7630658044609504e-9 1.7631874849044493e-9 2.220446049250313e-16]
14, 0.00034223134839151266, [8.854770090493957e-7 7.825772252445518e-10 7.826976844427236e-10 8.881784197001252e-16]
15, 0.00022815423226100844, [5.903804719542549e-7 3.482316657255069e-10 3.483519028790738e-10 -9.992007221626409e-16]
もう少し状況を把握するために,グラフにしてみよう. 例えば以下のようにすればよいだろう.
1default( marker = :circle,
2 xaxis = ("Δt", :log10), yaxis = ("error", :log10),
3 legend = :outertopright )
4# 共通の設定は default 宣言で一回だけすれば良い.
5
6plot( sq_dt, abs.(sq_errors[:,1]), label = "Euler")
7plot!(sq_dt, abs.(sq_errors[:,2]), label = "Symm(Newton)")
8plot!(sq_dt, abs.(sq_errors[:,3]), label = "Symm(NLsolve)")
9plot!(sq_dt, abs.(sq_errors[:,4]), label = "Runge-Kutta")
10
11p1(t) = 1.0e-3 * t
12p2(t) = 4.0e-4 * t^2
13p4(t) = 4.0e-4 * t^4
14
15plot!(sq_dt, p1.(sq_dt), marker = :none, label = "y = C1*x")
16plot!(sq_dt, p2.(sq_dt), marker = :none, label = "y = C2*x^2")
17plot!(sq_dt, p4.(sq_dt), marker = :none, label = "y = C3*x^4")
上の誤差のグラフからわかること
このグラフを見ると、以下のことが言えそうだ.
- Euler 法よりも対称スキーム(2つとも)のほうが誤差が小さく,Runge-Kutta法はさらに誤差が小さい.
- Runge-Kutta法は誤差を小さくできる限界に達してしまっているようだ.
- Euler 法では,$\Delta t$ と誤差 $\epsilon$ が比例関係にある.つまり,
\[
\text{Euler 法の誤差} \propto \Delta t
\]
これは $\Delta t$ を $1/2$ にすると誤差が $1/2$ になることを意味する.
言い換えれば,計算量を 2倍にすれば誤差を $1/2$ にできると期待できる.
この特徴を「この解法は 1次精度である」と言う. - 対称スキーム(2つとも)では $\Delta t$ と誤差 $\epsilon$ が二次関係にある.つまり,
\[
\text{対称スキームの誤差} \propto \Delta t^2
\]
これは $\Delta t$ を $1/2$ にすると誤差が $1/4$ になることを意味する.
これまた言い換えれば,計算量を 2倍にすれば誤差を $1/4$ にできると期待できる.
この特徴を「この解法は 2次精度である」と言う. - 古典的 Runge-Kutta 法では $\Delta t$ と誤差 $\epsilon$ が 4次関係にある.つまり,
\[
\text{Runge-Kutta法の誤差} \propto \Delta t^4
\]
これは $\Delta t$ を $1/2$ にすると誤差が $1/16$ になることを意味する.
これまた言い換えれば,計算量を 2倍にすれば誤差をなんと $1/16$ にできると期待できる. Euler 法や対称スキームよりもさらに効率が良い.
この特徴を「この解法は 4次精度である」と言う.
これらからわかるのは,この4つの中で比べるならば、Runge-Kutta法は多少複雑だが誤差も小さいし,計算量を増やしたとき期待できる利益の効率も良い、ということだ.あとは計算時間とのバランスを見て判断することになるだろう.
計算速度の比較をしてみよう
計算時間の測定に前回も用いた BenchmarkTools パッケージの @benchmark マクロを使おう.
BenchmarkTools を使って素朴に計算時間を測定
計算速度を測定し、これらを比較してみよう. まずパッケージの利用宣言を以下のようにして、
1using BenchmarkTools
あとは測定したい関数(上で定義した xxx_all という関数)を @benchmark マクロに渡すだけだ.
4つとも測定してみる.(具体的な数字は環境ごとにことなるが)たとえば以下のようになるだろう.
1N = 100 # もとの数字に設定しておく
2Δt = T/N # もとの数字に設定しておく
3
4@benchmark Euler_all()
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
Range (min … max): 14.300 μs … 4.320 ms ┊ GC (min … max): 0.00% … 98.28%
Time (median): 27.800 μs ┊ GC (median): 0.00%
Time (mean ± σ): 31.315 μs ± 68.027 μs ┊ GC (mean ± σ): 4.91% ± 2.39%
▄▁ ██▂▁ ▁ ▁
██▄▃▂▃▃▂▇▄▃██████▇█▅▇▇█▇▇▇▅▆▇▆▆█▆▅█▅▆▅█▅▆▇▅▇▅▃▄▇▃▃▇▃▃▂▇▇▄▃▆ █
14.3 μs Histogram: log(frequency) by time 80.5 μs <
Memory estimate: 17.22 KiB, allocs estimate: 1001.
1@benchmark Sym_Newton_all()
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
Range (min … max): 87.700 μs … 4.247 ms ┊ GC (min … max): 0.00% … 94.45%
Time (median): 178.100 μs ┊ GC (median): 0.00%
Time (mean ± σ): 182.491 μs ± 168.573 μs ┊ GC (mean ± σ): 4.98% ± 6.26%
▇▂▁▁▁▁▅█▄▂▁▁▁▁ ▂
█████████████████▇█▇▇▇▇▆▆▇▆▆▅▆▆▆▅▅▆▄▅▅▄▆▅▃▄▄▃▄▄▄▃▆▄▄▅▄▅▃▃▁▁▃▃ █
87.7 μs Histogram: log(frequency) by time 862 μs <
Memory estimate: 115.81 KiB, allocs estimate: 7311.
1@benchmark Sym_NLsolve_all()
BenchmarkTools.Trial: 3879 samples with 1 evaluation per sample.
Range (min … max): 692.300 μs … 7.026 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 1.307 ms ┊ GC (median): 0.00%
Time (mean ± σ): 1.288 ms ± 669.188 μs ┊ GC (mean ± σ): 2.19% ± 6.77%
▇▅▃▂▂▃▁▁▁█▇▄▂▂ ▁▁ ▁
██████████████████▇██▇▇▇█▇▇▇▇▆▆▅▆▆▅▆▆▇▆▆▅▆▆▆▆▆▅▄▅▅▆▅▄▅▃▃▁▃▄▄▃ █
692 μs Histogram: log(frequency) by time 4.52 ms <
Memory estimate: 463.31 KiB, allocs estimate: 18181.
1@benchmark RK_all()
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
Range (min … max): 36.800 μs … 3.896 ms ┊ GC (min … max): 0.00% … 91.72%
Time (median): 75.100 μs ┊ GC (median): 0.00%
Time (mean ± σ): 79.125 μs ± 116.141 μs ┊ GC (mean ± σ): 5.82% ± 4.41%
▅▅▁▁▁▁ ▇█▅▂▁▁ ▁
█████████▇▇███████▇█▇▇█▇▆▇▆▆▇▆▇▆▆▆▆▇▅▆▅▅▇▆▆▅▄▅▅▅▄▅▅▅▅▄▄▄▄▅▅▃ █
36.8 μs Histogram: log(frequency) by time 227 μs <
Memory estimate: 53.16 KiB, allocs estimate: 3301.
すると、この 4つの解法では平均値で比較するとおおよそ
| 解法 | 計算時間 平均値(μs) |
|---|---|
| Euler法 | 31 |
| 対称スキーム(Newton法利用) | 182 |
| 対称スキーム(NLsolveライブラリ利用) | 1,290 |
| Runge-Kutta スキーム | 79 |
となることがわかる.
計算式を眺めると Runge-Kutta スキームは Euler スキームの 4倍の計算時間がかかるはずだが、平均値だけ見るとそんなにかかってない.まあ測定値のばらつきも大きいので、おおよその傾向としては変ではないかな?
また, 非線形部分を毎回解かないといけない対称スキームは計算時間が大きいが、Newton法を用いるかライブラリを用いるかなど、実装によっても計算時間が大きく変化することもよく分かる.今回は、微分値という情報を与えた分だけ Newton法の方がライブラリよりも有利なのだろう.
プログラムが要する計算時間は直感による予想と異なることが多々ある.計算時間については、なるべくこのように「測定した値」をベースにして議論するほうが良い.
BenchmarkTools を使って、パラメータ $\Delta t$ と計算時間の関係を測定
では、この BenchmarkTools ライブラリを使って、$\Delta t$ と計算時間の関係を丁寧に測定しよう. まずは以下のように準備だ.
1Euler_time() = mean( (@benchmark Euler_all()).times )/1000
2Sym_Newton_time() = mean( (@benchmark Sym_Newton_all()).times )/1000
3Sym_NLsolve_time() = mean( (@benchmark Sym_NLsolve_all()).times )/1000
4RK_time() = mean( (@benchmark RK_all()).times )/1000
5
6times() = [ Euler_time() Sym_Newton_time() Sym_NLsolve_time() RK_time() ]
きちんと動作するかどうか、(少し時間はかかるが)以下のようにして確認しよう.
1times()
たとえば次のような結果が得られるはずだ.
1×4 Matrix{Float64}:
31.389 156.383 1209.88 57.5316
さて、上のようにうまく動作することが確認できたならば実測だ.下記のようなプログラムを動かせば良いだろう. かなり時間がかかるはずなので、ゆっくり待とう(教員の PC だと10分ほどかかった).
1# 全体条件: 変更しないパラメータ
2u0 = 0.9 # 初期値
3T = 10.0 # 最終時刻
4ratio = 1.5 # 計算回数を毎回 1.5倍する <=> Δt を毎回 2/3 に.
5N_iter = 15 # 何回 Δt を小さくするか
6
7# 初期化: 変更していくパラメータ
8N = 100
9Δt = T/N
10
11times_method = times() # 一回測定しておく.こうすると記録開始しやすい.
12println("iter, Δt, times_method") # 画面表示
13println("0, $Δt, $times_method") # 画面表示
14
15# 記録をとりはじめる.
16sq_dt = [ Δt ] # Δt の記録(既に記録があるが念の為)
17sq_times = times_method # 誤差の記録
18
19# Δt を小さくしていったときの近似解をそれぞれ求める.
20for i in 1:N_iter
21 N = round(Int, ratio * N) # N を ratio 倍する.
22 Δt = T / N # Δt も変更される.
23 times_method = times() # 計算時間を測定
24 println("$i, $Δt, $times_method") # 画面表示
25
26 push!( sq_dt, Δt ) # Δt の記録(既に記録があるが念の為)
27 sq_times = vcat(sq_times, times_method) # 誤差の記録
28end
iter, Δt, times_method
0, 0.1, [29.72221 149.5115 1207.8110493230174 69.68330999999999]
1, 0.06666666666666667, [42.17517 246.13264999999998 1706.6130761351997 121.55179]
2, 0.044444444444444446, [60.403220000000005 363.1179 2864.5963896848134 167.85529]
3, 0.029585798816568046, [104.40061 550.9658978037744 4130.904297520661 235.55932]
4, 0.01972386587771203, [145.88258 766.7101197788697 6032.503980699638 388.15568]
5, 0.013157894736842105, [224.94522 972.7089386562805 8919.870053475935 542.6482987281227]
6, 0.008771929824561403, [369.76365999999996 1459.0617698598132 13391.2 840.8958929473152]
7, 0.005847953216374269, [549.6589498018494 1709.3194871794872 19095.212977099236 1122.8012581442374]
8, 0.003898635477582846, [807.5605756791721 2774.8380688124307 27357.25760869565 1913.2372894333844]
9, 0.002598752598752599, [1237.222233226046 4415.5907243816255 40854.321951219514 2725.7575013638843]
10, 0.0017325017325017325, [1833.9655412844038 5689.997838452787 63288.14875 3866.8711523588554]
11, 0.001155001155001155, [2707.268327016784 8835.875441696113 92607.91818181818 5534.622676991151]
12, 0.00077000077000077, [4091.5445990180033 14240.605413105413 147264.32352941178 9116.065938069218]
13, 0.000513347022587269, [6422.094351732991 20503.851639344262 222420.8695652174 13747.952197802197]
14, 0.00034223134839151266, [9807.866666666667 32745.6522875817 320569.03125 21996.72543859649]
15, 0.00022815423226100844, [14184.260169491527 46317.95779816514 473619.94545454544 32540.74220779221]
状況を把握するために,グラフにしてみよう. 例えば以下のようにすればよいだろう.
1default( marker = :circle,
2 xaxis = ("Δt", :log10), yaxis = ("time(micro second)", :log10),
3 legend = :outertopright )
4# 共通の設定は default 宣言で一回だけすれば良い.
5
6plot( sq_dt, abs.(sq_times[:,1]), label = "Euler")
7plot!(sq_dt, abs.(sq_times[:,2]), label = "Symm(Newton)")
8plot!(sq_dt, abs.(sq_times[:,3]), label = "Symm(NLsolve)")
9plot!(sq_dt, abs.(sq_times[:,4]), label = "Runge-Kutta")
10
11p(t) = 8.0e-1 / t
12plot!(sq_dt, p.(sq_dt), marker = :none, label = "y = C/x")
上のグラフからは、 \[ \text{計算時間} \propto (\Delta t)^{-1} \] という結果が確認できる. これは、 \[ \text{計算ループ回数 }\, N = \frac{T}{\Delta t} \] であることから、まあ素直な結果と言える.
一番欲しいグラフは、計算時間 (コスト) と誤差 (利益) の関係グラフだ
最終的にわれわれが知りたいのは、計算にかけるコストである計算時間と、その利益である誤差(の小ささ)の関係になる. この関係が分かれば、許容できる誤差の大きさに応じて払うコストがわかり、「ベストな」解法を選ぶことができるのだ.
そのグラフを描くのは簡単だ.以下のようにすればよい.
1default( marker = :circle,
2 xaxis = ("times (micro sec)", :log10), yaxis = ("error", :log10),
3 legend = :outertopright )
4# 共通の設定は default 宣言で一回だけすれば良い.
5
6plot( abs.(sq_times[:,1]), abs.(sq_errors[:,1]), label = "Euler")
7plot!( abs.(sq_times[:,2]), abs.(sq_errors[:,2]), label = "Symm(Newton)")
8plot!( abs.(sq_times[:,3]), abs.(sq_errors[:,3]), label = "Symm(NLsolve)")
9plot!( abs.(sq_times[:,4]), abs.(sq_errors[:,4]), label = "Runge-Kutta")
このグラフからわかること
このグラフから、下記のような情報が読み取れる.
- Runge-Kutta法が他解法よりも明らかに速くて誤差が小さく,良い.
- 対称スキームの2つについて、Newton法を使ったほうが(同じ誤差で比較して)速い.
- $\Delta t = 0.1 (N = 100)$ のときは明らかに遅かった対称スキーム(Newton, NLsolve)の2つだが,誤差を $10^{-5}$ 以下ぐらいにしようとするならば Euler スキーム法よりも速い.
- 上のグラフから見る限り、Euler法の優位性はほとんど無い.
というわけで,Runge-Kutta法のような「高性能な数値解法」には大いに価値があることがよく分かる.
もう少し複雑な Runge-Kutta 法も紹介
Runge-Kutta法についてもっと詳しく知りたければ、例えば wikipedia の ルンゲ-クッタ法のリスト を見ておくと良い.
4(5)次 Runge-Kutta 法 (Runge-Kutta-Fehlberg 法)
これは、計算途中で $\Delta t$ をうまく調整していくことを想定したタイプの Runge-Kutta 法の一つで、有名なものである.
その前に, 近似解法の次数の定義を述べておこう.すぐ後でこの性質をうまく使うのだ.
定義: 解法が $p$ 次解法であるとは、局所誤差( 1ステップだけで発生する誤差) $\epsilon_p$ が $\Delta t$ の $p+1$ 次オーダーであることを言う.つまり、 \begin{equation} \epsilon_p \cong C\, (\Delta t)^{p+1} \end{equation} となる.なお、$C$ は時間や $u$ 等に依存する適当な係数.
さて、この RK-Fehlberg法の具体形を紹介しよう.以下のようなプロセスになる.
-
まず、時間 $t$ での $u(t)$ の値を $u$ として、 \begin{equation} \left\{ \begin{array}{rcl} r_1 & = & \displaystyle r(u, t), \cr r_2 & = & \displaystyle r\left(u + \frac{1}{4} \Delta t \, r_1 , t+ \frac{1}{4} \Delta t \right), \cr r_3 & = & \displaystyle r\left( u + \Delta t \left( \frac{3}{32} \, r_1 + \frac{9}{32}\, r_2 \right) , t + \frac{3}{8} \Delta t \right), \cr r_4 & = & \displaystyle r\left( u + \Delta t \left( \frac{1932}{2197} \, r_1 - \frac{7200}{2197}\, r_2\ + \frac{7296}{2197}\, r_3 \right) , t + \frac{12}{13} \Delta t \right), \cr r_5 & = & \displaystyle r\left( u + \Delta t \left( \frac{439}{216} \, r_1 - 8\, r_2 + \frac{3680}{513}\, r_3 - \frac{845}{4104}\, r_4 \right) , t + \Delta t \right), \cr r_6 & = & \displaystyle r\left( u + \Delta t \left( -\frac{8}{27} \, r_1 + 2\, r_2 -\frac{3544}{2565}\, r_3 + \frac{1859}{4104}\, r_4 - \frac{11}{40}\, r_5 \right) , t + \frac{1}{2} \Delta t \right) \end{array} \right. \end{equation}
と上から順に計算し、$u$ の微分 $r$ の近似値を 6つ計算する.
-
このうちの 4つの値 ($r_1, r_3, r_4, r_5$)を用いて $u(t + \Delta t)$ の近似値 $U$ を \begin{equation} U = u + \Delta t \, \left( \frac{25}{216}\,r_1 + \frac{1408}{2565}\, r_3 + \frac{2197}{4104}\, r_4 - \frac{1}{5}\, r_5 \right) \end{equation} として計算すると、これは 4次近似値となっている.つまり、1 step で発生する誤差(局所誤差)は $O(\Delta t^5)$ である.
-
同様に 5つの値 ($r_1, r_3, r_4, r_5, r_6$)を用いて $u(t + \Delta t)$ の近似値 $\hat{U}$ を \begin{equation} \hat{U} = u + \Delta t \, \left( \frac{16}{135}\,r_1 + \frac{6656}{12825}\, r_3 + \frac{28561}{56430}\, r_4 - \frac{9}{50}\, r_5 + \frac{2}{55}\,r_6 \right) \end{equation} として計算すると、これは 5次近似値となっている.つまり、1 step で発生する誤差(局所誤差)は $O(\Delta t^6)$ である.
-
低次近似値からみると高次近似値は随分と「良い」はずなので、これを真値の代わりに使って低近似値の誤差を推定できる. 具体的には、4次近似値 $U$ の誤差を \begin{equation} \epsilon_4 \cong \| U - \hat{U} \| \label{eq:error-eval} \end{equation} と見積もる. すると、「4次」近似値の性質($\epsilon_4 \cong C\, (\Delta t)^5$)から、この見積もりは \begin{equation} \| U - \hat{U} \| \cong C\, (\Delta t)^5 \label{eq:current} \end{equation} を意味する.
-
式 $(\ref{eq:error-eval})$ による局所誤差の見積もり値が許容値 $\mathcal{E}$ 以下の場合、 4次近似値は許容できるのでそれを採用し、次の時間ステップの計算へ進めば良い.
-
式 $(\ref{eq:error-eval})$ による局所誤差の見積もり値が許容値 $\mathcal{E}$ を超える場合、 4次近似値は許容できず、計算結果を破棄する. そのため、$\Delta t$ を $\Delta t_\text{new}$ に変更して計算し直すことで局所誤差を希望値 $\mathcal{E}$ 以下に抑えることを考える. 具体的には、 \begin{equation} \epsilon_{4}^\text{new} \cong C\, (\Delta t_\text{new} )^5 \lesssim \mathcal{E} \label{eq:hope} \end{equation} を希望する. この場合の現状と希望を整理すると以下の通り.
現状: $\, \| U - \hat{U} \| \cong C\, (\Delta t)^5$,
希望: $\, C\, (\Delta t_\text{new} )^5 \lesssim \mathcal{E}$この二つの式から未知の定数 $C$ を消去できる. すると、$\Delta t_\text{new}$ に対する条件が以下のように導出される.
修正時間ステップの満たすべき条件:
\begin{equation} \Delta t_\text{new} \lesssim \left( \frac{\mathcal{E}}{\| U - \hat{U} \|} \right)^{1 / 5} \, \Delta t \end{equation}そこで、時間ステップ幅をこの右辺の値よりちょっと小さな値に設定し、あらためて計算をやり直す.
-
以上、繰り返し.
ちなみに、上の記述からわかるようにこの Fehlberg 公式では近似解として 4次近似値を採用する.
しかし、もっと良い5次近似値があるのにそれを使わないのはもったいない.
もちろん、そのあたりを改善した解法が多く存在する.次に紹介するものもその一つだ.
5(4)次 Runge-Kutta 法 (Dormand-Prince 法)
より高次な近似値である 5次近似値 $\hat{U}$ を採用するように設計されているのが Dormand-Prince 法(wikipedia) である. パラメータは webを参照してもらうとして、基本的な考え方は上の Fehlberg 法に近い.
レポート No.06
以下の課題についてレポートしよう.
ファイル名を 学籍番号-氏名-06.pdf とし,web フォームから提出しよう.
基本的には、ファイルは pdf 形式だ.動画を pdf に埋め込むのは可能だが難しいので、その場合は mp4 などの形式でも良い. 紙媒体で手渡ししても良いが,破損・紛失の可能性があるのでお勧めしない.
一応、レポートやメールには,自分の 所属・学年・学籍番号・氏名 を必ず書いておこう.なにかと安全だ.
課題
- 上で紹介した Runge-Kutta-Fehlberg 法の 5次近似値の誤差 vs $\Delta t$ のグラフを描いてみよう.
そして,誤差が $\Delta t$ とが何次の関係にあるかを確認しよう.
なお,この問では $\Delta t$ の自動調整機能は使わず,単なる普通の解法として扱おう.
ちなみに、パラメータの転記ミス等があると困るので、英語 wikipedia の List of Runge-Kutta methods の該当する箇所を見てパラメータを確認しつつ、プログラムを進めよう. - 同様に様々な $\Delta t$ でのRunge-Kutta-Fehlberg 法の 5次近似値の計算時間の実測を行い、上の誤差の測定値とあわせて、
計算時間(コスト) vs 誤差(利益) のグラフを描いてみよう.
この問でも、$\Delta t$ は自動的に調整せず単なる普通の解法として扱おう. - 可能ならば、授業資料にある Euler法、対称解法(Newton, NLsolve), 古典的Runge-Kutta法の「計算時間(コスト) vs 誤差(利益)」に、上の問のグラフを重ねて描こう.
- チャレンジ問題: Runge-Kutta-Fehlberg 法の本来の使い方である $\Delta t$ の値の自動制御 を試みてみよう. ただ、その性能は「計算時間(コスト) vs 精度(利益) のグラフ」を描かないと見えてこないだろうから、ちょっと大変だ. なお、$\Delta t_\text{new}$ の値は式 $(\ref{eq:autotune})$ を用いれば良い.