이분법 (수학)

< \epsilon 이나 함수 값 등의 다른 종료 조건을 사용할 수도 있다.

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

컴퓨터로 이분법을 구현할 때는 부동소수점 연산의 정밀도 한계 때문에 몇 가지 고려할 점이 있다. 예를 들어, $f(c)$ 값이 이론적으로는 0이 되어야 하지만 실제 계산에서는 0에 매우 가깝지만 0이 아닌 값이 될 수 있다 ($f(x)\; =\; \backslash cos\; x$ 에서 $x\; =\; \backslash pi/2$ 근처 값). 또한, 구간 $[a,\; b]$의 폭이 매우 작아지면, 부동소수점 정밀도 내에서 중간점 $c$가 $a$ 또는 $b$와 같은 값으로 계산될 수도 있다. 따라서 실제 구현에서는 최대 반복 횟수를 제한하거나, 구간의 폭뿐만 아니라 함수 값의 크기를 함께 고려하는 종료 조건을 사용하는 것이 일반적이다.^[5][6]

2. 2. 반복 과정

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

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

계산된 $f(c)$의 값에 따라 다음 단계가 결정된다.

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

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

이 반복 과정은 미리 정해둔 허용 오차 ε에 도달할 때까지 계속된다. n번째 반복에서의 구간을 $[a\_n,\; b\_n]$이라고 할 때, 다음 조건 중 하나가 만족되면 반복을 멈출 수 있다.

• 구간의 길이가 충분히 작을 때:
• 구간의 상대적 길이가 충분히 작을 때: $\backslash frac$

<\epsilon (단, $|a\_n|$이 0에 매우 가깝지 않을 때 유용하다.)

중간점에서의 함수 값이 충분히 0에 가까울 때: (여기서 $c\_n\; =\; \backslash frac\{a\_n\; +\; b\_n\}\{2\}$)

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

요약하면, 이분법의 각 반복 단계는 다음과 같다.

# 구간의 중간점인 $c$를 계산한다: $c\; =\; \backslash 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''와 같아지는 경우가 발생할 수 있으므로, 최대 반복 횟수를 설정하는 것이 일반적이다.

다음은 이분법을 의사 코드로 표현한 예시이다:^[7]

```

입력: 함수 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\; \backslash times\; 2^\{-50\}\; \backslash approx\; 5.3\; \backslash 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'' = $\backslash frac\{a+b\}\{2\}$를 계산하고, ''f''(''c'')의 부호를 확인하여 해가 포함된 새로운 하위 구간 ([''a'', ''c''] 또는 [''c'', ''b''])을 선택한다.^[5][6] 이 과정을 통해 해가 존재하는 구간의 폭은 매 단계마다 절반으로 줄어든다.

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

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

3. 1. 수렴성

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

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

:$|c\_n-c|\backslash le\backslash frac$

{2^n}

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

이 공식을 이용하면 원하는 정밀도(허용 오차) ε를 얻기 위해 필요한 최소 반복 횟수 ''n''을 미리 계산할 수 있다. 오차 $|c\_n-c|$가 ε보다 작아지도록 하려면, 다음 조건을 만족하는 ''n''번 이상 반복해야 한다.

:$\backslash frac$

{2^n} \le \epsilon

이를 ''n''에 대해 정리하면 다음과 같다.

:$n\; \backslash ge\; \backslash log\_2\backslash frac$

{\epsilon}

또는 필요한 반복 횟수를 $n\_\{1/2\}$라고 할 때, 다음과 같이 표현할 수도 있다.^[9]

:$n\; \backslash ge\; n\_\{1/2\}\; \backslash equiv\; \backslash left\backslash lceil\backslash log\_2\backslash left(\backslash frac\{\backslash epsilon\_0\}\{\backslash epsilon\}\backslash right)\backslash right\backslash rceil$

여기서 $\backslash epsilon\_0\; =\; |b-a|$는 초기 구간의 크기이다.

이분법의 가장 큰 장점은 수렴이 보장된다는 점이다. 함수 ''f''가 연속이고 초기 구간 양 끝에서 함수 값의 부호가 다르기만 하면, 이분법은 반드시 해를 찾아낸다. 또한, 이분법은 최악의 경우 성능 면에서 최적이다. 즉, 어떤 연속 함수에 대해서도 주어진 허용 오차 ε 이내의 해를 찾는 데 필요한 반복 횟수가 $n\_\{1/2\}$번을 넘지 않음을 보장하며, 이보다 더 적은 반복 횟수를 보장하는 다른 일반적인 방법은 없다.^[9][10]

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

컴퓨터로 이분법을 구현할 때는 부동소수점 연산의 유한 정밀도 문제에 주의해야 한다. 예를 들어, 함수 값이 이론적으로는 0이 되어야 하지만 계산 과정에서는 0에 매우 가까운 작은 값으로만 표현될 수 있다. ($f(x)\; =\; \backslash cos\; x$에서 $x\; =\; \backslash 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'' 사이의 절대 오차는 다음과 같은 상한을 가진다.^[8]

:$|c\_n-c|\backslash le\backslash frac$

{2^n}

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

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

:$\backslash frac$

{2^n} \le \epsilon

이 부등식을 ''n''에 대해 풀면, 필요한 최소 반복 횟수는 다음과 같다.

:$n\; \backslash ge\; \backslash log\_2\backslash left(\backslash frac$

{\epsilon}\right)

따라서, 필요한 반복 횟수 ''n''은 $\backslash log\_2\backslash left(\backslash frac$

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

:$n\; =\; \backslash left\backslash lceil\backslash log\_2\backslash left(\backslash frac$

{\epsilon}\right)\right\rceil

여기서 $\backslash lceil\; \backslash cdot\; \backslash rceil$는 천장 함수를 의미한다.

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

4. 예제

다음과 같은 다항식의 근을 찾기 위해 이분법이 사용된다고 가정해 보자.

:$f(x)\; =\; x^3\; -\; x\; -\; 2\; \backslash ,.$

먼저 $f(a)$와 $f(b)$가 반대 부호를 갖도록 두 숫자 $a$와 $b$를 찾아야 한다. 위 함수에 대해 $a\; =\; 1$과 $b\; =\; 2$는 다음과 같이 이 조건을 충족한다.

:$f(1)\; =\; (1)^3\; -\; (1)\; -\; 2\; =\; -2$

그리고

:$f(2)\; =\; (2)^3\; -\; (2)\; -\; 2\; =\; +4\; \backslash ,.$

함수는 연속적이므로 닫힌구간 [1, 2] 내에 근이 존재해야 한다.

첫 번째 반복에서 근을 포함하는 구간의 끝점은 $a\_1\; =\; 1$과 $b\_1\; =\; 2$이므로, 중점은 다음과 같다.

:$c\_1\; =\; \backslash 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