ニュートン法とその理論的根拠

ニュートン法の目的と手順

実数空間\(\mathbb{R} \)もしくはその部分集合\(X\)を定義域とし、値として実数をとる1変数関数\begin{equation*}f:\mathbb{R} \supset X\rightarrow \mathbb{R} \end{equation*}が与えられれば、そこから方程式\begin{equation*}
f\left( x\right) =0
\end{equation*}を定義できます。この方程式の解（root）とは、以下の条件\begin{equation*}
f\left( c\right) =0
\end{equation*}を満たす実数\(c\in X\)です。これは、関数\(f\)のグラフと\(x\)軸の交点の\(x\)座標でもあります。

方程式\(f\left( x\right) =0\)に解が存在することが判明しているものの、解の正確な値\(c\)が不明であるような状況を想定します。ただし、真の解\(c\)が入り得るおおよその範囲は分かっており、なおかつ、真の解\(c\)の周辺には他に解が存在しないものとします。つまり、関数\(f\)のグラフが\(x\)軸と交わっており、周辺に他の交点が存在しないことを視覚的に確認できるものの、交点の\(x\)座標が正確には分からない状況を想定するということです。以上の条件に加えて、関数\(f\)が微分可能である場合には、ニュートン法（Newton’s Method）と呼ばれるアルゴリズムを利用することにより、真の解\(c\)の近似値を特定できます。具体的には以下の通りです。

方程式\(f\left( x\right) =0\)の解の正確な値\(c\)は不明であるものの、\(c\)がとり得るおおよその範囲は分かっている状況を想定しているため、まずは、その範囲に属する点を任意に選び、それを、\begin{equation*}x_{0}
\end{equation*}で表記します。仮に、\begin{equation*}
f\left( x_{0}\right) =0
\end{equation*}が成り立つのであれば\(x_{0}\)は真の解\(c\)に他ならず、話はここで終了です。そこで以降では、\begin{equation*}f\left( x_{0}\right) \not=0
\end{equation*}である状況、すなわち\(x_{0}\)が真の解\(c\)ではない状況を想定します。

関数\(f\)が微分可能である状況を想定しているため、関数\(f\)のグラフ上の点\(\left( x_{0},f\left( x_{0}\right) \right) \)における接線の方程式が、\begin{equation*}y=f^{\prime }\left( x_{0}\right) \left( x-x_{0}\right) +f\left( x_{0}\right)
\end{equation*}として得られます。この接線と\(x\)軸の交点の\(x\)座標を、\begin{equation*}x_{1}
\end{equation*}で表記します。このとき、\begin{equation*}
0=f^{\prime }\left( x_{0}\right) \left( x_{1}-x_{0}\right) +f\left(
x_{0}\right)
\end{equation*}が成り立ちます。特に、\(f^{\prime }\left( x_{0}\right) \not=0\)である場合には、これを\(x_{1}\)について解くことにより、\begin{equation*}x_{1}=x_{0}-\frac{f\left( x_{0}\right) }{f^{\prime }\left( x_{0}\right) }
\end{equation*}を得ます。

関数\(f\)が微分可能である状況を想定しているため、関数\(f\)のグラフ上の点\(\left( x_{1},f\left( x_{1}\right) \right) \)における接線の方程式が、\begin{equation*}y=f^{\prime }\left( x_{1}\right) \left( x-x_{1}\right) +f\left( x_{1}\right)
\end{equation*}として得られます。この接線と\(x\)軸の交点の\(x\)座標を、\begin{equation*}x_{2}
\end{equation*}で表記します。このとき、\begin{equation*}
0=f^{\prime }\left( x_{1}\right) \left( x_{2}-x_{1}\right) +f\left(
x_{1}\right)
\end{equation*}が成り立ちます。特に、\(f^{\prime }\left( x_{1}\right) \not=0\)である場合には、これを\(x_{2}\)について解くことにより、\begin{equation*}x_{2}=x_{1}-\frac{f\left( x_{1}\right) }{f^{\prime }\left( x_{1}\right) }
\end{equation*}を得ます。

同様のプロセスを繰り返します。一般に、それぞれの\(n\in \mathbb{N} \)について、関数\(f\)のグラフ上の点\(\left( x_{n},f\left( x_{n}\right)\right) \)における接線の方程式は、\begin{equation*}y=f^{\prime }\left( x_{n}\right) \left( x-x_{n}\right) +f\left( x_{n}\right)
\end{equation*}として得られるため、この接線と\(x\)軸の交点の\(x\)座標を、\begin{equation*}x_{n+1}
\end{equation*}と表記するのであれば、\begin{equation*}
0=f^{\prime }\left( x_{n}\right) \left( x_{n+1}-x_{n}\right) +f\left(
x_{n}\right)
\end{equation*}が成り立ちます。特に、\(f^{\prime }\left( x_{n}\right) \not=0\)である場合には、これを\(x_{n+1}\)について解くことにより、\begin{equation*}x_{n+1}=x_{n}-\frac{f\left( x_{n}\right) }{f^{\prime }\left( x_{n}\right) }
\end{equation*}を得ます。

以上のプロセスを繰り返すことにより、関数\(f\)のグラフの接線と\(x\)軸の交点の\(x\)座標からなる数列\begin{equation*}x_{0},x_{1},x_{2},\cdots ,x_{n},\cdots
\end{equation*}すなわち、\begin{equation*}
\left\{ x_{n}\right\}
\end{equation*}が得られますが、後ほど証明するように、\(n\)が大きくなるにつれてこの数列の項\(x_{n}\)は方程式\(f\left( x\right) =0\)の真の解\(c\)へ近づいていきます。先のプロセスを繰り返すほど、近似の精度は高くなるということです。また、究極的には、\begin{equation*}\lim_{n\rightarrow \infty }x_{n}=c
\end{equation*}が成り立ちます。つまり、数列\(\left\{ x_{n}\right\} \)は方程式\(f\left( x\right) =0\)の真の解へ収束します。以上がニュートン法の具体的な手続きです。

ニュートン法の根拠

関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)から定義される方程式\begin{equation*}f\left( x\right) =0
\end{equation*}に解\(c\in X\)が存在することは判明している一方で、その正確な値が不明である状況を想定します。また、\(c\)の周辺に他に解は存在しないものとします。点\(c\)の周辺にある点\(x_{0}\in X\)を任意に選びます。関数\(f\)が点\(c\)の周辺の任意の点\(x\)において微分可能であるとともに、そのような任意の点\(x\)において、\begin{equation*}f^{\prime }\left( x\right) \not=0
\end{equation*}が成り立つ場合には、以下の条件\begin{equation*}
x_{n+1}=x_{n}-\frac{f\left( x_{n}\right) }{f^{\prime }\left( x_{n}\right) }\quad \left( n\in \mathbb{Z} _{+}\right)
\end{equation*}を満たす数列\(\left\{ x_{n}\right\} \)が定義可能です。ニュートン法とは、この数列\(\left\{ x_{n}\right\} \)の項を具体的に特定することを通じて方程式\(f\left(x\right) =0\)の真の解\(c\)の近似値を特定するアルゴリズムです。ニュートン法が有効であることを保証するためには、\begin{equation*}\lim_{n\rightarrow \infty }x_{n}=c
\end{equation*}が成り立つことを確認しておく必要があります。以下で順番に考えます。

関数\(f:\mathbb{R} \supset X\rightarrow \mathbb{R} \)の変数\(x\)がとり得る値の範囲を方程式\(f\left( x\right) =0\)の真の解\(c\)の周辺に限定した上で、それを、有界閉区間\begin{equation*}\left[ \delta -c,\delta +c\right] \subset \mathbb{R} \end{equation*}として表現します。ただし、\(\delta >0\)です。さらに、関数\(f\)は区間\(\left[\delta -c,\delta +c\right] \)上において\(C^{2}\)級であるものとします。つまり、\(f\)は2階微分可能であるとともに、2階導関数\(f^{\prime \prime }\)は連続関数であるということです。加えて、\begin{equation}\forall x\in \left[ \delta -c,\delta +c\right] :f^{\prime }\left( x\right)
\not=0 \quad \cdots (1)
\end{equation}が成り立つものとします。このとき、それぞれの\(x\in \left[ \delta -c,\delta +c\right] \)に対して、\begin{equation*}F\left( x\right) =x-\frac{f\left( x\right) }{f^{\prime }\left( x\right) }
\end{equation*}を定める関数\(F:\mathbb{R} \supset \left[ \delta -c,\delta +c\right] \rightarrow \mathbb{R} \)が定義可能です。

関数\(f\)が\(C^{2}\)級である場合には\(f,f^{\prime }\)はともに微分可能であるため、微分可能な関数どうしの差ないし商として定義されている関数\(F\)もまた微分可能であり、その導関数は、\begin{eqnarray*}F^{\prime }\left( x\right) &=&1-\frac{f^{\prime }\left( x\right) f^{\prime
}\left( x\right) -f\left( x\right) f^{\prime \prime }\left( x\right) }{\left[
f^{\prime }\left( x\right) \right] ^{2}} \\
&=&\frac{\left[ f^{\prime }\left( x\right) \right] ^{2}-\left[ f^{\prime
}\left( x\right) \right] ^{2}+f\left( x\right) f^{\prime \prime }\left(
x\right) }{\left[ f^{\prime }\left( x\right) \right] ^{2}} \\
&=&\frac{f\left( x\right) f^{\prime \prime }\left( x\right) }{\left[
f^{\prime }\left( x\right) \right] ^{2}}
\end{eqnarray*}すなわち、\begin{equation}
F^{\prime }\left( x\right) =\frac{f\left( x\right) f^{\prime \prime }\left(
x\right) }{\left[ f^{\prime }\left( x\right) \right] ^{2}} \quad \cdots (2)
\end{equation}となります。

関数\(f\)が\(C^{2}\)級である場合には\(f,f^{\prime },f^{\prime \prime }\)はいずれも連続です。したがって、連続関数どうしの積および商として定義されている\(F^{\prime }\)も連続です。\(c\in \left[ \delta -c,\delta +c\right] \)であるため、\(F^{\prime }\)は点\(c\)において連続です。その一方で、\begin{eqnarray*}F^{\prime }\left( c\right) &=&\frac{f\left( c\right) f^{\prime \prime
}\left( c\right) }{\left[ f^{\prime }\left( c\right) \right] ^{2}}\quad
\because \left( 2\right) \\
&=&0\quad \because f\left( c\right) =0
\end{eqnarray*}すなわち、\begin{equation}
F^{\prime }\left( c\right) =0 \quad \cdots (3)
\end{equation}となります。したがって、関数の連続性の定義より、\(k\in \left( 0,1\right) \)を任意に選んだとき、それに対して十分小さい\(\delta >0\)を選べば、\(x\in \left[ c-\delta ,c+\delta \right] \)を満たす任意の\(x\)について、\begin{equation*}\left\vert F^{\prime }\left( x\right) -F^{\prime }\left( c\right)
\right\vert <k
\end{equation*}が成り立ちます。これと\(\left( 3\right) \)より、\begin{equation*}\left\vert F^{\prime }\left( x\right) \right\vert <k
\end{equation*}を得ます。以上より、\begin{equation*}
\forall k\in \left( 0,1\right) ,\ \exists \delta >0,\ \forall x\in \left[
c-\delta ,c+\delta \right] :\left\vert F^{\prime }\left( x\right)
\right\vert <k
\end{equation*}が成り立つことが明らかになりました。したがって、\(F\)は\(\left[ c-\delta,c+\delta \right] \)上において縮小関数であり、\(\left( 0,1\right) \)上の任意の値\(k\)が縮小定数となります。縮小関数の定義より、\begin{equation}\forall k\in \left( 0,1\right) ,\ \forall x,y\in \left[ c-\delta ,c+\delta \right] :\left\vert F\left( y\right) -F\left( x\right) \right\vert \leq
k\left\vert y-x\right\vert \quad \cdots (4)
\end{equation}が成り立つことに注意してください。

以上を踏まえると、\(x\in \left[ c-\delta ,c+\delta \right] \)を任意に選んだとき、\begin{eqnarray*}\left\vert F\left( x\right) -c\right\vert &=&\left\vert F\left( x\right)
-F\left( c\right) \right\vert \quad \because F\text{の定義より}F\left( c\right) =c \\
&\leq &k\left\vert x-c\right\vert \quad \because \left( 4\right) \\
&<&\left\vert x-c\right\vert \quad \because k\in \left( 0,1\right) \\
&<&\delta \quad \because x\in \left[ c-\delta ,c+\delta \right] \end{eqnarray*}となるため、\begin{equation*}
F\left( x\right) \in \left[ c-\delta ,c+\delta \right] \end{equation*}を得ます。したがって、\begin{equation*}
F\left( \left[ c-\delta ,c+\delta \right] \right) \subset \left[ c-\delta
,c+\delta \right] \end{equation*}が成り立つことが明らかになりました。つまり、関数\(F\)の値域は定義域の部分集合です。

関数\(F\)の定義域である有界閉区間\(\left[ c-\delta ,c+\delta \right] \)は\(\mathbb{R} \)上の閉集合であるため完備です。

以上より、関数\(F:\mathbb{R} \supset \left[ \delta -c,\delta +c\right] \rightarrow \mathbb{R} \)は縮小関数であり、その値域は定義域の部分集合であり、さらに定義域は\(\mathbb{R} \)上の完備部分集合であることが明らかになりました。つまり、関数\(F\)は縮小関数の不動点定理が要求する条件を満たすため、\(F\)は\(\left[ c-\delta ,c+\delta \right] \)上に不動点を持つとともに、それは一意的に定まります。

関数\(F:\mathbb{R} \supset \left[ \delta -c,\delta +c\right] \rightarrow \mathbb{R} \)に不動点が存在することが明らかになりました。したがって、関数\(F\)に不動点反復法を適用すれば不動点を特定できます。具体的には、点\(x_{0}\in \left[\delta -c,\delta +c\right] \)を任意に選んだ上で、数列\(\left\{ x_{n}\right\} \)を、\begin{eqnarray*}x_{1} &=&F\left( x_{0}\right) =x_{0}-\frac{f\left( x_{0}\right) }{f^{\prime
}\left( x_{0}\right) } \\
x_{2} &=&F\left( x_{1}\right) =x_{1}-\frac{f\left( x_{1}\right) }{f^{\prime
}\left( x_{1}\right) } \\
x_{3} &=&F\left( x_{3}\right) =x_{2}-\frac{f\left( x_{2}\right) }{f^{\prime
}\left( x_{2}\right) } \\
&&\vdots
\end{eqnarray*}と再帰的に定義すれば、この数列は関数\(F\)の不動点へ収束します。この数列\(\left\{ x_{n}\right\} \)はニュートン法のもとで生成される数列と一致することに注意してください。いずれにせよ、この数列\(\left\{ x_{n}\right\} \)について、\begin{eqnarray*}\left\vert x_{n+1}-c\right\vert &=&\left\vert F\left( x_{n}\right) -F\left(
c\right) \right\vert \quad \because F\text{の定義} \\
&\leq &k\left\vert x_{n}-c\right\vert \quad \because \left( 4\right) \\
&=&k\left\vert F\left( x_{n-1}\right) -F\left( c\right) \right\vert \quad
\because F\text{の定義} \\
&\leq &k^{2}\left\vert x_{n-1}-c\right\vert \quad \because \left( 4\right)
\\
&=&k^{3}\left\vert F\left( x_{n-2}\right) -F\left( c\right) \right\vert
\quad \because F\text{の定義} \\
&\leq &\cdots \\
&\leq &k^{n+1}\left\vert x_{0}-c\right\vert
\end{eqnarray*}となりますが、\(k\in \left(0,1\right) \)ゆえに右辺については、\begin{equation*}\lim_{n\rightarrow \infty }k^{n+1}\left\vert x_{0}-c\right\vert =0
\end{equation*}が成り立つため、はさみうちの定理より、\begin{equation*}
\lim_{n\rightarrow \infty }x_{n}=c
\end{equation*}を得ます。

以上の議論より、関数\(F:\mathbb{R} \supset \left[ \delta -c,\delta +c\right] \rightarrow \mathbb{R} \)には不動点が存在するとともに、それは\(c\)と一致することが明らかになりました。さらに、\begin{eqnarray*}F\left( c\right) =c &\Leftrightarrow &c-\frac{f\left( c\right) }{f^{\prime
}\left( c\right) }=c\quad \because F\text{の定義} \\
&\Leftrightarrow &\frac{f\left( c\right) }{f^{\prime }\left( c\right) }=0 \\
&\Leftrightarrow &f\left( c\right) =0\quad \because f^{\prime }\left(
c\right) \not=0
\end{eqnarray*}すなわち、\begin{equation*}
F\left( c\right) =c\Leftrightarrow f\left( c\right) =0
\end{equation*}が成り立ちます。つまり、\(c\)が方程式\(f\left( x\right)=0\)の解であることと、\(c\)が関数\(F\)の不動点であることは必要十分です。加えて、先に指摘したように、\(c\)はニュートン法のもとで生成される数列\(\left\{x_{n}\right\} \)の極限と一致します。したがって、ニュートン法によって生成される数列\(\left\{x_{n}\right\} \)の極限は方程式\(f\left( x\right) =0\)の解と一致することが明らかになりました。

演習問題