[수학] 이분법이란?

이분법(Bisection)

이분법은 중간값 정리에서 시작한다.

중간값 정리

구간 에서 연속인 가  구간  사이에 적어도 하나 이상의 실근이 존재한다.

중간값 정리를 그림으로 나타내면 다음과 같다.

그림1. 중간값 정리

위와 같은 함수에서 x1과 x2의 값을 곱하면 음수이므로(즉, 두 함수의 부호가 서로 다르므로) 두 구간 사이에 근이 있다는 것을 알 수 있다. 다시 구간을 mid와 x2로 정의하고 값을 비교하면 결과를 구할 수 있으며, 두 구간의 차이가 0.00001 보다 작으면 근을 찾은 것으로 간주하면 된다. 다음과 같은 루프안에서 코드를 수행하면 된다.

이분법 또한 잘 알려진 분할 정복 기법의 예라는 것을 기억하기 바란다.이분법에서는 중간값과 x1, x2 중에 어느 구간에 근이 존재하는지 결정해야 한다. 그러나 이분법은 근의 개수가 짝수, 중근, 발산의 경우에는 올바른 근을 찾아내지 못한다. 이분법은 이미 함수의 형태를 알고, 근이 존재하는 구간을 구한 경우에 쓸 수 있는 방법이지만, 근에 수렴하는 속도 즉, 근을 찾아내는 시간이 오래걸리는 방법이므로 다른 알고리즘을 사용한다.

출처: http://jongkok4.net/entry/Advanced-C-11-방정식-미적분법-그리고-delegate