ニュートン法の理論(１変数の場合)

こんにちはketです。初記事です。

本記事の構成

◇目次

適用条件と特徴
ニュートン法の理論
アルゴリズム

って感じの流れです。今回は、長くなりすぎてしまうので１変数の場合のみについてまとめたいと思います。n変数の場合に関しては別記事で。

ではさっそく。

※勾配法を知らない場合は勾配法を勉強してからの方がいいと思います！勾配法のまとめページも完成させたらリンク貼ります。

ニュートン法の適用条件と特徴

適用できる条件は以下の３つ

１回微分 $f'(x)$ と、２回微分 $f''(x)\$ が計算可能の場合。
目的関数に制約がない場合。
凸関数の場合、もしくは最大値に近い点がわかってる場合。

ニュートン法の特徴は何と言ってもこれ

収束がめっちゃ早い。(２次収束する)

軽くまとめると、

定義域に縛りがない、いっぱい微分できる凸関数 $\displaystyle f(x)$ の最大値(もしくは最小値)を探す時に使えて、すぐ答えが見つかるよ

って感じ。

ニュートン法の理論

ニュートン法が、なぜ収束しやすく、またなぜ二回微分が必要なのか等を数学的に確認していきます。

１変数の場合

$x$ 軸上の点 $\displaystyle \overline{x}$ の近くの点 $\displaystyle \overline{x} + \Delta x$ での関数 $f(x)$ の値はテイラー展開して、

$f( \overline{x} + \Delta x ) = f( \overline{x} ) + f'(\overline{x})\Delta x + \frac{1}{2}f''(\overline{x})\Delta x^2 + \cdots$

のように書けます。

具体的に考えてみましょう。例えばある点 $\displaystyle \overline{x} = 2$ だとします。そしてその近くの点 $\displaystyle \overline{x} + \Delta x = 2.1$ の値を求めるために $\Delta x = 0.1$ とし、テイラー展開を用いて計算しよう(近似しよう)としています。何も難しいことはしていません。

上式の $\cdots$ の部分は $\Delta x$ の3次以上の項であるため、 $\Delta x$ がとても小さな数の場合、急速に0に近づきます。そこでこれらの項を無視して近似した新たな関数を次のように定めます。

$f_2( \Delta x ) = f( \overline{x} ) + f'( \overline{x})\Delta x + \frac{1}{2}f''( \overline{x} )\Delta x^2$

かなりスッキリしましたね。添字の2は2次の項まで近似しましたよ〜っていう意味です。最初の目的関数の代わりに、この2次近似した関数の最大(最小)を求めよう！というのがニュートン法の根幹の考え方になっています。

関数の最大を求めると言ったら、おなじみの微分ですね。 $\Delta x$ で $\displaystyle f_2( \Delta x )$ を微分して値が0になる $x$ を探しましょう。

$\displaystyle f'( \overline{x}) + f''(\overline {x}) \Delta x = 0$

$\displaystyle \Leftrightarrow \Delta x = -\frac{f'(\overline{x})}{f''(\overline{x})}$

このように求めた2次近似関数の最大値に移動する、つまりは以下のように

$\displaystyle x ← \overline{x} - \frac{f'(\overline{x})}{f''(\overline{x})}$

と $x$ を更新することによって、近似する前の目的関数の最大値に近づくことがことができます。

この近づいた点で、また同じように

2次近似を行い→最大値を求め→ $x$ を更新

を繰り返すことによって徐々に目的関数の最大値に近づくことができます。

ニュートン法のアルゴリズム

それではアルゴリズムを確認しましょう。

-------procedure Newton(f'(x),f"(x))-----------------------

$x$ に初期値を代入する。
$\displaystyle \overline{x} ← x$ と置き、以下のように $x$ を更新する。

$\displaystyle x ← \overline{x} - \frac{f'(x)}{f''(x)}$
ステップ2に戻り、これを $\displaystyle |x - \overline{x}| \lt \delta$ となるまで繰り返す。
$x$ を返す。