Bisection Method 설명 (python 구현)

Bisection Method

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

 

 

수식

1. 구간 $[a, b]$를 잡는다.

    - $f(a) \times f(b) < 0$. 즉, $f(a)$와 $f(b)$는 서로 다른 부호

2. 양 끝점에 대해 중점 $c=\frac{a+b}{2}$를 계산한다.
    - 만약 $f(a)$와 $f(c)$가 서로 다른 부호라면 $b=c$, 아니면 $a=c$
3. $|f(c)| < \text{tol}$이 될 때까지 반복, `tol`은 허용오차

 

 

장단점

- 초기 두 점 $a$와 $b$에 대해 함수값의 부호가 서로 다르면 반드시 해를 찾을 수 있다. (단, $f$는 $[a, b]$에서 연속)
- 서로 다른 부호를 위해 두 지점의 간격을 넓히면 계산이 오래 걸린다.
- 상대적으로 다른 방법에 비해 계산 속도가 느리다.

 

 

구현 소스 코드

class bisection:
    
    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.b) / 2
            # 허용범위 이내일 때
            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 }) })$

BM = bisection(a=-1, b=1.5, func=f)
BM.solve() # 0.4515829086303711

f(BM.solution) # -3.194071968524581e-07

 

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

BM = bisection(a=0, b=2, func=g)
BM.solve() # 1.7198433876037598

g(BM.solution) # 6.69221502658246e-07

 

전체 소스 코드 → github

 

 

 

참조

- https://youtu.be/MlP_W-obuNg