Newton's Method 설명 (python 구현)

2024.02.02 - [데이터 분석/최적화 알고리즘] - Bisection Method 설명 (python 구현)

 

Newton's Method

방정식 $f(x) = 0$이 되게 하는 $x$를 찾는 알고리즘

 

수식

함수 $f(x)$가 해 $x*$ 근처에서 연속이고 미분가능할 때
- $x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)}, \, f'(x_n) \ne 0$
- $|x_{n+1}-x_{n}| \le \text{tol}$일 때까지 반복, `tol`은 임의의 작은 수

 

장단점

- Bisection Method보다 빠르다.
- 과정 중 $f'(x_n)=0$이 되는 지점이 나오면 탐색이 불가능해짐 → 노이즈를 추가하여 빠져나올 수 있음
- 연속이고 미분 가능하다는 조건이 반드시 필요함
- 초기 기울기가 0에 가까울 때 해로부터 멀리 떨어지게 됨

 

 

구현 소스 코드

def derivative(func, x):
    delta_x = 1e-4
    fx_plus_delta = func(x + delta_x)
    fx_minus_delta = func(x - delta_x)
    
    return (fx_plus_delta - fx_minus_delta) / (2 * delta_x)

class newton:
    
    def __init__(self, xn, func, tol=1e-6):
        self.xn = xn
        self.func = func
        self.tol = tol
        
    def solve(self):
        history = [self.xn]
        
        while True:
            f_prime_xn = derivative(self.func, self.xn)
            
            # 미분값이 0에 매우 가까운 경우, xn에 noise를 더하여 빠져나오기
            if abs(f_prime_xn) <= 1e-1:
                self.xn += self.tol
                continue
                
            xn1 = self.xn - self.func(self.xn) / f_prime_xn
            
            # xn+1과 xn 차이가 tol 이하인 경우
            if abs(xn1 - self.xn) <= self.tol:
                self.solution = xn1
                self.history = history
                return xn1
            
            self.xn = xn1
            history.append(xn1)

 

 

예제

$f(x) = \sin ({ \cos ({ \rm{e}^x }) })$

NM = newton(func=f, xn = 0.2)
NM.solve() # 0.45158270528986616

 

$g(x) = x^3 - x$

NM = newton(func=g, xn = 1/math.sqrt(3))
NM.solve() # 1

len(NM.history) # 10

 

 

미분값에 노이즈를 추가하지 않았을 때

len(NM2.history) # 49

 

노이즈가 있을 때 10번 만에 찾은 답을 없을 떄는 49번 만에 찾았다.

 

 

전체 소스 코드 → github