ニュートン法について
概要
- 微分可能な関数を対象に最適化する
- ある値を求めるときに、計算時間が
O(k)で済む- kは微分関数
導出
ある関数\(f(x)\)があるときに、テーラー展開すると以下のようになる
\[f(x) = f(x_0) + f'(x_0)(x - x_0) + O((x-x_0)^2)\]最後の項を外して整理すると
\[x = x_0 - \frac{f(x_0)}{f'(x_0)}\]\(O((x-x_0)^2)\)が正の値を持つから(行列では半正定値)
\[x_1 = x_0 - \frac{f(x)}{f'(x)}\]任意の値のルート(SQRT)を高速に求める
\(a = 3\) があるときに、$\sqrt{a}$ を求める
\(x = \sqrt{a}\) と置くことができ、変形すると \(f(x) = x^2 - a\)
ニュートン法で記すと
\[x_{n+1} = x_{n} + \frac{f(x_n)}{f'(x_n)}\]整理すると
\[x_{n+1} = x_{n} + \frac{x_{n}^2-a}{2 x_{n}}\]20回、最適化するとおおよそ正しい値が得られる
import random
a = 3
x_n = random.random()
for _ in range(20):
x_np = x_n - (x_n ** 2 - a) / (2 * x_n)
x_n = x_np
print(x_n) # 1.7320508075688772
import math
print(math.sqrt(a)) # 1.7320508075688772