ニュートン・ラプソン法
解を求めたいが、解析的に求められない場合にコンピューティング技術で近似解を出す方法。
更新を続け、漸近的に（ゆっくりと）解に近づいていく。
ニュートン・ラプソン法は古典的な方法でよく目にする。
wikipediaより図を拝借
https://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A5%E3%83%BC%E3%83%88%E3%83%B3%E6%B3%95
基本形
問題の条件
- 求める解は、x軸との交点（y=0)
- 解を求めたい関数が微分可能であること
アイデア
- $f(x)=0$となるxを求めたい
- 適当な初期値$x_0$を設定する
- このときの座標は、$(x_0, f(x_0))$
- $f(x)=0$ に向けて近づきたい
- xで微分して、$f(x_0)'$を求めると、$x_0$に於ける傾きが求められる
- この接線とx軸との交点 $(x_{k+1}とする)$ を求めると、この交点 $x_{k+1}$ は $x_0$ より解に近づいているだろう
（「傾きaで、座標(x,y)を通る直線とx軸との交点を求める」問題に帰着。中学校の連立方程式。）
繰り返していくと、だんだん真の $f(x)=0$ に近くなる。
計算
前述のステップ6.の計算だけ考えてみる。
連立方程式。
\begin{align}
\left\{
\begin{array}{ll}
f(x_k) &= ax_k +b \\
a &= f'(x_k)
\end{array}
\right.
\end{align}
$y=ax+b$の直線を求めたい。
未知定数はa、bだが、aは既に$f'(x_k)$で決定済み。
bのみ求める。
\begin{align}
f(x_k) &= f'(x_k)x_k+b \\
\rightarrow b &= f(x_k) - f'(x_k)x_k
\end{align}
得られる直線、$y=ax+b$ は、
y = f'(x_k)x + f(x_k) - f'(x_k)x_k
ｘ軸との交点を求める（y=0を代入し、xを求める）
このxが、次に使用するx_{k+1}にあたるので、式中にも $ x -> x_{k+1}$ と書き替えておく。
\begin{align}
0 &= f'(x_k)x_{k+1} + f(x_k) - f'(x_k)x_k \\
f'(x_k)x_{k+1} &= f'(x_k)x_k - f(x_k) \\
\therefore x_{k+1} &= x_k - \frac{f(x_k)}{f'(x_k)}
\end{align}
勾配降下法
問題の条件
- 求める解は、最小値（1階微分=0)
- 解を求めたい関数が微分可能であること
基本はニュートン・ラプソン法と同じ発想。
x軸交点ではなく、1階微分が0になる点を求めるため一般的な最小化問題を扱う。
アイデア
- 最小化問題の解を求めたい
- 1階微分=0となる点を解と考える
- 傾きに沿って転がっていけば、最小値に到達するはず
- xで微分して傾きを求め、傾きに沿って微小ステップ（学習率）ずつ移動
計算
非常に単純で、
x_{k+1} = x_k - \alpha \cdot f'(x_k)
$\alpha$：学習率。0.01などを設定。これで徐々に傾きが0に近づいていく。
傾きに比例して移動量が小さくなる。
前述のニュートン・ラプソン法は、y=0に近づくにつれて移動量が小さくなっていた。
- ニュートン・ラプソン法：
x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}
- 勾配降下法：
x_{k+1} = x_k - \alpha \cdot f'(x_k)
ニュートン・ラプソン法 その２
今回は、y=0との交点ではなく、勾配降下法と同様に最小値問題を対象としたときについて考える。
問題の条件
- 求める解は、最小値（1階微分=0)
- 解を求めたい関数が2階微分可能であること
→ 基本のニュートン・ラプソン法との違い：
$y=0$ を求める問題を、$f'(x)=0$ を求める問題に置き換える。
計算
おさらい
基本のニュートンラプソン法の計算では、「連立方程式」をたてて解くのであった。
連立方程式は、現在地$x_k$と、その時の傾き$f'(x)$を計算して接線の式を求めるのであった。
\begin{align}
\left\{
\begin{array}{ll}
f(x_k) &= ax_k +b \\
a &= f'(x_k)
\end{array}
\right.
\end{align}
$y=ax+b$の直線を求めたく、aは決定済みでbのみ求めるのであった。
\begin{align}
f(x_k) &= f'(x_k)x_k+b \\
\rightarrow b &= f(x_k) - f'(x_k)x_k
\end{align}
$y=ax+b$の式は、
y = f'(x_k)x + f(x_k) - f'(x_k)x_k
前回は$y=0$との交点となる$x_{k+1}$を求めた。
\begin{align}
0 &= f'(x_k)x_{k+1} + f(x_k) - f'(x_k)x_k \\
f'(x_k)x_{k+1} &= f'(x_k)x_k - f(x_k) \\
\therefore x_{k+1} &= x_k - \frac{f(x_k)}{f'(x_k)}
\end{align}
今回は、微分して0になる点との交点を求める、というイメージ。
目的を「y=0との交点」から「f'(x)=0」に置き換える
問題設定として最小化問題を考える。
これは言い換えると、微分が０の点を求めることに相当する。
$f'(x)=0$ を与える $x$ を求めるためにニュートンラプソン法を適用すると考えると、扱う「傾き」の量は $f''(x)$ となる。
| 対象：$y=0$とする場合 | 対象：$f'(x)=0$とする場合 | |
|---|---|---|
| 連立方程式部 | $f(x_k) = ax_k +b$ $ a = f'(x_k)$ |
$f'(x_k) = ax_k +b$ $ a = f''(x_k)$ |
| 直線$y=ax+b$ の対応 |
$y = f'(x_k)x + f(x_k) - f'(x_k)x_k$ | $y = f''(x_k)x + f'(x_k) - f''(x_k)x_k$ |
| 傾きaで、 y=0を通る |
$0 = f'(x_k)x_{k+1} + f(x_k) - f'(x_k)x_k$ | $0 = f''(x_k)x_{k+1} + f'(x_k) - f''(x_k)x_k$ |
| 求める$x_{k+1}$ | $ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ | $x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}$ |
対応を考えると、ニュートン・ラプソン法は
x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}
として式更新していくことで、最小化問題に適用できる
最小化ステップのイメージ
微分=0を探すために、2階微分$f''(x)$と、$f'(x)=0$との交点を求めた。
これは元の関数を2階微分（2次近似）してこれの傾き=0となる所まで移動していることに対応する。
元の関数をxの位置で2次関数に接するとして2次近似曲線を作り、この2次近似曲線の極小値まで移動することに相当する。
これは、x周りで2階のテーラー展開で近似して、近似2次関数の極小値へ移動することに対応している。
