이분법 (수치해석)

이분법(Bisection Method, 이등분법)은 부호가 서로 다른 두 점 사이에 근이 있다는 중간값 정리를 이용해, 근이 든 구간을 반씩 줄여 가며 비선형 방정식 f(x) = 0 의 근을 찾는 수치해법이다.

원리

f 가 구간 [a, b] 에서 연속이고 f(a)·f(b) < 0 이면, 중간값 정리에 따라 그 사이에 근이 적어도 하나 있다. 중점 m = (a + b) / 2 에서 f(m) 을 계산해 f(a) 와 부호가 같으면 근은 [m, b] 에, 다르면 [a, m] 에 있다. 이렇게 구간을 계속 반으로 나누면 근을 가둔 구간이 0 에 가까워진다.

절차

f(a)·f(b) < 0 인 구간 [a, b] 를 고른다
m = (a + b) / 2 를 계산한다
f(m) = 0 이면 m 이 근이다
f(a)·f(m) < 0 이면 b ← m, 아니면 a ← m
(b - a) / 2 가 허용 오차 ε 보다 작아질 때까지 2~4 를 되풀이한다

특징

반드시 수렴한다. 조건만 맞으면 발산하지 않는 가장 안전한 방법이다
수렴이 느리다(1차 수렴). 반복마다 오차 구간이 정확히 절반이 되므로 n 번 반복 뒤 오차는 (b - a) / 2ⁿ 이하다
필요한 반복 횟수를 미리 계산할 수 있다: n ≥ log₂((b - a) / ε)
도함수가 필요 없고 부호만 보면 된다
부호가 바뀌지 않는 근(중근, 예: x² = 0)은 찾지 못하고, 구간 안의 근이 여럿이면 그중 하나만 찾는다

뉴턴-랩슨 방법과 비교

뉴턴-랩슨 방법은 도함수로 접선을 그어 근에 다가가므로 근 근처에서 2차 수렴으로 훨씬 빠르지만, 출발값이 나쁘거나 f'(x) 가 0 에 가까우면 발산할 수 있다. 이분법은 느리지만 수렴이 보장된다. 두 방법의 비교와 x² - 4 = 0 계산 예는 비선형 방정식 문서에 있다.

같이 보기