ニュートン法

数値解析において、ニュートン・ラプソン法は、アイザック・ニュートンとジョセフ・ラプソンにちなんで単にニュートン法とも呼ばれ、実数値関数の根（または零点）のより良い近似値を次々に生み出す根探索アルゴリズムである。最も基本的なバージョンは、実数値関数f、その導関数f ′ 、およびfの根の初期推定値x ₀から始まる。f が特定の仮定を満たし、初期推定値が近い場合、

$${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}}$$

_はx ₀よりも良い近似値です。幾何学的には、( x ₁ , 0) は( x 0 , f ( x 0 )) における f のグラフの接線のx切片_です。つまり、改善された推定値x 1_は、 初期推定値x ₀におけるfの線形近似値の唯一の根です。このプロセスは次のように繰り返されます。

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

十分に正確な値に達するまで、この手順を繰り返します。正しい桁の数は、各ステップごとにほぼ 2 倍になります。このアルゴリズムは、ハウスホルダー法のクラスでは最初のもので、ハレー法に引き継がれました。この方法は、複雑な関数や連立方程式にも拡張できます。

考え方としては、まず初期推定値から始めて、関数をその接線で近似し、最後にこの接線のx切片を計算します。このx切片は通常、最初の推定値よりも元の関数の根への近似値として適しており、この方法は反復できます。

曲線f ( x )の接線がx = x _nでx軸と交わる位置がx _{n +1}の場合、傾きは

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

x _{n +1}を解くと、

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

このプロセスは、任意の初期値x ₀から開始します。(零点に近いほど良いですが、零点がどこにあるか直感的にわからない場合は、「推測と検証」の方法で中間値定理を利用して可能性をかなり狭い範囲に絞り込むことができます。 ) この初期推測が未知の零点に十分近く、f ′ ( x ₀ ) ≠ 0であれば、この方法は通常収束します。さらに、重複度1の零点の場合、零点の近傍では 収束は少なくとも 2 次式になります (収束率を参照) 。これは直感的に、正しい桁の数が各ステップでほぼ 2 倍になることを意味します。詳細については、以下の§ 分析を参照してください。

ハウスホルダー法は類似していますが、より高速な収束のために高次になっています。ただし、各ステップで追加の計算が必要になるため、特にfまたはその導関数を評価するのに計算コストがかかる場合は、ニュートン法に比べて全体的なパフォーマンスが低下する可能性があります。

この方法は、アイザック・ニュートンの著書『無限項の数の解析について』 （1669年執筆、1711年ウィリアム・ジョーンズ出版）と『無限項フラクシオンおよび無限フラクシオンの方法』（1671年執筆、1736年ジョン・コルソン訳『フラクシオン法』出版）でおおよそ初めて登場した。^[1]しかし、ニュートンは基本的な考え方を示したものの、その方法は上記の現代の方法とは異なる。彼はこの方法を多項式にのみ適用し、初期の根の推定から始めて、一連の誤差修正を抽出した。彼は各修正を使用して、残りの誤差に関して多項式を書き直し、次に高次項を無視して新しい修正を解いた。彼はこの方法を明示的に導関数と関連づけたり、一般公式を提示したりはしなかった。ニュートンはこの方法を数値問題と代数問題の両方に適用し、後者の場合は テイラー級数を生成した。

ニュートンは、数学者フランソワ・ヴィエトの類似した、より精度の低い方法から彼の方法を導き出した可能性があるが、2つの方法は同じではない。^[2]ヴィエト自身の方法のエッセンスは、ペルシャの数学者 シャラフ・アルディーン・アルトゥーシの研究に見出すことができるが、彼の後継者であるジャムシード・アル・カーシーは、ニュートン法の一種を使用してx ^P − N = 0 を解き、 Nの根を見つけた。この方法は代数的にはニュートン法と同等であり、ヘンリー・ブリッグスが1633年に出版した三角法ブリタニカにも同様の方法が見られる。古代ギリシャ人とバビロニア人は、補正項を追加することで解の推定値を改善することで方程式を解くという一般的な考え方に一致する根を抽出する方法を持っていた。^[3]

日本の数学者関興和は1680年代にニュートン法を使って一変数方程式を解いたが、微積分学との関連はなかった。^[4]

ニュートン法は、1685年にジョン・ウォリスの著書『歴史的かつ実用的な代数学の論文』で初めて発表されました。^[5] 1690年にジョセフ・ラプソンは『普遍的方程式の解析』で簡略化した説明を発表しました。^[6]ラプソンもこの方法を多項式にのみ適用しましたが、元の多項式から各修正を連続的に抽出することで、ニュートンの面倒な書き直しプロセスを回避しました。これにより、各問題に対して再利用可能な反復式を導き出すことができました。最後に、1740年にトーマス・シンプソンは、ニュートン法を微積分を使用して一般的な非線形方程式を解く反復法として説明し、基本的に上記の説明を示しました。同じ出版物で、シンプソンは2つの方程式のシステムへの一般化も示し、ニュートン法は勾配をゼロに設定することで最適化問題を解くために使用できると述べています。

アーサー・ケイリーは1879 年に「ニュートン-フーリエの虚数問題」で、ニュートン法を 2 より大きい次数と複素初期値を持つ多項式の複素根に一般化することの難しさに初めて気付きました。これにより、有理関数の 反復理論の研究への道が開かれました。

ニュートン法は強力な手法です。一般に収束は2 次式です。つまり、この方法が根に収束すると、根と近似値の差は各ステップで 2 乗されます (正確な桁数はほぼ 2 倍になります)。ただし、この方法にはいくつか問題があります。

ニュートン法では、導関数を直接計算できることが求められます。導関数の解析式は簡単には得られないか、評価にコストがかかる可能性があります。このような状況では、関数上の 2 つの近くの点を通る直線の傾きを使用して導関数を近似することが適切な場合があります。この近似を使用すると、セカント法のような結果になり、ニュートン法よりも収束が遅くなります。

ニュートン法を実装する前に、その 2 次収束の証明を確認することが重要です。特に、証明で行われた仮定を確認する必要があります。この方法が収束しない場合は、この証明で行われた仮定が満たされていないためです。

たとえば、ある特定の根の近傍で 1 次導関数が適切に動作しない場合、初期化をどこに設定してもニュートン法が収束しない可能性があります。場合によっては、ニュートン法は、逐次過剰緩和を使用して安定化したり、同じ方法を使用して収束速度を上げたりすることができます。

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

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

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

これは、逐次過剰緩和を使用するのと同じです。一方、根の多重度m が不明な場合は、1 回または 2 回の反復を実行してm を推定し、その値を使用して収束率を上げることができます。

根の重複度mが有限であれば、 g ( x ) = ⁠関数x​​/f ′ ( x ) の⁠ は同じ位置に重複度 1 の根を持ちます。ニュートン法を使用してg ( x )の根を求めると、多くの場合二次収束が回復しますが、通常はf ( x )の 2 次導関数が関係します。特に単純なケースでは、 f ( x ) = x ^mの場合、 g ( x ) = ⁠x/メートル⁠そしてニュートン法は、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 がαで零点を持つ、つまりf ( α ) = 0 であり、f がαの近傍で微分可能であるとします。

fが連続的に微分可能であり、その導関数が αでゼロでない場合、αの近傍が存在し、その近傍内のすべての開始値x ₀に対して、シーケンス( x _n )はαに収束します。^[8]

fが連続的に微分可能 で、その導関数がαでゼロ以外であり、αで 2 次導関数を持つ場合、収束は 2 次またはそれより速くなります。2 次導関数がαで 0 でない場合、収束は単なる 2 次です。3 次導関数が存在し、 αの近傍で制限されている場合は、次のようになります。

$${\displaystyle \Delta x_{i+1}={\frac {f''(\alpha )}{2f'(\alpha )}}\left(\Delta x_{i}\right)^{2}+O\left(\Delta x_{i}\right)^{3}\,,}$$

どこ

$${\displaystyle \Delta x_{i}\triangleq x_{i}-\alpha \,.}$$

導関数がαで 0 の場合、収束は通常は線形のみです。具体的には、fが 2 回連続微分可能で、f ′ ( α ) = 0かつf ″ ( α ) ≠ 0 である場合、 αの近傍が存在し、その近傍内のすべての開始値x ₀に対して、反復シーケンスは速度⁠ で線形収束します 。1/2⁠ . ^[9]あるいは、x ≠ αに対してf ′ ( α ) = 0かつf ′ ( x ) ≠ 0であり、x がαの近傍U にあり、α が重複度rの零点である場合、f ∈ C ^r ( U )であれば、その近傍内のすべての開始値x ₀に対して反復シーケンスが線形収束する ようなαの近傍が存在する。

ただし、病的な状況では線形収束さえも保証されません。

実際には、これらの結果は局所的であり、収束する近傍は事前にわかりません。しかし、大域的収束に関する結果もいくつかあります。たとえば、αの右近傍U _{+ が}与えられ、f がU ₊で 2 回微分可能であり、f ′ ≠ 0、U ₊でf · f ″ > 0である場合、U ₊の各x ₀に対して、シーケンスx _kはαまで単調減少します。

テイラーの定理によれば、連続した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）は次のようになる。

式（２）を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}\,.}$$

つまり、

両辺の絶対値を取ると

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

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 は}単調増加で収束し、必然的にζに収束することが分かります。^[10]

ジョセフ・フーリエは、右端から始まるニュートン法の修正を導入しました。

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

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

したがって、ゼロを持つ凹増加関数の場合、初期化はほとんど無関係です。ゼロの左側のどこから始めてもニュートン反復は収束し、ゼロの右側のどこから始めてもフーリエの修正ニュートン反復は収束します。反復のどのステップでも精度は、左からの反復の位置と右からの反復の位置の差から直接決定できます。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乗的にゼロに収束することを示している。^[10]

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

ニュートン法は平方根を計算する多くの既知の方法の1つです。正の数aが与えられたとき、 x ² = aとなる数x を求める問題は、関数f ( x ) = x ² − aの根を求めることと同じです。この関数によって定義されるニュートン反復法は次のように表されます。

${\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つの表は、612の平方根を求める計算結果の例を示しています。反復は1、10、-20の値で初期化されています。「x _n」列の各行は、前の式をその上のエントリに適用することで得られます。たとえば、

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

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

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

cos x = x ³となる正の数x を求める問題を考えてみましょう。これは、 f ( x ) = cos( x ) − x ³のゼロを求める問題と言い換えることができます。 f ′ ( x ) = −sin( x ) − 3 x ²となります。すべての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 _{6 は}小数点以下 12 桁まで正しいです。小数点以下の正しい数字の数は 2 ( x ₃の場合) から 5 および 10 に増加し、二次収束を示しています。

関数f ( x ) = x ²は0に根を持つ。^[13] fはその根で連続的に微分可能であるため、理論はニュートン法が根に十分近いところで初期化されると収束することを保証する。しかし、導関数f ′は根で0なので、理論では2次収束は保証されない。この特定の例では、ニュートン反復法は次のように与えられる。

${\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^{4/3}}{3+4x^{1/3}}}.}$

このことから、収束率は超線形だが二次以下であることがわかります。これは次の表で確認できます。表の左側は上記のf ( x ) = x + x ^4/3にニュートン法を適用したものを示し、右側はf ( x ) = x + x ²にニュートン法を適用したものです。右側に示されている反復における二次収束は、反復から真の根までの距離の桁数 (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 となり、二次収束を示しています。これは、ニュートン反復法の2次収束は、少数の反復のみが必要であることを意味するのではなく、反復のシーケンスが根に十分近い場合にのみ適用されることを強調しています。^[14]

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

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

このことから、ニュートン反復法には3つの現象が起こり得ることがわかります。厳密に±1の間で初期化された場合、ニュートン反復法は（超）2次収束して0になります。正確に1または-1で初期化された場合、ニュートン反復法は±1の間で無限に振動します。他の場所で初期化された場合、ニュートン反復法は発散します。^[15]この同じ3分法はf ( x ) = arctan xでも発生します。^[13]

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

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

${\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は根で微分不可能であり、ニュートン反復は正確に根から始まらないが、xn _{+ 1} − xn_とf ( xn )_は両方ともゼロに収束する。^[17]これは、初期化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で交差するだけで十分です。 ^[17]これは、たとえばf ( x ) = x ³ − 2 x + 2の場合に当てはまります。この関数では、0または1に十分近い値に初期化されたニュートン反復がこれらの値の間を漸近的に振動することさえあります。たとえば、ニュートン法を 0.99 で初期化すると、0.99、-0.06317、1.00628、0.03651、1.00196、0.01162、1.00020、0.00120、1.000002 などの反復結果が生成されます。この動作は、およそ -1.76929 に等しい fの根が存在するにもかかわらず発生します。

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

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

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

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

f が不完全な定義域を持つ場合、ニュートン法では反復を定義域外に送る可能性があり、反復を継続することが不可能になる。^[17]たとえば、自然対数関数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より大きい値で初期化された場合、次の反復は負になります。どちらの場合も、メソッドを続行することはできません。

ニュートン法を使ってk方程式の連立方程式を解くこともできる。これはk個の連続微分可能関数の（同時）零点を見つけることに相当する。これは単一のベクトル値関数の零点を見つけることと同等である。上記の定式化では、スカラーx _{n がベクトル}x _nに置き換えられ、関数f ( x _n )をその導関数f ′ ( x _n )で割る代わりに、関数F ( x _n )をそのk × kヤコビ行列J _F ( x _n )の逆行列で左乗算する必要がある。^{[18] [19] [20]}これは次の式になる 。${\displaystyle f:\mathbb {R} ^{k}\to \mathbb {R} .}$${\displaystyle F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}.}$

$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-J_{F}(\mathbf {x} _{n})^{-1}F(\mathbf {x} _{n}).}$$

あるいは、線形方程式系を解くことによって

$${\displaystyle J_{F}(\mathbf {x} _{n})(\mathbf {x} _{n+1}-\mathbf {x} _{n})=-F(\mathbf {x} _{n})}$$

未知数x _{n + 1} − x _nについて。^[21]

ニュートン法の k 次元変形は、アルゴリズムが J の逆行列の代わりに非正方ヤコビ行列の一般逆行列 J + = ( J T J ) −1 J T を使用する場合、 k より大きい (非線形) 方程式のシステムを解くのにも使用できます。非線形システムに解が^ない場合、^この方法は^非線形最小^二乗法の意味で解を見つけようとします。詳細については、 ガウス・ニュートン法を参照してください。

例えば、次の方程式は、既知の値のベクトルが与えられた場合、点のベクトルについて解く必要がある^[22]${\displaystyle \ [\ x_{1},x_{2}\ ]\ ,}$${\displaystyle \ [\ 2,3\ ]~.}$

${\displaystyle {\begin{array}{lcr}5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})&=\quad 2\\e^{2\ x_{1}-x_{2}}+4\ x_{2}&=\quad 3\end{array}}}$

反復kに対する関数ベクトルとヤコビ行列、および既知の値のベクトルは以下のように定義されます。 ${\displaystyle \ F(X_{k})\ ,}$${\displaystyle \ J(X_{k})\ }$${\displaystyle \ Y\ ,}$

${\displaystyle {\begin{aligned}~&F(X_{k})~=~{\begin{bmatrix}{\begin{aligned}~&f_{1}(X_{k})\\~&f_{2}(X_{k})\end{aligned}}\end{bmatrix}}~=~{\begin{bmatrix}{\begin{aligned}~&5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})\\~&e^{2\ x_{1}-x_{2}}+4\ x_{2}\end{aligned}}\end{bmatrix}}_{k}\\~&J(X_{k})={\begin{bmatrix}~{\frac {\ \partial {f_{1}(X)}\ }{\partial {x_{1}}}}\ ,&~{\frac {\ \partial {f_{1}(X)}\ }{\partial {x_{2}}}}~\\~{\frac {\ \partial {f_{2}(X)}\ }{\partial {x_{1}}}}\ ,&~{\frac {\ \partial {f_{2}(X)}\ }{\partial {x_{2}}}}~\end{bmatrix}}_{k}~=~{\begin{bmatrix}{\begin{aligned}~&10\ x_{1}+x_{2}^{2}\ ,&&2\ x_{1}\ x_{2}+4\ \sin(2\ x_{2})\ \cos(2\ x_{2})\\~&2\ e^{2\ x_{1}-x_{2}}\ ,&&-e^{2\ x_{1}-x_{2}}+4\end{aligned}}\end{bmatrix}}_{k}\\~&Y={\begin{bmatrix}~2~\\~3~\end{bmatrix}}\end{aligned}}}$

を吸収して方程式から消去する ように書き直すこともできることに注意してください。各反復で解く方程式は次のとおりです。 ${\displaystyle \ F(X_{k})\ }$${\displaystyle \ Y\ ,}$${\displaystyle Y}$

${\displaystyle {\begin{aligned}{\begin{bmatrix}{\begin{aligned}~&~10\ x_{1}+x_{2}^{2}\ ,&&2x_{1}x_{2}+4\ \sin(2\ x_{2})\ \cos(2\ x_{2})~\\~&~2\ e^{2\ x_{1}-x_{2}}\ ,&&-e^{2\ x_{1}-x_{2}}+4~\end{aligned}}\end{bmatrix}}_{k}{\begin{bmatrix}~c_{1}~\\~c_{2}~\end{bmatrix}}_{k+1}={\begin{bmatrix}~5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})-2~\\~e^{2\ x_{1}-x_{2}}+4\ x_{2}-3~\end{bmatrix}}_{k}\end{aligned}}}$

そして

${\displaystyle X_{k+1}~=~X_{k}-C_{k+1}}$

反復は、アプリケーションの要件を満たすのに十分小さい値に なるまで繰り返されます。${\displaystyle \ {\Bigg [}\sum _{i=1}^{i=2}{\Bigl |}f(x_{i})_{k}-(y_{i})_{k}{\Bigr |}{\Bigg ]}<E\ ,}$${\displaystyle \ E\ }$

ベクトルが最初に と選択され、が1.10 ⁻³と選択された場合、この例は4回の反復後に次の値に収束します。${\displaystyle \ X_{0}\ }$${\displaystyle \ {\begin{bmatrix}~1~&~1~\end{bmatrix}}\ ,}$${\displaystyle \ x_{1}=1\ ,}$${\displaystyle \ x_{2}=1\ ,}$${\displaystyle \ E\ ,}$${\displaystyle \ X_{4}=\left[~0.567297,\ -0.309442~\right]~.}$

解決の過程で、次の反復が行われました。

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

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

カート・マクマレンは、ニュートン法に似た純粋に反復的なアルゴリズムは、4次以上の多項式に適用すると、複素平面のいくつかの開いた領域で発散することを示した。しかし、マクマレンは3次多項式に対しては一般的に収束するアルゴリズムを示した。^[25]また、ハバード、シュライヒャー、サザーランドは、任意の多項式に対して、ニュートン法が少なくともそのうちの1つで確実に収束するように初期点の集合を選択する方法を示した。^[26]

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

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

ここで、F ′ ( Xn )は_Xnで計算されたフレシェ微分である。この方法を適用するには、フレシェ微分が各Xnで境界可逆であることが必要である_。根の存在と根への収束の条件はニュートン・カントロヴィッチの定理_によって与えられる。^[27]

1950年代に、ジョン・ナッシュは、ユークリッド空間における一般リーマン多様体の等長埋め込みを構築する問題に適用するニュートン法のバージョンを開発した。この文脈に存在する導関数の損失の問題により、標準的なニュートン反復法は適用不可能であった。なぜなら、それは無制限に継続することができない（収束するどころか）からである。ナッシュの解決策は、反復に平滑化演算子を導入することであった。彼は、等長埋め込みの暗黙の関数定理を証明する目的で、平滑化ニュートン法の収束を証明することができた。1960年代に、ユルゲン・モーザーは、ナッシュの方法が、特に天体力学において、等長埋め込み以外の問題にも適用できるほど柔軟であることを示した。それ以来、ミカエル・グロモフやリチャード・ハミルトンを含む多くの数学者が、ナッシュ-モーザー理論の一般化された抽象バージョンを発見した。^{[28] [29]ハミルトンの定式化では、ナッシュ・モーザーの定理は、特定の}フレシェ空間で行われるバナッハ空間ニュートン法の一般化を形成します。

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

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

ニュートン法は、通常の微分法のq類似体で一般化することができる。 ^[30]

非線形方程式は一般に複数の解を持つ。しかし、初期値が適切でない場合、ニュートン法は目的の解に収束しないか、以前に見つかった解と同じ解に収束する可能性がある。 のN個の解がすでに見つかった場合、次の方程式にニュートン法を適用することで次の根を見つけることができる。^{[31] [32]}${\displaystyle f(x)=0}$

$${\displaystyle F(x)={\frac {f(x)}{\prod _{i=1}^{N}(x-x_{i})}}=0.}$$

この方法は第二種ベッセル関数の零点を求めるために適用される。 ^[33]

平野の修正ニュートン法は、ニュートン法の収束性を保存し、不安定性を回避する修正法である。^[34]これは、複素多項式を解くために開発された。

ニュートン法と区間演算を組み合わせると、いくつかの状況では非常に便利です。これにより、通常の停止基準（関数の値が小さい、または連続する反復間の変数の小さな変化）よりも信頼性の高い停止基準が得られます。また、これにより、ニュートン法が理論的には収束するが、浮動小数点精度が不十分なために数値的には発散するケースを検出できます（これは通常、次数が大きい多項式の場合に当てはまり、変数の非常に小さな変化が関数の値を大幅に変更する可能性があります。ウィルキンソンの多項式を参照）。^{[35] [36]}

f → C ¹ ( X )を考えます。ここで、X は実数区間です。f ′の区間拡張F ′があるとします。つまり、F ′ は区間Y ⊆ X を入力として受け取り、次のような区間F ′ ( Y )を出力します。

$${\displaystyle {\begin{aligned}F'([y,y])&=\{f'(y)\}\\[5pt]F'(Y)&\supseteq \{f'(y)\mid y\in Y\}.\end{aligned}}}$$

また、0 ∉ F ′ ( X )と仮定すると、特にf はXに最大で1つの根を持ちます。次に、区間ニュートン演算子を次のように定義します。

$${\displaystyle N(Y)=m-{\frac {f(m)}{F'(Y)}}=\left\{\left.m-{\frac {f(m)}{z}}~\right|~z\in F'(Y)\right\}}$$

ここで、m∈Yです。F′の仮定は、N ( Y )が明確に定義され、区間であることを意味します（区間演算の詳細については、区間演算を参照してください）。これは自然に次のシーケンスにつながります。

$${\displaystyle {\begin{aligned}X_{0}&=X\\X_{k+1}&=N(X_{k})\cap X_{k}.\end{aligned}}}$$

平均値定理は、 X k_にfの根がある場合、それはX _{k + 1}にも存在するということを保証します。さらに、 F′の仮説は、 m がYの中点であるとき、X _{k + 1 は最大でも}X _kの半分の大きさになることを保証します。したがって、このシーケンスは[ x* , x* ]に向かって収束します。ここで、x*はXにおけるfの根です。

F ′ ( X )が厳密に0を含む場合、拡張区間除算を使用するとN ( X )の2つの区間の和集合が生成されます。したがって、多重根は自動的に分離され、境界が設定されます。

ニュートン法は関数f ( x )の最小値や最大値を見つけるのに使えます。最小値や最大値では導関数はゼロなので、ニュートン法を導関数に適用することで極小値と最大値を見つけることができます。^[37]反復は次のようになります。

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

重要な応用としてニュートン・ラプソン除法があります。これは、乗算と減算のみを使用して数aの逆数、つまり数xを素早く求めるために使用できます。1/x⁠ = a 。これをf ( x ) = ⁠のゼロを見つけると言い換えることもできます1/x⁠ − a . f ′ ( x ) = − ⁠1/× ²⁠ .

ニュートンの反復法は

$${\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 回の減算のみが必要です。

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

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

ニュートン法を複数回使用し、解の候補の集合を形成することによって、非線形方程式の解の数値検証が確立されました。^[要出典]

以下は、導関数 を持つ関数の根を見つけるための、Python (バージョン 3.x) プログラミング言語でのニュートン法の可能な実装例です。 ff_prime

初期推定値はx ₀ = 1となり、関数はf ( x ) = x ² − 2となるので、f ′ ( x ) = 2 xとなります。

ニュートン法の各新しい反復は で表されますx1。計算中に、分母 ( yprime) が小さくなりすぎないか ( より小さくならないか) を確認します。これは、 f ′ ( x _n ) ≈ 0の場合に該当します。そうでない場合、大きな誤差が生じる可能性 epsilonがあります。

• Gil, A.; Segura, J.; Temme, NM (2007). 特殊関数の数値解析法. 工業応用数学協会. ISBN 978-0-89871-634-4。
• スーリ、エンドレ、メイヤーズ、デイヴィッド（2003）。数値解析入門。ケンブリッジ大学出版局。ISBN 0-521-00794-1。

• ケンドール・E・アトキンソン『数値解析入門』(1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6 
• Tjalling J. Ypma、「ニュートン-ラプソン法の歴史的発展」、SIAM Review 37 (4)、531-551、1995年。doi : 10.1137/1037125。
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). 数値最適化: 理論と実践の側面。Universitext (1997 年フランス語版の翻訳の第 2 版)。ベルリン: Springer -Verlag。pp. xiv+490。doi :10.1007 / 978-3-540-35447-5。ISBN 3-540-35445-X. MR  2265882。
• P. Deuflhard、「非線形問題に対するニュートン法。アフィン不変性と適応アルゴリズム」。Springer Series in Computational Mathematics、第35巻。Springer、ベルリン、2004年。ISBN 3-540-21099-7。 
• CT Kelley、「ニュートン法による非線形方程式の解法」、アルゴリズムの基礎第 1 号、SIAM、2003 年。ISBN 0-89871-546-6。 
• JM Ortega、WC Rheinboldt、「複数変数の非線形方程式の反復解法」。応用数学の古典、SIAM、2000年。ISBN 0-89871-461-3。 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「第 9 章 根の探索と非線形方程式セットの重要度サンプリング」。数値レシピ: 科学計算の技術(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8。特にセクション9.4、9.6、および9.7を参照してください。
• アヴリエル、モーデカイ (1976)。非線形計画法:分析と方法。プレンティス ホール。pp. 216–221。ISBN 0-13-623603-0。

• 「ニュートン法」、数学百科事典、EMS Press、2001 [1994]
• ワイスタイン、エリック W.「ニュートン法」。MathWorld。
• ニュートン法、Citizendium。
• Mathews, J.、「加速および修正ニュートン法」、コースノート。
• Wu, X.、「方程式の根」、コースノート。