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

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

Stability 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$ 에 따라 변하는 마지막 노드 포인트의 인덱스를 나타낸다.

원래 주어진 초기값 $y_{0} , \cdots , y_{p}$ 에 대해 아주 조금 변화를 준 $z_{0} , \cdots , z_{p}$ 를 생각해보자. 메소드가 안정성을 가진다는 것은 충분히 작은 양수 $h$ 와 $\epsilon$ 에 대해 $\displaystyle \max_{0 \le n \le p} | y_{ n} - z_{n} | \le \epsilon$ 이라고 할 때, $\displaystyle \max_{0 \le n \le N(h) } | y_{ n} - z_{n} | \le c \epsilon$ 를 만족시키는 어떤 상수 $C$ 가 $h$ 와 독립적으로 존재한다는 것이다. 초기의 작은 변화가 $h$ 를 조절함에 따라서 큰 변화가 될 수도 있다면 메소드가 안정성을 갖지 않았다고 한다.

증명 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$ 이다.

여기서 $y_{0} , \cdots , y_{p}$ 에 대해 아주 조금 변화를 준 $z_{0} , \cdots , z_{p}$ 를 생각해보면 $$ z_{n+1} = a_{0} z_{n} + a_{1} z_{n-1} + \cdots + a_{p-1} z_{n-p-1} + a_{p} z_{n -p} $$ 캐릭터리스틱 솔루션을 구하기 위해 $z_{n} := r^{n}$ 라고 하면 $$ r^{n+1} = a_{0} r^{n} + a_{1} r^{n-1} + \cdots + a_{p-1} r^{n-p-1} + a_{p} r^{n -p} $$ 양변을 $r^{n-p}$ 로 나누면 $$ r^{p+1} = a_{0} r^{p} + a_{1} r^{n-1} + \cdots + a_{p-1} r^{1} + a_{p} $$ 이 $p+1$차 방정식은 $r_{0}=1$ 외에도 $p$ 개의 근 $r_{1}, r_{2} , \cdots , r_{p}$ 을 갖는다. 따라서 제너럴 솔루션은 어떤 $c_{0} , \cdots , c_{p}$ 에 대해 $$ z_{n} = c_{0} r_{0}^{n} + c_{1} r_{1}^{n} + \cdots + c_{p} r_{p}^{n} $$ 이때 어떤 $0 \le j \le p$ 에 대해 다음의 두 가지 경우를 생각해보자.

  • Case 1.
    조건 (i)을 만족하지 않아 $ j$ 에 대해 $|r_{j}| > 1$ 인 경우$z_{0} = 0 + \cdots + c_{j} r_{j}^{0} + \cdots + 0 = \epsilon$ 즉 $c_{i} = \begin{cases} \epsilon & , i = j \\ 0 & , i \ne j \end{cases} $ 이라고 하면 $$ z_{0} = c_{j} r_{j}^{0} = \epsilon $$ 이다. 다시 말해 $z_{0} = c_{j} ( r_{j} ) ^{0} \implies z_{ n} = c_{j} ( r_{j} ) ^{n}$ 이므로 $$ z_{0} = \epsilon, z_{1} = \epsilon r_{j } , \cdots , z_{p} = \epsilon r_{j}^{p} $$ 이고 $$ \max_{0 \le n \le p } | y_{n} - z_{n} | = \epsilon | r_{j} |^{p} $$ 메소드를 $[x_{0} , b]$ 에 적용시켜보면 $$ \max_{x_{0} \le x_{n} \le b } | y_{n} - z_{n} | = \epsilon |r_{j}|^{N(h)} $$ 그런데 $h \to 0$ 일 때 $N(h) \to \infty$ 이고 $|r_{j}| > 1$ 이므로 $$ \max_{x_{0} \le x_{n} \le b } | y_{n} - z_{n} | = c \cdot \epsilon |r_{j}|^{p} $$ 를 만족하는 $C>0$ 는 존재할 수 없다. 따라서 메소드는 안정성을 가지지 못하게 된다.
  • Case 2.
    조건 (ii)를 만족하지 않아 $j$ 에 대해 $|r_{j}| = 1 \implies \rho’(r_{j}) = 0$ 인 경우이는 $|r_{j}| = 1$ 이면 $r_{j}$ 이 특성방정식의 중근이라는 의미로, $r_{j}$ 의 중복도 $\nu$ 는 적어도 $2$ 여야한다. 이 경우 제너럴 솔루션은 선형독립인 파티큘러 솔루션 $r_{j}^{n} , n r_{j}^{n} , \cdots , n^{ \nu - 1} r_{j}^{n}$ 들을 포함한 선형결합으로 나타난다. 수식으로 쓰면, $$ z_{n} = c_{j_{0}} r_{j}^{n} + c_{j_{1}} n r_{j}^{n} + \dots + c_{j_{\nu-1}} n^{\nu-1} r_{j}^{n} $$ 여기서 $\displaystyle \epsilon := \max_{ 0 \le k \le \nu-1} | c_{j_{k}} |$ 라고 두면 $| r_{j} | = 1$ 이므로 $$ | z_{0 } | \le \epsilon , | z_{1 } | \le 2 \epsilon , \cdots , \displaystyle | z_{ p} | \le \epsilon( 1 + p + \cdots + p^{\nu -1} ) = \epsilon {{ p^{\nu} -1 } \over { p - 1}} $$ 멀티스텝 메소드이므로 $p \ge 2$ 에 대해 $$ \max_{0 \le n \le p } | y_{n} - z_{n} | = \epsilon {{ p^{\nu} -1 } \over { p - 1}} $$ 메소드를 $[x_{0} , b]$ 에 적용시켜보면 $$ \max_{x_{0} \le x_{n} \le b } | y_{n} - z_{n} | = \epsilon {{ N(h)^{\nu} -1 } \over { N(h) - 1}} $$ 그런데 $h \to 0$ 일 때 $N(h) \to \infty$ 이므로 $$ \max_{x_{0} \le x_{n} \le b } | y_{n} - z_{n} | = c \cdot \epsilon {{ p^{\nu} -1 } \over { p - 1}} $$ 를 만족하는 $C>0$ 는 존재할 수 없다. 따라서 메소드는 안정성을 가지지 못하게 된다.

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

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

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

$$ \begin{align} \displaystyle z_{n+1} = \sum_{j=0}^{p} a_{j} z_{n-j} + h \sum_{j = -1}^{p} b_{j} f (x_{n-j} , z_{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} , z_{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 $$ 이에 대해 $\displaystyle \max_{0 \le n \le p} | y_{ n} - z_{n} | = \epsilon$ 이라고 두자.주어진 메소드는 $$ 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*} \displaystyle | 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 & p \max_{1 \le i \le p} | g_{i}| \max_{1 \le i \le p} | r_{i} + s_{i} |^n \\ \le & p \cdot \epsilon \cdot 1 \end{align*} $$ 따라서 $\displaystyle \max_{ x_{0} \le x_{n} \le b} | e_{n} | = p \epsilon$ 이고, 메소드는 안정성을 갖는다.


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

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

댓글