이분법 · Hong-Iron

요약

함수 값의 부호가 다른 두 점 사이에는 연속 함수라면 반드시 근이 있다. 이분법은 가운데 점의 부호를 보고 근이 있는 반쪽만 남기기를 되풀이한다. 구간이 매번 정확히 절반이 되므로 반드시 수렴하고, 몇 번 만에 원하는 정확도가 되는지 미리 안다. 대신 느리고, 함수가 끊어진 곳에서는 근이 아닌 곳으로 갈 수 있으며, 부호가 같은 두 점 사이의 근은 찾지 못한다.

예시로 보기

질량 68.1 kg인 낙하산병이 10초 동안 떨어져 속도 40 m/s가 되려면 항력 계수 \(c\)가 얼마여야 하는가? 식으로 \(c\)를 따로 떼어 낼 수 없어, 다음 \(f(c) = 0\)의 근을 수치로 찾는다(\(g = 9.8\ \mathrm{m/s^2}\)).

\[f(c) = \frac{9.8 \cdot 68.1}{c}\left(1 - e^{-(c/68.1)\cdot10}\right) - 40\]

\(f(12) > 0\), \(f(16) < 0\)이라 \([12, 16]\)에 근이 있다.

반복	\(x_l\)	\(x_u\)	\(x_r\)	\(\lvert\epsilon_a\rvert\) (%)	\(\lvert\epsilon_t\rvert\) (%)
1	12	16	14		5.279
2	14	16	15	6.667	1.487
3	14	15	14.5	3.448	1.896
4	14.5	15	14.75	1.695	0.204
5	14.75	15	14.875	0.840	0.641
6	14.75	14.875	14.8125	0.422	0.219

참값은 14.7802다. 참 오차 \(\epsilon_t\)는 들쭉날쭉하지만 근사 오차 \(\epsilon_a\)는 매번 줄어든다¹.

위는 \(f(c)\)이고, 아래 막대는 회차마다 남은 구간과 그 가운데 점 \(x_r\)(주황 눈금)이다. 구간은 매번 정확히 절반이 되고, 언제나 근(점선)을 품는다. 가운데 점은 근의 양쪽을 오가므로 참 오차가 들쭉날쭉하다².

검증: 표의 모든 값, 20번 뒤 폭 \(4/2^{19}\), 필요한 횟수 공식, 카드 C2, \(1/x\)에서 불연속점으로 감, 부호가 같으면 시작 못 함, 증분 탐색의 간격 — 28_bisection_impl.py

정의

바탕. \(f\)가 \([x_l, x_u]\)에서 연속이고 \(f(x_l)f(x_u) < 0\)이면 그 사이에 근이 적어도 하나 있다(사잇값 정리). 부호가 바뀌지 않으면 근이 없을 수도, 짝수 개 있을 수도 있다. 부호가 바뀌면 근이 하나보다 많을 수도 있다.

입력: \(f(x_l)f(x_u) < 0\)인 두 점, 허용 오차 \(\epsilon_s\)(%). 출력: 근의 근삿값.

부호가 다른 \(x_l\), \(x_u\)를 고른다.
가운데 \(x_r = \frac{x_l + x_u}{2}\)를 근의 추정값으로 둔다.
\(f(x_l)f(x_r) < 0\)이면 근은 \([x_l, x_r]\)에 있어 \(x_u \leftarrow x_r\). \(f(x_l)f(x_r) > 0\)이면 \(x_l \leftarrow x_r\). \(= 0\)이면 \(x_r\)이 근이라 멈춘다.
상대 근사 오차 \(\vert \epsilon_a\vert = \left\vert \frac{x_r^{\text{new}} - x_r^{\text{old}}}{x_r^{\text{new}}}\right\vert \times 100\)을 구한다.
\(\vert \epsilon_a\vert \le \epsilon_s\)이면 멈추고, 아니면 2로 간다. 반복 횟수의 상한도 둔다.

flowchart TD
    A["f의 부호가 다른 xl, xu"] --> B["xr = 가운데 점"]
    B --> C{"f(xl)·f(xr)의 부호"}
    C -->|"0"| Z["xr이 근. 멈춤"]
    C -->|"음수"| D["xu ← xr"]
    C -->|"양수"| E["xl ← xr"]
    D --> F{"상대 오차 εa ≤ εs, 또는 횟수 상한?"}
    E --> F
    F -->|"예"| Y["xr을 답으로. 멈춤"]
    F -->|"아니오"| B

곱의 부호로 남길 반쪽을 고르고, 바뀐 정도가 기준 아래로 떨어질 때까지 고리를 돈다.

\(n\)번 뒤 구간의 폭은 \(\frac{x_u - x_l}{2^n}\)이다. 그래서 폭을 \(\varepsilon\) 이하로 하려면 \(n \ge \log_2\frac{x_u - x_l}{\varepsilon}\)번이면 된다. 폭 4를 \(10^{-6}\)으로 줄이려면 22번이다¹.

시작 구간 찾기(증분 탐색). 작은 간격으로 함수 값을 계산하며 부호가 바뀌는 곳을 찾는다. 간격이 너무 작으면 오래 걸리고, 너무 크면 가까이 붙은 두 근을 한 칸에 넣어 놓친다.

장점	단점
늘 수렴한다	느리다
구간이 반드시 매번 절반이 된다	시작점 하나가 근에 가까워도 그 이점을 못 살린다

부호는 바뀌지만 근이 없는 경우도 있다. \(f(x) = \frac1x\)는 \(x = 0\)에서 끊어져 부호가 바뀐다. 이분법은 근이 아니라 이 끊어진 점으로 간다.

활용

근이 있는 구간을 확실히 알 때 안전한 방법이다. 뉴턴 방법과 섞어(브렌트 방법) 안전함과 빠르기를 함께 얻는다¹.
흔한 실수: 연속인지 확인하지 않고 부호만 보는 것(\(\frac1x\)). 또 \(f(x_l)f(x_r)\)을 곱할 때 값이 아주 크거나 작으면 넘침이 생기므로 부호만 비교하는 편이 안전하다.

연결

선수: 연속과 사잇값 정리, 이분 탐색
같은 구조의 브리지: 매개변수 탐색 ↔ 사잇값 정리
더 빠른 방법들과 비교: 근 찾기 방법 비교

확인 문제

C1 이분법의 한 단계와 멈추는 기준을 쓰라.

답: \(x_r = \frac{x_l + x_u}{2}\). \(f(x_l)f(x_r) < 0\)이면 \(x_u = x_r\), \(> 0\)이면 \(x_l = x_r\), \(= 0\)이면 끝. \(\vert \epsilon_a\vert = \vert \frac{x_r^{\text{new}} - x_r^{\text{old}}}{x_r^{\text{new}}}\vert \times 100 \le \epsilon_s\)이면 멈춘다.

C2 \(f(x) = x^2 - 3\)을 \([1, 2]\)에서 세 번 반복하라. 각 \(x_r\)은?

답: \(f(1) = -2\), \(f(2) = 1\). \(x_r = 1.5\)(\(f = -0.75\), \([1.5, 2]\)) → \(1.75\)(\(f = 0.0625\), \([1.5, 1.75]\)) → \(1.625\). 참값 \(\sqrt3 \approx 1.732\).

C3 양 끝의 부호가 다른데 이분법이 근이 아닌 곳으로 가는 예를 들고 이유를 대라.

답: \(f(x) = \frac1x\), \([-1, 1.5]\). 부호는 바뀌지만 \(x = 0\)에서 끊어져 근이 없다. 사잇값 정리의 “연속” 가정이 깨져, 이분법은 끊어진 점 0으로 다가간다.

C4 단계 3의 if f(xl)·f(xr) < 0 then xu ← xr else xl ← xr가 하는 일을 한 문장으로 쓰라.

답: 가운데 점과 왼쪽 끝의 부호가 다르면 근이 왼쪽 반에, 같으면 오른쪽 반에 있으므로 근이 있는 반쪽만 남긴다.

구현 코드로 확인했다. ↩ ↩² ↩³
28_bisection_plot.py로 그렸고, 같은 코드로 다음 값을 확인했다: 표의 \(x_r\) = 14, 15, 14.5, 14.75, 14.875, 14.8125, \(f(12) > 0 > f(16)\), 근 14.7802. ↩