「大人の教養・知識・気付き」を伸ばすブログ

一流の大人（ビジネスマン、政治家、リーダー…）として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。データ分析・語学に力点を置いています。　→現在、コンサルタントの雛になるべく、少しずつ勉強中です(※2024年1月21日改訂)。

MENU

数値解析（07/XX）

数値解析

はじめに

　プログラミング云々ばかり言っていても、それがどのように計算されているかを知らないと仕様が無い。ということで数値解析を学んでいく。
　基本的には

数値解析入門 (サイエンスライブラリ現代数学への入門)

数値解析入門 (サイエンスライブラリ現代数学への入門)

Amazon
を参照しつつ、他書で補足する。


https://power-of-awareness.com/entry/2023/03/20/0500power-of-awareness.com

前回の復習

  • \mathrm{Newton}法は多変数においても成立し得るか。成立するならば、その収束速度について述べよ。

    　成立する。\mathrm{Newton}法はその解に近い初期値を選べば2次収束する。

  • \mathrm{Lipschitz}連続の定義を述べよ。

    　　閉集合\mathit{\Omega}\subset\mathbb{R}^nで定義された\boldsymbol{g}(\boldsymbol{x})が、\lambda\gt0に対して、ノルム\|\cdot\|が定義されていて、

    \begin{aligned}\left\|\boldsymbol{g}\left(\boldsymbol{x}\right)-\boldsymbol{g}\left(\boldsymbol{x}^{\prime}\right)\right\|\leq\lambda\left\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\right\|,\ \boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathit{\Omega}\end{aligned}

    が成り立つとき、\boldsymbol{g}(\boldsymbol{x})は（\|\cdot\|に関して）\mathrm{Lipschitz}連続であるという。

2.　非線形方程式の解

2.3　連立非線形方程式

2.3.5　多変数反復法の誤差解析

　定理2.12にはより精緻に改良されたものが存在する。


定理2.12　多変数反復法の誤差評価(2)　反復\boldsymbol{x}=\boldsymbol{g}\left(\boldsymbol{x}\right)がp(\gt1)次収束する、すなわちM\gt0に対して

\begin{aligned} \left\|\boldsymbol{x}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}\leq M\left\|\boldsymbol{x}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^p \end{aligned}

が成り立つならば、仮定\varepsilon_{\nu}\gt\delta,\ 0\lt\mu\leq\lambdaおよび

\begin{aligned} M\left(\varepsilon_{\nu}+\delta\right)^{p-1}\lt\displaystyle{\min\left\{\lambda(1-\lambda)^{p-1},\mu(1-\mu)^{p-1}\right\}} \end{aligned}

の下で、

\begin{aligned} \displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\lt\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\lt\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}}},\ p\gt1 \end{aligned}

が成り立つ。特にp=2ならば、仮定\varepsilon_{\nu}\gt\deltaおよびM(\varepsilon_{\nu}+\delta)\lt\lambda(1-\lambda)の下で、より詳しく書き下した

\begin{aligned} \displaystyle{\frac{2(\varepsilon_{\nu}-\delta)}{1+\sqrt{1+4M(\varepsilon_{\nu}-\delta)}}}\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\leq\displaystyle{\frac{2(\varepsilon_{\nu}+\delta)}{1+\sqrt{1-4M(\varepsilon_{\nu}-\delta)}}},\ p=2 \end{aligned}

が成り立つ。

(\because　まず

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\tilde{\boldsymbol{x}}_{\nu}\right\|_{\infty}&=\left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}+\boldsymbol{\alpha}-\tilde{\boldsymbol{x}}_{\nu}\right\|_{\infty}\\ &=\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)+\boldsymbol{\delta}_{\nu+1}-\boldsymbol{\alpha}+\boldsymbol{\alpha}-\tilde{\boldsymbol{x}}_{\nu}\right\|_{\infty}\\ &\leq\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{\alpha}\right\|_{\infty}+\left\|\boldsymbol{\delta}_{\nu+1}\right\|_{\infty}+\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\\ &\leq M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^{p}+\delta+\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty} \end{aligned}

であるから、

\begin{aligned} M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^{p}+\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}-\left(\varepsilon_{\nu}-\delta\right)\geq0 \end{aligned}

を得る。また

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\tilde{\boldsymbol{x}}_{\nu+1}\right\|_{\infty}+\left\|\boldsymbol{\delta}\right\|_{\infty}+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{\alpha}\right\|_{\infty}\\ &=\varepsilon_{\nu}+\left\|\boldsymbol{\delta}\right\|_{\infty}+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{\alpha}\right\|_{\infty}\\ &\leq\varepsilon_{\nu}+\delta+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{\alpha}\right\|_{\infty}\\ &\leq\varepsilon_{\nu}+\delta+M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^p \end{aligned}

より

\begin{aligned} M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^p-\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}+\varepsilon_{\nu}+\delta\geq0 \end{aligned}

を得る。
　ここで\varphi_p(t)=Mt^p+t-(\varepsilon_{\nu}-\delta),\psi_p(t)=Mt^p-t+\varepsilon_{\nu}+\deltaとおくと、

\begin{aligned} &\varphi_p\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\right)\\ =&M\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\right)^p+\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}-(\varepsilon_{\nu}-\delta)\\ =&M\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\right)^p-\displaystyle{\frac{M(\varepsilon_{\nu}-\delta)^{p-1}\left(\varepsilon_{\nu}-\delta\right)}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\\ =&M\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\right)(\varepsilon_{\nu}-\delta)^{p-1}\left\{\left(\displaystyle{\frac{1}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\right)^{p-1}-1\right\}\\ \lt&0 \end{aligned}

であり、また仮定より

\begin{aligned} &M\left(\varepsilon_{\nu}+\delta\right)^{p-1}\lt\displaystyle{\min\left\{\lambda(1-\lambda)^{p-1},\mu(1-\mu)^{p-1}\right\}}\leq\mu(1-\mu)^{p-1}\\ \Leftrightarrow&M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}\lt\mu\\ \Leftrightarrow&\displaystyle{\frac{1}{1-M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}}}\lt\displaystyle{\frac{1}{1-\mu}} \end{aligned}

に注意すれば、

\begin{aligned} &\psi_p\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}}}\right)\\ =&M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}}}\right)^p-\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}}}\right)+\varepsilon_{\nu}+\delta\\ \leq&(\varepsilon_{\nu}+\delta)\left\{\left(\displaystyle{\frac{1}{1-\mu}}\right)^p M(\varepsilon_{\nu}-\delta)-\displaystyle{\frac{1}{1-\mu}}+1\right\}\\ \lt&(\varepsilon_{\nu}+\delta)\left\{\left(\displaystyle{\frac{1}{1-\mu}}\right)^p \displaystyle{\min\left\{\lambda(1-\lambda)^{p-1},\mu(1-\mu)^{p-1}\right\}}-\displaystyle{\frac{1}{1-\mu}}+1\right\}\\ \leq&(\varepsilon_{\nu}+\delta)\left\{\left(\displaystyle{\frac{1}{1-\mu}}\right)^p\mu(1-\mu)^{p-1}-\displaystyle{\frac{1}{1-\mu}}+1\right\}\\ =&(\varepsilon_{\nu}+\delta)\left(\displaystyle{\frac{\mu}{1-\mu}}-\displaystyle{\frac{1}{1-\mu}}+1\right)=0 \end{aligned}

である。したがって\varphi_{p}(t)=0の正根を\xi_{p},\psi_{p}(t)=0の最小の正根を\eta_{p}とすれば、

\begin{aligned} \varphi_{p}\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)=&M\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)^p+\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}-(\varepsilon_{\nu}-\delta)\\ =&M\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)^p-\displaystyle{\frac{\lambda(\varepsilon_{\nu}-\delta)}{1+\lambda}}\\ \leq&M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1+\lambda}}\right)^{p-1}\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)-\displaystyle{\frac{\lambda(\varepsilon_{\nu}-\delta)}{1+\lambda}}\\ =&\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)\left\{M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1+\lambda}}\right)^{p-1}-\lambda\right\}\\ \lt&\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)\left\{\left(\displaystyle{\frac{1}{1+\lambda}}\right)^{p-1}\displaystyle{\min\left\{\lambda(1-\lambda)^{p-1},\mu(1-\mu)^{p-1}\right\}}-\lambda\right\}\\ \leq&\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)\left\{\left(\displaystyle{\frac{1}{1+\lambda}}\right)^{p-1}\lambda(1-\lambda)^{p-1}-\lambda\right\}\\ =&\lambda\left(\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\right)\left\{\left(\displaystyle{\frac{1-\lambda}{1+\lambda}}\right)^{p-1}-1\right\}\lt0 \end{aligned}

および

\begin{aligned} \psi_{p}\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)=&M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)^p-\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)+\varepsilon_{\nu}+\delta\\ =&M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)^p-\displaystyle{\frac{\lambda(\varepsilon_{\nu}+\delta)}{1-\lambda}}\\ =&\displaystyle{\frac{\lambda(\varepsilon_{\nu}+\delta)}{1-\lambda}}\left\{M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)^{p-1}-\lambda\right\}\\ \lt&\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)\left\{\left(\displaystyle{\frac{1}{1-\lambda}}\right)^{p-1}\displaystyle{\min\left\{\lambda(1-\lambda)^{p-1},\mu(1-\mu)^{p-1}\right\}}-\lambda\right\}\\ \leq&\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)\left\{\left(\displaystyle{\frac{1}{1-\lambda}}\right)^{p-1}\lambda(1-\lambda)^{p-1}-\lambda\right\}=0 \end{aligned}

に注意すれば、定理6.3も踏まえて、

\begin{aligned} \displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+M(\varepsilon_{\nu}-\delta)^{p-1}}}\lt\xi_p\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\leq\eta_{p}\lt\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-M\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\mu}}\right)^{p-1}}} \end{aligned}

を得る。
　特にp=2ならば、

\begin{aligned} \varphi_p(t)=&Mt^2+t-(\varepsilon_{\nu}-\delta)=0\\ \Leftrightarrow t=&\displaystyle{\frac{-1\pm\sqrt{1+4M(\varepsilon_{\nu}-\delta)}}{2M}},\\ \psi_p(t)=&Mt^2-t+\varepsilon_{\nu}+\delta=0\\ \Leftrightarrow t=&\displaystyle{\frac{1\pm\sqrt{1+4M(\varepsilon_{\nu}+\delta)}}{2M}} \end{aligned}

であるから、

\begin{aligned} \xi_p&=\displaystyle{\frac{-1+\sqrt{1+4M(\varepsilon_{\nu}-\delta)}}{2M}}=\displaystyle{\frac{2(\varepsilon_{\nu}-\delta)}{1+\sqrt{1+4(\varepsilon_{\nu}-\delta)}}},\\ \eta_p&=\displaystyle{\frac{1-\sqrt{1+4M(\varepsilon_{\nu}+\delta)}}{2M}}=\displaystyle{\frac{2(\varepsilon_{\nu}+\delta)}{1+\sqrt{1-4(\varepsilon_{\nu}-\delta)}}} \end{aligned}

で、これらを代入することで、

\begin{aligned} \displaystyle{\frac{2(\varepsilon_{\nu}-\delta)}{1+\sqrt{1+4(\varepsilon_{\nu}-\delta)}}}\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\leq\displaystyle{\frac{2(\varepsilon_{\nu}+\delta)}{1+\sqrt{1-4(\varepsilon_{\nu}-\delta)}}} \end{aligned}

を得る。　\blacksquare)

2.3.6　多変数Newton法の誤差評価

　特別な場合として、\boldsymbol{f}(\boldsymbol{x})=\boldsymbol{0}を解く\mathrm{Newton}型反復

\begin{aligned} \boldsymbol{x}_{\nu+1}&=\boldsymbol{x}_{\nu}-A\left(\boldsymbol{x}_{\nu}\right)\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right),\\ \boldsymbol{g}\left(\boldsymbol{x}\right)&=\boldsymbol{x}-A(\boldsymbol{x})\boldsymbol{f}(\boldsymbol{x}) \end{aligned}

を考える。ここでA(\boldsymbol{x})は、\boldsymbol{f}(\boldsymbol{x})=\boldsymbol{0}の解\boldsymbol{\alpha}を含む閉領域\mathscr{D}において正則なn次行列で、\boldsymbol{f}がC^2級だとする。



定理2.13　多変数\mathrm{Newton}法の誤差評価　\mathrm{Newton}法の反復

\begin{aligned} \boldsymbol{x}_{\nu+1}&=\boldsymbol{x}_{\nu}-A\left(\boldsymbol{x}_{\nu}\right)\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right),\\ \boldsymbol{g}\left(\boldsymbol{x}\right)&=\boldsymbol{x}-A(\boldsymbol{x})\boldsymbol{f}(\boldsymbol{x}) \end{aligned}

の誤差を含んだ反復

\begin{aligned} \tilde{\boldsymbol{x}}_{\nu+1}&=\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)+\boldsymbol{\delta}_{\nu+1},\\ \tilde{\boldsymbol{x}}_{0}&=\boldsymbol{x}_0+\boldsymbol{\delta}_0,\\ \left\|\boldsymbol{\delta}\right\|_{\infty}&\leq\delta,\nu\geq0 \end{aligned}

は、仮定

\begin{aligned} \varepsilon_{\nu}&=\left\|\tilde{\boldsymbol{x}}_{\nu}-\tilde{\boldsymbol{x}}_{\nu+1}\right\|_{\infty},\\ M(\varepsilon_{\nu}+\delta)&\lt(\lambda-\kappa)(1-\lambda) \end{aligned}

の下で

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\displaystyle{\frac{1-\kappa-2M\varepsilon_{\nu}-\sqrt{(1-\kappa)^2-4M(\varepsilon_{\nu}+\delta)}}{2M}}\\ &=\displaystyle{\frac{\delta+\kappa\varepsilon_{\nu}}{1-\kappa}}+\displaystyle{\frac{M(\varepsilon_{\nu}+\delta)^2}{1-\kappa}}+\cdots \end{aligned}

が成り立つ。

(\because　A(\boldsymbol{x})は、\boldsymbol{f}(\boldsymbol{x})=\boldsymbol{0}の解\boldsymbol{\alpha}を含む閉領域\mathscr{D}において正則なn次行列で、\boldsymbol{f}がC^2級だとすると、

\begin{aligned} \boldsymbol{0}=\boldsymbol{f}\left(\boldsymbol{\alpha}\right)&=\boldsymbol{f}\left(\boldsymbol{x}\right)+J_{\boldsymbol{f}}(\boldsymbol{x})(\boldsymbol{\alpha}-\boldsymbol{x})+\displaystyle{\frac{1}{2}}\boldsymbol{r},\\ J_{\boldsymbol{f}}(\boldsymbol{x})&=\displaystyle{\frac{\partial f_i(\boldsymbol{x})}{\partial x_j}},\\ \left\|\boldsymbol{r}\right\|_{\infty}&=M_0\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty}^2,\\ M_0&=n^2\displaystyle{\max_{i,j,k}\max_{\boldsymbol{x}\in\mathscr{D}}\left|\displaystyle{\frac{\partial^2 f_i(\boldsymbol{x})}{\partial x_j\partial x_k}}\right|} \end{aligned}

と書け、

\begin{aligned} \boldsymbol{g}(\boldsymbol{x})-\boldsymbol{g}(\boldsymbol{\alpha})=\left(I-A(\boldsymbol{x})J_{\boldsymbol{x}}(\boldsymbol{x})\right)(\boldsymbol{x}-\boldsymbol{\alpha})+\displaystyle{\frac{1}{2}}A(\boldsymbol{x})\boldsymbol{r} \end{aligned}

である。
　ここで

\begin{aligned} \kappa&=\displaystyle{\max_{\boldsymbol{x}\in\mathscr{D}}\left\|I-A(\boldsymbol{x})J_{\boldsymbol{f}}(\boldsymbol{x})\right\|_{\infty}},\\ M&=\displaystyle{\frac{1}{2}M_0\max_{\boldsymbol{x}\in\mathscr{D}}\left\|A(\boldsymbol{x})\right\|_{\infty}},\\ \lambda&=\kappa+Md \end{aligned}

とおくと、

\begin{aligned} \left\|\boldsymbol{g}(\boldsymbol{x})-\boldsymbol{g}(\boldsymbol{\alpha})\right\|_{\infty}&\leq\kappa\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty}+M\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty}^2\\ &\leq\lambda\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty} \end{aligned}

が成り立つ。A(\boldsymbol{x})をJ_{\boldsymbol{f}}(\boldsymbol{x})^{-1}に充分近く、d\gt0を十分に小さく選び、\lambda\lt1が成り立つとすれば、誤差を含んだ反復

\begin{aligned} \tilde{\boldsymbol{x}}_{\nu+1}&=\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)+\boldsymbol{\delta}_{\nu+1},\\ \tilde{\boldsymbol{x}}_{0}&=\boldsymbol{x}_0+\boldsymbol{\delta}_0,\\ \left\|\boldsymbol{\delta}\right\|_{\infty}&\leq\delta,\nu\geq0 \end{aligned}

において

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\tilde{\boldsymbol{x}}_{\nu+1}\right\|_{\infty}+\left\|\boldsymbol{\delta}_{\nu+1}\right\|_{\infty}+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\right\|_{\infty}\\ &\leq\varepsilon_{\nu}+\delta+\kappa\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}+M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^2 \end{aligned}
\begin{aligned} \therefore\ M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^2-(1-\kappa)\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}+\varepsilon_{\nu}+\delta\geq0 \end{aligned}

である。いま

\begin{aligned} \psi(t)=Mt^2-(1-\kappa)t+\varepsilon_{\nu}+\delta \end{aligned}

とおけば、

\begin{aligned} &\psi\left(\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}\right)\lt0\\ \Leftrightarrow&M(\varepsilon_{\nu}+\delta)\lt(1-\lambda)(\lambda-\kappa) \end{aligned}

である。この条件が成り立つ場合、定理2.12より、

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\leq\displaystyle{\frac{1-\kappa-\sqrt{(1-\kappa)^2-4M(\varepsilon_{\nu}+\delta)}}{2M}} \end{aligned}

である。この最右辺を\tauとおけば、二項展開により、

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\left\|\boldsymbol{\delta}_{\nu+1}\right\|_{\infty}+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\right\|_{\infty}\\ &\leq\delta+\kappa\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}+M\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^2\\ &\leq\delta+\kappa\tau+M\tau^2\\ &=\tau-\varepsilon_{\nu}\\ &\left[\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\kappa}}+\displaystyle{\frac{M(\varepsilon_{\nu}+\delta)^2}{(1-\kappa)^3}}+\cdots\right]-\varepsilon_{\nu} \end{aligned}

を得る。　\blacksquare)


　なお多変数\mathrm{Newton}法を実際に計算するとき、ヤコビアンの逆行列を実際に計算する必要はない。なぜならば、\boldsymbol{x}_kが求まったとすれば、\boldsymbol{y}に関する連立一次方程式

\begin{aligned} J_{\boldsymbol{f}}(\boldsymbol{x}_k)\boldsymbol{y}=\boldsymbol{f}(\boldsymbol{x}_k) \end{aligned}

を解き、\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-\boldsymbol{y}とすればよいからである。したがって多変数\mathrm{Newton}法における反復で最も重要なのは、連立一次方程式を解くことにある。

※今日の復習はなし

参考文献

プライバシーポリシー お問い合わせ