数値解析（02/XX） - 「大人の教養・知識・気付き」を伸ばすブログ

はじめに

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

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

作者:山本哲朗
サイエンス社

Amazon

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

はじめに
前回
前回の復習
2.　非線形方程式の解
- 2.1　反復法
  - 2.1.1　縮小写像の原理と収束定理
  - 2.1.2　反復法の収束性
今日の復習
次回
参考文献

前回

power-of-awareness.com

前回の復習

実数 $x$ をあるコンピュータに入力すると浮動小数点で記憶されるとき、 $β$ 進 $t$ 桁浮動小数点数で表示せよ。
　
$\begin{aligned}x=\pm0.d_1d_2\cdots d_n\times \beta^t=\pm \displaystyle{\sum_{i=1}^{t}d_i\beta^{m-i} },\ d_1\neq0\end{aligned}$

$a$ を実数 $x$ の近似値とするとき、誤差、絶対誤差、限界および相対誤差を定義せよ。
　
$\begin{aligned}誤差：&\varepsilon:=a-x,\\絶対誤差：&|\varepsilon|:=|a-x|,\\限界：&e\geq |\varepsilon|\end{aligned}$

丸め誤差を説明せよ。
　　コンピュータが実数 $x$ を $β$ 進 $t$ 桁浮動小数点数で表示する（近似される）ことで発生する誤差のこと。

桁落ちを説明せよ。
　　近しい値の引き算により誤差の桁数が大きくなること。

情報落ちを説明せよ。
　　指数部に大きな差のある2つの数による和や差で発生する誤差が大きくなること。

打切り誤差を説明せよ。
　　無限回数の計算により表現される値を有限回の計算に打ち切ったことで発生する誤差のこと。

オーバーフローを説明せよ。
　計算の途中で表現可能な上限値を値が超えてしまい、その値を表現できなくなること。

2.　非線形方程式の解

　関数 $f(x)$ が与えられたときに方程式 $f(x)=0$ を満たす解 $x$ を求める問題を考える。 $f(x)$ が4次以下の多項式であれば解の公式が存在する。しかし一般にはそのような公式は存在しない。そこで $f(x)$ の符号や微分係数などの情報を基に繰り返し計算を通じて解を求めていく。
　なお求める方程式が(連立)1次方程式である場合は線形代数の知見を基に解くことになり、そのためには別の知識や考え方が必要になるため、別項で改めて扱うことにする。

2.1　反復法

　 $x$ に関する任意の関数 $f(x)$ に対して方程式

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

を解くことを考える。
　解が存在しない場合を考えても意味が無いため、解は存在しまた複数存在するとしてもそのうちの1つがとりあえず求まればよいものとする。
　このときには反復法を用いるのが1つの方法である。すなわち適当な初期値 $x_0$ から出発し、求めたい解 $\alpha$ に収束するような数列 $\{x_{\nu}\}$ を構成し、 $x_{\nu}$ が $\alpha$ に充分近づいたら計算を打ち切ってその値を近似解とする手法である。収束判定には、正数 $\varepsilon$ を収束判断のための精度を表す水準として

$\left|x_{\nu+1}-x_{\nu}\right|\lt\varepsilon$
$\left|x_{\nu+1}-x_{\nu}\right|\lt\varepsilon\left|x_{\nu}\right|$
$\left|f\left(x_{\nu}\right)\right|\lt\varepsilon$

といった不等式のいずれかを採用する。
　収束列 $\{x_{\nu}\}$ は以下のような手順で構成される。まず方程式 $f(x)=0$ を変形して

$\begin{aligned} x=g(x) \end{aligned}$

を得る。次に求めたい解 $\alpha$ を含むような適当な閉区間 $I$ において $\varphi(x)\neq0$ になるように選び、

$\begin{aligned} g(x)=x-\varphi(x)f(x) \end{aligned}$

とおく。次に $x_0$ を適当に与えて

$\begin{aligned} x_{\nu+1}=g(x_{\nu}),\ \nu=0,1,2,\cdots \end{aligned}$

とおく。 $\varphi(x)$ を適当に与えることで様々な反復法を得る。

$\mathrm{Newton}$ 法
　 $x_{\nu+1}=x_{\nu}-\displaystyle{\frac{f(x_{\nu})}{f^{\prime}(x_{\nu})}},\ \varphi(x)=\displaystyle{\frac{1}{f^{\prime}(x)}}$
線形逆補間法
　 $x_{\nu+1}=x_{\nu}-\displaystyle{\frac{(x_{\nu}-x_0)f(x_{\nu})}{f(x_{\nu})-f(x_0)}},\ \varphi(x)=\displaystyle{\frac{x-x_0}{f(x)-f(x_0)}}$
$\mathrm{von\ Mises}$ 法
　 $x_{\nu+1}=x_{\nu}-\displaystyle{\frac{f(x_{\nu})}{f^{\prime}(x_{0})}},\ \varphi(x)=\displaystyle{\frac{1}{f^{\prime}(x_0)}}$

ただし、 $\varphi(x)$ の取り方によっては収束が遅かったり、そもそも発散する恐れもある。

2.1.1　縮小写像の原理と収束定理

　方程式

$\begin{aligned} x=g(x) \end{aligned}$

に対する反復

$\begin{aligned} x_{\nu+1}=g(x_{\nu}),\ \nu=0,1,2\cdots \end{aligned}$

の収束を論じるには、次の定理が基本的である。

定理2.1　縮小写像の原理　完備*1な区間 $I\subset\mathbb{R}$ で定義された関数 $g(x)$ が

$x\in I\Rightarrow g(x)\in I$
$\mathrm{Lipschitz}$ 条件
　
$\begin{aligned}x,x^{\prime}\in I\Rightarrow{}^{\exists}\lambda\in\left[0,1\right)\ \mathrm{s.t.}\ \left|g(x)-g(x^{\prime})\right|\leq\lambda\left|x-x^{\prime}\right|\end{aligned}$

を満たすならば、方程式 $x=g(x)$ は $I$ 内にただ1つの解が存在し、それは反復列 $\left\{x_{\nu}\right\}$ の極限として得られる。上記条件を満たす関数を縮小写像という。

( $\because$ 　 ${}^{\forall}x_0\in I$ について $\{x_{\nu}\}$ を

$\begin{aligned} x_{\nu+1}=g(x_{\nu}),\ \nu=0,1,2\cdots \end{aligned}$

を満たすように構成するとき、

$\begin{aligned} \left|x_{\nu+1}-x_{\nu}\right|=\left|g(x_{\nu})-g(x_{\nu-1})\right|leq\lambda\left|x_{\nu}-x_{\nu-1}\right|\leq\cdots\leq\lambda^{\nu}\left|x_{1}-x_{0}\right| \end{aligned}$

が成り立つ。したがって $\mu\gt\nu$ であるような $\mu\in\mathbb{N}$ について

$\begin{aligned} \left|x_{\nu}-x_{\mu}\right|&\leq\left|x_{\nu}-x_{\nu+1}\right|+\left|x_{\nu+1}-x_{\nu+2}\right|+\cdots+\left|x_{\mu-1}-x_{\mu}\right|\\ &\leq\left(\lambda^{\nu}+\lambda^{\nu+1}+\cdots+\lambda^{\mu-1}\right)\left|x_1-x_0\right|\\ &\leq\displaystyle{\frac{\lambda^{\nu}}{1-\lambda}}\left|x_1-x_0\right|\rightarrow0(\nu\rightarrow\infty) \end{aligned}$

が得られる。以上から $\{x_{\nu}\}$ は $\mathrm{Cauchy}$ 列をなし、区間 $I$ の完備性から、これはある点 $\alpha\in I$ に収束する。この $\alpha$ は方程式

$\begin{aligned} x=g(x) \end{aligned}$

の解である。実際、 $\mathrm{Lipschitz}$ 条件から $g$ は連続で

$\begin{aligned} \alpha=\displaystyle{\lim_{\nu\rightarrow\infty}x_{\nu+1}}=\displaystyle{\lim_{\nu\rightarrow\infty}g(x_{\nu})}=g\left(\displaystyle{\lim_{\nu\rightarrow\infty}x_{\nu}}\right)=g(\alpha) \end{aligned}$

が成り立つ。
　またその一意性について、もし $I$ 内における他の解 $\beta$ が存在するならば、

$\begin{aligned} 0\lt\left|\alpha-\beta\right|=\left|g(\alpha)-g(\beta)\right|\leq\lambda\left|\alpha-\beta\right|\lt\left|\alpha-\beta\right| \end{aligned}$

が成り立つがこれは矛盾である。したがって $\alpha$ は $I$ 内の唯一の解である。　 $\blacksquare$ )

　ここから2つの系が得られる。

系2.2　縮小写像の定理　方程式 $x=g(x)$ の1つの解 $\alpha$ 、区間 $I=[\alpha-d,\alpha+d],d\gt0$ とする。 $I$ において $g(x)$ が $\mathrm{Lipschitz}$ 条件

$\begin{aligned} x,x^{\prime}\in I\Rightarrow{}^{\exists}\lambda\in\left[0,1\right)\ \mathrm{s.t.}\ \left|g(x)-g(x^{\prime})\right|\leq\lambda\left|x-x^{\prime}\right| \end{aligned}$

を満たすならば、

$I$ 内の解は $\alpha$ のみであり、
$x_0\in I,x_{\nu+1}=g(x_{\nu})\Rightarrow x_{\nu}\in I\land x_{\nu}\rightarrow\alpha(\nu\rightarrow\infty)$

( $\because$ 　 $x\in I$ のとき

$\begin{aligned} \left|g(x)-\alpha\right|=\left|g(x)-g(\alpha)\right|\leq\lambda\left|x-\alpha\right|\leq\lambda d\lt d \end{aligned}$

である。したがって $g(x)\in I$ で、定理2.1の仮定が満たされることになる。　　 $\blacksquare$ )

系2.3　縮小写像の定理　 $g(x)$ が区間 $I=\left[\alpha-d,\alpha+d\right],d\gt0$ において $C^1$ 級で

$\begin{aligned} \displaystyle{\max_{x\in I}\left|g^{\prime}(x)\right|}\leq\lambda\lt1 \end{aligned}$

ならば系1が成り立つ。

( $\because$ 　 $x,x^{\prime}\in I$ ならば、平均値の定理から、

$\begin{aligned} \left|g(x)-g(x^{\prime})\right|=\left|g^{\prime}(\xi)(x-x^{\prime})\right|\leq\lambda\left|x-x^{\prime}\right|,0\leq\lambda\lt1 \end{aligned}$

を得る。したがって $g$ は区間 $I$ において縮小写像である。　 $\blacksquare$ )

定理2.4　誤差評価　縮小写像の定理における仮定の下で、反復

$\begin{aligned} x_{\nu+1}=g(x_{\nu}), \nu=0,1,2\cdots \end{aligned}$

を行なう。 $\varepsilon_{\nu}=\left|x_{\nu}-x_{\nu+1}\right|$ とおき、 $\alpha$ を方程式

$\begin{aligned} x=g(x) \end{aligned}$

の解とすれば、

$\begin{aligned} \displaystyle{\frac{\varepsilon_{\nu}}{1+\nu}}\leq\left|x_{\nu}-\alpha\right|\leq\displaystyle{\frac{\varepsilon_{\nu}}{1-\nu}}\leq\displaystyle{\frac{\lambda^{\nu}\varepsilon_{\varepsilon_0}}{1-\nu}},\ \nu\geq1 \end{aligned}$

が成り立つ。

( $\because$ 　最初の2つの不等式は、

$\begin{aligned} \varepsilon_{\nu}=\left|x_{\nu+1}-x_{\nu}\right|&\leq\left|x_{\nu+1}-\alpha\right|+\left|x_{\nu}-\alpha\right|\leq(\nu+1)\left|x_{\nu}-\alpha\right|,\\ \left|x_{\nu}-\alpha\right|&\leq\left|x_{\nu}-x_{\nu+1}\right|+\left|g(x_{\nu})-g(\alpha)\right|\leq\varepsilon_{\nu}+\lambda\left|x_{\nu}-\alpha\right| \end{aligned}$

から得られる。また $\varepsilon_{\nu}=\left|g(x_{\nu})-g(x_{\nu-1})\right|\leq\lambda\varepsilon_{\nu-1}\leq\cdots\leq\lambda^{\nu}\varepsilon_0$ より、3つ目の不等式を得る。　 $\blacksquare$ )

2.1.2　反復法の収束性

定理2.5　反復法の収束性　定数関数でない関数 $\varphi(x)$ に唯一の不動点 $a=\varphi(a)$ が存在するとし、 $\varphi(x)$ は $a$ の近傍で $C^1$ 級だとする。このとき以下が成り立つ。

$|\varphi^{\prime}(a)|\lt1$ ならば、 $a$ の充分近くに初期値 $a_0$ を取ると、反復法 $x_{k+1}=\varphi(x_k)$ は $a$ に収束する。
$|\varphi^{\prime}(a)|\gt1$ ならば、いかなる初期値 $a_0$ に対しても、反復法 $x_{k+1}=\varphi(x_k)$ は $a$ に収束しない。

( $\because$ 　1つ目について、 $\varepsilon=\displaystyle{\frac{1}{2}}\left(1-\left|\varphi^{\prime}(a)\right|\right)$ )とおく。 $\varphi^{\prime}(x)$ の連続性から、充分に小さな $\delta\gt0$ に対して

$\begin{aligned} {}^{\forall}x\ \mathrm{s.t.}\ |x-a|\leq\delta\left(\left|\varphi^{\prime}(x)-\varphi^{\prime}(a)\right|\leq\varepsilon\right) \end{aligned}$

とできる。三角不等式より

$\begin{aligned} \left|\varphi^{\prime}(x)\right|&=\left|\varphi^{\prime}(x)-\varphi^{\prime}(a)+\varphi^{\prime}(x)\right|\\ &\leq\left|\varphi^{\prime}(x)-\varphi^{\prime}(a)\right|+\left|\varphi^{\prime}(a)\right|\\ &\leq\displaystyle{\frac{1+\left|\varphi^{\prime}(a)\right|}{2}} \end{aligned}$

が得られる。 $\lambda=\displaystyle{\frac{1+\left|\varphi^{\prime}(a)\right|}{2}}$ とおくと、 $\displaystyle{\frac{1}{2}}\leq\lambda\lt1$ である。 $J=\left[a-\delta,a+\delta\right]$ とおき、 $x,x^{\prime}\in J,$ $x\gt x^{\prime}$ とすれば、系2により系1が成立する。
　2つ目について、任意の反復列 $x_{k+1}=\varphi(x_k)$ が $a$ に収束すると仮定して、背理法により示すこととする。1つ目と同様に考えて、充分小さな $\delta\gt0$ と、 $\mu\gt1$ に対して

$\begin{aligned} \left|\varphi^{\prime}(x)\right|\geq\mu,\ x\in J=\left[a-\delta,a+\delta\right] \end{aligned}$

が成り立つ。仮定より充分に大きな $k$ に対して、 $x_k\in J$ としてよい。 $x,x^{\prime}\in J,x\gt x^{\prime}$ とすれば、平均値の定理から、

$\begin{aligned} \left|\varphi(x)-\varphi(x^{\prime})\right|\geq\mu\left|x-x^{\prime}\right| \end{aligned}$

が成り立つから、

$\begin{aligned} \left|x_k-a\right|=\left|\varphi(x_{k-1})-\varphi(a)\right|&\geq\mu\left|x_{k-1}-x^{\prime}\right|\\ &\geq\mu^k\left|x_{0}-x^{\prime}\right| \end{aligned}$

が成り立つはずである。しかし $k\rightarrow\infty$ において最右辺が正の無限大に発散する一方で最左辺はそうでなく成立しないはずで、これは矛盾である。　 $\blacksquare$ )

今日の復習

反復法の基本的な構成手順を説明せよ。
関数 $f(x):I\rightarrow\mathbb{R},I\subset\mathbb{R}$ が縮小写像であることの定義を述べよ。

次回

power-of-awareness.com

参考文献

伊理正夫・藤野和建（1985）「数値計算の常識」（共立出版）
菊地文雄・齊藤宣一（2016）「数値解析の原理　現象の解明をめざして」（岩波書店）
齊藤宣一（2012）「数値解析入門」（東京大学出版）
齊藤宣一（2017）「数値解析」（共立出版）
高橋大輔（1996）「理工系の基礎数学8　数値計算」（岩波書店）
山本哲朗（2003）「数値解析入門[増訂版]」（サイエンス社）
日本応用数理学会監修・櫻井鉄也編・松尾宇泰編・片桐孝洋編（2018）「数値線形代数の数理とHPC」（共立出版）
Ridgway Scott, Larkin (2011), "Numerical Analysis", (Princeton University Press)

*1:すなわち区間 $I$ の任意の $\mathrm{Cauchy}$ 列が $I$ 内の点に収束する。

はじめに

前回

前回の復習

2. 非線形方程式の解

2.1 反復法

2.1.1 縮小写像の原理と収束定理

2.1.2 反復法の収束性

今日の復習

次回

参考文献

2.　非線形方程式の解

2.1　反復法

2.1.1　縮小写像の原理と収束定理

2.1.2　反復法の収束性