📂数値解析

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

定理

初期値問題 $\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$$

■