📂수치해석

멀티스텝 메소드의 일관성과 수렴차수

정리

초기값 문제 $\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 $$

■