False Position Method 설명 (python 구현)

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

 

False Position Method (Regula Falsi)

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

 

 

수식

1. 구간 $[a, b]$를 잡는다.
    - $f(a) \times f(b) < 0$. 즉, $f(a)$와 $f(b)$는 서로 다른 부호
2. 점 $(a, f(a))$와 점 $(b, f(b))$를 잇는 직선과 $x$축이 교차하는 점을 $c$로 한다.
    - 만약 $f(a)$와 $f(c)$가 서로 다른 부호라면 $b=c$, 아니면 $a=c$
3. $|f(c)| < \text{tol}$이 될 때까지 반복, `tol`은 허용오차

 

 

장단점

- 미분이 필요없기 때문에 미분 불가능한 함수에도 적용할 수 있다.
- 일반적으로 Bisection보다 빠르다.
- Bisection처럼 첫 두 지점의 함수값의 부호가 달라야 한다.

 

 

구현 소스 코드

class falsi:
    
    def __init__(self, a, b, func, tol=1e-6):
        """
        a, b: 최초 설정 구간
            f(a)*f(b) < 0, a < b
        func: 해를 찾을 함수
        """
        assert (func(a) * func(b) < 0) and (a < b)
        
        self.a = a
        self.b = b
        self.func = func
        self.tol = tol
           
        
    def solve(self):
        a_history = [self.a]
        b_history = [self.b]
        
        while True:
            c = (self.a * self.func(self.b) - self.b * self.func(self.a) ) / (self.func(self.b) - self.func(self.a))
            # 허용범위 이내일 때
            if abs(self.func(c)) <= self.tol:
                self.solution = c
                self.history = [(a, b) for (a, b) in zip(a_history, b_history)]
                return c
            
            # f(a)와 f(c)가 서로 다른 부호인 경우
            elif self.func(self.a) * self.func(c) < 0:
                self.b = c
                
            # f(a)와 f(c)가 서로 같은 부호인 경우
            else:
                self.a = c
            
            
            a_history.append(self.a)
            b_history.append(self.b)

 

 

 

예제

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

RF = falsi(a=-1, b=1.5, func=f)
RF.solve() # 0.45158270246950966

f(RF.solution) # 4.4295596692314075e-09

 

$g(x) = \sinh (\cosh (x) - 2) - 1$

RF = bisection(a=0, b=2, func=g)
RF.solve() # 1.719843033910307

g(RF.solution) # -6.824534327654064e-07

 

전체 소스 코드 → github