ニュートン法

提供: miniwiki
2018/8/19/ (日) 17:39時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

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

導入

ファイル:Newton iteration.svg
ニュートン法の一手順の概念図 (青い線が関数 f のグラフで、その接線を赤で示した). xn よりも xn+1 のほうが、 f(x)=0 の解 x についてのよりよい近似を与えている.

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

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

[math]f(x) = 0\,[/math]

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

[math]x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \quad \cdots (1) [/math]

例として、√2 を計算で求める場合に、

[math]f(x) = x^2 - 2\,[/math]

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

[math]f'(x) = 2x\,[/math]

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

[math]x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left( x_n + \frac{2}{x_n} \right)[/math]

と書き表せる。たとえば x0 = 1 とおくと、この数列は √2 に収束し、x0 = -1 とおくと、この数列は -√2 に収束する。

理論

局所収束定理

初期値[math]x_0[/math]を解の十分近くに選ぶことを要求した上で、

[math]f(x) = 0\,[/math]

の解を考える（解の存在を仮定する）。 [math]f(x)[/math] の [math]x=x_0[/math] でのテーラー展開をすると

[math]f(x) =f(x_0)+f^{\prime}(x_0)(x-x_0)+O((x-x_0)^2)[/math]

このとき、(右辺)=0の解は、(左辺)=0の根の [math]x_0[/math]での多項式次数一次の近似となっている。 右辺の解は

[math]x=x_0-\frac{f(x_0)}{f^{\prime}(x_0)}[/math]

次に、この近似値が、[math]x_0[/math]より根に近づいている ということに関する意味を考える。 上式を、次のような離散力学系として考える。

[math]x_{n+1} = g(x_n)[/math], ただし [math]g(x) = x - \frac{f(x)}{f'(x)}[/math]

この力学系において、[math]f(x^*)=0[/math] となる[math]x^*[/math]は明らかに固定点である。

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

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

たとえば[math]f(x^*)[/math]を、適当な近傍の点[math]x_n[/math]で展開すると[math]f'(x^*)\neq0[/math]なら、二次の余剰項[math]R_2=\frac{f''(\xi_n)}{2}(x_n-x^*)^2[/math]として

[math]x_{n+1}-x^*=-\frac{f''(\xi_n)}{2f'(x_n)}(x_n-x^*)^2[/math]

よって２次で収束する。

半局所収束定理

前節では解の存在を仮定した上で初期値[math]x_0[/math]を解の十分近くに選ぶことを要求した。これに対して、解の存在を仮定せず、初期値[math]x_0[/math]がある条件を満たすときに解の存在と反復の収束を示す定理を半局所収束定理（Semi-Local Convergence Theorem）という。1次元の場合での半局所収束定理はコーシーによって1829年に示され、[math]n[/math]次元ユークリッド空間での場合はファイン（Fine）によって1916年に示された。その後、バナッハ空間での半局所収束定理がカントロビッチ（Kantorovich）によって1948年に示され、現代ではニュートン-カントロビッチの定理と呼ばれている[2]。この定理にはいくつかの変種が知られており、[3]にまとめられている。

高次元の場合

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

[math]f(\mathbf{x}) = \mathbf{0}[/math]

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

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

[math] f(\mathbf{x}_0) + \partial f(\mathbf{x}_0)(\mathbf{x} - \mathbf{x}_0)[/math]

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

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

[math] f(\mathbf{x}_0) + \partial f(\mathbf{x}_0)(\mathbf{x} - \mathbf{x}_0)=\mathbf{0} [/math]

を解いて、

[math] \mathbf{x} = \mathbf{x}_0 - \partial f(\mathbf{x}_0)^{-1} f(\mathbf{x}_0)[/math]

となる。

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

[math] \partial f(\mathbf{x}_0) \mathbf{r} = f(\mathbf{x}_0) [/math]

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

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

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

注意

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

改良

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

[math] 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]\;} [/math]

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

平野の変形ニュートン法

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

簡易ニュートン法

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

[math]x_{n+1} = x_n - \frac{f(x_n)}{f'(x_0)}. [/math]

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

クラフチック法

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

区間ニュートン法

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

[math]q[/math]-ニュートン法

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

[math]x_{n+1} = x_n - \frac{f(x_n)}{D_q(x_n)}. [/math]

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

脚注

  1. ↑ Newton's Method(Wolfram Math World), http://mathworld.wolfram.com/NewtonsMethod.html . 2010閲覧. 
  2. ↑ 数値解析入門（増訂版）、山本哲郎、サイエンス社、2003年。
  3. ↑ J. Ortega & W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press (1970).
  4. ↑ 長島隆廣「ニュートン近似の改良」数学セミナー1980年5月号 p.112、日本評論社
  5. ↑ 室田一雄「平野の変形Newton法の大域的収束性」数理解析研究所講究録 (1981), 422: 104-118
  6. ↑ 非線形解析入門、大石進一、コロナ社、1997年。
  7. ↑ 精度保証付き数値計算、大石進一、コロナ社、2000年。
  8. ↑ Interval Newton Method
  9. ↑ Rajković, P., Stanković, M., & Marinković D, S. (2002). Mean value theorems in g-calculus. Matematički vesnik, 54(3-4), 171-178.
  10. ↑ Rajković, P. M., Marinković, S. D., & Stanković, M. S. (2005). On q-Newton–Kantorovich method for solving systems of equations. Applied Mathematics and Computation, 168(2), 1432-1448.

関連項目

外部リンク

テンプレート:最適化アルゴリズム



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ニュートン法&oldid=115364」から取得