コンテンツへスキップ
Topos Uranos
日本語

ニュートン・ラフソン法

要約

ボルツァーノの定理は、符号が変わる連続関数が根をもつことを保証し、二分法は一回の二分ごとに 2 進数の桁を一つずつ得ながら根の位置を突き止める。本課では、うまくいくときにははるかに速い方法を学ぶ。ニュートン・ラフソン法であり、グラフをその接線で置き換え、接線が軸と交わる点を新しい近似値とする方法である。こうして得られる近似値は整数 n≥0n \geq 0 に対して一つずつ順に定義され、その極限は、数列の理論を用いずに、変数が無限大に近づくときの極限の定義によって理解される。本課は、下に凸であることを用いて、導関数が 0 にならず関数が下に凸または上に凸ならば、適切な側から出発した反復値は根を越えることなく根に近づき、根に収束することを証明する。また平均値の定理を用いて、計算できる関数の値が、わからない根までの距離を押さえることを証明する。続いて数値例により、正しい桁数が反復ごとに倍になることを示し、方法が失敗する場合として、導関数が 0、循環、発散を示す。問題では、割り算を使わずに立方根と逆数を計算し、循環を断ち切り、重根を調べ、逆正接について収束と発散の正確な境目を求める。

学習目標

  1. 微分可能な関数のニュートン・ラフソン法の反復値を計算し、その中に接線と軸の交点を見てとる。
  2. 導関数が 0 にならず関数が下に凸または上に凸であるとき、反復値の単調収束を証明し、適切な側に初期値を選ぶ。
  3. 近似値から根までの距離を、関数の値と導関数の下界によって押さえる。
  4. 方法が失敗する場合を見分け、速さと確実さの点で二分法と比べる。

反復

ff を微分可能な関数とし、その根 rr を求めるものとし、x0x_0 を最初の近似値とする。x0x_0 の近くでは、ff のグラフはその接線 y=f(x0)+f′(x0)(x−x0)y = f(x_0) + f'(x_0)(x - x_0) に似ている。これは極限としての導関数の課の接線の定義による。高階導関数と微分の課の微分でいえば、増分 f(x0+Δx)−f(x0)f(x_0 + \Delta x) - f(x_0) は f′(x0)Δxf'(x_0) \Delta x に近い。f′(x0)≠0f'(x_0) \neq 0 ならば接線は軸とただ一点で交わり、その点を新しい近似値とするのが自然である。接線の方程式を 0 とおけば、その点が得られる。得られた点から同じ手続きを繰り返すのがニュートン・ラフソン法である。

定義ニュートン・ラフソン法の反復値

ff を区間 II で微分可能な関数とし、x0x_0 を II の点とする。x0x_0 から始まるニュートン・ラフソン法の反復値とは、以下の式によって一つずつ順に定義される数である。

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

ただし、xnx_n が II に属し f′(xn)≠0f'(x_n) \neq 0 である間に限る。これらの条件がすべての整数 n≥0n \geq 0 について成り立つならば、反復値は関数 n↦xnn \mapsto x_n をなし、これは非負整数全体の集合（上に有界でない）で定義されているので、変数が無限大に近づくときの極限の課の、変数が無限大に近づくときの極限の定義がこれに適用できる。反復値が rr に収束するとは、lim⁡n→∞xn=r\lim_{n \to \infty} x_n = r であること、すなわち

(∀ε>0)(∃M)(∀n≥0)(n>M→∣xn−r∣<ε)(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

各反復値は、(xn,f(xn))(x_n, f(x_n)) における接線と軸との交点である。y=0y = 0、x=xn+1x = x_{n+1} を方程式 y=f(xn)+f′(xn)(x−xn)y = f(x_n) + f'(x_n)(x - x_n) に代入して解けば、定義の式が得られる。この方法は、二分法のように与えられた区間で関数の符号が変わることを要求するのではなく、関数が微分可能で、通過する点で導関数が 0 にならないことを要求する。その代わり、反復値が根に近づくことを前もって保証するものは何もない。以下では、それを保証する条件を与える。

例2 の平方根

f(x)=x2−2f(x) = x^2 - 2 にニュートン・ラフソン法を x0=2x_0 = 2 から適用する。ステップは最初の三本の接線と、それらと軸との交点を示す。

証明

  1. xn+1=xn−xn2−22xn=12(xn+2xn),x1=32x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}

    導関数は f′(x)=2xf'(x) = 2x で、x>0x > 0 ならば 0 にならない。反復は以下の形になる。各近似値は、一つ前の近似値と、22 をそれで割ったものとの平均である。x0=2x_0 = 2 から、接線 y=2+4(x−2)y = 2 + 4(x - 2) は軸と 32\frac{3}{2} で交わる。

  2. x2=12(32+43)=1712≈1.416667x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1.416667

    (32,14)\left(\frac{3}{2}, \frac{1}{4}\right) における接線は、根にずっと近いところで軸と交わる。

  3. x3=12(1712+2417)=577408≈1.4142157,2≈1.4142136x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1.4142157, \qquad \sqrt{2} \approx 1.4142136

    三番目の反復値は、すでに正しい小数の桁を五つもつ。誤差 xn−2x_n - \sqrt{2} は約 0.590.59、0.0860.086、0.00250.0025、0.00000210.0000021 であり、それぞれが一つ前の誤差の平方の程度である。

この例の誤差は正確に平方になる。反復の式から、すべての xn>0x_n > 0 について以下の恒等式が得られる。

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

したがって、最初のものから先のすべての反復値は 2\sqrt{2} 以上であり、xn≥1x_n \geq 1 ならば、新しい誤差は現在の誤差の平方の半分以下である。四番目の反復値 x4=665 857470 832x_4 = \frac{665\,857}{470\,832} は、正しい小数の桁を十一個もつ。22 を任意の正の数で置き換えれば、同じ手続きで平方根が計算できる。これはすでに 1 世紀のアレクサンドリアのヘロンの測量術に現れ、そのためヘロンの方法とも呼ばれる。

アイザック・ニュートンは 1669 年に多項式方程式に対する自分の方法を記述し、その文書は手稿のまま流布して 1711 年に出版された。ジョゼフ・ラフソンは 1690 年により簡潔な解説を発表し、トマス・シンプソンは 1740 年に、これを一般の方程式に対する反復法として示した。