ニュートン法
Overview
ニュートン法は与えられた方程式の解を数値的に求める手法です。最適化の問題でも導関数が0になる点を求めることはつまり最適値を求めることになるので、ニュートン法が利用できることもあります。
Theory
$ f(x) = 0の解を求めたいとします。ニュートン法では、初期値$ x_0から、逐次解に近づけていきます。$ y = f(x)の$ x = x_kにおける接線と$ x軸との交点を$ x_{k+1}とし、$ x_kと$ x_{k+1}との誤差が十分に小さくなったら終了とします。
https://gyazo.com/b18e256733d5ee74ac85f50e17cf7867
ここで、$ y = f(x)の$ x = x_kにおける接線の傾きは$ f'(x_k)なので、ここでの接線の方程式は次で表されます。
$ y = f'(x_k)(x-x_k)+f(x_k)
これと$ x軸の交点が$ x = x_{k+1}となります。$ x=x_{k+1}、$ y = 0とおくと次の式が得られます。
$ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}
次にこの方程式の解を求めてみます。
Coding
code: Python
import numpy as np
import matplotlib.pyplot as plt
def newton1dim(f, df, x0, eps=1e-10, max_iter=1000):
"""
f: 最適化したい関数
df: 導関数
eps: 収束誤差
max_iter: 最大繰り返し回数（無限ループする可能性があるため設定）
"""
x = x0
iter = 0
while True:
x_new = x - f(x)/df(x)
if abs(x-x_new) < eps:
break
x = x_new
iter += 1
if iter == max_iter:
break
return x_new
def f(x):
return x**3-5*x+1
def df(x):
return 3*x**2-5
x_a = newton1dim(f, df, 2)
x_b = newton1dim(f, df, 0)
x_c = newton1dim(f, df, -3)
print(x_a)
print(x_b)
print(x_c)
x = np.linspace(-3, 3, 300)
plt.plot(x, f(x))
plt.hlines(0, -3, 3, linestyles="dashed")
plt.scatter(x_a, f(x_a))
plt.scatter(x_b, f(x_b))
plt.scatter(x_c, f(x_c))
plt.show()
--------------------------------------------------------------------------
2.1284190638445777
0.20163967572340463
-2.330058739567982
--------------------------------------------------------------------------
https://gyazo.com/0a9562024a1687b293fc8fed01c13217
このように、この関数では、解が3つあることがわかり、初期値によってその極値は変わります。