📂수치해석

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

정리

만약 멀티스텝 메소드가 일관성을 가진다고 하면, 메소드는 안정성을 가진다 $\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$ 를 조절함에 따라서 큰 변화가 될 수도 있다면 메소드가 안정성을 갖지 않았다고 한다.

증명 ¹

일관성을 가지는 멀티스텝 메소드: 초기값 문제 $\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)$ 원래의 증명이 지나치게 어려워서 많은 비약이 있다².

$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$ 이고, 메소드는 안정성을 갖는다.

■