일관성을 가지는 멀티스텝 메소드의 수렴성과 루트 컨디션

일관성을 가지는 멀티스텝 메소드의 수렴성과 루트 컨디션

Convergence and Root Condition of Multi Step Method with consistency

정리

만약 멀티스텝 메소드가 일관성을 가진다고 하면, 메소드는 수렴성을 가진다 $\iff$ 메소드는 루트 컨디션을 만족 시킨다

설명

폐구간 $[x_{0} , b]$ 에 대해 $h$ 를 단위로 잘라서 노드 포인트를 만들 때, $x_{0} \le x_{1} \le \cdots \le x_{N(h) -1} \le x_{N(h) } \le b$ 라고 하자. 여기서 $N(h)$ 는 $h$ 에 따라 변하는 마지막 노드 포인트의 인덱스를 나타낸다.

메소드가 수렴성을 가진다는 것은 $h \to 0$ 일 때 $\displaystyle \eta (h) : = \max_{0 \le n \le p} | Y_{n} - y_{ n} | \to 0$ 이면, $h \to 0$ 일 때 $\displaystyle \max_{x_{0} \le x_{n} \le b } | Y_{n} - y_{ n} | \to 0$ 이라는 것이다.

증명 1

일관성을 가지는 멀티스텝 메소드: 초기값 문제 $\begin{cases} y’ = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) ) = (Y_{0}, \cdots , Y_{p} ) \end{cases}$ 에 대해 멀티스텝 메소드 $$ 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} ) $$ 는 다음을 만족한다. $$ \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} $$

루트 컨디션: 일관성을 가진 멀티스텝 메소드에 대해 $\displaystyle \rho ( r) = r^{p+1} - \sum_{j=0}^{p} a_{j} r^{p-j}$ 라고 하자. 방정식 $\rho (r ) = 0$ 의 근 $r_{0} , \cdots , r_{p}$ 들이 다음 조건들을 만족시킬 때, 주어진 멀티스텝 메소드는 루트 컨디션Root Condition을 만족시킨다고 한다.

  • (i): $| r_{j} | \le 1$
  • (ii): $|r_{j}| = 1 \implies \rho ‘(r_{j}) \ne 0$

$(\Rightarrow)$

메소드가 수렴성을 가짐에도 루트 컨디션을 만족시키지 않는다고 가정해보자.이 가정에 대해 초기값 문제 $\begin{cases} y’ = 0 \\ y(0) = 0 \end{cases}$ 가 반례가 됨을 보일 것이다.

주어진 문제의 트루 솔루션은 자명하게도 모든 $n \ge 0$ 에 대해 $Y_{n} = 0$ 이다.

그리고 $f = 0$ 이므로 뉴메리컬 솔루션은 $\displaystyle y_{n+1} = \sum_{j=0}^{p} a_{j} y_{n - j}$ 이다. 그 중에서도 $y_{0} , \cdots , y_{p}$ 가 $h \to 0$ 일 때 $$ \eta (h) = \max_{0 \le n \le p} | Y_{n} - y_{ n} | = \max_{0 \le n \le p} | y_{ n} | \to 0 $$ 을 만족한다고 하자.이때 어떤 $0 \le j \le p$ 에 대해 다음의 두 가지 경우를 생각해보자.

  • Case 1.
    (i)을 만족하지 않아 $ j$ 에 대해 $|r_{j}| > 1$ 인 경우$\displaystyle y_n = h r_{j} ^n$ 은 $h \to 0$ 일 때 $$ \eta (h) = \max_{0 \le n \le p} | y_{ n} | = h \left| r_{j} \right| ^{p} \to 0 $$ 를 만족시킨다. 그러나 $h \to 0$ 일 때 $N(h) \to \infty$ 이므로 $$ \max_{x_{0} \le x_{n} \le b} | Y_{n} - y_{ n} | = h \left| r_{j} \right| ^{N (h) } \to \infty $$ 따라서 메소드는 수렴성을 가지지 못한다.
  • Case 2.
    (ii)를 만족하지 않아 $ j$ 에 대해 $|r_{j}| = 1 \implies \rho’(r_{j}) = 0$ 인 경우이는 $|r_{j}| = 1$ 이면 $r_{j}$ 이 특성방정식의 중근이라는 의미로, 중근인 $r_{j}$ 가 적어도 하나 존재한다. 따라서 파티큘러 솔루션 $n r_{j}^{n}$ 이 존재해서 $\displaystyle y_n = h n r_{j} ^n$ 은 $h \to 0$ 일 때 $$ \eta (h) = \max_{0 \le n \le p} | y_{ n} | = h p \left| r_{j} \right| ^{p} \to 0 $$ 를 만족시키고, $\displaystyle y_n = h \left[ r_{j} (0) \right]^n$ 은 $h \to 0$ 일 때 $$ \eta (h) = \max_{0 \le n \le p} | y_{ n} | = h \left| r_{j} (0) \right| ^{p} \to 0 $$ 를 만족시킨다. 그러나 $h \to 0$ 일 때 $$ \max_{x_{0} \le x_{n} \le b} | Y_{n} - y_{ n} | = h \left| r_{j} (0) \right| ^{N (h) } \to \infty $$ 따라서 메소드는 수렴성을 가지지 못한다.

$(\Leftarrow)$ 원래의 증명이 지나치게 어려워서 많은 비약이 있다. 2

$e_{n} : = Y_{n} -y_{n}$ 이라고 하면 비동차 선형미분방정식 $Y = y + e$ 을 푸는 것으로 생각할 수 있다.

반대로 $y = Y - e$ 는 동차 선형미분방정식이 된다. $$ \begin{align} 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} ) \end{align} $$

$$ \begin{align} 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} ) \end{align} $$ $(1)$ 에서 $(2)$ 를 빼면 $$ e_{n+1} = \sum_{i=0}^{n} a_{j} e_{n-j} + h \sum_{j= -1}^{p} b_{j} \left[ f(x_{n-j} , Y_{n- j }) - f(x_{n-j} , y_{n- j }) \right] $$ 을 얻는다. $Y_{n} = d_{0} s_{0}^{n} + d_{1} s_{1}^{n} + \cdots + d_{p} s_{p}^{n}$ 이라고 하면 $$ e_{n} = g_{0} ( r_{0} + s_{0} )^n + g_{1} ( r_{1} + s_{1} )^n + \cdots + g_{p} ( r_{p} + s_{p} )^n $$ 주어진 메소드는 $N \ge p$ 일 때 $$ e_{N} = g_{0} ( r_{0} + s_{0} )^N + g_{1} ( r_{1} + s_{1} )^N + \cdots + g_{p} ( r_{p} + s_{p} )^N $$ 의 $( r_{0} + s_{0} ) , \cdots , ( r_{p} + s_{p} )$ 에 대해서도 루트 컨디션을 만족하므로, $$ \begin{align*} | e_{N} | & =& | g_{0} | | r_{0} + s_{0} |^N + | g_{1} | | r_{1} + s_{1} | ^N + \cdots + | g_{p} | | r_{p} + s_{p} |^N \\ \le & \max_{0 \le n \le p} | Y_{ n} - y_{n} | \end{align*} $$ 여기서 $h \to 0$ 일 때 $\displaystyle \max_{0 \le n \le p} | Y_{ n} - y_{n} | \to 0$ 임을 가정한다면 $e_{N} \to 0$ 이므로 $$ \max_{x_{0} \le x_{n} \le b} | Y_{n} - y_{ n} | = h \left| r_{j} (0) \right| ^{N (h) } \to 0 $$ 이어야하고, 따라서 메소드는 수렴성을 갖는다.


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

  2. Isaacson. (2012). ANALYSIS OF NUMERICAL METHODS: p405~417. https://www.researchgate.net/file.PostFileLoader.html?id=56c583ac5e9d97577f8b458e&assetKey=AS:330399868833792@1455784875579 ↩︎

댓글