해를 향하여 #2: Newton-Raphson Method

이번글은

2022.06.12 - [수학의 재미/아름다운 이론] - 해를 향하여 #1 : Bisection Method

해를 향하여 #1 : Bisection Method

에서 이어집니다. 함수 $f(x)$가 있을 때, 

$$f(x)=0$$

의 해를 구하는 방법입니다.

해를 찾고자하는 의지가 돋보이는 T-shirt

 

저번 글에서는 bisection method를 설명하였습니다. 이번 글에서는 접선의 방정식을 구하는 개념이 등장합니다. 따라서 함수 $f(x)$가 미분 가능하다는 조건이 필요합니다.

 

위와 같은 함수의 개형이 있다고 합시다. 오렌지색의 해를 구하는 것이 우리의 목적입니다. 해를 구하는 과정은 다음과 같습니다.

1. 초기값 $x_0$ 한 점을 아무 데나 찍어봅니다.

그러면 함수 위의 점  $(x_0, f(x_0))$ 이 있을 것입니다.

2. 함수위의 점 $(x_0, f(x_0))$ 에서 접선을 그려 이것의 $x$절편을 $x_1$이라 합니다.

3. 다시 함수위의 점 $(x_1, f(x_1))$에서 접선을 그려 접선의 $x$절편을 $x_2$ 라 합니다.

$x_2$ 가 한결 오렌지 해에 더 가까워지네요

4. 이 과정을 반복합니다. 언제까지 하냐면, 해를 구하는 사람의 tolerance를 허용할 때까지 합니다.

 

bisection method와 마찬가지로 아주 정확한 해를 구할 수는 없습니다. 다만 이 정도면 충분하다 싶은 tolerance가 있죠.

위 그림처럼 $x_0, x_1, x_2, \cdots$ 이렇게 $x$를 구해 나가면서

$$|f(x_n)| <\rm{ tolerance }$$

가 되는 $n$에서 멈추면 되는 것입니다.

 

---

점화식으로 표현하여 볼까요? $x_n$에서 $x_{n+1}$를 얻어내는 과정입니다.

점 $(x_n, f(x_n))$에서의 접선의 방정식은

$$y - f(x_n) = f'(x_n )(x-x_n)$$

입니다. $x$절편을 구하기 위해 $y=0$을 대입하면 

$$x= x_n - \frac{f(x_n)}{f'(x_n)}$$

입니다. 이것이 바로 $x_{n+1}$ 인 것이죠. 따라서 정리하면

$$x_{n+1}= x_n - \frac{f(x_n)}{f'(x_n)}~,~ x_0 : \rm{ initial~ value }\tag{1}$$

 

python code를 보겠습니다. bisection code처럼 멋진 code를 발견하여 그대로 첨부하겠습니다.

import math
import numpy as np
import matplotlib.pyplot as plt

def my_newton(f, df, x0, tol):
    # output is an estimation of the root of f
    # using the Newton Raphson method
    # recursive implementation
    if abs(f(x0)) < tol:
        return x0
    else:
        return my_newton(f, df, x0 - f(x0)/df(x0), tol)

if __name__ == '__main__':
 
 	f = lambda x: x ** 2 - 2
    f_prime = lambda x: 2 * x
    estimate = my_newton(f, f_prime, 1.5, 1e-6)
    
    print("estimate =", estimate)
    print("sqrt(2) =", np.sqrt(2))

 

달리 설명할 부분은 없고

        return my_newton(f, df, x0 - f(x0)/df(x0), tol)

에 바로 점화식(1)이 쓰인 것입니다.

 

위 예제는 $f(x)=x^2-2=0$ 의 해를 구한 것이므로 당연히 해는 $\sqrt{2}$입니다. 이제 결과를 볼까요?

 

estimate = 1.4142135623746899
sqrt(2) = 1.4142135623730951

Process finished with exit code 0

estimate가 Newton-Raphson 방법으로 구한 것이고, sqrt(2)는 실제값입니다. 엄청 정확하죠?

 

 지금까지 bisection method와 Newton-Raphson method를 알아봤습니다. 해 찾는 기법들은

• 정규분포 난수를 만들거나
• 옵션에서 내재변동성(implied volatility)을 추출하거나

등에 아주 많이 쓰이는 방법입니다. 차차 알아보기로 해요.