Root finding algorithme - Newton's method 설명, 코드 구현

이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.

Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.

Newton's method 가 잘 설명되어 있는 영상입니다. 알고리즘 자체의 방법론과 Rate of convergence(이하 수렴률) 에 대한 설명은 영상에 충분히 시각화되어 추가적인 설명이 필요 없다고 생각됩니다.

여기서는 Newton's method 의 장점과 단점을 생각해보려 합니다.

장점

1. 이전 글에서 다뤘던 Bisection method 보다 (일반적으로) 수렴률이 높기 때문에, (일반적으로) 탐색속도가 더 빠릅니다.(모든 경우에 그런 것은 아닙니다.)

단점

1. 낮은 확률이겠지만 계산 과정중 f'(x) = 0 이 되는 지점을 탐색하게 되면 접선이 x 축에 수평하게 되며 더 이상의 탐색이 불가능하게 됩니다.

위 그래프처럼 탐색 지점의 접선이 x 축과 평행할 경우 다음 탐색 지점이 계산되지 않기 때문입니다.

2. 함수에 미분 불가능한 정의역이 있다면 해당 구간에는 적용할 수 없습니다.

3. 초기 기울기가 0에 가까울때 해로부터 멀리 떨어지게 됩니다.

코드 구현

핑계일 뿐이지만, 제대로된 코딩 수업을 들어본 적이 없기 때문에 코드가 개똥 같을 수 있습니다.

코드는 python 으로 작성되었습니다. myEquation1() 함수에는 Newton's method 를 적용하고자 하는 함수를 myEquation2() 함수에는 도함수를 넣어서 사용하시면 됩니다.

import math
import numpy as np

def myEquation1(x):
    return -1 * (x**3)

def myEquation2(x):
    return -3 * (x**2)

def newton(a, iteration, my_func, my_func2):
    iteration = iteration + 1
    if my_func(a) < 0.0000001 and my_func(a) > (-1 * 0.0000001):
        print("case close")
        print("iteration: ", str(iteration).ljust(3), "  x: ", str(a).ljust(25))
    elif my_func(a) != 0:
        a_1 = a - (my_func(a)/my_func2(a))
        print("iteration: ", str(iteration).ljust(3), "  x1: ", str(a).ljust(25), "  x2: ", str(a_1).ljust(25))
        newton(a_1, iteration, my_func, my_func2)

newton(-100, 0, myEquation1, myEquation2)

Newton's method 설명 Newton's method 뜻 Newton's method 구현