이분법

1. 개요

이분법 Bisection Method
푸는 것	연속함수의 스칼라 방정식 f(x) = 0
필요한 것	부호가 바뀌는 구간 [a, b], 반복당 함수 평가 1회
수렴	1차, 반복마다 구간 길이 1/2 (평가 1회 = 1비트)
보장	구간 안의 근(또는 부호 변화점)으로 반드시 수렴
후손	가위치법 · 브렌트 방법 · ITP 방법

느리다고 무시하지 마라. 이 바닥에서 배신하지 않는 유일한 놈이다.

이분법(bisection method)은 연속함수 $f$ 가 구간 양 끝에서 부호가 다를 때, 구간의 중점에서 부호를 보고 근이 있는 쪽 절반만 남기는 일을 반복해 근을 가두어 가는 방법이다. 근거는 중간값 정리 하나뿐이고, 도함수도 초기 추측도 필요 없다. 반복 한 번에 구간이 정확히 절반이 되므로 몇 번 돌려야 끝나는지가 시작 전에 정해진다.

수렴 차수는 1이고 수렴률은 1/2로, 뉴턴-랩슨법·할선법에 비하면 거북이다. 그런데도 실무 근 찾기 루틴 거의 전부가 이분법을 안전망으로 품고 있다. 빠른 방법이 헛발질할 때 돌아갈 곳이 있어야 하기 때문이다. 이 문서는 알고리즘 자체보다, 그 “보장”이 정확히 무엇을 보장하고 무엇을 보장하지 않는지, 부동소수점에서 어떻게 끝내야 하는지를 판다.

2. 알고리즘과 반복 횟수

$f(a)f(b)<0$ 인 구간에서 시작한다.

1. 중점 $m = a + (b-a)/2$ 에서 $f(m)$ 을 계산한다.
2. $f(m)$ 과 $f(a)$ 의 부호가 같으면 $a \leftarrow m$, 아니면 $b \leftarrow m$.
3. 구간 폭이 허용오차보다 작아질 때까지 반복한다.

$k$ 번 반복 뒤 구간 폭은 $(b-a)/2^k$ 이고, 중점을 답으로 내면 오차는 그 절반 이하다. 따라서 폭을 $\varepsilon$ 이하로 만드는 데 필요한 반복 수는

$$k = \left\lceil \log_2 \frac{b-a}{\varepsilon} \right\rceil$$

로 함수 $f$ 의 모양과 무관하다. 함수가 얼마나 구불구불하든, 근 근처에서 얼마나 평평하든 같다. 이게 이분법의 가장 큰 장점이자, 함수가 아무리 착해도 그 이상 빨라지지 않는다는 단점이다.

2.1. 검산 — 월리스의 삼차식

뉴턴이 예제로 썼던 $f(x)=x^3-2x-5$ (근 $r = 2.0945514815423265\ldots$) 를 $[2,3]$ 에서 폭 $10^{-12}$ 까지 줄여 봤다. 공식은 $\lceil\log_2 10^{12}\rceil = 40$ 회를 예언하고, 실제로 40회 반복·함수 평가 41회(시작점 $f(a)$ 포함)로 끝났다. 같은 구간을 브렌트 방법은 평가 8회로 끝낸다 — 이 차이가 이분법을 혼자 쓰지 않는 이유다.

3. 보장의 정확한 내용

이분법이 보장하는 것은 “근으로 수렴”이 아니라 **“부호가 바뀌는 점으로 수렴”**이다. 이 둘이 다른 경우가 있다.

• 극(pole). $f(x) = 1/(x-0.5)$ 를 $[0, 1.3]$ 에서 돌리면 이분법은 신나게 $x=0.5$ 로 수렴한다. 거기서 $f$ 는 0이 아니라 무한대다. 연속성 가정이 깨지면 보장도 깨진다. 끝난 뒤 $|f(m)|$ 이 실제로 작은지 한 번 보는 게 국룰이다.
• 짝수 중복근. $f(x)=(x-1)^2$ 처럼 근에서 부호가 안 바뀌면 애초에 구간을 못 잡는다. 이분법은 이런 근이 존재한다는 사실조차 모른다.
• 여러 근. 구간 안에 근이 3개면 그중 하나로 간다. 어느 것일지는 중점들이 어디에 떨어지느냐에 달렸다. 모든 근이 필요하면 구간을 쪼개 훑거나, 다항식이면 스텀 수열로 근의 개수부터 센다.

그래도 이 보장은 강력하다. 반대로 말하면, 부호가 바뀌는 연속함수라면 잡음이 섞여 있든, 도함수가 없든, 매끄럽지 않든 이분법은 상관하지 않는다. $f$ 의 값이 아니라 부호만 쓰기 때문이다. 부호 정보만 쓰는 방법들 중에서는 최악의 경우 오차 기준으로 이분법이 최적이라는 결과도 알려져 있다.¹

4. 부동소수점에서 끝내기

허용오차를 너무 작게 잡으면 이분법은 “끝나지 않는” 루프가 된다. 근 근처의 두 이웃 부동소수점 사이에는 더 쪼갤 수 있는 수가 없기 때문이다.

• 중점이 끝점과 같아지면 멈춘다. $m=a$ 또는 $m=b$ 가 되는 순간이 정밀도의 바닥이다. 위 삼차식을 이 조건으로 끝까지 돌리면 51회 만에 $[2.0945514815423265,\ 2.094551481542327]$ — 이웃한 두 배정밀도 수 — 에 도착한다. $[2,4)$ 의 수 간격이 $2^{-51}$ 이니 폭 1에서 51번 반으로 접으면 정확히 그렇게 된다.
• 절대·상대 허용오차를 함께. 근이 $10^{8}$ 근처에 있는데 절대 허용오차 $10^{-12}$ 를 요구하면 이룰 수 없다(그 근처 수 간격이 이미 $10^{-8}$ 대다). 실무 라이브러리는 대개 $|b-a| \le \text{xtol} + \text{rtol}\,|m|$ 꼴을 쓴다.
• 곱으로 부호를 판정하지 마라. $f(a)f(m)<0$ 은 두 값이 각각 $10^{-200}$ 이면 곱이 언더플로해 0이 되고 판정이 틀린다. sign(f(a)) != sign(f(m)) 처럼 부호를 직접 비교한다.
• 중점 공식. $(a+b)/2$ 는 $a,b$ 가 둘 다 표현 가능한 최대값 근처면 오버플로한다. $a+(b-a)/2$ 가 흔한 대안이지만 이번엔 부호가 반대인 거대한 두 끝점에서 $b-a$ 가 넘칠 수 있으니, 어느 쪽이든 결과가 $(a,b)$ 안에 있는지 확인하는 편이 안전하다.

재미있는 변종으로, 배정밀도 수를 비트 패턴 순서대로 늘어놓고 그 정수 인덱스를 반으로 자르면 어떤 구간이든 최대 64번이면 이웃한 두 수까지 간다. $[10^{-300}, 10^{300}]$ 처럼 자릿수가 수백 단위로 걸친 구간에서는 산술 중점보다 이쪽이 훨씬 빠르다.²

5. 왜 아직도 쓰이는가

1. 안전망. 브렌트 방법은 할선법·역 이차 보간을 시도하되 구간이 충분히 줄지 않으면 이분법으로 후퇴한다. 가위치법의 일리노이 변형, 2020년의 ITP 방법도 같은 철학 — 평소엔 빠르게, 최악에도 이분법 수준 — 을 각자 방식으로 구현한다.
2. 고유값. 대칭 삼중대각 행렬의 $k$ 번째 고유값은 스텀 수열의 부호 변화 개수로 “이 값 아래 고유값이 몇 개인가”를 세서 이분법으로 찾는다. LAPACK 의 xSTEBZ 가 이 방식이고, 원하는 고유값 몇 개만 골라 구할 수 있다는 게 장점이다.
3. 함수가 블랙박스이고 비쌀 때. $f$ 하나가 시뮬레이션 한 번(예: 사격법에서 상미분방정식 적분 한 번)이면 도함수를 구할 수 없고 잡음도 낀다. 부호만 믿을 수 있다면 이분법이 가장 정직하다.
4. 이산 문제. 정렬된 배열에서의 이진 탐색, 임계 하중·임계 시간 스텝을 “터지나 안 터지나”로 찾는 일은 모두 이분법이다. CFL 한계를 실험적으로 찾을 때 시간 스텝을 반씩 줄여 가는 것도 결국 같은 짓이다.

6. 비슷한 이름, 다른 방법

• 황금분할 탐색법. 근이 아니라 단봉함수의 최솟값을 가둔다. 부호 대신 함수값 비교를 쓰므로 점이 둘 필요하고, 구간이 반복당 0.618배로 준다.
• 구간 해석의 이분. 구간 뉴턴법 등이 “이 상자에 근이 없음을 증명”하지 못하면 상자를 반으로 쪼갠다. 같은 쪼개기지만 목적이 근의 존재·유일성 증명이다.
• 수치 연속법의 분기점 탐지. 경로를 따라가다 행렬식 부호가 바뀌면 그 스텝 안에서 이분법으로 분기점을 좁힌다.

7. 관련 문서

• 할선법 · 뉴턴-랩슨법 · 역 이차 보간 · 브렌트 방법 · 가위치법
• 스텀 수열 · 구간 해석 · 황금분할 탐색법 · 수치 연속법
• 부동소수점 연산 · 사격법 · 중간값 정리

8. Footnotes

1. 시코르스키(Sikorski, 1982)의 논문 제목이 아예 「Bisection is optimal」이다. 제목으로 스포일러하는 논문은 대개 결과가 확실하다는 뜻이다. ↩

2. IEEE 754 양수는 비트 패턴을 정수로 읽어도 순서가 보존되게 설계됐다. 설계자들이 이분법 하는 사람들을 위해 그런 건 아니겠지만, 덕분에 64번이면 무조건 끝난다. ↩