本記事は機械翻訳によるものであり、原文は英語です。 原文を読む
ニュートン法は1ステップごとに誤差を倍増させることがある――答えまではわずか0.01だったにもかかわらず
答えから0.01離れた位置から始める。20ステップ後には−5,242.88に達している。しかも、すべてのステップは正しく計算されていた。
x³ − x − 2 = 0 を解くことを考える。記憶しておく価値のある簡潔な公式など存在しない。そこで、あらゆる数値計算ソフトウェアが行っている通りのことをする。まず推測値を置き、ニュートン法にその推測値を修正させるのだ。
1.5 から始める。3回の反復後には 1.52138 が得られ、その地点での関数の値は 5.89387 × 10⁻⁷ となって、0から100万分の1未満の範囲に収まる。わずか3ステップである。ステップごとにおよそ正しい桁数が倍増していく。電卓、CADパッケージ、表計算ソフトのソルバーにこの解法が組み込まれているのは、まさにそのためである。
では、もっと簡単な問題を解かせてみよう。∛x = 0 を解く。
答えは分かっている。0であり、それ以外にはない。すでに100分の1以内に迫っている 0.01 から開始して、推移を見てみよう。
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 に達している。この手法は停滞したわけでも迷走したわけでもない。完全に理にかなった一本道の推論に従い、毎ステップ誤差を倍増させ、符号を反転させながら、答えから遠ざかっていったのである。
何ひとつ計算の誤りはない
ついバグを探したくなるかもしれない。だがバグなど存在せず、その計算はごく短いため自ら確かめてみる価値がある。
ニュートン法の更新ステップは 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 プリセットにある反復表から、この等比数列の全容を読み取ることができる。
立方根が引き起こしたのは、この手法の拠って立つ仮定を突き崩すことだった。ニュートン法は曲線を接線で置き換え、その接線が0と交差する点へと跳ぶ。根の近傍では、これは極めて優れた近似となる。テイラー展開の第1項に相当し、無視された項は2次で急速に小さくなる。桁数が倍増していく理由はまさにそこにある。しかし ∛x は、0において接線が垂直になる。その導関数は0において単に小さくなるだけでなく無限大になり、曲線はどれほど拡大しても局所的に直線状にはならない。0の近傍での接線はほぼ真上を向き、軸との交点はやはり −2x に着地する。つまり、開始地点よりも根から2倍遠い反対側の位置である。
表の中で並んでいる2つの列に注目してほしい。f(x) が増大する一方で、f′(x) は 0.001 に向かって縮小していく。更新ステップはその比であるため、二重の勢いで増大するのだ。
第2の失敗はさらに厄介である。なぜなら成功に見えるからだ
発散であれば、少なくともそれ自体が異常を知らせてくれる。
根が −1、0、+1 である f(x) = x³ − x を例にとろう。0.57 から始める。この手法は13回の反復できれいに収束し、残差は 2.3 × 10⁻¹¹ となる――そして返される根は −1 である。
0.57 の位置を確認してほしい。+1 からは 0.43、−1 からは 1.57 離れている。また、0 にある根からもわずか 0.57 しか離れていない。ニュートン法は、より近い2つの根をまっすぐに通り過ぎ、最も遠い根を返し、小数点以下11桁まで正確な完全な成功として報告する。
今度は代わりに 0.58 から始めてみる。15回の反復で、答えは +1 となる。
初期推測値をわずか100分の1変えただけで、ソルバーは関数の正反対の端に着地する。これら2つの開始点の間には、x³ − x の導関数が0になる 1/√3 ≈ 0.5774 が存在する。そこでの接線は水平であり、近傍のどこにも軸と交差しない。どちらの側からその点に近づいても、最初のステップは反対方向に向かって途方もなく巨大になる。曲線上の平坦な箇所はすべて発射台となり、そこから放り出される領域は、もとの位置との近さとは無関係である。
これこそが、「どの根が得られるのか？」という問いを一般には答えられないものにしている性質である。複素数上の多項式において、各根へと至る初期値の集合は吸引領域と呼ばれ、その境界はフラクタルである。ある根に収束する点からいくらでも近い場所に、別の根に収束する点が存在する。それにもかかわらず、与えられた多項式のすべての根を見つけることが保証された初期値の有限集合を構成できることを、ハバード、シュライヒャー、サザーランドが2001年に示した。これは実質的な成果であり、「単にニュートン法を使えばよい」という言葉が背後にどれほどの課題を暗黙のうちに隠蔽しているかを測る指標でもある。
この事実がもたらす実用上の変化
ここから3つの実践的な帰結が導かれる。そのうち最初の2つは、このページ上でも確認できる。
第1に、残差が小さいことは保証書にはならない。上記の diverge の実行では残差が 17.37 で増加しているため、異常を検知できる。しかし 0.57 の実行では残差は 2 × 10⁻¹¹ であり、得られた答えは完全に正当な根であるものの、問いを投げかけた者が求めていた解ではない。収束判定が教えられるのは、ある一つの解が見つかったということだけである。それが求めていた解であるかどうかを、この手法から知る手立てはない。
第2に、反復回数の上限設定は不可欠な安全装置である。エクスプローラーはデフォルトで20回で停止するが、発散した実行がオーバーフローを起こさずに終了できる理由はそれしかない。実運用のソルバーも同様の処理を行っており、この回数は決して恣意的なものではない。素性の良い関数に対する健全なニュートン反復なら5〜10ステップでマシン精度に達するため、20回に達しても動作し続けているものは、収束が遅いのではなく、そもそも収束していないのである。
第3に、不適切な初期値への対処法は、通常、より優れたアルゴリズムを探すことではなく、区間の挟み込みを行うことである。二分法は決して発散しない――区間の両端で関数の符号が反転している場合、中点則がその区間から外れることはあり得ない――そして、挟み込まれた区間内に根が1つしか存在しないため、誤った根を選ぶこともない。単に速度が遅く、桁数が倍増するのではなくステップごとに1ビットずつ精度が増していくだけである。そのため、大半の実用的なソルバーはハイブリッド方式を採用している。推定値が確実に十分に近づくまで二分法を進め、その後ニュートン法によって3ステップで仕上げるのだ。こうすれば、前提条件が満たされている場面では高速性を享受でき、満たされていない場面では確実性が保証される。
その名称に関しては、ひとつの付記がある。1669年頃のニュートン自身の手法は導関数を用いず、多項式に対する一連の代入操作として記述されていた。1690年にラフソンがそれを簡素化し、f′ と任意の微分可能関数 f を用いる今日教えられている形式は、1740年のシンプソンによるものである。1995年にイプマがその系譜をくまなく辿った。立方根において極めて示唆に富む失敗を見せるこの手法は、17世紀の処方を18世紀に整理したものであり、以来あらゆる数値計算ツール群に常備されてきた。だからこそ、それがどこで破綻するのかを正確に知っておく必要があるのだ。