양분법
양분법 (二分法, Bisection method)은 수학, 특히 수치해석학에서 방정식의 해를 구하는 근사적인 방법 중 하나이다. 특정 구간 내에서 연속 함수 f의 부호가 바뀌는 것을 이용하여 해를 찾는 방식으로, 폐구간의 중간점을 계산하고, 그 중간점에서의 함수 값의 부호에 따라 해가 존재할 가능성이 있는 구간을 절반으로 줄여나가는 과정을 반복한다. 이러한 과정을 통해 해에 점진적으로 수렴하는 근삿값을 얻을 수 있다.
원리
양분법은 중간값 정리(Intermediate Value Theorem)에 기반한다. 중간값 정리는 폐구간 [a, b]에서 연속인 함수 f에 대해 *f(a)*와 *f(b)*의 부호가 서로 다르다면, f(c) = 0을 만족하는 c가 구간 (a, b) 안에 적어도 하나 존재한다는 정리이다.
양분법은 다음과 같은 단계를 거친다:
- 초기 구간 [a, b]를 설정한다. 이때, *f(a)*와 *f(b)*의 부호가 달라야 한다.
- 구간 [a, b]의 중간점 c = (a + b) / 2를 계산한다.
- *f(c)*를 계산한다.
- f(c) = 0이면 c는 해이다. 알고리즘을 종료한다.
- *f(c)*의 부호가 *f(a)*와 같다면, 새로운 구간을 [c, b]로 설정한다.
- *f(c)*의 부호가 *f(b)*와 같다면, 새로운 구간을 [a, c]로 설정한다.
- 2단계부터 반복한다.
장점 및 단점
장점:
- 구현이 간단하고 이해하기 쉽다.
- 함수가 연속이고 초기 구간이 적절하게 설정되었다면 해로 반드시 수렴한다.
- 수렴 속도가 예측 가능하며, 각 반복마다 구간의 크기가 절반으로 줄어든다.
단점:
- 수렴 속도가 다른 방법에 비해 느리다.
- 중근이나 짝수 중복도를 갖는 근을 찾지 못할 수 있다.
- 함수의 도함수를 이용하지 않으므로, 함수의 특성을 활용한 다른 방법에 비해 효율성이 떨어진다.
- 초기 구간을 잘못 설정하면 해를 찾지 못할 수 있다.
활용
양분법은 비교적 단순한 알고리즘이지만, 안정적인 수렴성을 바탕으로 다양한 분야에서 활용된다. 예를 들어, 방정식의 근을 찾는 기본적인 방법으로 사용될 뿐만 아니라, 다른 수치해석 알고리즘의 초기값을 구하는 데에도 활용될 수 있다. 또한, 컴퓨터 과학 분야에서 탐색 알고리즘의 기본 원리로 사용되기도 한다.
관련 항목
- 뉴턴-랩슨 방법 (Newton-Raphson method)
- 할선법 (Secant method)
- 중간값 정리 (Intermediate Value Theorem)
- 수치해석학 (Numerical analysis)