ニュートン法
数値解析の分野において、ニュートン法(ニュートンほう、Newton's method)またはニュートン・ラフソン法(Newton-Raphson method)は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソンに由来する。
この方法の考え方は以下のようである:まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線を考え、その x 切片を計算する。このx切片の値は、予想される真の解により近いものとなるのが一般である。以後、この値に対してそこでグラフの接線を考え、同じ操作を繰り返していく。
上の考え方は次のように定式化される。
ここでは、考える問題を f: R → R, x ∈ Rとして
f(x) = 0\,
となる x を求めることに限定する。このとき、x の付近に適当な値 x0 をとり、次の漸化式によって、x に収束する数列を得ることができる場合が多い。
naive-newtonx_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \quad \cdots (1)
例として、 \sqrt{2}  を計算で求める場合に、
f(x) = x^2 - 2\,
とおき、f(x) = 0 の解を求めることを考える。
f'(x) = 2x\,
であるので、(1) の式は
x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left( x_n + \frac{2}{x_n} \right)
と書き表せる。たとえば x0 = 2 とおくと、この数列は  \sqrt{2} に収束するが、その収束の仕方は
x0 = 2
x1 = 1.5
x2 = 1.416666…
x3 = 1.4142156862745…
x4 = 1.4142135623746899… (下線部は\sqrt{2}と一致する部分)
となる。
また、x0 = −1 とおくと、この数列は -\sqrt{2}に収束する。
初期値x_0を解の十分近くに選ぶことを要求した上で、
f(x) = 0\,
の解を考える(解の存在を仮定する)。
f(x)
x=x_0
f(x) =f(x_0)+f^{\prime}(x_0)(x-x_0)+O((x-x_0)^2)
このとき、(右辺)=0の解は、(左辺)=0の根の
x_0での多項式次数一次の近似となっている。
x=x_0-\frac{f(x_0)}{f^{\prime}(x_0)}
次に、この近似値が、x_0より根に近づいている
ということに関する意味を考える。
上式を、次のような離散力学系として考える。
x_{n+1} = g(x_n), ただし g(x) = x - \frac{f(x)}{f'(x)}
この力学系において、f(x^*)=0
となるx^*は明らかに固定点である。
したがって|g'(x^*)|<1、つまりx^*が沈点(アトラクター、安定固定点)であり、
与えられた初期条件x_0が、このアトラクターの吸引領域に属していれば
x_nの\omega-極限(n \rightarrow \infty)は
f(x^*)=0となるx^*に収束する。
x^*が沈点である保証は、常に担保されてはいない。
例えばx軸の漸近線や関数f(x)の極値近傍では固定点が不安定になる事が知られている。
たとえばf(x^*)を、適当な近傍の点x_nで展開するとf'(x^*)\neq0なら、二次の余剰項R_2=\frac{f(\xi_n)}{2}(x_n-x^*)^2として
x_{n+1}-x^*=-\frac{f(\xi_n)}{2f'(x_n)}(x_n-x^*)^2
よって2次で収束する。
前節では解の存在を仮定した上で初期値x_0を解の十分近くに選ぶことを要求した。これに対して、解の存在を仮定せず、初期値x_0がある条件を満たすときに解の存在と反復の収束を示す定理を半局所収束定理(semi-local convergence theorem)という。1次元の場合での半局所収束定理はコーシーによって1829年に示され、n次元ユークリッド空間での場合はファインによって1916年に示された。その後、バナッハ空間での半局所収束定理がカントロヴィチによって1948年に示され、現代ではニュートン=カントロヴィチの定理と呼ばれている。この定理にはいくつかの変種が知られており、にまとめられている。
ニュートン法は、接線を一次近似式、接線のx切片を一次近似式の零点と考えることにより、より高次元の関数の場合に一般化できる。
対象となる関数を f: Rm → Rm, x ∈ Rm とし、
f(\mathbf{x}) = \mathbf{0}
なる点 x を求めるには次のようにする。(f が同じ次元の空間の間の関数であることに注意せよ。)
まず、今 x0 ∈ Rm が既知であるとする。x0における f(x) の一次近似式
f(\mathbf{x}_0) + \partial f(\mathbf{x}_0)(\mathbf{x} - \mathbf{x}_0)
を考える。ただし、∂f(x0) は、m × m のヤコビ行列である。
この一次近似式の零点を求める。ヤコビ行列∂f(x0) が正則行列であるとして、
f(\mathbf{x}_0) + \partial f(\mathbf{x}_0)(\mathbf{x} - \mathbf{x}_0)=\mathbf{0}
を解いて、
\mathbf{x} = \mathbf{x}_0 - \partial f(\mathbf{x}_0)^{-1} f(\mathbf{x}_0)
となる。
コンピュータで計算を行う場合 ∂f(x0)-1f(x0) を直接求めることは困難なので、
\partial f(\mathbf{x}_0) \mathbf{r} = f(\mathbf{x}_0)
という方程式をガウスの消去法などの解法によって線形方程式系を解き r を求め、x = x0 - r によって x を求める。
ここで求めた x はx0よりも f(x) = 0 の解に近いことが見込まれる。そこで、今求めた x を x1 として、再び同様の計算を繰り返す。計算を繰り返すことによって xn は f(x) = 0 の解に近づいていく。
逆行列を求めることを避けるために共役勾配法を用いることがある。
ニュートン法により近似値を求めようとする場合にはヤコビ行列が陽に分からなければ計算できない。しかし、関数 f によってはヤコビ行列が陽に分からない場合もある。この場合にはヤコビ行列を必要としない準ニュートン法を用いる。
また、f (x*)  0 を満たす真の解 x* において導関数が f '(x*)  0 であった場合、収束の速さは1次に退化する。
ニュートン法の考え方を少し改良することにより、(1) の代わりに次の式を用いる方法を得る。
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]\;}
この方法は、場合によっては従来の方法より速い。
ニュートン法の局所的な2次収束性を保ちつつ、不安定な振る舞いを抑えるように工夫した方法として平野の変形ニュートン法が知られている。
ニュートン法における導関数の計算を簡略化したものが簡易ニュートン法である:
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_0)}.
簡易ニュートン法に対する半局所収束定理は占部の定理として知られる。占部の定理は元々数学的帰納法を使って示されたが、その後、バナッハの不動点定理を使った別証明が与えられた。
簡易ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発された簡易ニュートン法の変種がクラフチック(Krawczyk)法である。
ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発されたニュートン法の変種が区間ニュートン法である。
ニュートン法において微分の代わりに微分のq-類似(q-微分)を使う反復をq-ニュートン法という:
x_{n+1} = x_n - \frac{f(x_n)}{D_q(x_n)}.
q-ニュートン法に対する半局所収束定理がq-ニュートン-カントロビッチの定理である。