뉴튼랩슨 Newton-Raphson

함수의 미분을 해석적으로 계산해야 함
하나의 초깃값만 설정, 발산할 수 있음(기울기가 '0'이 되기 때문에)
근의 수렴 속도가 비교적 빠름(초깃값 선정이 중요)

1. x0부터 시작해서 x0의 기울기를 이용한 x절편이 x1이 된다
2. x1에서의 기울기→ 절편 → x2가 된다 → 반복
3. 일정 수준보다 작아질 때까지 반복(상대오차)

구간을 정하는 것이 아닌 초기값을 예측하여 사용
초기값을 a라 했을 때 f(a)=0이면 방정식의 근이다
초기값을 𝑥(0)으로 가정. 여기서 (0)는 0번째 𝑥 의 값
만일 $$f(x^{(0)}) \ne 0$$이라면 새로운 예측값(근삿값) $$x^{(1)} = x^{(0)}+h$$을 대입
만일 $$f(x^{(1)}) = 0$$이라면 $$x^{(1)}$$이 방정식의 근임

---

테일러급수

Taylor series
도함수들의 한 점에서의 값으로 계산된 항의 무한합으로 해석 함수를 나타내는 방법

$f(x^{(1)}) = f(x^{(0)}+h)$
$$=f(x^{(0)}) +hf'(x^{(0)}) + {1\over2!}h^2f''(x^{(0)})+ {1\over3!}h^3f'''(x^{(0)})+\cdots = 0$$
$$f(x^{(0)}) + hf'(x^{(0)}) = 0$$

---

이를 일반화하면

$$x^{(k+1)} = x^{(k)} - {{f(x^{(k)})}\over{f'(x^{(k)})}}$$
여기서 $k=0,1,2,\cdots$이며 다음의 오차 조건을 만족할 때까지 반복하는 과정을 거침
$\varepsilon$은 목표하는 오차값
$$ |{{x^{(k+1)} - x^{(k)}}\over{x^{(k+1)}}}| \le \varepsilon $$

---

from scipy import optimize  
root1 = optimize.newton(f, 4.0)

import numpy as np
import matplotlib.pyplot as plt

def f(x):
    return -x**2 + 6.0 * x - 5.0

def df(x):
    return -2.0 * x + 6.0

n = 7
x = np.zeros(n) 
err = np.zeros(n)
err[0] = 0

x[0] = -2.0 # 4

from scipy import optimize
from numpy import log as ln

# root1 = optimize.newton(f, x[0], full_output = True)
root1 = optimize.newton(f,x[0])
print(root1)

root2 = optimize.newton(f, x[0], fprime = df)
print(root2)

for k in range(n-1):
    x[k+1] = x[k] - f(x[k])/df(x[k])
    err[k+1] = np.abs((x[k+1] - x[k])/x[k+1]) * 100.0

print("%5s %9s %12s"%('k', 'x', 'err'))
for k in range(n):
    print("%5d %9.4f, %10.8s"%(k+1, x[k], err[k]))

itr = np.arange(n)

plt.plot(itr, x)
plt.xlabel('Iterations')
plt.ylabel('x')

plt.plot(itr[:-1], err[1:])
plt.xlabel('Iterations')
plt.ylabel('epsilon')

xi = np.linspace(-4, 4, 50)
y = f(xi)
plt.plot(xi, y)
plt.xlabel('x')
plt.ylabel('f(x)')
plt.grid()
plt.show()

---

방정식 $f(x)=1+3\ln{x}-e^{-x} $에 대하여 Newton-Raphson 방법을 적용하여 근을 찾기

def f(x):
    return 1+ 3*np.log1p(x) - np.exp(-x)

root1 = optimize.newton(f, 0, full_output = True)
print(root1)

(0.0,       converged: True
           flag: 'converged'
 function_calls: 3
     iterations: 2
           root: 0.0)