Secant Method 설명 (python 구현)

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

 

Secant Method

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

 

수식

- Newton's Method와 거의 동일하지만 함수 $f(x)$가 미분 불가능해도 쓸 수 있다.
- $x_{n+1} = x_n - \frac{f(x_n)}{\left[ \frac{f(x_n)-f(x_{n-1})}{x_n - x_{n-1}} \right]}$

 

 

장단점

- 미분 불가능해도 가능
- Bisection에 비해 빨리 찾는다.
- 두 지점의 함수값이 같으면 더이상 탐색이 불가능해짐

 

구현 소스 코드

class secant:
    
    def __init__(self, xn_1, xn, func, tol=1e-6):
        """
        xn_1, xn: 최초 두 점
        func: 해를 찾을 함수
        """
        self.xn_1 = xn_1
        self.xn = xn
        self.func = func
        self.tol = tol
        
    def solve(self):
        history = [(self.xn_1, self.xn)]
        
        while True:
            fxn_1 = self.func(self.xn_1)
            fxn = self.func(self.xn)
            
            # 두 함수 값이 거의 같은 경우 노이즈 추가
            if abs(fxn_1 - fxn) <= 1e-3:
                self.xn += 1e-2
                continue
                
            xn1 = self.xn - self.func(self.xn) / ((fxn - fxn_1) / (self.xn - self.xn_1))
            
            # xn+1과 xn 차이가 tol 이하인 경우
            if abs(xn1 - self.xn) <= self.tol:
                self.solution = xn1
                self.history = history
                return xn1
            
            self.xn_1 = self.xn
            self.xn = xn1
            
            history.append((self.xn_1, self.xn))

 

예제

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

SM = secant(xn_1=-0.375, xn=0, func=f)
SM.solve() # 0.4515827022152965

f(SM.solution) # 4.8288766931228065e-09

 

전체 소스 코드 → github