기초수학이분법#348

이분법

Bisection Method

이분법은 닫힌구간에서 연속인 함수의 양 끝 함수값이 반대 부호일 때, 해를 포함한 절반 구간을 반복해 남기는 방법이다. 중점이 해면 즉시 끝내며, k번 이분 뒤 구간 중점의 오차는 처음 구간폭의 2ᵏ⁺¹분의 1 이하다. 원하는 오차에 필요한 이분 횟수와 삼차방정식의 근삿값도 구한다.

읽는 시간
약 7분
선수 개념
알고리즘의 표현연속함수의 성질

직관 — 답이 들어 있는 범위를 반씩 좁힌다

직관

답이 두 수 사이에 있다는 것은 알지만 정확한 위치는 모른다. 가운데를 확인해 답이 남아 있는 쪽 절반을 선택한다. 이 일을 되풀이하면 답이 들어 있는 범위가 줄어들고, 가운데를 택했을 때의 최대 오차도 함께 작아진다.

이 설명을 방정식에 쓰려면 어느 절반에 해가 남는지 판단할 근거가 필요하다. 사잇값 정리의 연속 조건과 함수값의 부호가 그 근거다. 해의 존재를 아는 것에서 나아가, 원하는 오차 이내의 값을 실제로 구해 보자.

이분법은 해를 포함하는 구간을 유지하는 알고리즘이다

이분법은 함수 ff가 유한한 닫힌구간 [a,b][a,b]에서 연속이고 a<ba<b, f(a)f(b)<0f(a)f(b)<0일 때 적용하는 근사해 알고리즘이다. 해가 적어도 하나 존재하며, 중점이 해가 아니면 함수값의 부호가 다른 양 끝점을 가진 절반을 남긴다.

c=a+b2,{f(c)=0이면 c를 반환,f(a)f(c)<0이면 [a,c]를 선택,f(a)f(c)>0이면 [c,b]를 선택.(1)c=\frac{a+b}{2},\qquad \begin{cases} f(c)=0&\text{이면 }c\text{를 반환},\\ f(a)f(c)<0&\text{이면 }[a,c]\text{를 선택},\\ f(a)f(c)>0&\text{이면 }[c,b]\text{를 선택}. \end{cases}\tag{1}

마지막 경우에는 처음 두 끝의 부호가 반대였으므로 f(c)f(c)와 f(b)f(b)의 부호가 반대다. 중점에서 0인 경우를 먼저 처리해야 세 가지가 겹치지 않는다.

정의
기호이름원어뜻
ff연속함수continuous function처음 닫힌구간 전체에서 연속인 함수
a,b,ca,b,c양 끝점, 중점endpoints, midpoint현재 구간의 왼쪽·오른쪽·가운데
a0,b0a_0,b_0시작 끝점initial endpoints계산을 시작한 구간의 끝
kk이분 횟수bisection count절반 구간을 선택한 횟수, 0 이상 정수
Wk,mkW_k,m_k구간폭, 구간 중점width, midpointk번 이분한 뒤의 폭과 중점
α\alpha남은 구간의 해rootf(α)=0f(\alpha)=0인 값
ε\varepsilon허용 오차tolerance해와 출력값의 거리 상한으로 원하는 양수

제곱이 3인 수를 세 번 이분해 보자

f(x)=x2−3f(x)=x^2-3은 [1,2][1,2]에서 연속이고 f(1)=−2f(1)=-2, f(2)=1f(2)=1이다. 이 구간에서는 x가 커지면 제곱도 커지므로 해는 하나다. 이 유일성은 예제의 추가 성질이며 이분법의 기본 가정 자체는 아니다.

이분 횟수검사한 중점 c함수값 f(c)선택한 새 구간
13/23/2−3/4-3/4[3/2,2][3/2,2]
27/47/41/161/16[3/2,7/4][3/2,7/4]
313/813/8−23/64-23/64[13/8,7/4][13/8,7/4]

첫 줄은 f(3/2)=9/4−3=−3/4f(3/2)=9/4-3=-3/4이므로 오른쪽 끝 2와 부호가 다른 절반을 남긴 것이다. 그림 1에서는 같은 수직선 눈금 위에서 구간이 겹쳐 좁아진다.

f(x)=x^2-3의 시작 구간 [1,2]와 세 번 선택한 구간을 같은 눈금에 표시했다. 마지막 폭은 1/8이고 그 구간의 중점은 27/16이다. 점선은 실제 해의 위치를 비교용으로 표시한 것이며 알고리즘 입력으로 사용하지 않는다.
그림 1 f(x)=x2−3f(x)=x^2-3의 시작 구간 [1,2]와 세 번 선택한 구간을 같은 눈금에 표시했다. 마지막 폭은 1/8이고 그 구간의 중점은 27/16이다. 점선은 실제 해의 위치를 비교용으로 표시한 것이며 알고리즘 입력으로 사용하지 않는다. figures/nested_intervals.py

세 번째 검사점 13/813/8은 새 구간의 왼쪽 끝이 되었다. 세 번 이분한 뒤의 구간 중점은 다시 두 끝을 평균하여

m3=13/8+7/42=2716,W3=74−138=18.(2)m_3=\frac{13/8+7/4}{2}=\frac{27}{16},\qquad W_3=\frac74-\frac{13}8=\frac18.\tag{2}

검사한 마지막 점과 최종 출력할 구간 중점을 혼동하지 않는다.

구간폭과 중점의 오차는 왜 두 배 차이일까?

해가 구간 안에 있으므로 중점에서 어느 끝까지 가도 구간폭의 절반이다. 예제에서 폭은 1/81/8이지만, 중점의 오차 상한은 1/161/16이다.

정확한 해를 만나 조기 종료하지 않았다면 매번 구간폭이 반으로 줄어든다. k번 이분한 뒤

Wk=b0−a02k,∣mk−α∣≤Wk2=b0−a02k+1.(3)W_k=\frac{b_0-a_0}{2^k},\qquad \lvert m_k-\alpha\rvert\le\frac{W_k}{2} =\frac{b_0-a_0}{2^{k+1}}.\tag{3}

그림 2는 앞의 예제에서 k=0k=0부터 10까지 중점의 실제 오차와 식 (3)의 상한을 비교한다. 상한은 한 번에 정확히 절반씩 줄지만, 실제 오차는 상한 아래에서 들쭉날쭉 줄어든다. 실제 해를 모르고도 믿을 수 있는 것은 상한 쪽이다.

f(x)=x^2-3, 시작 구간 [1,2]에서 k번 이분한 뒤 중점 m_k의 실제 오차(빈 원)와 보장 상한 1/2^k+1(채운 원)을 세로 로그 눈금에 그렸다. k=0부터 10까지 실제 오차는 늘 상한 이하지만, k=1에서 k=2로 갈 때처럼 커지기도 한다.
그림 2 f(x)=x2−3f(x)=x^2-3, 시작 구간 [1,2]에서 k번 이분한 뒤 중점 mkm_k의 실제 오차(빈 원)와 보장 상한 1/2k+11/2^{k+1}(채운 원)을 세로 로그 눈금에 그렸다. k=0부터 10까지 실제 오차는 늘 상한 이하지만, k=1에서 k=2로 갈 때처럼 커지기도 한다. figures/error_bounds.py

원하는 오차가 ε>0\varepsilon>0이면 상한이 ε\varepsilon 이하가 되는 만큼 이분하면 충분하다.

b0−a02k+1≤ε  ⟺  2k+1≥b0−a0ε.(4)\frac{b_0-a_0}{2^{k+1}}\le\varepsilon \iff 2^{k+1}\ge\frac{b_0-a_0}{\varepsilon}.\tag{4}

처음 폭이 1이고 허용 오차가 1/10001/1000이면 210=1024≥10002^{10}=1024\ge1000이므로 k+1=10k+1=10, 곧 9번 뒤 충분하다. 8번의 보장값 1/5121/512는 더 커서 그 횟수만으로는 같은 정확도를 보장하지 못한다. 실제 오차가 상한보다 작을 가능성과 보장되는 오차를 구별한다.

구간마다 연속성과 반대 부호가 유지되므로 매번 적어도 한 해가 남는다. 폭이 0으로 줄어드는 중첩 닫힌구간의 한 점에 끝점들이 모이고, 연속성에 의해 그 점의 함수값은 0이다. 몇 번의 계산 표가 아니라 이 구간 유지와 폭 감소가 일반적인 수렴 이유다.

원하는 오차에서 멈추는 절차를 표현하자

다음 의사코드는 알고리즘의 표현의 기호를 따르며, 처음부터 닫힌구간 전체의 연속성, a<ba<b, 반대 부호, ε>0\varepsilon>0을 확인한 뒤 사용한다. 연속성을 몇 점 계산으로 판정하는 절차는 아니다. 끝점 자체가 해인 별도 입력은 먼저 그 끝점을 반환하면 된다.

[정의] BISECT(f, a, b, ε):    # 위 네 조건을 만족
    [반복] (b − a)/2 > ε인 동안:
        c ← (a + b)/2
        [조건] f(c) = 0이면:
            [반환] c
        [조건] f(a) × f(c) < 0이면:
            b ← c
        [그렇지 않으면]:
            a ← c
    [반환] (a + b)/2

그림 3의 T/F는 참/거짓, OUT은 값을 반환하고 종료한다는 뜻이다. 반복을 건너뛰는 경우에도 처음 구간폭이 이미 충분히 작으므로 바로 중점을 반환할 수 있다. 실제 컴퓨터 구현에서는 반올림 때문에 중점이 끝점과 같아질 수 있어 그 경우의 중단도 별도로 설계해야 한다. 위 의사코드는 실수 연산을 정확히 수행한다는 수학적 모형이다.

연속성·반대 부호·a<b·양의 허용 오차를 전제로 한 이분법 순서도다. 먼저 폭의 절반을 검사하고, 중점에서 0이면 즉시 반환한다. 그 외에는 부호가 다른 절반을 선택해 폭 검사로 돌아간다.
그림 3 연속성·반대 부호·a<b·양의 허용 오차를 전제로 한 이분법 순서도다. 먼저 폭의 절반을 검사하고, 중점에서 0이면 즉시 반환한다. 그 외에는 부호가 다른 절반을 선택해 폭 검사로 돌아간다. figures/bisection_flow.py

공식으로 풀기 어려운 삼차방정식의 해를 이분법으로 구해 보자

이분법은 공식으로 풀기 어려운 방정식에서 쓸모가 크다. 방정식 x3+x−1=0x^3+x-1=0의 해는 시작 구간 [0,1]에서 6번 이분하면 오차 1/1001/100 이하로 보장된다.

방정식 f(x)=0f(x)=0의 실수 해는 y=f(x)y=f(x)의 그래프가 x축과 만나는 점의 xx좌표다. 먼저 정수를 대입해 부호가 바뀌는 곳을 찾는다. f(x)=x3+x−1f(x)=x^3+x-1은 다항함수라 연속이고 f(0)=−1<0f(0)=-1<0, f(1)=1>0f(1)=1>0이다. xx가 커지면 x3x^3과 xx가 모두 커지므로 이 방정식의 실수 해는 하나뿐이다.

필요한 횟수는 식 (4)에 b0−a0=1b_0-a_0=1, ε=1/100\varepsilon=1/100을 넣어 찾는다. 26=64<100≤128=272^6=64<100\le128=2^7이므로 k+1=7k+1=7, 곧 k=6k=6이다. kk번째로 검사한 중점을 ckc_k라 하면 다음과 같다.

k검사한 중점 ckc_k함수값 f(ck)f(c_k)남긴 구간
11/21/2−0.375-0.375[1/2, 1][1/2,\,1]
23/43/4≈0.172\approx0.172[1/2, 3/4][1/2,\,3/4]
35/85/8≈−0.131\approx-0.131[5/8, 3/4][5/8,\,3/4]
411/1611/16≈0.012\approx0.012[5/8, 11/16][5/8,\,11/16]
521/3221/32≈−0.061\approx-0.061[21/32, 11/16][21/32,\,11/16]
643/6443/64≈−0.025\approx-0.025[43/64, 11/16][43/64,\,11/16]

그림 4는 처음 세 중점을 그래프 위에 표시한 것이다. f(a)f(a)가 음수인 이 구간들에서 함수값이 음수인 c1c_1, c3c_3은 오른쪽 절반을, 양수인 c2c_2는 왼쪽 절반을 남긴다.

y=x^3+x-1의 그래프에서 시작 구간 [0,1]의 두 끝(검은 점)과 처음 세 중점 c_1=1/2, c_2=3/4, c_3=5/8의 함수값을 표시했다. 아래의 굵은 선분은 세 번 이분한 뒤 남은 구간 [5/8, 3/4]이다.
그림 4 y=x3+x−1y=x^3+x-1의 그래프에서 시작 구간 [0,1]의 두 끝(검은 점)과 처음 세 중점 c1=1/2c_1=1/2, c2=3/4c_2=3/4, c3=5/8c_3=5/8의 함수값을 표시했다. 아래의 굵은 선분은 세 번 이분한 뒤 남은 구간 [5/8, 3/4]이다. figures/cubic_bisection.py

최종 구간 [43/64, 11/16][43/64,\,11/16]의 폭은 1/641/64이고, 출력은 중점 87/128≈0.68087/128\approx0.680이다. 오차 상한은 1/1281/128로 1/1001/100보다 작다. 따로 계산한 해 약 0.6820.682와의 실제 거리는 약 0.0030.003이다.

핵심

이분법은 유한한 [a₀,b₀]에서 연속인 f의 양 끝 부호가 반대일 때 해가 남는 절반을 선택한다. k번 뒤 중점의 오차는 (b₀−a₀)/2ᵏ⁺¹ 이하며, 폭의 절반으로 종료를 판단하고 정확한 해면 즉시 끝낸다.

그림 5는 아래 두 질문의 함수다. 위는 끝 부호가 반대지만 x=0x=0에서 끊어진 함수, 아래는 끝 부호가 같지만 해가 있는 함수다.

구간 [−1,1]에서 위는 y=1/x로, 양 끝 함숫값이 −1과 1로 부호가 반대지만 x=0(점선)에서 정의되지 않아 그래프가 x축을 지나지 않는다. 아래는 y=x^2로, 양 끝 함숫값이 모두 1이지만 x=0에서 함숫값이 0이다.
그림 5 구간 [−1,1]에서 위는 y=1/xy=1/x로, 양 끝 함숫값이 −1과 1로 부호가 반대지만 x=0(점선)에서 정의되지 않아 그래프가 x축을 지나지 않는다. 아래는 y=x2y=x^2로, 양 끝 함숫값이 모두 1이지만 x=0에서 함숫값이 0이다. figures/condition_counterexamples.py

이분법은 양 끝의 부호만 다르면 사용할 수 있나요?

아니다. f(x)=1/xf(x)=1/x는 −1과 1에서 부호가 다르지만 그 사이 0에서 정의되지 않아 닫힌구간에서 연속이 아니며, 함수값이 0인 점도 없다. 연속 조건을 빼면 해의 존재부터 보장되지 않는다.

이분법의 부호 조건이 실패하면 해가 없나요?

아니다. f(x)=x2f(x)=x^2는 −1과 1에서 모두 양수지만 0이 해다. 반대 부호는 이분법의 구간 보장을 위한 충분조건이며, 해가 존재하기 위한 필요조건은 아니다.

이분법은 시작 구간의 모든 해를 찾아 주나요?

아니다. f(x)=x3−xf(x)=x^3-x는 [−2,2] 안에 −1, 0, 1의 세 해가 있지만, 첫 중점 0이 해라서 0만 반환하고 끝난다. 이분법 한 번의 실행은 해 하나의 근삿값 또는 정확한 해를 반환하므로, 다른 해는 구간을 나누어 다시 찾는다.

이분법에 관한 오해

  • 함수값이 작으면 위치 오차도 같은 크기로 작다 — 예를 들어 f(x)=0.001xf(x)=0.001x에서 f(1)=0.001f(1)=0.001이지만 해 0까지의 거리는 1이다. 이분법의 위치 오차 보장은 구간폭에서 나온다.
  • 표에서 마지막 검사한 중점이 최종 구간의 중점이다 — 그 검사점은 선택 뒤 끝점이 된다. 예제의 13/813/8과 최종 중점 27/1627/16을 구별한다.
  • 한 번 더 이분하면 근삿값이 반드시 해에 가까워진다 — 제곱이 3인 수의 예제에서 m1=7/4m_1=7/4는 해와 약 0.0180.018, m2=13/8m_2=13/8은 약 0.1070.107 떨어져 있다. 반씩 줄어드는 것은 실제 오차가 아니라 보장 상한이다.

직접 해보기

  1. f(x)=x2−5f(x)=x^2-5, 시작 구간 [2,3]에서 두 번 이분한 구간과 그 중점, 오차 상한을 구하자.
답

첫 중점 5/25/2에서는 25/4−5=5/4>025/4-5=5/4>0이므로 [2,5/2]를 남긴다. 다음 중점 9/49/4에서도 81/16−5=1/16>081/16-5=1/16>0이라 [2,9/4]다. 최종 중점은 17/817/8, 폭은 1/41/4, 중점 오차는 1/81/8 이하다.

  1. f(x)=2x−7f(x)=2x-7, 시작 구간 [2,5]에서는 첫 검사 뒤 무엇을 반환하는가?
답

c=7/2c=7/2에서 f(c)=0f(c)=0이므로 정확한 해 7/27/2를 즉시 반환한다. 미리 정한 횟수만큼 계속할 필요가 없다.

  1. 시작 구간폭이 6일 때, 최종 중점의 오차를 1/101/10 이하로 보장하려면 적어도 몇 번 이분하면 충분한가?
답

6/2k+1≤1/106/2^{k+1}\le1/10을 확인한다. k=4이면 6/32=3/16>1/106/32=3/16>1/10이고, k=5이면 6/64=3/32≤1/106/64=3/32\le1/10이다. 따라서 정확한 해를 먼저 만나지 않는 경우 5번이 그 상한을 만족시키는 최소 횟수다.

  1. f(x)=(x−2)2f(x)=(x-2)^2에 [1,3]을 주었더니 양 끝 함수값이 모두 1이었다. ‘해가 없다’고 결론내려도 되는가?
답

안 된다. x=2에서 함수값은 0이다. 이 구간은 위 부호 조건을 충족하지 않는 것이며, 해가 없다는 뜻이 아니다.

  1. f(x)=x3−2x−5f(x)=x^3-2x-5에 정수 x=0,1,2,3x=0,1,2,3을 대입해 이분법을 시작할 구간을 정하자. 한 번 이분한 구간과 그 중점의 오차 상한은?
답

f(0)=−5f(0)=-5, f(1)=−6f(1)=-6, f(2)=−1f(2)=-1, f(3)=16f(3)=16이므로 부호가 바뀌는 [2,3]에서 시작한다. 중점 5/25/2에서 125/8−5−5=45/8>0125/8-5-5=45/8>0이라 [2, 5/2]를 남긴다. 그 중점은 9/49/4이고 오차 상한은 폭 1/21/2의 절반인 1/41/4이다.

더 읽기

영상 노트

영상 노트
  • 00:00 범위를 반으로 줄이면 오차는 얼마나 줄까?
  • 00:40 식 (1)의 세 경우와 연속 조건 확인하기
  • 01:20 그림 1의 세 구간 선택과 식 (2)의 최종 중점 계산하기
  • 02:20 식 (3)의 폭과 위치 오차를 구별하고 그림 2에서 실제 오차와 비교하기
  • 03:10 식 (4)로 필요한 이분 횟수 구하기
  • 03:50 그림 3의 조기 반환과 종료 검사 따라가기
  • 04:40 그림 4에서 삼차방정식의 해를 6번 이분으로 구하기
  • 05:40 그림 5로 연속과 부호 조건이 빠진 경우 보기

지도에서의 위치

이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 실제 오차와 상한 비교, 필요한 이분 횟수 식, 삼차방정식의 시작 구간 찾기와 6번 이분 풀이, 조건이 깨지는 두 함수 그림, 해보기 5문항 보강, 오해의 중점 기호와 삼차방정식 그림 눈금 정리 (에이전트 수정, 그림 2→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림