ニュートン法

数値解析の分野において、ニュートン法（ニュートンほう、）またはニュートン・ラフソン法（）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソンに由来する。
導入.
この方法の考え方は以下のようである：まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線を考え、その "x" 切片を計算する。この"x"切片の値は、予想される真の解により近いものとなるのが一般である。以後、この値に対してそこでグラフの接線を考え、同じ操作を繰り返していく。
上の考え方は次のように定式化される。
ここでは、考える問題を "f": R → R, "x" ∈ Rとして
となる "x" を求めることに限定する。このとき、"x" の付近に適当な値 "x"0 をとり、次の漸化式によって、"x" に収束する数列を得ることができる場合が多い。
例として、formula_3 を計算で求める場合に、
とおき、"f"("x") = 0 の解を求めることを考える。
であるので、(1) の式は
と書き表せる。たとえば "x"0 = 2 とおくと、この数列は formula_7 に収束するが、その収束の仕方は
となる。
また、"x"0 = −1 とおくと、この数列は formula_9に収束する。
理論.
局所収束定理.
初期値formula_10を解の十分近くに選ぶことを要求した上で、
の解を考える（解の存在を仮定する）。
formula_12
の
formula_13
でのテーラー展開をすると
このとき、(右辺)=0の解は、(左辺)=0の根の
formula_10での多項式次数一次の近似となっている。
右辺の解は
次に、この近似値が、formula_10より根に近づいている
ということに関する意味を考える。
上式を、次のような離散力学系として考える。
この力学系において、formula_20
となるformula_21は明らかに固定点である。
したがってformula_22、つまりformula_21が沈点(アトラクター、安定固定点)であり、
与えられた初期条件formula_10が、このアトラクターの吸引領域に属していれば
formula_25のformula_26-極限(formula_27)は
formula_20となるformula_21に収束する。
formula_21が沈点である保証は、常に担保されてはいない。
例えばx軸の漸近線や関数formula_12の極値近傍では固定点が不安定になる事が知られている。
たとえばformula_32を、適当な近傍の点formula_25で展開するとformula_34なら、二次の余剰項formula_35として
formula_36
よって２次で収束する。
半局所収束定理.
前節では解の存在を仮定した上で初期値formula_10を解の十分近くに選ぶことを要求した。これに対して、解の存在を仮定せず、初期値formula_10がある条件を満たすときに解の存在と反復の収束を示す定理を半局所収束定理（）という。1次元の場合での半局所収束定理はコーシーによって1829年に示され、formula_39次元ユークリッド空間での場合はファインによって1916年に示された。その後、バナッハ空間での半局所収束定理がカントロヴィチによって1948年に示され、現代ではニュートン＝カントロヴィチの定理と呼ばれている。この定理にはいくつかの変種が知られており、にまとめられている。
高次元の場合.
ニュートン法は、接線を一次近似式、接線の"x"切片を一次近似式の零点と考えることにより、より高次元の関数の場合に一般化できる。
対象となる関数を "f": R"m" → R"m", x ∈ R"m" とし、
なる点 x を求めるには次のようにする。（"f" が同じ次元の空間の間の関数であることに注意せよ。）
まず、今 x0 ∈ R"m" が既知であるとする。x0における "f"(x) の一次近似式
を考える。ただし、∂"f"(x0) は、"m" × "m" のヤコビ行列である。
この一次近似式の零点を求める。ヤコビ行列∂"f"(x0) が正則行列であるとして、
を解いて、
となる。
コンピュータで計算を行う場合 ∂"f"(x0)-1"f"(x0) を直接求めることは困難なので、
という方程式をガウスの消去法などの解法によって線形方程式系を解き r を求め、x = x0 - r によって x を求める。
ここで求めた x はx0よりも "f"(x) = 0 の解に近いことが見込まれる。そこで、今求めた x を x1 として、再び同様の計算を繰り返す。計算を繰り返すことによって xn は "f"(x) = 0 の解に近づいていく。
逆行列を求めることを避けるために共役勾配法を用いることがある。
注意.
ニュートン法により近似値を求めようとする場合にはヤコビ行列が陽に分からなければ計算できない。しかし、関数 "f" によってはヤコビ行列が陽に分からない場合もある。この場合にはヤコビ行列を必要としない準ニュートン法を用いる。
また、 を満たす真の解 において導関数が であった場合、収束の速さは1次に退化する。
改良.
ニュートン法の考え方を少し改良することにより、(1) の代わりに次の式を用いる方法を得る。
この方法は、場合によっては従来の方法より速い。 
平野の変形ニュートン法.
ニュートン法の局所的な２次収束性を保ちつつ、不安定な振る舞いを抑えるように工夫した方法として平野の変形ニュートン法が知られている。
簡易ニュートン法.
ニュートン法における導関数の計算を簡略化したものが簡易ニュートン法である:
簡易ニュートン法に対する半局所収束定理は"占部の定理"として知られる。占部の定理は元々数学的帰納法を使って示されたが、その後、バナッハの不動点定理を使った別証明が与えられた。
クラフチック法.
簡易ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発された簡易ニュートン法の変種がクラフチック（Krawczyk）法である。
区間ニュートン法.
ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発されたニュートン法の変種が区間ニュートン法である。
-ニュートン法.
ニュートン法において微分の代わりに微分のq-類似（-微分）を使う反復を-ニュートン法という:
-ニュートン法に対する半局所収束定理が-ニュートン-カントロビッチの定理である。