해를 향하여 #1 : Bisection Method

해가 요기잉네~?

이번 글에서는 해 찾기 방법을 소개할까 합니다.  그 중 널리 쓰이는 방법이 바로 Bisection Method (이분법) 방법입니다.

이어지는 내용을 보시면 알겠지만, 야구의 rundown과 유사합니다.

 

좁혀오는 포위망.. 아 곧 만날것 같아..

 

Bisection Method 란 이름 그대로 해가 있을 법한 구간을 계속 반으로 나누어서 해가 있는 영역을 찾아내는 것입니다.

계속 반으로 나누다 보니 해가 있을 법한 영역을 무지 작아지게 되고, 그렇게 해를 가둬가면서(야구에서는 rundown) 찾아내는 방법이지요. 구체적인 원리를 보실까요?

 

1. 해가 있을법한 곳을 가늠하여 영역을  설정한다.

 

오렌지 색깔의 공이 파란색 곡선(함수 $f(x)$라 합시다.)이 직선과 만나는 점($f(x)=0$의 해)입니다. 이 점을 구해보는 것이 목적인데, 일단 이 점이 사이에 있을만한! $a_1$과 $b_1$을 설정합니다.

이 점이 사이에 있을 만한? 이라는 뜻이 뭘까요? 바로 $a_1$의 함숫값과 $b_1$의 함숫값이 부호가 다르다는 것입니다. 0을 가운데 두고 (+)인 부분과 (-)인 부분에서 협공해오는 것입니다.

이것이 초기간격입니다.

 

2. $[a_1, b_1]$을 반으로 나눕니다. 그래서 해가 있을법한 절반의 영역을 찾아냅니다.

$a_1$과 $b_1$을 반으로 나누면(평균이죠) 

$$ \frac{a_1+b_1}2$$

라는 점인데요, 얘의 부호가 $a_1$과 $b_1$중 어느 것과 똑같은지를 살피는 것입니다. 그림상에서는 $a_1$부호가 같지요. 아직 $b_1$과는 부호가 다른 상태입니다.

따라서 해를 찾는데 $[a_1, a_2]$구간을 쓸모가 없습니다. 이 쪽은 버려버리죠.  이 중간값을 다시 $a_2$라는 이름을 달아서 구간 $[a_2, b_1]$을 만듭니다. 초기 간격보다 길이가 절반이 줄었죠? 이게 해 찾기의 첫 번째 단계입니다.

 

3. $[a_2,b_1]$의 간격을 무작정 또 반으로 나누고, 해가 있을 법한 영역을 찾습니다.

$a_2 ,b_1$의 절반은 $\frac{a_2+b1}2$입니다. 이점은 그림상으로는 $b_1$과 부호가 같죠. 따라서 이점과 $b_1$사이의 구간을 해 찾는데, 하등  쓸모가 었습니다. 버려버리죠.  이제 이 중간점에 $b_2$라는 이름을 달고 $[a_2,b_2]$ 구간을 설정합니다. 기존 $[a_1,b_1]$보다 길이가 절반이 줄었죠.

4. 계속 반복합니다. 해 찾는 사람이 만족할 때까지 계속한다.

세번째 간격 찾기

네 번째 간격찾기

세 번째, 네 번째 간격을 찾는 그림입니다. 계속 절반씩 줄어들며 그 사에는 항상 오렌지색 해가 있지요. 해를 가두는 구간이 절반씩 줄어들기 때문에 그 구간은 굉장히 작아집니다. 실제로 초기 간격을 $l$이라 하면, $n$ 번 bisection을 했을 때 구간의 길이는

$$ \frac{l}{2^n}$$

이 되고 이는 $n$이 커지면 급속도로 $0$으로 수렴하게 됩니다.

 

하지만, bisection으로 찾는다 한들 유한 번의 과정으로 정확한 해를 찾아낼 순 없습니다. 예컨대 

$$x^-2 =0$$ 

의 근은 잘 알려진 대로 $x=\sqrt{2}$이지만, 이 값은 무리수로 소수점 아래로 끝없이 수가 이어집니다.  따라서 이것을 아주 딱 들어맞게 찾는 방법은 없고요, 대신 tolerance라는 방법을 씁니다.

사용자가 tolerance를 $10^{-8}$ 이런 식으로 설정을 합니다. bisection을 하면 할수록 $a_n$과 $b_n$은 어마어마하게 달라붙어 있는 상황이 되고, 

$$ \frac{a_n+b_n}2$$

을 해라고 생각할 수 있습니다.

따라서

$$ \Big| f \left( \frac{a_n+b_b}2 \right) \Big| <\rm{tolerance} $$

일 때 과정을 종료하면 될 것 같습니다.

 

python code를 보실까요?  제가 짠 코드도 있었지만, 인터넷을 검색하다 보니 멋진 code가 나와서 첨부합니다. 해당 code는 다음의 책에 실려있다고 합니다.

갑자기 흥분되는 책이네요.

 

import math
import numpy as np
import matplotlib.pyplot as plt

def my_bisection(f, a, b, tol):
    # approximates a root, R, of f bounded
    # by a and b to within tolerance
    # | f(m) | < tol with m the midpoint
    # between a and b Recursive implementation

    # check if a and b bound a root
    if np.sign(f(a)) == np.sign(f(b)):
        raise Exception(
            "The scalars a and b do not bound a root")

    # get midpoint
    m = (a + b) / 2

    if np.abs(f(m)) < tol:
        # stopping condition, report m as root
        return m
    elif np.sign(f(a)) == np.sign(f(m)):
        # case where m is an improvement on a.
        # Make recursive call with a = m
        return my_bisection(f, m, b, tol)
    elif np.sign(f(b)) == np.sign(f(m)):
        # case where m is an improvement on b.
        # Make recursive call with b = m
        return my_bisection(f, a, m, tol)
if __name__ == '__main__':
    f = lambda x: x ** 2 - 2

    r1 = my_bisection(f, 0, 2, 0.001)
    print("r1 =", r1)

달리 설명할 부분은 없고

    # check if a and b bound a root
    if np.sign(f(a)) == np.sign(f(b)):
        raise Exception(
            "The scalars a and b do not bound a root")

이 부분만 짚고 넘어가자면, 해를 찾는데 함수의 부호가 다른 데서 시작해야 한다고 했었죠? 그래야 함숫값이 0이라는 곳에 해를 가둬서 잡을 수 있다고.. 그것을 뜻하는 것입니다. 만일 함수값이 같다면 error을 내뱉습니다.

 

 

이것이 어찌 보면 초기값을 잘 설정해야만 하는.. bisection method의 한계점일 수도 있겠습니다.