📂数値解析

強いリプシッツ条件とオイラーメソッドの誤差

定理

$[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$ 局所リプシッツ条件

説明

非常に長い説明だったが、要約すると、オイラーメソッドの解の正確性について話す少し強い条件が リプシッツ条件よりあるということだ。リプシッツ条件の場合は連続性のみを仮定していたが、強いリプシッツ条件を使う場合は微分可能性まで考慮する点が異なる。

証明 ¹

$$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})$ に関して指数関数的に増加する誤差の上限を線形に減少させたということだ。幸いにも自然界に存在する多くの問題がこの仮定を満たしており、そのおかげで誤差が大幅に減少することが保証される。