Newton's Method

Newton's Method

모든 방정식이 정확한 해를 가지지는 않습니다. 이러한 경우 근사해(approximate solution)을 계산할 필요가 있습니다. 이러한 근사해를 계산하는 다양한 방법들 중에 가장 많이 사용되는 방법이 뉴턴의 방법입니다. 

위 그림에서 파란선의 경우 x_0에서의 접선, 초록선의 경우는 x_1에서의 접선을 나타냅니다. 이 접선이 x축과 만나는 점을 기준으로 함수f(x)와의 점에서의 접선의 기울기는 f'(x_1)이 됩니다. 함수 f(x)의 해를  x_n이라고 하면 다음과 같이 초기 임의의 점 x_0에서 시작하여 x_n까지의 근사시킬 수 있습니다. 

tangent line at x_0 : y=f(x_0)+f'(x_0)(x-x_0)

x_1: 0=f(x_0)+f'(x_1)(x_1-x_0) → x_1=x_0-\frac{f(x_0)}{f'(x_1)}

tangent line at x_1: y=f(x_1)+f'(x1)(x-x_1)

위 식을 적용하여 x_2는 다음과 같이 계산됩니다. 

0=f(x_1)+f'(x1)(x_2-x_1)→ x_2=x_1-\frac{f(x_1)}{f'(x_2)}

위 과정은 x_n을 계산할 수 있을 때까지 반복할 수 있습니다. 

위 과정을 다음과 같이 일반화 할 수 있습니다. 

x_n이 f(x)=0의 근사해이고 f'(x_n) ≠ 0 이 아니면 다음식이 성립됩ㄴ다. 

$x_{n+1}=x_n -\frac{f(x_n)}{f'(x_n)}

근사해를 계산하기 위해 위의 식을 적용할 경우 위 과정의 반복정도를 결정해야 합니다. 이 식은 근해를 계산하는 것으로서 반복수에 대한 일반적인 기준을 설정할 수는 없지만 각 반복의 결과의 차이가 매우 작을 경우까지 반복 계산을 합니다. 

예) 뉴턴방법을 적용하여 구간 [0, 2] 에서  f(x)=cos(x)-x의 근사해를 계산합니다. 

>>> import numpy as np 
>>> import pandas as pd 
>>> from sympy import *
>>> x=symbols('x')
>>> f=cos(x)-x;f
-x + cos(x)
>>> df=diff(f, x);df

-sin(x) - 1

>>> rng=np.linspace(2, 0, 1000)

>>> re={}

>>> re[0]=2.1-f.subs(x, 2.1)/df.subs(x, 2.1)

def NewtonMethodS(g, dg, rng):
    re={}
    initialx=rng[len(rng)-1]+0.00001
    re[0]=initialx-g.subs(x, initialx)/dg.subs(x, initialx)
    n=1
    for i in rng:
        re[n]=i-f.subs(x, i)/df.subs(x, i)
        if abs(re[n]-re[n-1])<0.000001:
            break
        n=n+1
        return(re[len(re)-1])

>>> NewtonMethodS(f, df, rng)

0.734536168854463