§C4.22ニュートン法と収束の速さ

最終更新

方程式f(x)=0f(x)=0の解を、式の変形によって書き下すことができるとは限りません。書き下すことができない場合には、解に近い値を作る手続きを用います。ニュートン法は、いま持っている近似値の点で曲線y=f(x)y=f(x)をその点における接線で置き換え、接線がxx軸と交わる点を次の近似値とする手続きです。

本記事は、この手続きを定め、平方根を求める反復式がこの形になることを確かめます。平方根の場合には、 1回の反復で誤差がどう変わるかが等式の形で書き表されるので、誤差がほぼ2乗で縮むことを近似を用いずに確かめることができます。一般の場合については、一次近似によって同じ形の関係が現れることを示します。あわせて、初期値の取り方によっては収束しない場合があることを、二つの例で扱います。方程式をx=g(x)x=g(x)の形へ書き直して反復するという枠組みそのものは「微積分」が扱い、本記事はその特別な場合を扱います。

1 接線による反復

定義 1.1 (ニュートン法).ffを微分可能な関数、x0x_0を実数とする。f′(xn)≠0f'(x_n)\ne0である限り

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

によってx1,x2,…x_1, x_2, \dotsを順に定める手続きを、方程式f(x)=0f(x)=0についてのニュートン法という。x0x_0をこの手続きの初期値という。

この式は、接線とxx軸との交点のxx座標を与える式です。実際、点(xn,f(xn))(x_n, f(x_n))における接線がxx軸と交わる点のxx座標は§C4.21 公式 1.1によりxn−f(xn)f′(xn)x_n - \dfrac{f(x_n)}{f'(x_n)}です。f′(xn)=0f'(x_n)=0のとき接線はxx軸に平行なので交点がなく、xn+1x_{n+1}は定まりません。

2 平方根を求める反復

例 2.1 (f(x)=x2−af(x)=x^2-aに対する反復式).a>0a>0とし、f(x)=x2−af(x)=x^2-aとします。f′(x)=2xf'(x)=2xなので、xn≠0x_n \ne 0のとき

xn+1=xn−xn2−a2xn=2xn2−xn2+a2xn=12(xn+axn)x_{n+1} = x_n - \frac{x_n^2-a}{2x_n} = \frac{2x_n^2 - x_n^2 + a}{2x_n} = \frac12\left(x_n + \frac{a}{x_n}\right)

です。すなわち、次の近似値はxnx_nとaxn\dfrac{a}{x_n}の相加平均です。

この反復式について、収束することを示します。

定理 2.2 (平方根を求める反復の収束).a>0a>0、x0>0x_0>0とし、xn+1=12(xn+axn)x_{n+1} = \dfrac12\left(x_n+\dfrac{a}{x_n}\right)で数列{xn}\{x_n\}を定める。このとき次が成り立つ。

  1. すべてのnnについてxn>0x_n>0であり、とくに反復は途中で止まらない。
  2. n≥1n \ge 1を満たすすべてのnnについてxn≥ax_n \ge \sqrt aである。
  3. n≥1n \ge 1を満たすすべてのnnについてxn+1≤xnx_{n+1} \le x_nである。
  4. lim⁡n→∞xn=a\displaystyle\lim_{n\to\infty}x_n = \sqrt aである。

証明. 1はnnについての帰納法によります。x0>0x_0>0です。xn>0x_n>0とするとaxn>0\dfrac{a}{x_n}>0なのでxn+1>0x_{n+1}>0です。したがって、すべてのnnについてxn>0x_n>0であり、f′(xn)=2xn≠0f'(x_n)=2x_n\ne0なので反復は止まりません。

2は相加平均と相乗平均の大小関係によります。xn>0x_n>0、axn>0\dfrac{a}{x_n}>0なので

xn+1=12(xn+axn)≥xn⋅axn=ax_{n+1} = \frac12\left(x_n+\frac{a}{x_n}\right) \ge \sqrt{x_n\cdot\frac{a}{x_n}} = \sqrt a

です。これはすべてのn≥0n \ge 0について成り立つので、n≥1n\ge1についてxn≥ax_n \ge \sqrt aです。

3について、n≥1n\ge1のときxn≥ax_n \ge \sqrt a、すなわちxn2≥ax_n^2 \ge aなので

xn+1−xn=12(axn−xn)=a−xn22xn≤0x_{n+1}-x_n = \frac12\left(\frac{a}{x_n}-x_n\right) = \frac{a-x_n^2}{2x_n} \le 0

です。

4について、2と3により、n≥1n\ge1の範囲で{xn}\{x_n\}は単調に減少し、a\sqrt aを下界にもちます。単調で下に有界な数列は収束するので（「数列と極限」）、極限L=lim⁡n→∞xnL = \displaystyle\lim_{n\to\infty}x_nが存在し、L≥a>0L \ge \sqrt a > 0です。漸化式の両辺の極限をとるとL=12(L+aL)L = \dfrac12\left(L+\dfrac{a}{L}\right)であり、両辺に2L2Lを掛けて整理するとL2=aL^2 = aです。L>0L>0なのでL=aL=\sqrt aです。▨

収束することが分かったので、次に速さを調べます。この反復式では、1回の反復で誤差がどう変わるかが等式の形で書き表されます。

定理 2.3 (誤差についての等式).定理 2.2と同じ設定のもとで、すべてのnnについて

xn+1−a=(xn−a)22xnx_{n+1}-\sqrt a = \frac{\left(x_n-\sqrt a\right)^2}{2x_n}

が成り立つ。

証明.a=(a)2a = \left(\sqrt a\right)^2を用いて

xn+1−a=12(xn+axn)−a=xn2+a−2a xn2xn=(xn−a)22xnx_{n+1}-\sqrt a = \frac12\left(x_n+\frac{a}{x_n}\right) - \sqrt a = \frac{x_n^2 + a - 2\sqrt a\,x_n}{2x_n} = \frac{\left(x_n-\sqrt a\right)^2}{2x_n}

となります。▨

公式 2.4 (誤差の縮み方).定理 2.2と同じ設定のもとで、n≥1n\ge1を満たすすべてのnnについて

0≤xn+1−a≤(xn−a)22a0 \le x_{n+1}-\sqrt a \le \frac{\left(x_n-\sqrt a\right)^2}{2\sqrt a}

が成り立つ。

証明.定理 2.3の右辺は00以上なので、左側の不等式が成り立ちます。n≥1n\ge1のとき定理 2.2の2によりxn≥a>0x_n \ge \sqrt a>0なので、12xn≤12a\dfrac{1}{2x_n} \le \dfrac{1}{2\sqrt a}であり、右側の不等式が成り立ちます。▨

誤差xn−ax_n-\sqrt aがε\varepsilonであるとき、次の誤差はε22a\dfrac{\varepsilon^2}{2\sqrt a}以下です。ε\varepsilonが小さいほど、ε2\varepsilon^2はε\varepsilonに比べて急に小さくなります。

例 2.5 (a=5a=5、x0=2x_0=2の場合).xn+1=12(xn+5xn)x_{n+1} = \dfrac12\left(x_n+\dfrac{5}{x_n}\right)によって順に計算すると

x1=94,x2=16172,x3=5184123184x_1 = \frac94, \qquad x_2 = \frac{161}{72}, \qquad x_3 = \frac{51841}{23184}

です。小数で書くとx1=2.25x_1 = 2.25、x2=2.23611⋯x_2 = 2.23611\cdots、x3=2.2360679779⋯x_3 = 2.2360679779\cdotsであり、5=2.2360679775⋯\sqrt5 = 2.2360679775\cdotsです。誤差xn−5x_n-\sqrt5は、およそ

1.4×10−2,4.3×10−5,4.2×10−101.4\times10^{-2}, \qquad 4.3\times10^{-5}, \qquad 4.2\times10^{-10}

です。定理 2.3によりx2−5=(x1−5)22x1x_2-\sqrt5 = \dfrac{(x_1-\sqrt5)^2}{2x_1}であり、(1.4×10−2)24.5=4.3×10−5\dfrac{(1.4\times10^{-2})^2}{4.5} = 4.3\times10^{-5}となって、実際の値と合います。 1回の反復で、正しく定まる小数の桁数がおよそ2倍になっています。

3 一般の場合に何が起きているか

一般のffについて、同じ形の関係が一次近似のもとで現れます。α\alphaをf(α)=0f(\alpha)=0、f′(α)≠0f'(\alpha)\ne0を満たす数とし、en=xn−αe_n = x_n-\alphaと置きます。ffが2回微分可能で、xnx_nがα\alphaに近いとき、ffとf′f'をα\alphaのまわりで近似すると

f(xn)≈f′(α)en+f′′(α)2en2,f′(xn)≈f′(α)+f′′(α)enf(x_n) \approx f'(\alpha)e_n + \frac{f''(\alpha)}{2}e_n^2, \qquad f'(x_n) \approx f'(\alpha) + f''(\alpha)e_n

です。β=f′′(α)f′(α)\beta = \dfrac{f''(\alpha)}{f'(\alpha)}と置くと

f(xn)f′(xn)≈en⋅1+β2en1+βen≈en(1+β2en)(1−βen)≈en−β2en2\frac{f(x_n)}{f'(x_n)} \approx e_n\cdot\frac{1+\dfrac{\beta}{2}e_n}{1+\beta e_n} \approx e_n\left(1+\frac{\beta}{2}e_n\right)\left(1-\beta e_n\right) \approx e_n - \frac{\beta}{2}e_n^2

となります。ここで∣βen∣|\beta e_n|が小さいことを用い、ene_nについて3次以上の項を落としました。したがって

en+1=en−f(xn)f′(xn)≈f′′(α)2f′(α)en2e_{n+1} = e_n - \frac{f(x_n)}{f'(x_n)} \approx \frac{f''(\alpha)}{2f'(\alpha)}e_n^2

です。誤差は、1回の反復でおよそ2乗になります。

注意 3.1 (この計算の位置づけ). 上の計算は、xnx_nがα\alphaに十分近いことと、ene_nについての高次の項を落としてよいことを前提としている。したがって、これは誤差の評価ではなく、誤差の縮み方の見当を与える計算である。どれだけ近ければこの見当が当てになるのか、および誤差の上からの評価を仮定つきで与えることは、「数値解析 I」が扱う。

平方根の場合には近似を用いない等式定理 2.3があり、そこではf(x)=x2−af(x)=x^2-a、α=a\alpha=\sqrt aについてf′′(α)2f′(α)=24a=12a\dfrac{f''(\alpha)}{2f'(\alpha)} = \dfrac{2}{4\sqrt a} = \dfrac{1}{2\sqrt a}である。定理 2.3の右辺の分母2xn2x_nはn→∞n\to\inftyで2a2\sqrt aに近づくので、上の計算の結果と一致する。

4 収束しない場合

上の計算は、xnx_nがα\alphaに近いことを前提としています。初期値が解から遠い場合には、何も保証しません。

例 4.1 (接線がxx軸に平行になる場合).f(x)=x2−2f(x)=x^2-2、x0=0x_0=0とします。f′(0)=0f'(0)=0なので、点(0,−2)(0,-2)における接線はxx軸に平行であり、xx軸と交わりません。したがってx1x_1が定まらず、反復は最初の段で止まります。方程式x2−2=0x^2-2=0は解±2\pm\sqrt2をもつので、解がないことが原因ではありません。

例 4.2 (二つの値を往復する場合).f(x)=x3−2x+2f(x)=x^3-2x+2、x0=0x_0=0とします。f′(x)=3x2−2f'(x)=3x^2-2です。f(0)=2f(0)=2、f′(0)=−2f'(0)=-2なので

x1=0−2−2=1x_1 = 0 - \frac{2}{-2} = 1

です。f(1)=1−2+2=1f(1)=1-2+2=1、f′(1)=3−2=1f'(1)=3-2=1なので

x2=1−11=0x_2 = 1 - \frac{1}{1} = 0

です。したがってx0=0x_0=0、x1=1x_1=1、x2=0x_2=0、x3=1x_3=1と続き、数列は二つの値を往復して収束しません。

この方程式には実数の解があります。f(−2)=−8+4+2=−2<0f(-2)=-8+4+2=-2<0、f(−1)=−1+2+2=3>0f(-1)=-1+2+2=3>0であり、ffは連続なので、中間値の定理により−2<x<−1-2<x<-1の範囲にf(x)=0f(x)=0を満たすxxがあります。この初期値からの反復は、その解に近づきません。

注意 4.3 (初期値の取り方は結論を変える).例 4.2のffについて、初期値をx0=−2x_0=-2にとるとf′(−2)=10f'(-2)=10からx1=−2−−210=−1.8x_1 = -2-\dfrac{-2}{10} = -1.8となり、以降は解へ近づく。同じ方程式でも、初期値によって収束するかどうかが変わる。ニュートン法を用いるときには、初期値を解の近くにとる必要があり、そのためには解のおよその位置を別の方法であらかじめ知っておくことになる。

5 不動点反復との関係

定理 5.1 (ニュートン法は特別な不動点反復である).ffを2回微分可能な関数とし、f′(x)≠0f'(x)\ne0を満たすxxについて

g(x)=x−f(x)f′(x)g(x) = x - \frac{f(x)}{f'(x)}

と置く。このとき、定義 1.1の反復はxn+1=g(xn)x_{n+1}=g(x_n)である。さらに、f(α)=0f(\alpha)=0かつf′(α)≠0f'(\alpha)\ne0とすると、g(α)=αg(\alpha)=\alphaかつg′(α)=0g'(\alpha)=0である。

証明.xn+1=g(xn)x_{n+1}=g(x_n)は定義そのものです。f(α)=0f(\alpha)=0なのでg(α)=α−0f′(α)=αg(\alpha) = \alpha-\dfrac{0}{f'(\alpha)} = \alphaです。商の微分により

g′(x)=1−{f′(x)}2−f(x)f′′(x){f′(x)}2=f(x)f′′(x){f′(x)}2g'(x) = 1 - \frac{\{f'(x)\}^2 - f(x)f''(x)}{\{f'(x)\}^2} = \frac{f(x)f''(x)}{\{f'(x)\}^2}

であり、x=αx=\alphaでは分子にf(α)=0f(\alpha)=0が現れるのでg′(α)=0g'(\alpha)=0です。▨

注意 5.2 (不動点反復の判定との関係). 方程式をx=g(x)x=g(x)の形へ書き直して反復する枠組みでは、不動点α\alphaにおいて∣g′(α)∣<1|g'(\alpha)|<1であれば、α\alphaに十分近い初期値から始めた反復の誤差が、1回ごとにおよそ∣g′(α)∣|g'(\alpha)|倍に縮む（「微積分」）。ニュートン法は、この書き直しのうちg′(α)=0g'(\alpha)=0となるものを、接線によって作る手続きである。誤差がene_nの1次の項では縮まず、2次の項から縮むのは、このg′(α)=0g'(\alpha)=0に対応している。

一方、∣g′(α)∣<1|g'(\alpha)|<1という判定は不動点の近くから始めた場合についてのものであり、この点はニュートン法でも変わらない。例 4.2は、遠くから始めた場合に判定が何も述べないことを示す例である。

注意 5.3 (本記事が扱う範囲). 本記事は、接線による反復を作り、平方根の場合について収束と誤差の縮み方を等式の形で示し、収束しない例を挙げるところを扱う。どの範囲の初期値から始めれば収束するかという条件と、一般のffについての誤差の上からの評価は「数値解析 I」が扱う。方程式をx=g(x)x=g(x)の形へ書き直して反復する枠組みと、∣g′(α)∣|g'(\alpha)|による判定は「微積分」が扱う。

前提記事