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

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

MENU

数値解析（06/XX）

数値解析

はじめに

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


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

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

Amazon


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


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

2.　非線形方程式の解

2.3　連立非線形方程式

2.3.4　多変数Newton法の収束性と収束の速さ

　多変数の場合でも、1変数の場合と同様に収束性や収束の速さに関する結果が知られている。


定理2.10　多変数関数の\mathrm{Newton}法の収束性　n元連立非線形方程式

\begin{aligned} \boldsymbol{f}(\boldsymbol{x})=\boldsymbol{0} \end{aligned}

の解を\boldsymbol{\alpha}とし、その反復列\left\{\boldsymbol{x}_{\nu}\right\}を

\begin{aligned} \boldsymbol{x}_{\nu+1}=\boldsymbol{x}_{\nu}-J_{\boldsymbol{f}}(\boldsymbol{x}_{\nu})^{-1}\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right) \end{aligned}

とするとき、\boldsymbol{f}(\boldsymbol{x})がC^2級でJ_{\boldsymbol{f}}(\boldsymbol{\alpha})が正則ならば、\boldsymbol{\alpha}に近い初期値から始めれば\left\{\boldsymbol{x}_{\nu}\right\}は\boldsymbol{\alpha}に2次収束する。

(\because　\boldsymbol{f}がn元連立非線形方程式

\begin{aligned} \boldsymbol{f}(\boldsymbol{x})=\boldsymbol{0} \end{aligned}

の解\boldsymbol{\alpha}の近傍でC^2級で、J_{\boldsymbol{f}}(\boldsymbol{\alpha})が正則であると仮定する。このとき行列式の連続性から、充分に小さな正数d^{*}を取れば、\mathscr{D}^{*}=\left\{\boldsymbol{x}\in\mathbb{R}^n\left|\right.\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty}\leq d^{*}\right\}においてJ_{\boldsymbol{f}}(\boldsymbol{x})は正則である。したがって

\begin{aligned} \boldsymbol{g}(\boldsymbol{x})=\boldsymbol{x}-J_{\boldsymbol{f}}(\boldsymbol{x})^{-1}\boldsymbol{f}(\boldsymbol{x}) \end{aligned}

は少なくとも\mathscr{D}^{*}において意味を持つ。両辺をx_jに関して偏微分すれば、

\begin{aligned} \displaystyle{\frac{\partial \boldsymbol{g}(\boldsymbol{x})}{\partial x_j}}=\displaystyle{\frac{\partial \boldsymbol{x}}{\partial x_j}}-\left(\displaystyle{\frac{\partial}{\partial x_j}}J_{\boldsymbol{f}}(\boldsymbol{x})^{-1}\right)\boldsymbol{f}(\boldsymbol{x})-J_{\boldsymbol{f}}(\boldsymbol{x})^{-1}\displaystyle{\frac{\partial \boldsymbol{f}(\boldsymbol{x})}{\partial x_j}} \end{aligned}

が得られる。\displaystyle{\frac{\partial \boldsymbol{f}}{\partial x_j}}はJ_{\boldsymbol{f}}(\boldsymbol{x})の第j列に他ならないから、上式の右辺第3項は第j成分のみ1、それ以外はすべて0であるようなn次元列ベクトルに他ならない。後者はまた\displaystyle{\frac{\partial \boldsymbol{x}}{\partial x_j}}にも等しいから、したがって

\begin{aligned} \displaystyle{\frac{\partial \boldsymbol{g}(\boldsymbol{x})}{\partial x_j}}&=-\left(\displaystyle{\frac{\partial}{\partial x_j}}J_{\boldsymbol{f}}(\boldsymbol{x})^{-1}\right)\boldsymbol{f}(\boldsymbol{x}),\\ \displaystyle{\frac{\partial \boldsymbol{g}(\boldsymbol{\alpha})}{\partial x_j}}&=-\left(\displaystyle{\frac{\partial}{\partial x_j}}J_{\boldsymbol{f}}(\boldsymbol{x})^{-1}\right)\left.\right|_{\boldsymbol{x}=\boldsymbol{\alpha}}\boldsymbol{f}(\boldsymbol{\alpha})=0 \end{aligned}

であるから、

\begin{aligned} G(\boldsymbol{x})=\left(\displaystyle{\frac{\partial g_i(\boldsymbol{x})}{\partial x_i}}\right),\ \left\|G\left(\boldsymbol{x}\right)\right\|_{\infty}\leq\lambda\lt1,\ \boldsymbol{x}\in\mathscr{D} \end{aligned}

に対して、G\left(\boldsymbol{\alpha}\right)=Oを得る。
　以上から、\boldsymbol{\alpha}の充分小さい近傍\mathscr{D}=\left\{\boldsymbol{x}\in\mathbb{R}^n\left|\right.\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty}\leq d\right\}\subset\mathscr{D}^{*}を取れば、ノルムの連続性から、

\begin{aligned} {}^{\exists}\lambda\gt0\ \mathrm{s.t.}\ \left\|G(\boldsymbol{x})\right\|_{\infty}\leq\lambda\lt1 \end{aligned}

が成り立つ。したがって縮小写像の原理　系2を用いることで\boldsymbol{x}_{\nu}\rightarrow\boldsymbol{\alpha}(\boldsymbol{\nu}\rightarrow\infty)を得る。
　またC^2級であるという仮定から、多変数関数に対する\mathrm{Taylor}の定理より\boldsymbol{x}_{\nu}=\begin{bmatrix}x_{\nu,1}\\\vdots\\x_{\nu,j}\\\vdots\\x_{\nu,n}\end{bmatrix}として、

\begin{aligned} 0=f_i(\alpha)=&f_i\left(\boldsymbol{x}_{\nu}\right)+\displaystyle{\sum_{j=1}^{n}\frac{\partial f_i\left(\boldsymbol{x}_{\nu}\right)}{\partial x_j}}\left(\alpha_j-x_{\nu,j}\right)\\ &+\displaystyle{\frac{1}{2!}\sum_{j=1}^{n}\sum_{k=1}^{n}\frac{\partial^2 f_i\left(\boldsymbol{x}_{\nu}+\theta_i\left(\boldsymbol{\alpha}-\boldsymbol{x}_{\nu}\right)\right)}{\partial x_j\partial x_k}}\left(\alpha_j-x_{\nu,j}\right)\left(\alpha_k-x_{\nu,k}\right),\ 0\lt\theta_i\lt1 \end{aligned}

が成り立つ。M=\displaystyle{\max_{j,k}\max_{\boldsymbol{x}\in\mathscr{D}}\left|\frac{\partial^2 f_i\left(\boldsymbol{x}\right)}{\partial x_j\partial x_k}\right|}とおけば、

\begin{aligned} \left|f_i\left(\boldsymbol{x}_{\nu}\right)+\displaystyle{\sum_{j=1}^{n}\frac{\partial f_i\left(\boldsymbol{x}_{\nu}\right)}{\partial x_j}}\left(\alpha_j-x_{\nu,j}\right)\right|\leq\displaystyle{\frac{n^2}{2}}M\left\|\boldsymbol{\alpha}-\boldsymbol{x}_{\nu}\right\|_{\infty}^2 \end{aligned}


であるから、

\begin{aligned} \left\|\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right)+J_{\boldsymbol{f}}\left(\boldsymbol{x}_{\nu}\right)\left(\boldsymbol{\alpha}-\boldsymbol{x}_{\nu}\right)\right\|_{\infty}\leq\displaystyle{\frac{n^2}{2}}M\left\|\boldsymbol{\alpha}-\boldsymbol{x}_{\nu}\right\|_{\infty}^2, \end{aligned}
\begin{aligned} \left\|\boldsymbol{x}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&=\left\|\boldsymbol{x}_{\nu}-\boldsymbol{\alpha}-J_{\boldsymbol{f}}\left(\boldsymbol{x}_{\nu}\right)^{-1}\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right)\right\|_{\infty}\\ &=\left\|-J_{\boldsymbol{f}}\left(\boldsymbol{x}_{\nu}\right)^{-1}\left\{J_{\boldsymbol{f}}\left(\boldsymbol{x}_{\nu}\right)\left(\boldsymbol{\alpha}-\boldsymbol{x}_{\nu}\right)+\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right)\right\}\right\|_{\infty}\\ &\leq\left\|-J_{\boldsymbol{f}}\left(\boldsymbol{x}_{\nu}\right)^{-1}\right\|_{\infty}\left\|J_{\boldsymbol{f}}\left(\boldsymbol{x}_{\nu}\right)\left(\boldsymbol{\alpha}-\boldsymbol{x}_{\nu}\right)+\boldsymbol{f}\left(\boldsymbol{x}_{\nu}\right)\right\|_{\infty}\\ &=O\left(\left\|\boldsymbol{x}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}^2\right) \end{aligned}

が成り立つ。　\blacksquare)

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

　閉領域

\begin{aligned} \mathscr{D}=\left\{\boldsymbol{x}\in\mathbb{R}^n\left|\right.\left\|\boldsymbol{x}-\boldsymbol{\alpha}\right\|_{\infty}\leq d\right\},d\geq0 \end{aligned}

において、n元連立方程式

\begin{aligned} \boldsymbol{x}=\boldsymbol{g}\left(\boldsymbol{x}\right) \end{aligned}

の1つの解\boldsymbol{\alpha}を求める反復

\begin{aligned} \boldsymbol{x}_{\nu+1}=\boldsymbol{g}\left(\boldsymbol{x}_{\nu}\right) \end{aligned}

を考える。
　このとき、実際には誤差限界を\deltaとして、

\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}_{0}\right\|_{\infty}&\leq\delta \end{aligned}

を用いて計算される。\boldsymbol{\delta}_iはその反復における様々な誤差（丸め誤差、打切り誤差など）の合計である。


　収束判定条件\left\|\tilde{\boldsymbol{x}}_{\nu+1}-\tilde{\boldsymbol{x}}_{\nu}\right\|\leq\varepsilonにより誤差を含む反復を打ち切った場合の誤差

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|,\\ \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\| \end{aligned}

を評価する。なお\boldsymbol{g}(\boldsymbol{x})は\mathrm{Lipschitz}連続であると仮定する。
　このとき

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{0}-\boldsymbol{\alpha}\right\|_{\infty}\leq d-\displaystyle{\frac{\delta}{1-\lambda}}\Longrightarrow \tilde{\boldsymbol{x}}_{\nu}\in\mathscr{D},\ \ \nu\geq0 \end{aligned}

が成り立つ。実際、\left\|\tilde{\boldsymbol{x}}_{0}-\boldsymbol{\alpha}\right\|_{\infty}\leq d-\displaystyle{\frac{\delta}{1-\lambda}}ならば、

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&=\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)+\boldsymbol{\delta}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}\\ &=\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)+\boldsymbol{\delta}_{\nu+1}-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\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+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\right\|_{\infty}\\ &\leq\delta+\lambda\left\|\tilde{\boldsymbol{x}}_{\nu-1}-\boldsymbol{\alpha}\right\|_{\infty}\\ &\leq\delta+\lambda\left(\delta+\lambda\left\|\tilde{\boldsymbol{x}}_{\nu-2}-\boldsymbol{\alpha}\right\|_{\infty}\right)\\ &\ \ \ \ \ \ \vdots\\ &\leq\delta\displaystyle{\sum_{k=0}^{\nu-1}}\lambda^{k}+\lambda^{\nu}\left\|\tilde{\boldsymbol{x}}_{0}-\boldsymbol{\alpha}\right\|_{\infty}\\ \end{aligned}

であり、\delta\gt0,0\leq\lambda\lt1より、S_{\nu}=\left\{\delta\displaystyle{\sum_{k=0}^{\nu-1}}\lambda^{k}\right\}_{\nu=1,2,\cdots}は\nuに対して単調増加列であり、

\begin{aligned} S_{1}\leq\cdots\leq S_{\nu}\leq\cdots\leq\displaystyle{\lim_{\nu\rightarrow\infty}S_{\nu}}=\displaystyle{\frac{\delta}{1-\lambda}} \end{aligned}

が成り立つ。したがって

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\displaystyle{\frac{\delta}{1-\lambda}}+\lambda^{\nu}\left\|\tilde{\boldsymbol{x}}_{0}-\boldsymbol{\alpha}\right\|_{\infty}\\ &\leq d \end{aligned}

を得、これは\boldsymbol{x}_{\nu}\in\mathscr{D}に他ならない。
　さらに以下が成り立つ。



定理2.11　多変数反復法の誤差評価(1)　\varepsilon_{\nu}=\left\|\tilde{\boldsymbol{x}}_{\nu}-\tilde{\boldsymbol{x}}_{\nu+1}\right\|_{\infty}とおけば、

\begin{aligned} \displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}}\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}},\\ \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\displaystyle{\frac{\lambda\varepsilon_{\nu}+\delta}{1-\lambda}} \end{aligned}

が成り立つ。

(\because　\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}について、

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}&=\left\|\tilde{\boldsymbol{x}}_{\nu}-\tilde{\boldsymbol{x}}_{\nu+1}+\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}\\ &\leq\left\|\tilde{\boldsymbol{x}}_{\nu}-\tilde{\boldsymbol{x}}_{\nu+1}\right\|_{\infty}+\left\|\tilde{\boldsymbol{\delta}}_{\nu+1}\right\|_{\infty}+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\right\|_{\infty}\\ &=\varepsilon_{\nu}+\left\|\tilde{\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+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\right\|_{\infty}\\ &\leq\varepsilon_{\nu}+\delta+\lambda\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty} \end{aligned}

より、

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}},\\ \left\|\tilde{\boldsymbol{x}}_{\nu+1}-\boldsymbol{\alpha}\right\|_{\infty}&\leq\left\|\boldsymbol{\delta}_{\nu+1}\right\|+\left\|\boldsymbol{g}\left(\tilde{\boldsymbol{x}}_{\nu}\right)-\boldsymbol{g}\left(\boldsymbol{\alpha}\right)\right\|,\\ &\leq\left\|\boldsymbol{\delta}_{\nu+1}\right\|+\lambda\left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|\\ &\leq\delta+\lambda\displaystyle{\frac{\varepsilon_{\nu}+\delta}{1-\lambda}}=\displaystyle{\frac{\delta+\lambda\varepsilon_{\nu}}{1-\lambda}} \end{aligned}

である。また

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

より、

\begin{aligned} \left\|\tilde{\boldsymbol{x}}_{\nu}-\boldsymbol{\alpha}\right\|_{\infty}\geq\displaystyle{\frac{\varepsilon_{\nu}-\delta}{1+\lambda}} \end{aligned}

が成り立つ。　\blacksquare)

今日の復習

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

参考文献

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