이분법 (수학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

이분법은 연속 함수 f(x)의 해를 찾는 방법으로, 주어진 구간 내에서 함수의 부호가 바뀌는 지점을 찾아 해를 근사한다. 구간 [a, b]에서 f(a)와 f(b)의 부호가 다를 경우, 중간값 정리에 의해 해당 구간 내에 적어도 하나의 해가 존재하며, 이분법은 구간을 반복적으로 반으로 나누어 해를 좁혀나간다. 각 반복마다 오차가 절반으로 줄어들어 선형적으로 수렴하며, 최악의 경우 성능은 뛰어나지만, 수렴 속도는 다른 방법들에 비해 느린 편이다. 다차원 함수로의 일반화된 이분법도 존재하며, 특성 다면체를 활용하는 방법 등이 있다.

이분법 (수학)

개요

이미지 준비중입니다.

이분법의 처음 몇 단계를 보여주는 다이어그램. 여기서 f(x)는 파란색으로 표시되고 이분법의 현재 중간점은 빨간색 점으로 표시된다.

분야	수치해석학
다른 이름	이진 탐색법 구간 이분법 반분법

세부 사항

종류	근 찾기 알고리즘
안정성	선형
최악의 경우	O(log( (b - a) / ε ))

관련 알고리즘	뉴턴 방법 할선법 가위치법

2. 방법

이분법은 연속 함수 $f(x)$ 에 대해 $f(a)f(b) < 0$ 을 만족하는, 즉 함숫값이 양 끝점에서 서로 다른 부호를 가지는 폐구간 $[a, b]$ 에서 시작한다. 중간값 정리에 따라 이 구간 안에는 방정식 $f(x)=0$ 의 해가 적어도 하나 존재한다.

이분법의 기본적인 아이디어는 해를 포함하는 구간을 반복적으로 반으로 줄여나가는 것이다. 각 단계에서 구간의 중간점 $c = \frac{a+b}{2}$ 를 계산하고, 이 점에서의 함숫값 $f(c)$ 를 확인한다.
* 만약 $f(c) = 0$ 이면 $c$ 가 해이므로 과정을 멈춘다. (실제 계산에서는 $|f(c)|$ 가 매우 작을 때 해로 간주하기도 한다.)
* 만약 $f(c)$ 가 0이 아니면, $f(c)$ 의 부호를 원래 구간의 끝점 함숫값 $f(a)$ 또는 $f(b)$ 와 비교한다.
* $f(a)$ 와 $f(c)$ 의 부호가 다르면 해는 새로운 구간 $[a, c]$ 안에 존재한다. 따라서 다음 단계에서는 구간의 상한 $b$ 를 $c$ 로 바꾼다.
* $f(c)$ 와 $f(b)$ 의 부호가 다르면 해는 새로운 구간 $[c, b]$ 안에 존재한다. 따라서 다음 단계에서는 구간의 하한 $a$ 를 $c$ 로 바꾼다.

이 과정을 반복하면 각 단계마다 해를 포함하는 구간의 길이가 절반으로 줄어든다. 목표로 하는 정밀도(허용 오차)에 도달할 때까지 이 과정을 계속하여 해의 근사값을 찾는다. 이 방식은 원하는 값을 찾기 위해 범위를 절반씩 줄여나가는 이진 검색과 유사하다.

2.1. 기본 원리

이분법은 실수 변수 $x$ 에 대한 방정식 $f(x) = 0$ 의 해를 찾는 가장 기본적인 수치적 방법 중 하나이다. 이 방법을 사용하려면 함수 $f$ 가 구간 $[a, b]$ 에서 연속 함수여야 하고, 구간의 양 끝점에서 함수 값 $f(a)$ 와 $f(b)$ 의 부호가 서로 달라야 한다 ( $f(a)f(b) < 0$ ).

중간값 정리에 따르면, 연속 함수 $f$ 가 $f(a)f(b) < 0$ 을 만족하면, $f(c) = 0$ 이 되는 해 $c$ 가 구간 $(a, b)$ 안에 적어도 하나 존재한다. 이분법은 바로 이 원리에 기반하여 해가 존재하는 구간을 반복적으로 반으로 줄여나가며 근사 해를 찾는 방법이다.

--

이분법의 과정은 다음과 같다.

1. 초기값 $a$ 와 $b$ 를 정한다. 이때 $f(a)$ 와 $f(b)$ 는 서로 다른 부호를 가져야 한다. 이 구간 $[a, b]$ 를 해 구간이라고 한다.
2. 구간의 중간점 $c = \frac{a+b}{2}$ 를 계산한다.
3. 중간점에서의 함수 값 $f(c)$ 를 계산한다.
4. 만약 $f(c) = 0$ 이면, $c$ 가 정확한 해이므로 과정을 멈춘다. 실제 계산에서는 $|f(c)|$ 가 미리 정한 아주 작은 허용 오차 $\epsilon$ 보다 작으면 $c$ 를 해로 간주하고 멈출 수 있다.
5. 만약 $f(c) \neq 0$ 이면, $f(c)$ 의 부호를 확인한다.
* $f(a)$ 와 $f(c)$ 의 부호가 다르면 ( $f(a)f(c) < 0$ ), 해는 구간 $[a, c]$ 안에 존재한다. 따라서 $b$ 의 값을 $c$ 로 업데이트한다 ( $b \leftarrow c$ ).
* $f(c)$ 와 $f(b)$ 의 부호가 다르면 ( $f(c)f(b) < 0$ ), 해는 구간 $[c, b]$ 안에 존재한다. 따라서 $a$ 의 값을 $c$ 로 업데이트한다 ( $a \leftarrow c$ ).
6. 새롭게 정해진 더 작은 구간 $[a, b]$ 에 대해 2단계부터 과정을 반복한다.

이 과정을 반복하면 해를 포함하는 구간 $[a, b]$ 의 폭( $|b-a|$ )은 각 단계마다 50%씩 줄어든다. 이분법은 이 구간의 폭이 미리 정한 허용 오차 $\epsilon$ 보다 작아질 때까지, 즉 $|a_n - b_n| < \epsilon$ (여기서 $n$ 은 반복 횟수) 조건을 만족할 때까지 계속된다. 또는 상대 오차 $\frac$

👆

좌우로 밀어서 보기

👆

좌우로 밀어서 보기

< \epsilon 이나 함수 값

|f(a_n)| < \epsilon

등의 다른 종료 조건을 사용할 수도 있다.

이 방법은 해가 존재하는 구간의 범위를 반복적으로 반으로 줄여서 찾는 방식으로, 컴퓨터 과학 분야의 이진 검색과 유사하다.

컴퓨터로 이분법을 구현할 때는 부동소수점 연산의 정밀도 한계 때문에 몇 가지 고려할 점이 있다. 예를 들어,

f(c)

값이 이론적으로는 0이 되어야 하지만 실제 계산에서는 0에 매우 가깝지만 0이 아닌 값이 될 수 있다 (

f(x) = \cos x

에서

x = \pi/2

근처 값). 또한, 구간

[a, b]

의 폭이 매우 작아지면, 부동소수점 정밀도 내에서 중간점

c

가

a

또는

b

와 같은 값으로 계산될 수도 있다. 따라서 실제 구현에서는 최대 반복 횟수를 제한하거나, 구간의 폭뿐만 아니라 함수 값의 크기를 함께 고려하는 종료 조건을 사용하는 것이 일반적이다.

2.2. 반복 과정

이분법은 해를 포함하는 구간을 반복적으로 절반으로 줄여나가면서 해의 근사값을 찾는 방법이다. 이 과정은 다음과 같이 진행된다.

먼저, 구간 $[a, b]$ 의 중간점 $c = \frac{a+b}{2}$ 를 계산한다. 그리고 함수 $f$ 의 중간점에서의 값 $f(c)$ 를 계산한다.

계산된 $f(c)$ 의 값에 따라 다음 단계가 결정된다.
* 만약 $f(c) = 0$ 이면, $c$ 가 바로 방정식 $f(x) = 0$ 의 해이므로 과정을 멈춘다. (실수 연산의 정밀도 한계 때문에 실제로 정확히 0이 되는 경우는 드물다.)
* 만약 $f(a)$ 와 $f(c)$ 가 서로 다른 부호를 갖는다면 (즉, $f(a)f(c) < 0$ ), 해는 구간 $[a, c]$ 안에 존재한다. 이 경우, 다음 반복을 위해 $b$ 의 값을 $c$ 로 업데이트한다.
* 만약 $f(c)$ 와 $f(b)$ 가 서로 다른 부호를 갖는다면 (즉, $f(c)f(b) < 0$ ), 해는 구간 $[c, b]$ 안에 존재한다. 이 경우, 다음 반복을 위해 $a$ 의 값을 $c$ 로 업데이트한다.

--
위 과정을 통해 해를 포함하는 새로운 구간은 원래 구간의 절반 크기로 줄어든다. 이 새로운 (더 작은) 구간에 대해 중간점을 계산하고 구간을 갱신하는 과정을 계속 반복한다. 각 반복마다 해가 존재하는 구간의 범위는 50%씩 줄어들게 된다.

이 반복 과정은 미리 정해둔 허용 오차 ε에 도달할 때까지 계속된다. n번째 반복에서의 구간을 $[a_n, b_n]$ 이라고 할 때, 다음 조건 중 하나가 만족되면 반복을 멈출 수 있다.
* 구간의 길이가 충분히 작을 때: $|a_n - b_n| <\epsilon$
* 구간의 상대적 길이가 충분히 작을 때: $\frac$

👆

좌우로 밀어서 보기

👆

좌우로 밀어서 보기

<\epsilon (단,

|a_n|

이 0에 매우 가깝지 않을 때 유용하다.)
* 중간점에서의 함수 값이 충분히 0에 가까울 때:

|f(c_n)| < \epsilon

(여기서

c_n = \frac{a_n + b_n}{2}

)
* 구간 끝점에서의 함수 값이 충분히 0에 가까울 때:

|f(a_n)| < \epsilon

요약하면, 이분법의 각 반복 단계는 다음과 같다.
# 구간의 중간점인

c

를 계산한다:

c = \frac{a + b}{2}

.
# 중간점에서 함수 값,

f(c)

를 계산한다.
# 수렴 조건을 확인한다. (예: 구간의 크기

|b - a|

가 충분히 작거나, 함수 값

|f(c)|

가 충분히 작은가?) 조건이 만족되면

c

를 해의 근사값으로 반환하고 반복을 중단한다.
#

f(c)

의 부호를 검사하여 해가 포함된 하위 구간을 결정하고, 그에 따라

a

또는

b

의 값을

c

로 업데이트하여 새로운 구간을 설정한다.

이러한 반복 과정은 컴퓨터 과학 분야의 이진 검색 알고리즘과 유사하게 작동한다.

2.3. 알고리즘

이분법은 f(a) 와 f(b) 가 다른 부호를 갖는 두 개의 초기값 a 와 b를 필요로 한다. 중간값 정리에 의해 연속 함수 f는 폐구간 [a, b]에서 최소한 한 개의 해를 가지게 되며, 이 구간을 해 구간이라고 한다. 알고리즘은 다음과 같은 단계로 진행된다.

1. 구간의 중간점 c = (a + b) / 2 를 계산한다.
2. 중간점에서의 함수 값 f(c)를 계산한다.
3. 만약 f(c) = 0 이거나 구간의 크기 (b - a) / 2 가 미리 정한 허용 오차(TOL)보다 작으면, c를 해로 간주하고 과정을 종료한다.
4. 만약 f(c)가 0이 아니면, f(c)의 부호를 확인한다.
* f(a)와 f(c)의 부호가 같으면, 해는 구간 [c, b]에 존재하므로 a를 c로 업데이트한다. (a ← c)
* f(b)와 f(c)의 부호가 같으면 (즉, f(a)와 f(c)의 부호가 다르면), 해는 구간 [a, c]에 존재하므로 b를 c로 업데이트한다. (b ← c)
5. 새로운 구간 [a, b]에 대해 1단계부터 반복한다.

--
각 반복마다 해를 포함하는 구간의 크기는 절반으로 줄어든다. 이 과정은 원하는 정밀도에 도달할 때까지 또는 미리 정해진 최대 반복 횟수(NMAX)에 도달할 때까지 계속된다. 이는 컴퓨터 과학 분야의 이진 검색과 유사한 방식으로 해를 찾아가는 과정이다.

허용 오차 ε에 대해, n번째 구간을 [a_n, b_n]이라고 할 때, 다음 조건 중 하나가 만족될 때까지 반복할 수 있다.
* |a_n - b_n| < ε
* |a_n - b_n| / |a_n| < ε (상대 오차)
* |f(a_n)| < ε (함수 값 기준)

컴퓨터로 구현할 때는 부동 소수점 연산의 유한 정밀도 문제를 고려해야 한다. 예를 들어, f(x) = cos x 에서 해는 x = π/2 이지만, 부동 소수점 값으로 정확히 f(c) = 0 이 되지 않을 수 있다. 또한, 구간의 폭 (b - a)가 매우 작아지면, 부동 소수점 정밀도 한계로 인해 중간점 c가 a 또는 b와 같아지는 경우가 발생할 수 있으므로, 최대 반복 횟수를 설정하는 것이 일반적이다.

다음은 이분법을 의사 코드로 표현한 예시이다:
```
입력: 함수 f, 끝점 값 a, b, 허용 오차 TOL, 최대 반복 횟수 NMAX
조건: a < b, f(a) * f(b) < 0
출력: f(x) = 0 의 근사해 c 또는 실패 메시지

N ← 1
while N ≤ NMAX do
c ← (a + b) / 2
if f(c) = 0 or (b - a) / 2 < TOL then
출력(c)
정지
end if
N ← N + 1
if sign(f(c)) = sign(f(a)) then
a ← c
else
b ← c
end if
end while
출력("메서드 실패.") // 최대 반복 횟수 초과
```

Perl을 사용한 구현 예시는 다음과 같다. 아래 코드는 f(x) = cos(x/2) 함수의 해(π)를 찾는 예시이다.

```perl
# 이분법
sub F { # 함수의 정의
my ($x) = @_;
my $y = cos($x / 2); # 예상되는 해는 x=원주율
return ($y);
}

my $x1 = 0; # 구간 하한
my $x2 = 6; # 구간 상한
my $s1 = (F($x1) <=> 0); # 구간 하한에서의 함수값의 부호
my $s2 = (F($x2) <=> 0); # 구간 상한에서의 함수값의 부호

# f(x1)과 f(x2)의 부호가 다른지 확인 (필수는 아니나, 기본적인 가정)
if ($s1 * $s2 >= 0) {
print "f(x1)과 f(x2)의 부호가 같거나 0입니다. 이분법 적용 불가.\n";
exit;
}

for (1 .. 50) { # 50회 반복
my $xm = ($x1 + $x2) / 2; # 중간점을 계산
my $sm = (F($xm) <=> 0); # 중간점에서의 함수값의 부호

if ($sm == 0) { # 정확한 해를 찾은 경우 (부동소수점에서는 드묾)
$x1 = $xm;
$x2 = $xm;
last;
} elsif ($sm == $s1) {
$x1 = $xm; # 구간 하한을 중간점으로 대체
} else {
$x2 = $xm; # 구간 상한을 중간점으로 대체
}
# 매우 작은 구간이 되면 종료 (오차 기반 종료 조건 추가 가능)
# if (abs($x1 - $x2) < 1e-15) { last; }
}
# 최종 결과는 $x1 또는 $x2 또는 ($x1+$x2)/2 중 하나를 사용
my $result = ($x1 + $x2) / 2;
print "x=", $result, "\n"; # 결과 표시
```

위 Perl 코드 예시에서 초기 구간 폭은 6이고 반복 횟수는 50회이다. 이론적으로 구간 폭은 $6 \times 2^{-50} \approx 5.3 \times 10^{-15}$ 까지 줄어들 수 있으며, 이는 약 15자리의 정밀도를 의미한다. 실행 결과로 얻는 `x=3.14159265358979`는 실제 원주율 값과 매우 높은 정밀도로 일치한다.

2.4. 구현 시 고려 사항

실제로 이분법을 컴퓨터 프로그램 등으로 구현할 때는 몇 가지 고려해야 할 점이 있다.

우선, 중간값 c가 정확히 해가 되는 경우를 고려해야 한다. 이론적으로는 가능성이 매우 낮지만, 실제 계산에서 발생할 수 있다.

또한, 컴퓨터는 실수를 유한한 정밀도로 표현하기 때문에 발생하는 문제가 있다.
* 함수 f가 연속 함수이더라도 계산된 함수 값 f(c)가 정확히 0이 되지 않을 수 있다. 예를 들어, f(x) = cos x의 해는 x = π/2이지만, 컴퓨터는 π를 근사값으로 사용하므로 cos(π/2)의 계산 결과가 정확히 0이 아닐 수 있다.
* 구간의 양 끝점 a와 b의 차이가 매우 작아지면, 부동소수점 연산의 정밀도 한계 때문에 중간값 c = (a+b)/2가 a 또는 b와 같은 값으로 계산될 수 있다. 이 경우 더 이상 구간이 줄어들지 않아 알고리즘이 멈추지 않을 수 있다.

이러한 유한 정밀도 문제 때문에, 단순히 f(c) = 0인지 확인하는 것 외에 추가적인 종료 조건이 필요하다. 일반적으로 다음 조건 중 하나가 만족되면 반복을 멈춘다.
* 구간의 크기 |b-a|가 미리 정해둔 아주 작은 값(허용 오차, ε)보다 작아지는 경우.
* 함수 값 |f(c)|가 허용 오차보다 충분히 작아지는 경우.
* 미리 정해둔 최대 반복 횟수에 도달하는 경우. 이는 무한 반복을 방지하기 위한 안전 장치이다.

아래는 Perl을 사용한 이분법 구현 예시를 설명한다. 이 예시는 f(x) = cos(x/2)의 해를 구하는 과정이며, 예상되는 해는 x = π이다.
이 Perl 코드는 먼저 함수 F(x) = cos(x/2)를 정의한다. 초기 구간으로 [0, 6]을 설정하고, 각 끝점에서의 함수 값 부호를 확인한다. 이후 정해진 횟수(예시에서는 50회)만큼 반복하면서, 구간의 중간점 xm = (x1+x2)/2을 계산한다. 중간점에서의 함수 값 F(xm)의 부호를 계산하여, 이 부호가 구간 하한에서의 부호와 같으면 하한(x1)을 중간점(xm)으로 업데이트하고, 다르면 상한(x2)을 중간점(xm)으로 업데이트한다. 이 과정을 통해 해를 포함하는 구간을 계속 절반으로 줄여나간다. 초기 구간 폭이 6이고 50회 반복하면, 최종 오차는 대략 6 * 2^-50 (약 5.3 x 10^-15) 수준으로 매우 작아진다.

이 코드의 실행 결과 예시는 다음과 같다.

x=3.14159265358979

이 결과는 실제 π 값과 매우 높은 정밀도로 일치한다.

3. 분석

함수 f가 폐구간 [a, b]에서 연속 함수이고 f(a)와 f(b)의 부호가 서로 다를 때 (즉, f(a)f(b) < 0), 이분법은 방정식 f(x) = 0의 해에 대해 반드시 수렴한다는 것이 보장된다. 이는 중간값 정리에 기반한다.

이분법은 해가 포함된 구간을 반복적으로 절반으로 줄여나가는 방식으로 작동한다. 각 단계에서는 구간의 중간점 c = $\frac{a+b}{2}$ 를 계산하고, f(c)의 부호를 확인하여 해가 포함된 새로운 하위 구간 ([a, c] 또는 [c, b])을 선택한다. 이 과정을 통해 해가 존재하는 구간의 폭은 매 단계마다 절반으로 줄어든다.

이러한 방식 덕분에 이분법은 수렴이 보장되는 매우 안정적인 방법이다. 하지만 구간 폭이 절반씩 줄어들기 때문에 선형적으로 수렴하며, 이는 뉴턴 방법 등 다른 수치해석적 방법에 비해 상대적으로 느릴 수 있다. 그럼에도 불구하고, 이분법은 최악의 경우 성능 면에서 최적성을 가지며, 특정 정밀도를 얻기 위한 최대 반복 횟수를 예측할 수 있다는 장점이 있다.

만약 주어진 구간 [a,b] 내에 여러 개의 해가 존재한다면, 이분법은 그중 하나의 해로 수렴하게 된다.

3.1. 수렴성

함수 f가 폐구간 [a, b]에서 연속 함수이고 f(a)와 f(b)의 부호가 서로 다르면 (즉, f(a)f(b) < 0), 이분법은 f의 해(근)에 대해 반드시 수렴한다. 이는 중간값 정리에 의해 보장된다.

각 단계를 반복할 때마다 해가 존재하는 구간의 폭이 절반으로 줄어들기 때문에, 절대 오차 역시 각 단계마다 절반으로 감소한다. 따라서 이 방법은 해에 대해 선형적으로 수렴한다고 말한다. 구체적으로, n번 반복했을 때 해의 추정값과 실제 해 사이의 오차는 다음과 같이 제한된다.
: $|c_n-c|\le\frac$

👆

좌우로 밀어서 보기

{2^n}
여기서 c는 실제 해, c_n은 n번째 단계에서의 추정값(구간의 중간점), [a, b]는 초기 구간이다.

이 공식을 이용하면 원하는 정밀도(허용 오차) ε를 얻기 위해 필요한 최소 반복 횟수 n을 미리 계산할 수 있다. 오차

|c_n-c|

가 ε보다 작아지도록 하려면, 다음 조건을 만족하는 n번 이상 반복해야 한다.
:

\frac

👆

좌우로 밀어서 보기

{2^n} \le \epsilon
이를 n에 대해 정리하면 다음과 같다.
:

n \ge \log_2\frac

👆

좌우로 밀어서 보기

{\epsilon}
또는 필요한 반복 횟수를

n_{1/2}

라고 할 때, 다음과 같이 표현할 수도 있다.
:

n \ge n_{1/2} \equiv \left\lceil\log_2\left(\frac{\epsilon_0}{\epsilon}\right)\right\rceil

여기서

\epsilon_0 = |b-a|

는 초기 구간의 크기이다.

이분법의 가장 큰 장점은 수렴이 보장된다는 점이다. 함수 f가 연속이고 초기 구간 양 끝에서 함수 값의 부호가 다르기만 하면, 이분법은 반드시 해를 찾아낸다. 또한, 이분법은 최악의 경우 성능 면에서 최적이다. 즉, 어떤 연속 함수에 대해서도 주어진 허용 오차 ε 이내의 해를 찾는 데 필요한 반복 횟수가

n_{1/2}

번을 넘지 않음을 보장하며, 이보다 더 적은 반복 횟수를 보장하는 다른 일반적인 방법은 없다.

그러나 이분법은 수렴 속도가 느리다는 단점이 있다. 오차가 선형적으로 감소하기 때문에, 매우 높은 정밀도를 요구하는 경우 많은 반복이 필요할 수 있다. 할선법, 리더스 방법, 브렌트 방법과 같은 다른 수치적 해법들은 일반적으로 더 빠른 수렴 속도(더 높은 수렴 차수)를 보여주지만, 항상 수렴을 보장하지는 않는다. 다만, 최근에 개발된 ITP 방법은 이분법의 최악 성능 보장을 유지하면서도 더 빠른 수렴 속도를 달성하는 개선된 방법이다.

컴퓨터로 이분법을 구현할 때는 부동소수점 연산의 유한 정밀도 문제에 주의해야 한다. 예를 들어, 함수 값이 이론적으로는 0이 되어야 하지만 계산 과정에서는 0에 매우 가까운 작은 값으로만 표현될 수 있다. (

f(x) = \cos x

에서

x = \pi/2

근처 값) 또한, 구간의 폭

|b-a|

가 매우 작아지면, 부동소수점 정밀도의 한계로 인해 중간점 c가 a 또는 b와 동일한 값으로 표현될 수 있어 더 이상 구간을 좁히지 못할 수도 있다. 따라서 실제 구현에서는 최대 반복 횟수를 제한하거나, 구간의 크기 또는 함수 값의 절댓값이 충분히 작아졌을 때 반복을 멈추는 조건을 추가한다.

만약 폐구간 [a,b] 내에서 f가 여러 개의 해를 가지고 있다면, 이분법은 그 중 하나의 해로 수렴하게 된다. 어떤 해로 수렴할지는 초기 구간과 계산 과정에 따라 달라질 수 있다.

3.2. 오차 분석

f가 폐구간 [a, b]에서 연속 함수이고 f(a)와 f(b)가 서로 다른 부호를 가지면, 이분법은 f의 해에 대해 수렴하는 것이 보장된다. 이분법의 중요한 특징은 각 반복마다 오차의 상한이 절반으로 줄어든다는 점이다. 이로 인해 이분법은 선형적으로 수렴하지만, 수렴 속도는 다른 수치해석 방법에 비해 상대적으로 느린 편이다.

이분법은 근의 정확한 위치 대신 근이 포함된 구간을 제시한다. 따라서 특별한 정보가 없다면, 가장 좋은 근사값은 현재 구간의 중간점 c = (a+b) / 2 로 본다. n번의 반복 후, 실제 해와 중간점 c_n 사이의 절대 오차는 다음과 같은 상한을 가진다.
: $|c_n-c|\le\frac$

👆

좌우로 밀어서 보기

{2^n}
여기서 c는 실제 해를 의미한다. 이 식은 이분법을 n번 반복했을 때 얻을 수 있는 해의 최대 오차 범위를 나타낸다.

이 공식을 이용하면, 원하는 허용 오차 ε 이하의 정밀도를 얻기 위해 필요한 최소 반복 횟수 n을 미리 계산할 수 있다. 절대 오차가 ε보다 작거나 같아지려면 다음 조건을 만족해야 한다.
:

\frac

👆

좌우로 밀어서 보기

{2^n} \le \epsilon
이 부등식을 n에 대해 풀면, 필요한 최소 반복 횟수는 다음과 같다.
:

n \ge \log_2\left(\frac

👆

좌우로 밀어서 보기

{\epsilon}\right)
따라서, 필요한 반복 횟수 n은

\log_2\left(\frac

👆

좌우로 밀어서 보기

{\epsilon}\right)보다 크거나 같은 가장 작은 정수이다. 즉,
:

n = \left\lceil\log_2\left(\frac

👆

좌우로 밀어서 보기

{\epsilon}\right)\right\rceil
여기서

\lceil \cdot \rceil

는 천장 함수를 의미한다.

이분법은 그 단순함과 수렴의 안정성 때문에 널리 사용되지만, 뉴턴 방법, 할선법, 리더스 방법, 브렌트 방법 등과 비교하면 수렴 속도가 느리다. 그러나 ITP 방법과 같이 이분법의 안정성을 유지하면서 수렴 속도를 개선한 방법도 존재한다.

4. 예제

다음과 같은 다항식의 근을 찾기 위해 이분법이 사용된다고 가정해 보자.
: $f(x) = x^3 - x - 2 \,.$
먼저 $f(a)$ 와 $f(b)$ 가 반대 부호를 갖도록 두 숫자 $a$ 와 $b$ 를 찾아야 한다. 위 함수에 대해 $a = 1$ 과 $b = 2$ 는 다음과 같이 이 조건을 충족한다.
: $f(1) = (1)^3 - (1) - 2 = -2$
그리고
: $f(2) = (2)^3 - (2) - 2 = +4 \,.$
함수는 연속적이므로 닫힌구간 [1, 2] 내에 근이 존재해야 한다.

첫 번째 반복에서 근을 포함하는 구간의 끝점은 $a_1 = 1$ 과 $b_1 = 2$ 이므로, 중점은 다음과 같다.
: $c_1 = \frac{2+1}{2} = 1.5$
중점에서 함수의 값은 $f(c_1) = (1.5)^3 - (1.5) - 2 = -0.125$ 이다. $f(c_1)$ 가 음수이므로, $f(a)$ 와 $f(b)$ 가 반대 부호를 갖도록 하기 위해 다음 반복에서 $a = 1$ 이 $a = 1.5$ 로 대체된다. 이 과정이 계속되면 $a$ 와 $b$ 사이의 간격이 점점 작아지면서 함수의 근으로 수렴하게 된다. 아래 표에서 이 과정을 확인할 수 있다.

👆

좌우로 밀어서 보기

반복	$a_n$	$b_n$	$c_n$	$f(c_n)$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

13번의 반복 후, 다항식의 근인 1.521에 수렴하는 것을 확인할 수 있다.

다음은 Perl을 사용한 프로그램의 예이다. 이 예제에서는

f(x) = \cos(x/2)

함수의 근을 찾는다.

# 이분법
sub F { # 함수의 정의
($x) = @_;
$y = cos($x / 2); # 예상되는 해는 $x=원주율
return ($y);
}

$x1 = 0; # 구간 하한
$x2 = 6; # 구간 상한
$s1 = (&F($x1) <=> 0); # 구간 하한에서의 함수값의 부호
$s2 = (&F($x2) <=> 0); # 구간 상한에서의 함수값의 부호

for (1 .. 50) { # 50회 반복
$xm = ($x1 + $x2) / 2; # 중간점을 계산
$sm = (&F($xm) <=> 0); # 중간점에서의 함수값의 부호
if ($sm == $s1) {
$x1 = $xm; # 구간 하한을 중간점으로 대체
}
else {
$x2 = $xm; # 구간 상한을 중간점으로 대체
}
}
print "x=", $xm, "¥n"; # 결과 표시

이 코드는 함수값 F($x1)과 F($x2)의 부호가 다른 구간의 하한($x1)과 상한($x2)을 설정한다. 이후 중간점 $xm과 그 지점에서의 함수값 F($xm)의 부호를 계산한다. 만약 중간점에서의 함수값 부호가 구간 하한에서의 부호와 같으면, 하한을 중간점으로 업데이트한다. 그렇지 않으면 상한을 중간점으로 업데이트한다. 이 예에서는 초기 구간 폭이 6이고 50회 반복하므로,

6 \times 2^{-50} \approx 10^{-15}

정도의 정밀도, 즉 약 15자리의 정밀도를 얻을 수 있을 것으로 예측할 수 있다.

실행 결과의 예는 다음과 같다.

x=3.14159265358979

이 결과는 예상되는 해(x=원주율)와 약 15자리의 정밀도로 일치한다.

5. 특징

함수 f가 닫힌구간 [a, b]에서 연속 함수이고 구간의 양 끝점에서 함수값의 부호가 서로 다르면(f(a)f(b) < 0), 이분법은 반드시 f의 해로 수렴한다. 이는 중간값 정리에 의해 구간 (a, b) 안에 적어도 하나의 해가 존재함을 보장하기 때문이다.

이분법의 가장 큰 특징은 수렴이 보장된다는 점이다. 각 단계를 반복할 때마다 해가 존재하는 구간의 폭이 절반으로 줄어들기 때문에, 오차 역시 각 단계마다 절반으로 감소한다. 이러한 수렴 형태를 선형 수렴이라고 하며, 비록 수렴 속도 자체는 다른 수치해석적 해법에 비해 느리지만, 안정적으로 해를 찾아갈 수 있다는 장점이 있다.

이분법은 해의 정확한 값을 직접 알려주기보다는 해가 포함된 구간을 계속 좁혀나가는 방식으로 작동한다. 따라서 특정 단계에서 가장 좋은 해의 추정값은 그 단계에서 얻어진 가장 작은 구간의 중간점이다. 이분법을 n번 반복했을 때, 해의 절대 오차는 초기 구간의 폭 |b − a| 를 이용하여 다음과 같이 계산할 수 있다.

* 중간점을 근사해로 사용할 경우: |b - a| / 2ⁿ⁺¹
* 구간 자체를 해의 범위로 볼 경우 최대 오차: |b - a| / 2ⁿ

이 공식을 이용하면 원하는 정밀도(허용 오차 ε)를 얻기 위해 몇 번의 반복 계산이 필요한지 미리 예측할 수 있다. 필요한 반복 횟수 n은 다음 부등식을 만족해야 한다.
n > log₂(|b - a| / ε)

만약 주어진 구간 [a, b] 안에 여러 개의 해가 존재한다면, 이분법은 그중 하나의 해로 수렴하게 된다.

다른 수치해석 방법들과 비교했을 때, 이분법의 수렴 속도는 상대적으로 느린 편이다. 예를 들어 뉴턴 방법이나 할선법, 리더스 방법, 브렌트 방법 등은 특정 조건 하에서 이분법보다 훨씬 빠르게 해에 수렴한다. 하지만 이 방법들은 초기값 설정이나 함수의 특성에 따라 수렴하지 않을 수도 있는 반면, 이분법은 초기 조건만 만족하면 반드시 수렴한다는 장점이 있다. 특히, 이분법은 '최악의 경우' 성능 면에서는 다른 어떤 방법보다도 효율적이라고 알려져 있다. 이는 초기 구간 크기 ε₀ = |b - a| 와 목표 오차 ε 가 주어졌을 때, 필요한 반복 횟수의 상한 n_1/2 (ε₀ / ε의 밑이 2인 로그 값을 올림한 값) 보다 적은 반복으로 해를 보장하는 방법은 없다는 것을 의미한다. 그러나 평균적인 경우의 성능이나 점근적 성능은 다른 방법들이 더 우수하며, 이분법의 장점(최악의 경우 성능 보장)을 유지하면서 수렴 속도를 개선한 ITP 방법과 같은 기법도 개발되었다.

컴퓨터로 이분법을 구현할 때는 부동소수점 연산으로 인한 유한 정밀도 문제를 고려해야 한다. 예를 들어, 함수의 값이 이론적으로는 0이 되어야 하지만 계산 과정에서는 정확히 0이 되지 않을 수 있으며 (예: f(x) = cos x 에서 x = π/2 근방), 구간의 폭이 매우 작아지면 중간점이 구간의 양 끝점 중 하나와 수치적으로 동일해지는 현상이 발생할 수 있다. 따라서 실제 구현에서는 최대 반복 횟수를 제한하거나, 구간의 폭 또는 함수 값의 절댓값이 충분히 작아졌을 때 반복을 멈추는 등의 추가적인 종료 조건을 사용한다.

6. 다차원 일반화

이분법은 다차원 함수로 일반화될 수 있다. 이러한 방법들을 일반화된 이분법이라고 한다.

6.1. 위상 차수 기반 방법

이러한 방법 중 일부는 위상 차수 계산에 기반한다. 이는 유계 영역 $\Omega \subseteq \mathbb{R}^n$ 과 미분 가능한 함수 $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ 에 대해 다음과 같이 근의 합으로 정의된다.
: $\deg(f, \Omega) := \sum_{y\in f^{-1}(\mathbf{0})} \sgn \det(Df(y))$ ,
여기서 $Df(y)$ 는 야코비 행렬이고, $\mathbf{0} = (0,0,...,0)^T$ 이며,
: $\sgn(x) = \begin{cases}1, & x>0 \\0, & x=0 \\-1, & x<0 \\\end{cases}$
는 부호 함수이다. 근이 존재하기 위해서는 $\deg(f, \Omega) \neq 0$ 인 것이 충분하며, 이는 $\Omega$ 의 경계에 대한 면적분을 사용하여 확인할 수 있다.

6.2. 특성 이분법

특성 이분법은 서로 다른 점에서의 함수의 부호만을 사용한다. 정수 d ≥ 2에 대해 R^d에서 R^d로의 함수 f가 있다고 하자. f의 특성 다면체(허용 가능한 다각형)는 R^d의 다면체로서, 각 꼭짓점 v에서 f(v)의 부호 조합이 고유하고, 내부에서의 f의 위상 차수가 0이 아닌(근의 존재를 보장하기 위한 필수 조건) 2^d개의 꼭짓점을 갖는다. 예를 들어, d=2인 경우, f의 특성 다면체는 (예를 들어) A, B, C, D를 꼭짓점으로 하는 사변형이며, 다음과 같다.

* sgn f(A) = (-, -), 즉, f₁(A)<0, f₂(A)<0.
* sgn f(B) = (-, +), 즉, f₁(B)<0, f₂(B)>0.
* sgn f(C) = (+, -), 즉, f₁(C)>0, f₂(C)<0.
* sgn f(D) = (+, +), 즉, f₁(D)>0, f₂(D)>0.

특성 다각형의 적절한 모서리는 부호 벡터가 단일 부호만 다른 두 꼭짓점 사이의 모서리이다. 위의 예에서 특성 사변형의 적절한 모서리는 AB, AC, BD, CD이다. 대각선은 부호 벡터가 모든 d개의 부호가 다른 두 개의 꼭짓점 쌍이다. 위 예에서 대각선은 AD와 BC이다.

각 반복에서 알고리즘은 다면체의 적절한 모서리(예: AB)를 선택하고, 중간점(예: M)에서 f의 부호를 계산한다. 그런 다음 다음과 같이 진행한다.

* sgn f(M) = sgn(A)인 경우 A를 M으로 바꾸고 더 작은 특성 다면체를 얻는다.
* sgn f(M) = sgn(B)인 경우 B를 M으로 바꾸고 더 작은 특성 다면체를 얻는다.
* 그렇지 않으면 새로운 적절한 모서리를 선택하고 다시 시도한다.

원래 특성 다면체의 지름(= 가장 긴 적절한 모서리의 길이)이 D라고 가정하자. 그러면, 나머지 다각형의 지름이 최대 ε가 되도록 하기 위해서는, 최소한 $\log_2(D/\varepsilon)$ 개의 모서리 이분이 필요하다. 초기 다면체의 위상 차수가 0이 아니면, 다음 다면체도 0이 아닌 차수를 갖도록 모서리를 선택할 수 있는 절차가 있다.