직관 — 답이 들어 있는 범위를 반씩 좁힌다
답이 두 수 사이에 있다는 것은 알지만 정확한 위치는 모른다. 가운데를 확인해 답이 남아 있는 쪽 절반을 선택한다. 이 일을 되풀이하면 답이 들어 있는 범위가 줄어들고, 가운데를 택했을 때의 최대 오차도 함께 작아진다.
이 설명을 방정식에 쓰려면 어느 절반에 해가 남는지 판단할 근거가 필요하다. 사잇값 정리의 연속 조건과 함수값의 부호가 그 근거다. 해의 존재를 아는 것에서 나아가, 원하는 오차 이내의 값을 실제로 구해 보자.
이분법은 해를 포함하는 구간을 유지하는 알고리즘이다
이분법은 함수 가 유한한 닫힌구간 에서 연속이고 , 일 때 적용하는 근사해 알고리즘이다. 해가 적어도 하나 존재하며, 중점이 해가 아니면 함수값의 부호가 다른 양 끝점을 가진 절반을 남긴다.
마지막 경우에는 처음 두 끝의 부호가 반대였으므로 와 의 부호가 반대다. 중점에서 0인 경우를 먼저 처리해야 세 가지가 겹치지 않는다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 연속함수 | continuous function | 처음 닫힌구간 전체에서 연속인 함수 | |
| 양 끝점, 중점 | endpoints, midpoint | 현재 구간의 왼쪽·오른쪽·가운데 | |
| 시작 끝점 | initial endpoints | 계산을 시작한 구간의 끝 | |
| 이분 횟수 | bisection count | 절반 구간을 선택한 횟수, 0 이상 정수 | |
| 구간폭, 구간 중점 | width, midpoint | k번 이분한 뒤의 폭과 중점 | |
| 남은 구간의 해 | root | 인 값 | |
| 허용 오차 | tolerance | 해와 출력값의 거리 상한으로 원하는 양수 |
제곱이 3인 수를 세 번 이분해 보자
은 에서 연속이고 , 이다. 이 구간에서는 x가 커지면 제곱도 커지므로 해는 하나다. 이 유일성은 예제의 추가 성질이며 이분법의 기본 가정 자체는 아니다.
| 이분 횟수 | 검사한 중점 c | 함수값 f(c) | 선택한 새 구간 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
첫 줄은 이므로 오른쪽 끝 2와 부호가 다른 절반을 남긴 것이다. 그림 1에서는 같은 수직선 눈금 위에서 구간이 겹쳐 좁아진다.
figures/nested_intervals.py세 번째 검사점 은 새 구간의 왼쪽 끝이 되었다. 세 번 이분한 뒤의 구간 중점은 다시 두 끝을 평균하여
검사한 마지막 점과 최종 출력할 구간 중점을 혼동하지 않는다.
구간폭과 중점의 오차는 왜 두 배 차이일까?
해가 구간 안에 있으므로 중점에서 어느 끝까지 가도 구간폭의 절반이다. 예제에서 폭은 이지만, 중점의 오차 상한은 이다.
정확한 해를 만나 조기 종료하지 않았다면 매번 구간폭이 반으로 줄어든다. k번 이분한 뒤
그림 2는 앞의 예제에서 부터 10까지 중점의 실제 오차와 식 (3)의 상한을 비교한다. 상한은 한 번에 정확히 절반씩 줄지만, 실제 오차는 상한 아래에서 들쭉날쭉 줄어든다. 실제 해를 모르고도 믿을 수 있는 것은 상한 쪽이다.
figures/error_bounds.py원하는 오차가 이면 상한이 이하가 되는 만큼 이분하면 충분하다.
처음 폭이 1이고 허용 오차가 이면 이므로 , 곧 9번 뒤 충분하다. 8번의 보장값 는 더 커서 그 횟수만으로는 같은 정확도를 보장하지 못한다. 실제 오차가 상한보다 작을 가능성과 보장되는 오차를 구별한다.
구간마다 연속성과 반대 부호가 유지되므로 매번 적어도 한 해가 남는다. 폭이 0으로 줄어드는 중첩 닫힌구간의 한 점에 끝점들이 모이고, 연속성에 의해 그 점의 함수값은 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은 값을 반환하고 종료한다는 뜻이다. 반복을 건너뛰는 경우에도 처음 구간폭이 이미 충분히 작으므로 바로 중점을 반환할 수 있다. 실제 컴퓨터 구현에서는 반올림 때문에 중점이 끝점과 같아질 수 있어 그 경우의 중단도 별도로 설계해야 한다. 위 의사코드는 실수 연산을 정확히 수행한다는 수학적 모형이다.
figures/bisection_flow.py공식으로 풀기 어려운 삼차방정식의 해를 이분법으로 구해 보자
이분법은 공식으로 풀기 어려운 방정식에서 쓸모가 크다. 방정식 의 해는 시작 구간 [0,1]에서 6번 이분하면 오차 이하로 보장된다.
방정식 의 실수 해는 의 그래프가 x축과 만나는 점의 좌표다. 먼저 정수를 대입해 부호가 바뀌는 곳을 찾는다. 은 다항함수라 연속이고 , 이다. 가 커지면 과 가 모두 커지므로 이 방정식의 실수 해는 하나뿐이다.
필요한 횟수는 식 (4)에 , 을 넣어 찾는다. 이므로 , 곧 이다. 번째로 검사한 중점을 라 하면 다음과 같다.
| k | 검사한 중점 | 함수값 | 남긴 구간 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
그림 4는 처음 세 중점을 그래프 위에 표시한 것이다. 가 음수인 이 구간들에서 함수값이 음수인 , 은 오른쪽 절반을, 양수인 는 왼쪽 절반을 남긴다.
figures/cubic_bisection.py최종 구간 의 폭은 이고, 출력은 중점 이다. 오차 상한은 로 보다 작다. 따로 계산한 해 약 와의 실제 거리는 약 이다.
이분법은 유한한 [a₀,b₀]에서 연속인 f의 양 끝 부호가 반대일 때 해가 남는 절반을 선택한다. k번 뒤 중점의 오차는 (b₀−a₀)/2ᵏ⁺¹ 이하며, 폭의 절반으로 종료를 판단하고 정확한 해면 즉시 끝낸다.
그림 5는 아래 두 질문의 함수다. 위는 끝 부호가 반대지만 에서 끊어진 함수, 아래는 끝 부호가 같지만 해가 있는 함수다.
figures/condition_counterexamples.py이분법은 양 끝의 부호만 다르면 사용할 수 있나요?
아니다. 는 −1과 1에서 부호가 다르지만 그 사이 0에서 정의되지 않아 닫힌구간에서 연속이 아니며, 함수값이 0인 점도 없다. 연속 조건을 빼면 해의 존재부터 보장되지 않는다.
이분법의 부호 조건이 실패하면 해가 없나요?
아니다. 는 −1과 1에서 모두 양수지만 0이 해다. 반대 부호는 이분법의 구간 보장을 위한 충분조건이며, 해가 존재하기 위한 필요조건은 아니다.
이분법은 시작 구간의 모든 해를 찾아 주나요?
아니다. 는 [−2,2] 안에 −1, 0, 1의 세 해가 있지만, 첫 중점 0이 해라서 0만 반환하고 끝난다. 이분법 한 번의 실행은 해 하나의 근삿값 또는 정확한 해를 반환하므로, 다른 해는 구간을 나누어 다시 찾는다.
이분법에 관한 오해
- 함수값이 작으면 위치 오차도 같은 크기로 작다 — 예를 들어 에서 이지만 해 0까지의 거리는 1이다. 이분법의 위치 오차 보장은 구간폭에서 나온다.
- 표에서 마지막 검사한 중점이 최종 구간의 중점이다 — 그 검사점은 선택 뒤 끝점이 된다. 예제의 과 최종 중점 을 구별한다.
- 한 번 더 이분하면 근삿값이 반드시 해에 가까워진다 — 제곱이 3인 수의 예제에서 는 해와 약 , 은 약 떨어져 있다. 반씩 줄어드는 것은 실제 오차가 아니라 보장 상한이다.
직접 해보기
- , 시작 구간 [2,3]에서 두 번 이분한 구간과 그 중점, 오차 상한을 구하자.
답
첫 중점 에서는 이므로 [2,5/2]를 남긴다. 다음 중점 에서도 이라 [2,9/4]다. 최종 중점은 , 폭은 , 중점 오차는 이하다.
- , 시작 구간 [2,5]에서는 첫 검사 뒤 무엇을 반환하는가?
답
에서 이므로 정확한 해 를 즉시 반환한다. 미리 정한 횟수만큼 계속할 필요가 없다.
- 시작 구간폭이 6일 때, 최종 중점의 오차를 이하로 보장하려면 적어도 몇 번 이분하면 충분한가?
답
을 확인한다. k=4이면 이고, k=5이면 이다. 따라서 정확한 해를 먼저 만나지 않는 경우 5번이 그 상한을 만족시키는 최소 횟수다.
- 에 [1,3]을 주었더니 양 끝 함수값이 모두 1이었다. ‘해가 없다’고 결론내려도 되는가?
답
안 된다. x=2에서 함수값은 0이다. 이 구간은 위 부호 조건을 충족하지 않는 것이며, 해가 없다는 뜻이 아니다.
- 에 정수 을 대입해 이분법을 시작할 구간을 정하자. 한 번 이분한 구간과 그 중점의 오차 상한은?
답
, , , 이므로 부호가 바뀌는 [2,3]에서 시작한다. 중점 에서 이라 [2, 5/2]를 남긴다. 그 중점은 이고 오차 상한은 폭 의 절반인 이다.
더 읽기
- 교육부 고시 제2022-33호 — 별책20 [12이수02-05]의 이분법과 방정식 해 구하기.
- 우리교과서 『이산 수학』 공개 원문 — 인쇄74–76쪽의 사잇값 정리, 중점 부호 검사와 허용 오차. 이 글은 제곱이 3인 수의 새 계산과 구간폭·중점 오차의 일반식을 제시했다.
영상 노트
- 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로 연속과 부호 조건이 빠진 경우 보기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 실제 오차와 상한 비교, 필요한 이분 횟수 식, 삼차방정식의 시작 구간 찾기와 6번 이분 풀이, 조건이 깨지는 두 함수 그림, 해보기 5문항 보강, 오해의 중점 기호와 삼차방정식 그림 눈금 정리 (에이전트 수정, 그림 2→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림