logo

マルチステップ法の収束性と誤差 📂数値解析

マルチステップ法の収束性と誤差

定理

初期値問題 {y=f(x,y)(y(x0),,y(xp))=(Y0,,Yp)\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) )= ( Y_{0} , \cdots , Y_{p} ) \end{cases} に対して、マルチステップ法 yn+1=j=0pajynj+hj=1pbjf(xnj,ynj) \displaystyle y_{n+1} = \sum_{j=0}^{p} a_{j} y_{n-j} + h \sum_{j = -1}^{p} b_{j} f (x_{n-j} , y_{n-j} ) が一貫性があり、初期誤差 η(h):=max0ipY(xi)yh(xi)\displaystyle \eta (h) : = \max_{ 0 \le i \le p} | Y (x_{i} ) - y_{h} (x_{i} ) |limh0η(h)=0\displaystyle \lim_{ h \to 0} \eta (h) = 0 を満たし、j=0,1,,pj = 0, 1, \cdots , p に対して aj0a_{j} \ge 0 が成り立ち、ff がリプシッツ条件を満たせば、方法は収束し、適切な定数 c1,c2c_{1} , c_{2} に対して maxx0xnbY(xn)yh(xn)c1η(h)+c2τ(h) \max_{ x_{0} \le x_{n} \le b} | Y (x_{n} ) - y_{h} (x_{n} ) | \le c_{1} \eta (h) + c_{2} \tau (h) が成立します。特に η(h)=O(hm)\eta (h) = O ( h^{m} ) であれば、方法の収束速度は O(hm)O ( h^{m} ) です。

説明

マルチステップ法は特定の方法を指すわけではないため、その収束性を証明することは非常に重要です。hh に従った誤差がどれだけ拡大するかを理解することも、実際に使うなら当然の作業です。

証明 1

真値 YiY_{i} と計算値 yiy_{i} の差を ϵi:=Yiyi\epsilon_{i} : = Y_{i} - y_{i} と表すと、 Yn+1=j=0pajYnj+hj=1pbjf(xnj,Ynj)+hτn(Y) Y_{n+1} = \sum_{j=0}^{p} a_{j} Y_{n-j} + h \sum_{j = -1}^{p} b_{j} f (x_{n-j} , Y_{n-j} ) + h \tau_{n} (Y)

yn+1=j=0pajynj+hj=1pbjf(xnj,ynj) y_{n+1} = \sum_{j=0}^{p} a_{j} y_{n-j} + h \sum_{j = -1}^{p} b_{j} f (x_{n-j} , y_{n-j} ) 上記の二つの式を引くと、 ϵn+1=j=0pajϵnj+hj=1pbj[f(xnj,Ynj)f(xnj,ynj)]+hτn(Y) \epsilon_{n+1} = \sum_{j=0}^{p} a_{j} \epsilon_{n-j} + h \sum_{j = -1}^{p} b_{j} [ f (x_{n-j} , Y_{n-j} ) - f (x_{n-j} , y_{n-j} ) ] + h \tau_{n} (Y) ffリプシッツ条件を満たすので、 ϵn+1j=0pajϵnj+hKj=1pbjϵnj+hτn(h) | \epsilon_{n+1} | \le \sum_{j=0}^{p} a_{j} | \epsilon_{n-j} | + h K \sum_{j = -1}^{p} b_{j} | \epsilon_{n - j} | + h \tau_{n} (h) nn までの ϵi\epsilon_{i} の中で最も大きな誤差を表す式 En:=max0inϵi\displaystyle E_{n} := \max_{0 \le i \le n} | \epsilon_{i} | を使うと、 ϵn+1j=0pajEn+hKj=1pbjEn+1+hτn(h) | \epsilon_{n+1} | \le \sum_{j=0}^{p} a_{j} E_{n}+ h K \sum_{j = -1}^{p} | b_{j} | E_{n+1 } + h \tau_{n} (h)

マルチステップ法の一貫性と収束次数:初期値問題 {y=f(x,y)(y(x0),,y(xp))=(Y0,,Yp)\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) )= ( Y_{0} , \cdots , Y_{p} ) \end{cases} に対して、マルチステップ法 yn+1=j=0pajynj+hj=1pbjf(xnj,ynj) \displaystyle y_{n+1} = \sum_{j=0}^{p} a_{j} y_{n-j} + h \sum_{j = -1}^{p} b_{j} f (x_{n-j} , y_{n-j} ) の一貫性の必要十分条件は (i) であり、収束次数 mNm \in \mathbb{N} を持つ必要十分条件は (ii) です。

  • (i): {j=0paj=1j=0pjaj+j=1pbj=1\begin{cases} \displaystyle \sum_{j = 0}^{p} a_{j} = 1 \\ \displaystyle - \sum_{j = 0}^{p} j a_{j} + \sum_{j = -1}^{p} b_{j} = 1 \end{cases}
  • (ii): i=0,1,,mi = 0, 1 , \cdots , m に対して、j=0p(j)iaj+ij=1p(j)i1bj=1\sum_{j=0}^{p} (-j)^{i} a_{j} + i \sum_{j=-1}^{p} (- j )^{i-1} b_{j} = 1

与えられたマルチステップ法が一貫性があるため、c:=Kj=1pbj\displaystyle c : = K \sum_{j = -1}^{p} | b_{j} | とすると、 ϵn+1En+hcEn+1+hτn(h) | \epsilon_{n+1} | \le E_{n}+ hc E_{n+1 } + h \tau_{n} (h) ϵn+1En+1 | \epsilon_{n+1} | \le E_{n+1} の場合 En+1=EnE_{n+1} = E_{n} なので、 ϵn+1En+1=EnEn+hcEn+1+hτn(h) | \epsilon_{n+1} | \le E_{n+1} = E_{n} \le E_{n}+ hc E_{n+1 } + h \tau_{n} (h) ϵn+1>En+1 | \epsilon_{n+1} | > E_{n+1} の場合、 En+1<ϵn+1EnEn+hcEn+1+hτn(h) E_{n+1} < | \epsilon_{n+1} | \le E_{n} \le E_{n}+ hc E_{n+1 } + h \tau_{n} (h) したがって、どんな場合でも、 En+1En+hcEn+1+hτn(h) E_{n+1} \le E_{n}+ hc E_{n+1 } + h \tau_{n} (h) 項を整理すると、 (1hc)En+1En+hτn(h) (1 - hc ) E_{n+1} \le E_{n} + h \tau_{n} (h) h0h \to 0 を仮定しているので、hh(1hc)>0 (1 - hc ) > 0hc12\displaystyle hc \le {{1 } \over {2}} を満たすほど十分に小さいと考えることができます。したがって、 En+1En1hc+hτn(h)1hc(1+2hc)En+2hτn(h) \begin{align*} E_{n+1} \le & {{E_{n} } \over {1 - hc}}+ {{ h \tau_{n} (h) } \over {1 - hc }} \\ \le & (1 + 2 hc ) E_{n} + 2 h \tau_{n} (h) \end{align*} 再帰的に解くとEn=maxx0xnbY(xn)yh(xn)e2c(bx0)η(h)+[e2c(bx0)1c]τ(h) \begin{align*} E_{n} =& \max_{ x_{0} \le x_{n} \le b} | Y (x_{n} ) - y_{h} (x_{n} ) | \\ \le & e^{2c(b-x_{0})} \eta (h) + \left[ {{ e^{2c (b - x_{0} ) } - 1 } \over {c}} \right] \tau (h) \end{align*}


  1. Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p360~361. ↩︎