これは自動翻訳された記事であり、原文は英語です。 原文を読む
ニュートン法は毎ステップ誤差を2倍に広げることがあり、解までの距離は0.01だった
解から0.01離れた場所から始める。20ステップ後、到達するのは−5,242.88であり、しかもすべてのステップは正しく計算されている。
x³ − x − 2 = 0 を解く。覚えておく価値のある都合の良い公式はないため、あらゆる数値計算ソフトウェアが行っている通りのことを行う。すなわち、値を推測し、ニュートン法によってその推測を修正させるのである。
1.5 から開始する。3回の反復後、値は 1.52138 となり、その点での関数値は 5.89387 × 10⁻⁷ — ゼロから100万分の1未満の精度である。わずか3ステップである。ステップごとに正確な桁数がほぼ2倍になるため、この手法は電卓、CADパッケージ、表計算ソフトのソルバーに搭載されているのである。
今度は、より簡単な問題を解かせてみよう。∛x = 0 を解くのである。
答えは分かっている。ゼロであり、それが唯一の解である。0.01 から開始する — すでに100分の1の範囲内にある — そして結果を見てほしい。
0.01 → −0.02 → 0.04 → −0.08 → 0.16 → −0.32 → 0.64 → −1.28 → 2.56 → …
20回の反復後、推測値は −5242.88 となる。最初に 0.215 であった残差は、現在 17.37 に達している。この手法は停滞したり迷走したりしたわけではない。ステップごとに誤差を2倍にし、符号を反転させながら、完全に理にかなった軌跡を描いて解から遠ざかったのである。
何も間違っていない
プログラムのバグを探したくなるかもしれない。しかしバグは存在しない。そしてその計算はきわめて短いため、実際に確かめてみる価値がある。
ニュートン法のステップは x − f(x)/f′(x) である。f(x) = x1/3 のとき、導関数は (1/3)x−2/3 となるため、
f(x)/f′(x) = x1/3 ÷ ⅓x−2/3 = 3x
そして次の推測値は x − 3x = −2x となる。近似ではなく、正確にである。どのような初期値から開始しても、反復ごとに推測値は永遠に −2 倍される。−5242.88 という数値はここから生じる — すなわち 0.01 × (−2)19 であり、Newton's Method Explorer の diverge プリセットにおける反復表から、この等比数列全体を読み取ることができる。
立方根が引き起こしたのは、ニュートン法が依拠している前提条件の破綻である。ニュートン法は曲線をその接線で置き換え、その接線がゼロと交差する位置へ移動する。根の近くでは、これは非常に優れた近似となる — それはテイラー展開の1次の項であり、無視された項は2次的に縮小するため、桁数が2倍になるのはまさにこれが理由である。しかし ∛x はゼロにおいて垂直接線を持つ。その導関数はそこで単に小さくなるのではなく無限大となり、どんな倍率に拡大しても曲線が局所的に直線になることはない。ゼロ付近の接線はほぼ真上を向くため、軸と交差する場所は開始位置よりもほぼ3倍遠くになってしまうのである。
表の隣り合う2つの列を観察してほしい。f′(x) が 0.001 に向かって縮小する一方で、f(x) は増大していく。ステップはその比であるため、増加効果が重なって二重に増大するのである。
成功しているように見えるため、2つ目の失敗はより深刻である
発散であれば、少なくともそれと自覚できる。以下に示すのは、自覚できないケースである。
根が −1、0、+1 である f(x) = x³ − x を考える。0.57 から開始すると、この手法は13回の反復で残差 2.3 × 10⁻¹¹ と鮮やかに収束し — 最終的に返してくる根は −1 である。
0.57 が位置する場所を確認してほしい。+1 からは 0.43、−1 からは 1.57 離れている。また、ゼロにある根からもわずか 0.57 しか離れていない。ニュートン法は、より近くにある2つの根を素通りし、最も遠くにある根を返したうえで、小数点以下11桁まで正確であるとして完全な成功を報告するのである。
今度は代わりに 0.58 から開始してみよう。15回の反復で、得られる答えは +1 となる。
初期推測値を100分の1変更しただけで、ソルバーは関数の反対側の端に行き着いてしまう。これら2つの初期値の間には 1/√3 ≈ 0.5774 が存在し、そこでは x³ − x の導関数がゼロになる。そこでの接線は水平であり、軸との交点ははるか彼方になる。どちら側からその点にアプローチしても、最初の1ステップは互いに反対方向への巨大な跳躍となる。曲線上の傾きがゼロの箇所はすべて発射台であり、そこから投げ出される領域は距離の近さとは無関係なのである。
この性質こそが、「どの根が得られるのか？」という問いを一般に回答不能なものにしている。複素数体上の多項式において、各根へと導く初期値の集合は「吸引域」と呼ばれ、その境界はフラクタルである。ある根に収束する点のいくらでも近くに、別の根に収束する点が存在するのである。それにもかかわらず、ハバード、シュライヒャー、サザーランドは2001年に、与えられた多項式のすべての根を確実に見つけることができる初期値の有限集合を構築できることを示した — これは極めて重要な成果であり、「単にニュートン法を使えばよい」という表現がどれほど多くの計算上の労力を暗黙のうちに覆い隠しているかを示すものである。
ニュートン法の利用においてこれが意味すること
ここから3つの実用的な帰結が導かれ、その3つすべてがこのページ上で示されている。
第1に、小さな残差は保証書にはならない。上記の diverge 実行では残差は 17.37 であり増加傾向にあるため、異常として捕捉できる。しかし 0.57 の実行では残差は 2 × 10⁻¹¹ であり、得られた答えは完全に正しい根である — 単に質問者が求めていた根ではないというだけである。収束判定は ある1つの 解が見つかったことを示すことはできる。しかし、この手法のいかなる要素も、それが 求めていた唯一の 解であることを示してくれるわけではない。
第2に、反復回数の上限設定は極めて重要である。エクスプローラーはデフォルトで20回で停止するが、発散する実行がオーバーフローせずに終了する理由はこれしかない。商用のソルバーも同様の処理を行っており、この数値は任意のものではない。条件の良い関数に対する正常なニュートン反復は5〜10ステップでマシン精度に達するため、20ステップ目でも動いているものは、遅く収束しているのではなく収束していないのである。
第3に、不適切な初期値に対する処方箋は、通常、より優れたアルゴリズムではなく「区間の挟み込み」である。二分法は発散することがなく — 区間内で関数の符号が変わる場合、中点規則がその区間から外れることはない — また区間内に根が1つしかなければ誤った根を選ぶこともない。単に遅く、桁数を2倍にするのではなく1ステップあたり1ビットずつ精度を得るだけである。そのため、実際のソルバーの多くはハイブリッド方式を採用している。すなわち、推測値が十分に近づいたと証明できるまで二分法を行い、そこからニュートン法に引き継いで3ステップで終わらせるのである。前提条件が成り立つ場所では速度を、成り立たない場所では確実性を得ることができる。
名称についての補足がある。1669年頃のニュートン自身の手法は微分を用いず、多項式に対する一連の代入手順として記述されていた。1690年にラフソンがこれを簡略化し、f′ と任意の可微分関数 f を用いる今日教えられている形式は1740年のシンプソンによるものである。イプマは1995年にこの歴史的経緯の全容を辿った。立方根においてこれほど教訓的な失敗を示すこの手法は、17世紀の手順を19世紀に整理したものであり、それ以来すべての数値計算ツールボックスに組み込まれてきた — だからこそ、それがどこで破綻するかを正確に把握しておくべきなのである。