ニュートン法

数値解析の分野において、ニュートン法（ニュートンほう、英: Newton's method）またはニュートン・ラフソン法（英: Newton–Raphson method）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソンに由来する。

この方法の考え方は以下のようである：まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線を考え、その x 切片を計算する。このx切片の値は、予想される真の解により近いものとなるのが一般である。以後、この値に対してそこでグラフの接線を考え、同じ操作を繰り返していく。

上の考え方は次のように定式化される。 ここでは、考える問題を f: R → R, x ∈ Rとして

${\displaystyle f(x)=0\,}$

となる x を求めることに限定する。このとき、x の付近に適当な値 x₀ をとり、次の漸化式によって、x に収束する数列を得ることができる場合が多い。

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

例として、${\displaystyle {\sqrt {2}}}$ を計算で求める場合に、

${\displaystyle f(x)=x^{2}-2\,}$

とおき、f(x) = 0 の解を求めることを考える。

${\displaystyle f'(x)=2x\,}$

であるので、(1) の式は

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

と書き表せる。たとえば x₀ = 2 とおくと、この数列は ${\displaystyle {\sqrt {2}}}$ に収束するが、その収束の仕方は

x₀ = 2

x₁ = 1.5

x₂ = 1.416666…

x₃ = 1.4142156862745…

x₄ = 1.4142135623746899… (下線部は${\displaystyle {\sqrt {2}}}$と一致する部分)

となる。

また、x₀ = −1 とおくと、この数列は ${\displaystyle -{\sqrt {2}}}$に収束する。

初期値${\displaystyle x_{0}}$を解の十分近くに選ぶことを要求した上で、

${\displaystyle f(x)=0\,}$

の解を考える（解の存在を仮定する）。 ${\displaystyle f(x)}$ の ${\displaystyle x=x_{0}}$ でのテーラー展開をすると

${\displaystyle f(x)=f(x_{0})+f^{\prime }(x_{0})(x-x_{0})+O((x-x_{0})^{2})}$

このとき、(右辺)=0の解は、(左辺)=0の根の ${\displaystyle x_{0}}$での多項式次数一次の近似となっている。 右辺の解は

${\displaystyle x=x_{0}-{\frac {f(x_{0})}{f^{\prime }(x_{0})}}}$

次に、この近似値が、${\displaystyle x_{0}}$より根に近づいている ということに関する意味を考える。 上式を、次のような離散力学系として考える。

${\displaystyle x_{n+1}=g(x_{n})}$, ただし ${\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}$

この力学系において、${\displaystyle f(x^{*})=0}$ となる${\displaystyle x^{*}}$は明らかに固定点である。

したがって${\displaystyle |g'(x^{*})|<1}$、つまり${\displaystyle x^{*}}$が沈点(アトラクター、安定固定点)であり、 与えられた初期条件${\displaystyle x_{0}}$が、このアトラクターの吸引領域に属していれば ${\displaystyle x_{n}}$の${\displaystyle \omega }$-極限(${\displaystyle n\rightarrow \infty }$)は ${\displaystyle f(x^{*})=0}$となる${\displaystyle x^{*}}$に収束する。

${\displaystyle x^{*}}$が沈点である保証は、常に担保されてはいない。 例えばx軸の漸近線や関数${\displaystyle f(x)}$の極値近傍では固定点が不安定になる事が知られている。 ^[1]

たとえば${\displaystyle f(x^{*})}$を、適当な近傍の点${\displaystyle x_{n}}$で展開すると${\displaystyle f'(x^{*})\neq 0}$なら、二次の余剰項${\displaystyle R_{2}={\frac {f''(\xi _{n})}{2}}(x_{n}-x^{*})^{2}}$として

${\displaystyle x_{n+1}-x^{*}=-{\frac {f''(\xi _{n})}{2f'(x_{n})}}(x_{n}-x^{*})^{2}}$

よって２次で収束する。

前節では解の存在を仮定した上で初期値${\displaystyle x_{0}}$を解の十分近くに選ぶことを要求した。これに対して、解の存在を仮定せず、初期値${\displaystyle x_{0}}$がある条件を満たすときに解の存在と反復の収束を示す定理を半局所収束定理（semi-local convergence theorem）という。1次元の場合での半局所収束定理はコーシーによって1829年に示され、${\displaystyle n}$次元ユークリッド空間での場合はファイン^[2]によって1916年に示された。その後、バナッハ空間での半局所収束定理がカントロヴィチによって1948年に示され、現代ではニュートン＝カントロヴィチの定理と呼ばれている^[3]。この定理にはいくつかの変種が知られており、(Ortega & Rheinboldt 1970)^[4]にまとめられている。

ニュートン法は、接線を一次近似式、接線のx切片を一次近似式の零点と考えることにより、より高次元の関数の場合に一般化できる。 対象となる関数を f: R^m → R^m, x ∈ R^m とし、

${\displaystyle f(\mathbf {x} )=\mathbf {0} }$

なる点 x を求めるには次のようにする。（f が同じ次元の空間の間の関数であることに注意せよ。）

まず、今 x₀ ∈ R^m が既知であるとする。x₀における f(x) の一次近似式

${\displaystyle f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})}$

を考える。ただし、∂f(x₀) は、m × m のヤコビ行列である。

この一次近似式の零点を求める。ヤコビ行列∂f(x₀) が正則行列であるとして、

${\displaystyle f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})=\mathbf {0} }$

を解いて、

${\displaystyle \mathbf {x} =\mathbf {x} _{0}-\partial f(\mathbf {x} _{0})^{-1}f(\mathbf {x} _{0})}$

となる。

コンピュータで計算を行う場合 ∂f(x₀)^-1f(x₀) を直接求めることは困難なので、

${\displaystyle \partial f(\mathbf {x} _{0})\mathbf {r} =f(\mathbf {x} _{0})}$

という方程式をガウスの消去法などの解法によって線形方程式系を解き r を求め、x = x₀ - r によって x を求める。

ここで求めた x はx₀よりも f(x) = 0 の解に近いことが見込まれる。そこで、今求めた x を x₁ として、再び同様の計算を繰り返す。計算を繰り返すことによって x_n は f(x) = 0 の解に近づいていく。

逆行列を求めることを避けるために共役勾配法を用いることがある。

ニュートン法により近似値を求めようとする場合にはヤコビ行列が陽に分からなければ計算できない。しかし、関数 f によってはヤコビ行列が陽に分からない場合もある。この場合にはヤコビ行列を必要としない準ニュートン法を用いる。

また、f (x^*) = 0 を満たす真の解 x^* において導関数が f '(x^*) = 0 であった場合、収束の速さは1次に退化する^[5]。

ニュートン法の考え方を少し改良することにより、(1) の代わりに次の式を用いる方法を得る。

${\displaystyle x_{k+1}=x_{k}-{\frac {{\Bigl [}f(x_{k}){\Bigr ]}^{2}}{\;f^{\boldsymbol {\prime }}(x_{k}){\Bigl [}f(x_{k})-f{\Bigl (}x_{k}-{\dfrac {f(x_{k})}{f^{\boldsymbol {\prime }}(x_{k})}}{\Bigr )}{\Bigr ]}\;}}}$

この方法は、場合によっては従来の方法より速い^[6]。

ニュートン法の局所的な２次収束性を保ちつつ、不安定な振る舞いを抑えるように工夫した方法として平野の変形ニュートン法が知られている^[7]。

ニュートン法における導関数の計算を簡略化したものが簡易ニュートン法である:

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

簡易ニュートン法に対する半局所収束定理は占部の定理として知られる。占部の定理は元々数学的帰納法を使って示されたが、その後、バナッハの不動点定理を使った別証明が与えられた^[8]。

簡易ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発された簡易ニュートン法の変種がクラフチック（Krawczyk）法である^[9][10]。

ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発されたニュートン法の変種が区間ニュートン法である^[11]。

ニュートン法において微分の代わりに微分のq-類似（q-微分）を使う反復をq-ニュートン法という^[12]:

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

q-ニュートン法に対する半局所収束定理がq-ニュートン-カントロビッチの定理である^[13]。

ウィキメディア・コモンズには、ニュートン法に関連するカテゴリがあります。

• 除算 (デジタル)
• ガウス・ニュートン法
• ニュートン＝カントロビッチの定理

• 『ニュートン法の解説とそれを背景とする入試問題』 - 高校数学の美しい物語
• 山本哲朗、「Newton法とその周辺」『数学』 1985年 37巻 1号 p.1-15, doi:10.11429/sugaku1947.37.1, 日本数学会

表 話 編 歴 微分積分学
Precalculus	二項定理 凹関数 連続関数 階乗 有限差分 自由変数と束縛変数 基本定理 関数のグラフ 線型関数 平均値の定理 ラジアン ロルの定理 割線 傾き 接線
極限	不定形（英語版） 関数の極限 片側極限 数列の極限 数列の加速法 近似のオーダー（英語版） ε-δ論法
微分法	連鎖律 導関数 微分 微分方程式 微分作用素 陰関数微分 逆関数の微分（英語版） ロピタルの定理 ライプニッツ則 対数微分 平均値の定理 ニュートン法 記法 ライプニッツの記法 ニュートンの記法 レギオモンタヌスの問題 相対変化率（英語版） 基本法則 線型性（英語版） 積 商 冪函数（英語版） 停留点 極値の判定（英語版） 最大値の定理 極値 テイラーの定理
積分法	逆微分 弧長 積分定数 積分記号下の微分（英語版） 微分積分学の基本定理 正割の立方の積分（英語版） 正割関数の積分（英語版） 半角正接置換法（英語版） 積分における部分分数（英語版） 二次有理式の積分（英語版） 円周率が22/7より小さいことの証明 基本法則 線型性（英語版） 部分積分 置換積分 台形公式 三角函数置換法（英語版）
ベクトル解析	回転 方向微分 発散 発散定理 勾配 勾配定理（英語版） グリーンの定理 ラプラシアン ストークスの定理
多変数微分積分学	曲率 Disc integration（英語版） 発散定理 外微分 ガブリエルのホルン 幾何解析（英語版） ヘッセ行列 ヤコビ行列と行列式 線積分 Matrix calculus 多重積分 偏微分 バウムクーヘン積分 面積分 テンソル解析 体積分
級数	アーベルの判定法（英語版） 交代 交代級数判定法（英語版） 算術幾何数列 二項 コーシーの凝集判定法 比較判定法 ディリクレの判定法 オイラー–マクローリンの公式 フーリエ 幾何 超幾何 q超幾何 調和 無限 積分判定法 極限比較判定法（英語版） マクローリン 冪 比判定法 冪根判定法 テイラー 項判定法（英語版）
特殊関数と数学定数	ベルヌーイ数 ネイピア数 オイラー定数 指数関数 自然対数 ガンマ関数 スターリングの近似 楕円関数
歴史（英語版）	擬等式（英語版） ブルック・テイラー コリン・マクローリン 代数の一般性（英語版） ゴットフリート・ヴィルヘルム・ライプニッツ 無限小 無限小解析（英語版） アイザック・ニュートン 連続の法則（英語版） レオンハルト・オイラー 『流率法』 (流率（英語版）) 『方法（英語版）』
一覧	微分法則（英語版） 指数関数の原始関数 双曲線関数の原始関数 逆双曲線関数の原始関数 逆三角関数の原始関数 無理関数の原始関数 対数関数の原始関数 有理関数の原始関数 三角関数の原始関数 ガウス関数の原始関数 極限 数学記号 原始関数
カテゴリ