ニュートン法

ニュートン法では、導関数を直接計算できることが前提となります。導関数の解析式は容易に得られない場合や、計算コストが高い場合があります。このような場合、関数上の近接する2点を通る直線の傾きを用いて導関数を近似することが適切です。この近似を用いると、ニュートン法よりも収束が遅い割線法のような手法が得られます。

ニュートン法を実装する前に、その二次収束性の証明を復習することが重要です。特に、証明で用いられている前提条件を確認する必要があります。この方法が収束しない場合は、証明で用いられている前提条件が満たされていないことが原因です。

例えば、特定の根の近傍で一次導関数が良好な挙動を示さない場合、初期化位置をどこに設定してもニュートン法が収束しない可能性があります。場合によっては、逐次過緩和法を用いることでニュートン法を安定化させたり、同じ方法を用いることで収束速度を向上させたりすることができます。

ニュートン法の堅牢な実装においては、反復回数に制限を設けたり、解を根を含むことが分かっている区間に限定したり、より堅牢な根探索法と組み合わせたりすることが一般的である。

求める根の多重度が1 より大きい場合、特別な手順を踏まない限り、収束速度は単に線形 (各ステップで誤差が一定の係数で減少) になります。互いに近い根が 2 つ以上ある場合、反復が 1 つに十分近づいて二次収束が明らかになるまで、多くの反復が必要になる場合があります。ただし、根の多重度mがわかっている場合は、次の修正アルゴリズムにより二次収束速度が維持されます。 ^{[ 10 ]}

$${\displaystyle x_{n+1}=x_{n}-m{\frac {f(x_{n})}{f'(x_{n})}}.}$$

これは、逐次過緩和法を用いることと同等である。一方、根の重複度mが不明な場合は、 1回または2回の反復計算を行った後にmを推定し、その値を用いて収束速度を向上させることが可能である。

根の重複度mが有限であれば、 g ( x ) = ⁠ f ( x ) / f ′ ( x ) ⁠ は同じ位置に重複度 1 の根を持ちます。ニュートン法を適用してg ( x )の根を求めると、多くの場合、二次収束が回復しますが、一般的にはf ( x )の 2 階微分が関係します。特に単純なケースでは、f ( x ) = x ^mの場合、g ( x ) = ⁠ x / m ⁠となり、ニュートン法は 1 回の反復で根を見つけます。

$${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {\;{\frac {x_{n}}{m}}\;}{\frac {1}{m}}}=0\,.}$$

関数f ( x ) = x ²は 0 に根を持ちます。^{[ 11 ]} fは根で連続微分可能であるため、理論的には、根に十分近い初期値でニュートン法を行えば収束することが保証されます。しかし、導関数f ′は根でゼロになるため、理論的には二次収束は保証されません。この例では、ニュートン反復は次のように与えられます。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {1}{2}}x_{n}.}$

このことから、ニュートン法は任意の初期値から始めてもゼロに収束するものの、収束速度は線形であることがわかる。もし初期値を1とした場合、10桁の精度を達成するには数十回の反復計算が必要となる。

関数f ( x ) = x + x ^4/3も 0 に根を持ち、そこで連続的に微分可能です。根では1 階微分f ′はゼロではありませんが、2 階微分f ′′は存在しないため、2 階収束は保証されません。実際、ニュートン反復法は次のように与えられます。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {x_{n}^{4/3}}{3+4x_{n}^{1/3}}}\approx x_{n}\cdot {\frac {x_{n}^{1/3}}{3}}.}$

このことから、収束速度は超線形だが、2次未満であることがわかる。これは次の表で確認でき、左側は上記のf ( x ) = x + x ^4/3にニュートン法を適用した結果を示し、右側はf ( x ) = x + x ²にニュートン法を適用した結果を示している。右側に示されている反復における2次収束は、反復から真の根 (0,1,2,3,5,10,20,39,...) までの距離の桁数が、行ごとにほぼ2倍になっていることで示されている。左側の収束は超線形だが、桁数は行ごとに約 4/3 倍になっているだけである (0,1,2,4,5,7,10,13,...)。

収束速度は、所定の精度に達するために必要な反復回数とは区別されます。たとえば、関数f ( x ) = x ²⁰ − 1は 1 に根を持ちます。 f ′(1) ≠ 0 であり、 f は滑らかであるため、1 に収束する任意のニュートン反復は二次収束することが知られています。ただし、0.5 で初期化すると、ニュートン法の最初の数回の反復は、約 26214、24904、23658、22476 となり、ゆっくりと減少し、200 番目の反復のみが 1.0371 になります。次の反復は 1.0103、1.00093、1.0000082、および 1.00000000065 であり、二次収束を示しています。これは、ニュートン反復の二次収束が、必要な反復回数が少ないことを意味するわけではないことを強調しています。これは、反復のシーケンスがルートに十分近い場合にのみ適用されます。^{[ 12 ]}

関数f ( x ) = x (1 + x ² ) ^−1/2は 0 に根を持ちます。ニュートン反復法は次のように与えられます。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}(1+x_{n}^{2})^{-1/2}}{(1+x_{n}^{2})^{-3/2}}}=-x_{n}^{3}.}$

このことから、ニュートン反復には 3 つの現象が起こり得ることがわかる。厳密に±1の間に初期化すると、ニュートン反復は (超) 2 乗的に 0 に収束する。正確に1または−1で初期化すると、ニュートン反復は±1の間で無限に振動する。それ以外の場所で初期化すると、ニュートン反復は発散する。^{[ 13 ]}この同じ 3 区分はf ( x ) = arctan xにも当てはまる。^{[ 11 ]}

問題の関数が複数の根を持つ場合、初期化の選択によって、ニュートン法によってどの根（存在する場合）が特定されるかを制御することは困難になることがあります。たとえば、関数f ( x ) = x ( x ² − 1)( x − 3)e ^{−( x − 1) 2 /2}は、−1、0、1、および 3 に根を持ちます。^{[ 14 ]} −1.488 で初期化すると、ニュートン反復は 0 に収束します。−1.487 で初期化すると、∞に発散します。−1.486 で初期化すると、−1 に収束します。−1.485 で初期化すると、−∞に発散します。−1.4843 で初期化すると、3 に収束します。−1.484 で初期化すると、1に収束します。このような初期化に対する微妙な依存性は珍しくありません。これは複素平面上でニュートンフラクタルの形で頻繁に研究されている。

f ( x ) = x¹ ^/³の根を求める問題を考えてみましょう。ニュートン反復法は

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{1/3}}{{\frac {1}{3}}x_{n}^{-2/3}}}=-2x_{n}.}$

ニュートン法を正確な根0で初期化しない限り、反復列は収束しないことがわかります。たとえば、0.001という妥当な推定値で初期化した場合でも、最初の数回の反復は-0.002、0.004、-0.008、0.016となり、20回目の反復までに1048.58、-2097.15、...に達します。この場合、fは根で微分可能ではないため、この収束の失敗は解析理論と矛盾しません。

上記の例では、 n が増加するにつれてf ( x _n )がゼロに近づかないこと、および連続する反復の間隔がどんどん広がっていくことによって、収束の失敗が反映されます。しかし、関数f ( x ) = x ^1/3 e ^{− x 2}も 0 に根を持ちます。ニュートン反復は次のように与えられます。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}\left(1-{\frac {3}{1-6x_{n}^{2}}}\right).}$

この例では、f は根で微分可能ではないため、根から正確に開始しないニュートン反復は発散しますが、x _{n + 1} − x _nとf ( x _n )は両方ともゼロに収束します。^{[ 15 ]}これは、初期化 1 による反復を示す次の表で確認できます。

この場合、x _{n + 1} − x _nの収束はそれほど速くはありませんが、反復式から証明できます。この例は、 x _{n + 1} − x _nとf ( x _n )の小ささだけに基づくニュートン法の停止基準が、誤って根を特定してしまう可能性があることを示しています。

ニュートン法が2つの異なる値の間で無限に振動する状況は容易に見つけることができます。たとえば、関数fに適用されたニュートン法が 0 と 1 の間で振動するには、 fの 0 における接線がx軸と 1 で交わり、 fの 1における接線がx軸と 0 で交わるだけで十分です。 ^{[ 15 ]}これは、たとえばf ( x ) = x³ - 2x + 2の場合に当てはまります。この関数では、0 または 1 に十分近い初期値でニュートン法を反復すると^、漸近的にこれらの値の間で振動することさえあります。例えば、ニュートン法を0.99で初期化すると、反復値は0.99、-0.06317、1.00628、0.03651、1.00196、0.01162、1.00020、0.00120、1.000002などとなります。この挙動は、fの根が約-1.76929であるにもかかわらず発生します。

場合によっては、ニュートン反復法を実行することさえ不可能です。たとえば、f ( x ) = x² - 1の場合、ニュートン反復法は次のように定義されます^。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-1}{2x_{n}}}={\frac {x_{n}^{2}+1}{2x_{n}}}.}$

したがって、ニュートン法は0で初期化することはできません。なぜなら、そうするとx ₁が未定義になってしまうからです。幾何学的には、これはfの0における接線が水平（つまりf ′(0) = 0 ）であり、 x軸と交わらないためです。

ニュートン反復を開始できるように初期化を選択したとしても、同じ現象によって反復が無限に継続できなくなる可能性がある。

fの定義域が不完全な場合、ニュートン法では反復計算の結果が定義域外に送られてしまい、反復計算を継続できなくなる可能性があります。^{[ 15 ]}例えば、自然対数関数f ( x ) = ln x は根が 1 であり、正のxに対してのみ定義されます。この場合のニュートン法の反復計算は次のようになります。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}(1-\ln x_{n}).}$

つまり、反復処理がeで初期化された場合、次の反復値は0になります。反復処理がeより大きい値で初期化された場合、次の反復値は負になります。どちらの場合も、メソッドを続行することはできません。

テイラーの定理によれば、連続な2階微分を持つ任意の関数f ( x )は、 f ( x )の根に近い点の周りでの展開で表すことができる。この根をαとすると、 x _nの周りでのf ( α )の展開は次のようになる。

ここで、テイラー級数展開のラグランジュ形式は、

$${\displaystyle R_{1}={\frac {1}{2!}}f''(\xi _{n})\left(\alpha -x_{n}\right)^{2}\,,}$$

ここで、ξ _nはx _nとαの間にある。

αは根なので、（ 1）は次のようになる。

式（2）を_f ′ （ xn ）で割って整理すると、

x _{n + 1}は次のように定義されることを覚えておいてください。

次のようなことがわかった

$$\displaystyle \underbrace {\alpha -x_{n+1}} _{\varepsilon _{n+1}}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}{(\,\underbrace {\alpha -x_{n}} _{\varepsilon _{n}}\,)}^{2}\,.}$$

つまり、

両辺の絶対値を取ると

式（6）は、以下の条件が満たされる場合、収束次数が少なくとも2次であることを示している。

1. f ′ ( x ) ≠ 0 ; すべてのx ∈ Iに対して、ここでIは区間[ α − | ε ₀ | , α + | ε ₀ | ]です。
2. f ″ ( x )は、すべてのx ∈ Iに対して連続です。
3. M | ε ₀ | < 1

ここで、Mは次のように与えられる。

$${\displaystyle M={\frac {1}{2}}\left(\sup _{x\in I}\vert f''(x)\vert \right)\left(\sup _{x\in I}{\frac {1}{\vert f'(x)\vert }}\right).\,}$$

これらの条件が満たされる場合、

$${\displaystyle \vert \varepsilon _{n+1}\vert \leq M\cdot \varepsilon _{n}^{2}\,.}$$

f ( x )が区間上で狭義単調増加の凹関数であると仮定します。左端点で負、右端点で正の場合、中間値の定理により、区間内のどこかにfのゼロζが存在することが保証されます。幾何学的原理から、左端点から始まるニュートン反復x _iは単調増加かつ収束し、必然的にζに収束することがわかります。^{[ 18 ]}

ジョセフ・フーリエは、右端点から始めるニュートン法の改良版を導入した。

${\displaystyle y_{i+1}=y_{i}-{\frac {f(y_{i})}{f'(x_{i})}}.}$

この数列は単調減少かつ収束する。この定義の極限をとると、 y _iの極限もゼロζでなければならないことがわかる。^{[ 18 ]}

したがって、零点を持つ凹型増加関数の場合、初期化はほとんど関係ありません。零点の左側のどこからでも開始するニュートン反復法は収束し、零点の右側のどこからでも開始するフーリエ修正ニュートン反復法も同様に収束します。反復の任意のステップでの精度は、左側からの反復の位置と右側からの反復の位置の差から直接決定できます。f が 2 回連続微分可能であれば、テイラーの定理を使用して証明できます。

${\displaystyle \lim _{i\to \infty }{\frac {y_{i+1}-x_{i+1}}{(y_{i}-x_{i})^{2}}}=-{\frac {1}{2}}{\frac {f''(\zeta )}{f'(\zeta )}},}$

この位置の差が2乗でゼロに収束することを示している。^{[ 18 ]}

上記のすべては、複数の変数の方程式系にも拡張できますが、その文脈では、単調性と凹性に関する関連概念を定式化するのはより微妙です。^{[ 19 ]}単一の変数の単一の方程式の場合、ニュートン法の上記の単調収束は、凹性をfの任意の高階導関数の正または負の条件に置き換えるように一般化することもできます。ただし、この一般化では、ニュートンの反復は、接線ではなくテイラー多項式に基づくように変更されます。凹性の場合、この変更は標準ニュートン法と一致します。^{[ 20 ]}

単一の関数の根源を探求する場合${\displaystyle f:\mathbf {R} ^{n}\to \mathbf {R} }$ するとエラー${\displaystyle \epsilon _{n}=x_{n}-\alpha }$は、その成分が以下の条件を満たすベクトルである。${\displaystyle \epsilon _{k}^{(n+1)}={\frac {1}{2}}(\epsilon ^{(n)})^{T}Q_{k}\epsilon ^{(n)}+O(\|\epsilon ^{(n)}\|^{3})}$どこ${\displaystyle Q_{k}}$これは二次形式です。 ${\displaystyle (Q_{k})_{i,j}=\sum _{\ell }((D^{2}f)^{-1})_{i,\ell }{\frac {\partial ^{3}f}{\partial x_{j}\partial x_{k}\partial x_{\ell }}}}$ 根元で評価${\displaystyle \alpha }$ （どこ${\displaystyle D^{2}f}$は2階微分ヘッセ行列です。

ニュートン法は、平方根を計算する多くの既知の方法の1つです。正の数aが与えられたとき、 x ² = aとなる数xを見つける問題は、関数f ( x ) = x ² − aの根を見つけることと同等です。この関数によって定義されるニュートン反復は、 ^{[ 21 ]}で与えられます。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)}$。

これは、平方根を求める「バビロニア式」の方法と一致します。この方法は、近似平方根x _{n を}x _nとa ⁄ x _nの算術平均で置き換えるというものです。この反復処理を行うことで、基本的な算術演算のみを使用して、任意の精度で平方根を評価することが可能です。

以下の 3 つの表は、反復計算の初期値を 1、10、および -20 とした場合の、612 の平方根を求める計算結果の例を示しています。「x _n」列の各行は、その上のエントリに前述の式を適用することによって得られます。たとえば、

${\displaystyle 306.5={\frac {1}{2}}\left(1+{\frac {612}{1}}\right).}$

正しい数字には下線が引かれています。わずか数回の反復で、多くの小数点以下の桁まで正確な解が得られることがわかります。最初の表は、ニュートン反復を非常に不正確な初期値である1で開始した場合でも、これが真であることを示しています。

ゼロでない平方根を計算する場合、fの一次導関数は根においてゼロであってはならず、fは滑らかな関数でなければなりません。したがって、計算を行う前から、収束するニュートン法の反復計算は二次収束率を持つことがわかっています。これは、上記の表にも反映されており、ニュートン法の反復計算が根に近づくと、正しい桁数が反復ごとにほぼ倍増します。

cos( x ) = x³となる^正の数x を求める問題を考えてみましょう。これは^、f ( x ) = cos( x ) - x³の零点を求める問題と言い換えることができます。f ′ ( x ) = -sin ( x ) - 3x²^となります。すべてのxに対してcos( x ) ≤ 1 であり、x > 1に対して^x³ > 1 であることから、解は 0 から 1 の間にあることがわかります。

初期値として0を用いると、結果は未定義となるため、解に近い初期値を用いることの重要性がわかる。例えば、初期推定値x₀ = 0.5の場合、ニュートン法による数列は次のようになる_。

$${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}}$$

上記の例では、正しい桁数に下線が引かれています。特に、x⁶_{は小数点以下 12 桁まで正しい値です。小数点以下の正しい桁数が、} x³_の2 桁から 5 桁、10 桁へと増加していることがわかり、二次収束を示しています。

複素関数を扱う場合、ニュートン法を直接適用して零点を見つけることができます。^{[ 27 ]}各零点には複素平面上に吸引領域があり、これはその零点に収束するすべての初期値の集合です。これらの集合は、図に示すようにマッピングできます。多くの複素関数では、吸引領域の境界はフラクタルです。

場合によっては、複素平面にはこれらの吸引領域のいずれにも含まれない領域があり、反復が収束しないことを意味します。たとえば、^{[ 28 ]} x ² + 1の根を求めるために実数の初期条件を使用すると、その後のすべての反復は実数になり、両方の根が非実数であるため、反復はどちらの根にも収束しません。この場合、ほとんどすべての実数の初期条件はカオス的な挙動につながり、一部の初期条件は無限に反復するか、任意の有限長の繰り返しサイクルに反復します。

Curt McMullen は、ニュートン法に似た任意の純粋反復アルゴリズムについて、次数 4 以上の多項式に適用すると、複素平面のいくつかの開領域でアルゴリズムが発散することを示した。しかし、McMullen は次数 3 の多項式に対しては一般的に収束するアルゴリズムを示した。^{[ 29 ]}さらに、Hubbard、Schleicher、Sutherland は、ニュートン法の普遍的な開始点の集合を構築した。任意の次数dに対して、約1.11 d (log d ) ²個の明示的に構築可能な点の集合が存在し、次数dの適切に正規化された任意の多項式に対して、各根は集合の少なくとも 1 つの点から開始するニュートン反復によって見つかる。^{[ 30 ] [ 31 ]}

もう一つの一般化は、バナッハ空間で定義された関数Fの根を見つけるためのニュートン法である。この場合の定式化は次のようになる。

$${\displaystyle X_{n+1}=X_{n}-{\bigl (}F'(X_{n}){\bigr )}^{-1}F(X_{n}),\,}$$

ここで、F ′ ( X _n )はX _nで計算されたフレシェ微分です。この方法を適用するには、各X _nでフレシェ微分が有界に可逆である必要があります。根の存在と収束の条件は、ニュートン-カントロビッチの定理によって与えられます。^{[ 32 ]}

ヤコビ行列が利用できない場合、または各反復ごとに計算するにはコストがかかりすぎる場合は、準ニュートン法を用いることができる。

高次のテイラー展開は関数fのより正確な局所近似を提供するので、ニュートン法がなぜ 2 次テイラー近似のみに依存しているのか疑問に思うのは当然です。19 世紀、ロシアの数学者パフヌティ・チェビシェフは、3 次近似を使用するニュートン法の変種を開発することでこの考えを探求しました。^{[ 35 ] [ 36 ] [ 37 ]}

p進解析において、1変数多項式がp進根を持つことを示す標準的な方法は、p進数に対するニュートン法の漸化式を用いるヘンゼルの補題です。p進数における加算と乗算の挙動は実数に比べて安定しているため（具体的には、 p進数における単位球は環です）、ヘンゼルの補題における収束は、実数直線上の古典的なニュートン法よりもはるかに単純な仮定の下で保証されます。

ニュートン法は、通常の微分のq類似物を用いて一般化することができる。 ^{[ 38 ]}

ニュートン法は、関数f ( x )の最小値または最大値を求めるために使用できます。最小値または最大値では導関数がゼロになるため、導関数にニュートン法を適用することで局所的な最小値と最大値を求めることができます。^{[ 45 ]}反復は次のようになります。

$${\displaystyle x_{n+1}=x_{n}-{\frac {f'(x_{n})}{f''(x_{n})}}.}$$

重要な応用例として、ニュートン・ラフソン除法があります。これは、乗算と減算のみを使用して、数aの逆数、つまり1 / x = aとなる数xを素早く求めるために使用できます。これを、 f ( x ) = 1 / x − aの零点を求めることと言い換えることができます。f ′ ( x ) = − 1 / x 2^となります。

ニュートンの反復法は

$${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}+{\frac {{\frac {1}{x_{n}}}-a}{\frac {1}{x_{n}^{2}}}}=x_{n}(2-ax_{n}).}$$

したがって、ニュートンの反復法では、乗算が2回、減算が1回しか必要ありません。

この方法は、べき級数の乗法逆数を計算する際にも非常に効率的です。

多くの超越方程式は、ニュートン法を用いることで任意の精度まで解くことができます。例えば、既知の確率に適合する正規分布などの累積確率密度関数を求める場合、一般的には閉じた形で解く方法が知られていない積分関数が用いられます。しかし、ニュートン法を用いて数値的に解くために必要な導関数は一般的に既知であるため、数値解を求めることが可能です。例として、逆正規累積分布の数値解を参照してください。

ニュートン法を複数回適用し、解候補のセットを作成することにより、非線形方程式の解の数値検証が確立された。