강한 립시츠 조건과 오일러 메소드의 오차

강한 립시츠 조건과 오일러 메소드의 오차

Stronger lipschitz

정리

$[x_{0} , b] \times \mathbb{R}$ 에서 정의된 $f$ 에 대해 초기값 문제 $\begin{cases} y’ = f(x,y) \\ y( x_{0} ) = Y_{0} \end{cases}$ 의 해 $Y(x)$ 가 $[x_{0} , b]$ 에서 두 번 미분가능하다고 하자. $f$ 가 모든 $x_{0} \le x \le b$ 와 $ y_{1} , y_{2} \in \mathbb{R}$, 그리고 $K \ge 0$ 에 대해 **강한 립시츠 조건

$$ |f(x,y_{1} ) - f(x,y_{2}) | \le K | y_{1} - y_{2} | $$ 을 만족하면 오일러 메소드로 얻은 해 $\left\{ y_{n} ( x_{ n } ) \ : \ x_{0} \le x_{n} \le b \right\} $ 에 대해 $$ \max_{ x_{0 } \le x_{n} \le b } | Y_{x_{n}} - y_{h} (x_{n}) | \le \epsilon^{( b - x_{0} ) K} | \epsilon_{0} | + \left[ {{ \epsilon^{(b- x_{0}) K } - 1 } \over {K}} \right] \tau (h) $$ 여기서 $\tau (h) = {{h} \over {2}} \left\| Y’’ \right\|_{\infty}$ 이고 $\epsilon_{0} = Y_{0} - y_{h} (x_{0 } )$ 이다.

같이보기

강한 립시츠 조건 $\implies$ 립시츠 조건 $\implies$ 국소 립시츠 조건

설명

말이 정말 어마어마하게 긴데, 요약하면 립시츠 조건보다 조금 강한 조건이 있음으로 하여 오일러 메소드의 정확도를 말해주는 정리다. 조건이 립시츠 조건만 있을 땐 연속성만을 가정했지만 강한 립시츠 조건을 사용할땐 미분가능성까지 생각한다는 점이 다르다.

증명 1

$$ x_{i} : = x_{0} + ih $$

$$ x_{n+1} - x_{n} = h $$

$$ Y_{n} := Y(x_{n} ) $$

$$ y_{n} := y(x_{n}) $$ 이에 대해 $n$ 번째의 오차를 $\epsilon_{n} : = Y(x_{n}) - y (x_{n} )$ 이라 나타내자.

$Y(x_{n+1} )$ 를 $ x_{n}$ 에 대해 $2$ 차 테일러 전개하면 어떤 $x_{n} \le \xi_{n} \le x_{n+1}$ 에 대해 $$ Y_{n+1} = Y_{n} + h Y’_{n} + {{h^2} \over {2}} Y’’ ( \xi_{n} ) $$ 편의상 $\displaystyle \tau_{n} := {{h} \over {2}} Y’’ ( \xi_{n} )$ 이라 하면 $$ Y_{n+1} = Y_{n} + h Y’_{n} + h \tau_{n} $$

$$ \max_{n} | \tau_{n} | \le \tau (h) $$ 양변에서 오일러 메소드로 얻은 식 $y_{n+1} = y_{n} + h f ( x_{n} , y_{n} )$ 을 빼면 $$ Y_{n+1} - y_{n+1} = Y_{n} - y_{n} + h ( f( x_{n} , Y_{n} ) - f (x_{n} , y_{n}) ) + h \tau_{n} $$ $\epsilon_{n}$ 에 대해 나타내면 $$ \epsilon_{n+1} = \epsilon_{n} + h ( f( x_{n} , Y_{n} ) - f (x_{n} , y_{n}) ) + h \tau_{n} $$ 양변에 절댓값을 취하면 $$ | \epsilon_{n+1} | \le | \epsilon_{n} | + h | f( x_{n} , Y_{n} ) - f (x_{n} , y_{n}) | + h | \tau (h) | $$ 립시츠 조건에 의해 $$ | \epsilon_{n+1} | \le | \epsilon_{n} | + h K | Y_{n} - y_{n} | + h | \tau (h) | $$ 정리하면 $$ | \epsilon_{n+1} | \le (1 + hK ) | \epsilon_{n} | + h | \tau (h) | $$ 재귀적으로 풀어내면 $$ | \epsilon_{n+1} | \le (1 + hK )^n | \epsilon_{0} | + [ 1 + (1 + hK) + \cdots + (1 + hK)^{n-1} ] h | \tau (h) | $$ 유한등비급수의 합 공식에 의해 $$ | \epsilon_{n+1} | \le (1 + hK )^n | \epsilon_{0} | + \left[ {{ (1+ hK)^{n} - 1} \over {hK }} \right] h | \tau (h) | $$

베르누이 부등식의 따름 정리: $(1 + x )^{ \alpha } \le e^{ x \alpha }$

베르누이 부등식의 따름정리에 따라 $ (1 + hK )^n \le e^{hKn}$ 이므로 $$ | \epsilon_{n} | \le e^{( b - x_{0} ) K} | \epsilon_{0} | + \left[ {{ e^{(b- x_{0}) K } - 1 } \over {K}} \right] \tau (h) $$

추가 조건

한편, 립시츠 조건에 의해 $\displaystyle | \epsilon_{n+1} | \le | \epsilon_{n} | + h K | Y_{n} - y_{n} | + h | \tau (h) | $ 인 부분부터 $\displaystyle {{\partial f (x,y) } \over { \partial y }} \le 0$ 이라는 조건이 추가된다고 생각해보자. 표현을 보기 좋게 고치면 $$ | \epsilon_{n+1} | \le (1 + hK) | \epsilon_{n} | + {{h^2} \over {2}} | Y’’ ( \xi_{n } ) | $$ 평균값 정리에 의해 $$ K = \left| {{f(x,y_{1} ) - f(x,y_{2}) } \over {y_{1} - y_{2}}} \right| = \left| {{ \partial f ( x_{n} , \zeta_{n} ) } \over { \partial y }} \right| $$ 를 만족하는 $\zeta_{n} \in \mathscr{H} \left\{ y_{h} (x_{n} ) , Y ( x_{n} ) \right\}$ 이 존재한다. 이 때 $h$ 가 충분히 작아서 $\displaystyle 1+ h {{ \partial f ( x_{n} , \zeta_{n} ) } \over { \partial y }} \ge -1$ 이면 $$ | \epsilon_{n+1} | \le | \epsilon_{n} | + {{h^2} \over {2}} | Y’’ ( \xi_{n } ) | $$ 이 부등식도 재귀적으로 풀어내면 $$ | \epsilon_{n} | \le | \epsilon_{0} | + {{h^2} \over {2}} [ |Y’’ ( \xi_{0 } ) | + \cdots + |Y’’ ( \xi_{n-1 } ) | ] $$ 따라서 $$ | \epsilon_{n} | \le | \epsilon_{0} | + {{h^2} \over {2}} n \left\| Y’’ \right\|_{\infty} $$ 인데, $nh = b - x_{0}$ 이므로 $$ | \epsilon_{n} | \le | \epsilon_{0} | + {{h} \over {2}} \left\| Y’’ \right\|_{\infty} ( b - x_{0}) $$ 이 말인즉슨 $\displaystyle {{\partial f (x,y) } \over { \partial y }} \le 0$ 라는 조건이 원래 $(b - x_{0})$ 에 대해 지수적으로 증가하는 오차의 상한을 선형적으로 줄였다는 뜻이다. 다행스럽게도 자연계에 산재하는 많은 문제들이 이런 가정을 만족시키고, 그 덕분에 오차가 크게 줄어듦을 장담할 수 있다.


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

댓글