ニュートン・ラフソン法と極値

*赤げふさんからコメントを頂いたので修正 2017/3/26

ちょっと混乱したのでそのまとめ。

世の中には非線形方程式に解を与えなければならないことがある。この手の問題は解析的に解を求められるのが最善であることは確かだが、実際にはそうかんたんではない場合も多い。そのような場合、コンピュータで数値的に解を求められることがある。その方法の一つにニュートンラフソン法と呼ばれるものがある。

ニュートンラフソン法の場合、対象とする問題は$$f:\mathbb{R}^n \to \mathbb{R}^n$$のような関数、すなわち

$$ f(\bf{x}) = \bf{0} $$

のような非線形連立方程式の解を求めたい場合に使用する。注意してほしいのは、入力と出力の次元が等しい非線形方程式でないといけないことである。そうでないと使用できない(と思われる)。さて、この問題を解く場合、ニュートンラフソン法ではある入力\(\bf{x_0}\)における一次近似式を求め、これが\( 0\)となる場合の\(\bf x\)を求めるというのを繰り返すことで解を求める。これに対する直感的な説明は、他のページに譲るとして、この方程式を解いてみよう。$$f(\bf{x})$$の一次近似式は

$$ f(\bf{x}_0)+ Jf(\bf{x_0}) (\bf{x-x_0})$$

ここで\(Jf(\bf{x_0})\)はヤコビ行列である。この一次近似式が\(0 \)となる点を求めればいいので

$$\bf x_1 = x_0- Jf^{-1}(\bf{x_0})f(\bf{x}_0)$$

となる。ここで\(\bf{x_1}\)が次の点となる。これを、\(\bf x_1\)を次の点として同様の操作を逐次繰り返せば求めたい解となる。ここでヤコビ行列の逆行列を求める必要があるので、関数\(f\)は入力と出力の次元が等しい必要がある。

さて、本来の場合、出力が\(0 \)となる入力を求めるのが目的だが、場合によって関数の極値を求めるのにも使用される。その場合入力の次元が多次元で、出力が1次元の場合を扱う。というのも、極値となる点(候補の点)は、\(\nabla f(\bf x)\)が\( 0\)となる点を求めることに等しいため、ナブラを使用する都合上、出力が入力の次元と等しくなる。すると、そのままニュートンラフソン法が使用できるからである。

そして多くの文献ではこれをテイラー展開によって説明する。すなわち関数\(f( \bf x)\)のある点\(\bf x_0\)を中心とした二次までのテイラー展開

$$f(\bf x) \approx f(\bf x_o) + {}^{t}(\bf x – x_0) \nabla f(\bf x_0) + \frac{1}{2} {}^{t}(\bf{x – x_0}) \nabla \nabla f(\bf x_0) (x-x_0) $$

を考え、この両辺の勾配を取る。

$$\nabla f(\bf x) \approx \nabla f(\bf x_o) +  \nabla \nabla f(\bf x_0) (x – x_0)$$

ここで\( \nabla \nabla f(\bf x_0)\)はヘッセ行列*1である。さて、テイラー展開はn次まででやめると、n次のテイラー多項式と呼ばれ、それ自体がn次多項式近似となること、また多項式展開は基本的に一意的であること*2を考えれば、先程の勾配を取ったものは\(\nabla f(\bf x)\)の一次近似式であることがわかる。したがって、先程と同様の議論で

$$\bf x_1 = x_0- \nabla \nabla f^{-1}(\bf{x_0})f(\bf{x}_0)$$

が得られる。基本的に最初の例と原理は同じなので、これもニュートンラフソン法と呼ばれる。さて、これが一体何の役に立つのかということがわからない読者も多いかもしれない。私は役に立たないとやる気が起きないという物臭な性格をしているので、そういうあたりが気になるところだが、例えば複数のパラメータを調整することで、与えられた点を近似するような関数を求めたい場合に使用する。具体的にはそれはカメラの内部パラメータを求める場合であったり、またあるいは機械学習でパラメータ推定する場合等がある。注意しなければならないのは、この調整しようとする関数の出力は別に多次元でもかまわないという点である。なぜなら大抵の場合これらの近似における指標はスカラーの誤差関数で与えられるので、多変数を取るスカラー値を返す関数の極値を求める問題に帰着できるからである。

*このヘッセ行列は、当然だが\(\nabla f(\bf x)\)のヤコビ行列になっている。
*この事実は強力だ。というのも例えば\(\frac{1}{1-r}\)のテイラー展開を知りたいとしよう。さて、勉強熱心な読者はこれは等比級数で表現できることを知っているだろう。すなわち
$$\frac{1}{1-r} = 1 – r + r^2 – r^3 + \cdots $$
が成り立つ。そして多項式展開の一意性よりこれがテイラー展開の結果でもあることがわかる。更にこれを両辺積分すれば
$$\log(1-r) = r – \frac{1}{2}r^2 + \frac{1}{3}r^3 + \cdots $$
であることまでわかり、また同様にこれもテイラー展開した結果でもある。ちなみに積分定数はr=0のとき0であるので省略した。

内容についてどう思いますか?
  • いいね (4)
  • だめ (2)

ニュートン・ラフソン法と極値」への1件のフィードバック

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA