📂数値解析

マルチステップ法の一貫性と収束次数

定理

初期値問題 $\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) )= ( Y_{0} , \cdots , Y_{p} ) \end{cases}$に対してマルチステップ法 $$ \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)であり、収束次数$m \in \mathbb{N}$を持つための必要十分条件は(ii)**である。

• (i): $$\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 , \cdots , m$に対して $$\sum_{j=0}^{p} (-j)^{i} a_{j} + i \sum_{j=-1}^{p} (- j )^{i-1} b_{j} = 1$$

説明

マルチステップ法は、ある一つのメソッドというより、数多くのメソッドを包括する形式そのものと見るのが望ましい。この定理は様々なメソッドについて一貫性と収束次数をチェックするのに有用であり、(i)と(ii)はどちらも必要十分条件なので、逆にメソッドがどのようなときに意味を持つのか、収束速度をどれだけ上げられるのかを把握するのにも使える。

証明¹

(i)

打ち切り誤差 $\displaystyle T_{n} (Y) := Y_{n+1} - \sum_{j=0}^{p} a_{j} Y_{n-j} + h \sum_{j = -1}^{p} b_{j} Y’_{n-j}$は線形性を持つ。言い換えれば、 $$ T_{n} ( \alpha Y + \beta W ) = \alpha T_{n} (Y) + \beta T_{n} (W) $$

---

Part 1.

初期値問題の解$Y(x)$を$x_{n}$について$m$次でテイラー展開すると $$ Y(x) = \sum_{i=0}^{m} {{1} \over {i! }} (x - x_{n} )^{i} Y^{ ( i ) } ( x_{n} ) + R_{m+1} (x) $$ 打ち切り誤差の表現で表してみると $$ T_{n} (Y) = \sum_{i=0}^{m} {{1} \over {i! }} Y^{ ( i ) } ( x_{n} ) T_{n} \left( (x - x_{n} )^{i} \right) + T_{n} \left( R_{m+1} \right) $$

---

Part 2.

$T_{n} \left( (x - x_{n} )^{i} \right)$を計算しよう。

• Case 1. $i = 0$
  $$ \displaystyle T_{n} (1) = 1 - \sum_{j=0}^{p} a_{j} 1 + h \sum_{j = -1}^{p} b_{j} ( 1 ) ' = 1 - \sum_{j=0}^{p} a_{j} $$ ここで$\displaystyle c_{0} : = 1 - \sum_{j=0}^{p} a_{j}$と置こう。
• Case 2. $i \ge 1$
  $$ \begin{align*} \displaystyle T_{n} \left( ( x - x_{n})^{i} \right) =& (x_{n+1} - x_{n})^{i} - \left[ \sum_{j=0}^{p} a_{j} ( x_{n-j} - x_{n} )^{i} + h \sum_{j = -1}^{p} b_{j} i ( x_{n-j} - x_{n} )^{i-1} \right] \\ =& h^{i} - \left[ h^{i} \sum_{j=0}^{p} a_{j} ( -j )^{i} + h^{i} i \sum_{j = -1}^{p} b_{j} ( -j )^{i-1} \right] \\ =& h^{i} \left[ 1 - \left( \sum_{j=0}^{p} ( -j )^{i} a_{j} + i \sum_{j = -1}^{p} ( -j )^{i-1} b_{j} \right) \right] \end{align*} $$ ここで$\displaystyle c_{i} : =1 - \left( \sum_{j=0}^{p} ( -j )^{i} a_{j} + i \sum_{j = -1}^{p} ( -j )^{i-1} b_{j} \right)$と置こう。

結局、$i$が何であれ次を得る。 $$ T_{n} (Y) = \sum_{i=0}^{m} {{c_{i} h^{i} } \over {i! }} Y^{ ( i ) } ( x_{n} ) + T_{n} \left( R_{m+1} \right) $$

---

Part 3.

マルチステップ法が一貫性を持つためには $$ \lim_{h \to 0} \max_{x_{p} \le x_{n} \le b} \left| {{T_{n}} \over {h}} (Y) \right| = 0 $$ でなければならないので、$T_{n} (Y) = O(h^2)$を満たせば良い。上のPart 2で $$ T_{n} (Y) = \sum_{i=0}^{m} {{c_{i} h^{i} } \over {i! }} Y^{ ( i ) } ( x_{n} ) + T_{n} \left( R_{m+1} \right) $$ であったので、$m=1$で$c_{0} = c_{1} = 0$であれば良い。整理すると $$ \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)

Part 4. $$ R_{m+1} = {{1} \over { (m+1)! }} (x - x_{n} )^{m+1} Y^{(m+1)} (x_{n}) + \cdots = O (h^{m+1} ) $$ なので、 $$ T_{n} ( R_{m+1} ) = {{ c_{m+1} } \over { (m+1)! }} h^{m+1} Y^{(m+1)} (x_{n}) + O (h^{m+2} ) $$ である。マルチステップ法が収束次数$m$を持つためには $$ \max_{x_{p} \le x_{n} \le b} \left| {{T_{n}} \over {h}} (Y) \right| = O ( h^{m} ) $$ でなければならないので、$T_{n} (Y) = O(h^{m+1})$を満たせば良い。これは単純に$i = 0,1, \cdots , m$に対して$c_{i} = 0$であれば良い。整理すると、$i = 0, 1 , \cdots , m$に対して $$ \sum_{j=0}^{p} (-j)^{i} a_{j} + i \sum_{j=-1}^{p} (- j )^{i-1} b_{j} = 1 $$

■