数値解析 の分野において、ニュートン法 （ニュートンほう、英 : Newton's method ）またはニュートン・ラフソン法 （英 : Newton–Raphson method ）は、方程式 系を数値計算によって解くための反復法 による求根アルゴリズム の1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性 などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートン とジョゼフ・ラフソン に由来する。
ニュートン法の一手順の概念図 (青い線が関数 f のグラフで、その接線を赤で示した). x n x n +1f (x )=0 の解 x についてのよりよい近似を与えている. この方法の考え方は以下のようである：まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線を考え、その x 切片を計算する。このx 切片の値は、予想される真の解により近いものとなるのが一般である。以後、この値に対してそこでグラフの接線を考え、同じ操作を繰り返していく。
上の考え方は次のように定式化される。
ここでは、考える問題を f : R → R , x ∈ R として
f
(
x
)
=
0
{\displaystyle f(x)=0\,}
となる x を求めることに限定する。このとき、x の付近に適当な値 x 0 をとり、次の漸化式 によって、x に収束 する数列を得ることができる場合が多い。
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
n
)
⋯
(
1
)
{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\quad \cdots (1)}
例として、
2
{\displaystyle {\sqrt {2}}}
f
(
x
)
=
x
2
−
2
{\displaystyle f(x)=x^{2}-2\,}
とおき、f (x ) = 0 の解を求めることを考える。
f
′
(
x
)
=
2
x
{\displaystyle f'(x)=2x\,}
であるので、(1) の式は
x
n
+
1
=
x
n
−
x
n
2
−
2
2
x
n
=
1
2
(
x
n
+
2
x
n
)
{\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 0 = 2 とおくと、この数列は
2
{\displaystyle {\sqrt {2}}}
x 0 = 2x 1 = 1 .5x 2 = 1.41 6666…x 3 = 1.41421 56862745…x 4 = 1.41421356237 46899… (下線部は
2
{\displaystyle {\sqrt {2}}}
となる。
また、x 0 = −1 とおくと、この数列は
−
2
{\displaystyle -{\sqrt {2}}}
初期値
x
0
{\displaystyle x_{0}}
f
(
x
)
=
0
{\displaystyle f(x)=0\,}
の解を考える（解の存在を仮定する）。
f
(
x
)
{\displaystyle f(x)}
x
=
x
0
{\displaystyle x=x_{0}}
テーラー展開 をすると
f
(
x
)
=
f
(
x
0
)
+
f
′
(
x
0
)
(
x
−
x
0
)
+
O
(
(
x
−
x
0
)
2
)
{\displaystyle f(x)=f(x_{0})+f^{\prime }(x_{0})(x-x_{0})+O((x-x_{0})^{2})}
このとき、(右辺)=0の解は、(左辺)=0の根の
x
0
{\displaystyle x_{0}}
x
=
x
0
−
f
(
x
0
)
f
′
(
x
0
)
{\displaystyle x=x_{0}-{\frac {f(x_{0})}{f^{\prime }(x_{0})}}}
次に、この近似値が、
x
0
{\displaystyle x_{0}}
x
n
+
1
=
g
(
x
n
)
{\displaystyle x_{n+1}=g(x_{n})}
g
(
x
)
=
x
−
f
(
x
)
f
′
(
x
)
{\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}
この力学系において、
f
(
x
∗
)
=
0
{\displaystyle f(x^{*})=0}
x
∗
{\displaystyle x^{*}}
固定点 である。
したがって
|
g
′
(
x
∗
)
|
<
1
{\displaystyle |g'(x^{*})|<1}
x
∗
{\displaystyle x^{*}}
x
0
{\displaystyle x_{0}}
x
n
{\displaystyle x_{n}}
ω
{\displaystyle \omega }
n
→
∞
{\displaystyle n\rightarrow \infty }
f
(
x
∗
)
=
0
{\displaystyle f(x^{*})=0}
x
∗
{\displaystyle x^{*}}
x
∗
{\displaystyle x^{*}}
漸近線 や関数
f
(
x
)
{\displaystyle f(x)}
極値 近傍 では固定点が不安定になる事が知られている。
[ 1]
たとえば
f
(
x
∗
)
{\displaystyle f(x^{*})}
x
n
{\displaystyle x_{n}}
f
′
(
x
∗
)
≠
0
{\displaystyle f'(x^{*})\neq 0}
R
2
=
f
″
(
ξ
n
)
2
(
x
n
−
x
∗
)
2
{\displaystyle R_{2}={\frac {f''(\xi _{n})}{2}}(x_{n}-x^{*})^{2}}
x
n
+
1
−
x
∗
=
−
f
″
(
ξ
n
)
2
f
′
(
x
n
)
(
x
n
−
x
∗
)
2
{\displaystyle x_{n+1}-x^{*}=-{\frac {f''(\xi _{n})}{2f'(x_{n})}}(x_{n}-x^{*})^{2}}
よって２次で収束する。
前節では解の存在を仮定した上で初期値
x
0
{\displaystyle x_{0}}
x
0
{\displaystyle x_{0}}
semi-local convergence theorem ）という。1次元の場合での半局所収束定理はコーシー によって1829年に示され、
n
{\displaystyle n}
ユークリッド空間 での場合はファイン[ 2] バナッハ空間 での半局所収束定理がカントロヴィチ によって1948年に示され、現代ではニュートン＝カントロヴィチの定理 と呼ばれている[ 3] Ortega & Rheinboldt 1970 )[ 4]
ニュートン法は、接線を一次近似式、接線のx 切片を一次近似式の零点と考えることにより、より高次元の関数の場合に一般化できる。
対象となる関数を f : R m R m x ∈ R m
f
(
x
)
=
0
{\displaystyle f(\mathbf {x} )=\mathbf {0} }
なる点 x を求めるには次のようにする。（f が同じ次元の空間の間の関数であることに注意せよ。）
まず、今 x 0 ∈ R m x 0 における f (x ) の一次近似式
f
(
x
0
)
+
∂
f
(
x
0
)
(
x
−
x
0
)
{\displaystyle f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})}
を考える。ただし、∂f (x 0 ) は、m × m のヤコビ行列 である。
この一次近似式の零点を求める。ヤコビ行列∂f (x 0 ) が正則行列 であるとして、
f
(
x
0
)
+
∂
f
(
x
0
)
(
x
−
x
0
)
=
0
{\displaystyle f(\mathbf {x} _{0})+\partial f(\mathbf {x} _{0})(\mathbf {x} -\mathbf {x} _{0})=\mathbf {0} }
を解いて、
x
=
x
0
−
∂
f
(
x
0
)
−
1
f
(
x
0
)
{\displaystyle \mathbf {x} =\mathbf {x} _{0}-\partial f(\mathbf {x} _{0})^{-1}f(\mathbf {x} _{0})}
となる。
コンピュータで計算を行う場合 ∂f (x 0 )-1 f (x 0 ) を直接求めることは困難なので、
∂
f
(
x
0
)
r
=
f
(
x
0
)
{\displaystyle \partial f(\mathbf {x} _{0})\mathbf {r} =f(\mathbf {x} _{0})}
という方程式をガウスの消去法 などの解法によって線形方程式系 を解き r を求め、x = x 0 - r によって x を求める。
ここで求めた x はx 0 よりも f (x ) = 0 の解に近いことが見込まれる。そこで、今求めた x を x 1 として、再び同様の計算を繰り返す。計算を繰り返すことによって x n は f (x ) = 0 の解に近づいていく。
逆行列を求めることを避けるために共役勾配法を用いることがある。
ニュートン法により近似値を求めようとする場合にはヤコビ行列が陽に分からなければ計算できない。しかし、関数 f によってはヤコビ行列が陽に分からない場合もある。この場合にはヤコビ行列を必要としない準ニュートン法 を用いる。
また、f (x * ) = 0x * f '(x * ) = 0[ 5]
ニュートン法の考え方を少し改良することにより、(1) の代わりに次の式を用いる方法を得る。
x
k
+
1
=
x
k
−
[
f
(
x
k
)
]
2
f
′
(
x
k
)
[
f
(
x
k
)
−
f
(
x
k
−
f
(
x
k
)
f
′
(
x
k
)
)
]
{\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]
ニュートン法における導関数の計算を簡略化したものが簡易ニュートン法 である:
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
0
)
.
{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{0})}}.}
簡易ニュートン法に対する半局所収束定理は占部 の定理占部 の定理は元々数学的帰納法 を使って示されたが、その後、バナッハの不動点定理 を使った別証明が与えられた[ 8]
簡易ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発された簡易ニュートン法の変種がクラフチック（Krawczyk）法 である[ 9] [ 10]
ニュートン法に対する半局所収束定理の条件をより容易に評価するために開発されたニュートン法の変種が区間ニュートン法 である[ 11]
q -ニュートン法ニュートン法において微分の代わりに微分のq-類似 （q -微分）を使う反復をq -ニュートン法[ 12]
x
n
+
1
=
x
n
−
f
(
x
n
)
D
q
(
x
n
)
.
{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{D_{q}(x_{n})}}.}
q -ニュートン法に対する半局所収束定理がq -ニュートン-カントロビッチの定理である[ 13]
^
Newton's Method(Wolfram Math World) , http://mathworld.wolfram.com/NewtonsMethod.html 2010年6月8日 閲覧。
^
Fine, Henry B. (1916-09-15). “On Newton’s Method of Approximation”. Proceedings of the National Academy of Sciences of the United States of America 2 (9): 546–552. JSTOR 83815 .
^ 数値解析入門（増訂版）、山本哲朗、サイエンス社 、2003年。
^
Ortega, J.; Rheinboldt, W. (1970). Iterative Solution of Nonlinear Equations in Several Variables . Academic Press
^ 小澤一文『Cで学ぶ数値計算アルゴリズム』共立出版、2008年、49頁。ISBN 978-4-320-12221-5 。 ^ 長島, 隆廣「ニュートン近似の改良」『数学セミナー』第19巻第5号、日本評論社、1980年5月、112頁。 ^ 室田一雄「平野の変形Newton法の大域的収束性 」『情報処理学会論文誌』第21巻第6号、情報処理学会、1980年11月、469-474頁、CRID 1050282812867143936 、ISSN 1882-7764 。 ^ 非線形解析入門、大石進一 、コロナ社 、1997年。
^ 精度保証付き数値計算、大石進一 、コロナ社 、2000年。
^ 大石進一 et. al. (2018), 精度保証付き数値計算の基礎, コロナ社 .^ Interval Newton Method ^ Rajković, P.; Stanković, M.; Marinković, D, S. (2002-01), “Mean value theorems in g-calculus” , Matematički vesnik (Mathematical Society of Serbia, Belgrade) 54 (3-4): 171-178, http://scindeks-clanci.ceon.rs/data/pdf/0025-5165/2002/0025-51650204171R.pdf ^ Rajković, P. M.; Marinković, S. D.; Stanković, M. S. (2005-09-15), “On q-Newton–Kantorovich method for solving systems of equations” , Applied Mathematics and Computation (Elsevier) 168 (2): 1432-1448, doi :10.1016/j.amc.2004.10.035 , https://www.researchgate.net/publication/220557685_On_q-Newton-Kantorovich_method_for_solving_systems_of_equations
ウィキメディア・コモンズには、
ニュートン法 に関連するカテゴリがあります。
![{\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 ]}\;}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca1aa5547df6a0d7265955d306f51a9a3e0ff9f0)
