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

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。

MENU

数値解析(02/XX)

はじめに

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

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

前回の復習

  • 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}

が成り立つがこれは矛盾である。したがって\alphaI内の唯一の解である。 \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}が縮小写像であることの定義を述べよ。

参考文献

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

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