# 이분법(Bisection Method)과 수렴성 분석

비선형 방정식 근사 문제에서 이분법(Bisection Method)은 가장 기초적이면서도 안정적으로 뿌리 내린 기법 중 하나다. 어떤 구간 안에 해가 존재한다는 사실을 알고 있다면, 이분법은 구간을 절반씩 줄여 가며 방정식의 근을 점차 정밀하게 추적한다. 이때 구간 내에서의 연속성과 함숫값 부호 변환에 대한 고전적 정리를 이용한다. 예를 들어 연속함수 $f(x)$가 구간 $\[a, b]$에서 $f(a)$와 $f(b)$의 부호가 서로 반대임을 보인다면, 적어도 하나의 해 $\alpha$가 $\[a, b]$ 안에 존재한다고 할 수 있다. 이때 해를 만족하는

$$
f(\alpha) = 0
$$

이 되는 어떤 $\alpha$를 구간을 절반씩 줄이는 과정에서 점진적으로 찾아가는 것이 이분법이다.

#### 이분법 알고리즘

연속함수 $f(x)$가 주어졌다고 하자. 구간 $\[a\_0, b\_0]$에서 $f(a\_0)$와 $f(b\_0)$의 부호가 다르면, 반드시 $\[a\_0, b\_0]$ 안에 적어도 하나의 근이 존재한다. 이 근을 향해 접근하기 위해 첫 단계에서는 중점

$$
x\_1 = \frac{a\_0 + b\_0}{2}
$$

를 취한다. $f(x\_1)$의 부호가 $f(a\_0)$의 부호와 동일하다면 근은 구간 $\[x\_1, b\_0]$ 안에 존재하므로 다음 단계에서 $a\_1 = x\_1$로 놓고 $b\_1 = b\_0$로 둔다. 반면 $f(x\_1)$의 부호가 $f(b\_0)$와 동일하다면 근은 $\[a\_0, x\_1]$ 안에 존재하므로 $a\_1 = a\_0$와 $b\_1 = x\_1$로 갱신한다. 이후

$$
\begin{align}
a\_{n+1} = \begin{cases}
x\_n & \text{if } f(a\_n) f(x\_n) > 0,\\
a\_n & \text{if } f(a\_n) f(x\_n) < 0,
\end{cases}
\\
b\_{n+1} = \begin{cases}
b\_n & \text{if } f(a\_n) f(x\_n) > 0, \\
x\_n & \text{if } f(a\_n) f(x\_n) < 0,
\end{cases}
\end{align}
$$

와 같이 구간을 절반씩 좁혀가면서 중점을 취해나간다. 이러한 과정을 반복하면, 각 단계마다 구간의 길이가 절반으로 줄어드는 특성을 가진다.

#### 이분법의 수렴성 분석

연속함수 $f(x)$에 대해, $\[a\_0, b\_0]$를 초기 구간이라 하고 이 구간에 해가 하나 존재한다고 하자. 이때 이분법으로 단계 $n$번을 반복한 후 구해지는 구간 $\[a\_n, b\_n]$의 길이는

$$
|b\_n - a\_n| = \frac{|b\_0 - a\_0|}{2^n}
$$

이므로, 구간의 길이가 기하급수적으로 감소한다. 또한 $a\_n \le \alpha \le b\_n$라고 할 때 $\alpha$가 참해라면, $n$이 충분히 커질수록 $|b\_n - a\_n|$이 작아지므로

$$
\lim\_{n \to \infty} a\_n = \alpha, \quad \lim\_{n \to \infty} b\_n = \alpha
$$

임을 추론할 수 있다. 결국 이분법은 $O(\log(\frac{1}{\varepsilon}))$ 정도의 오차 $\varepsilon$에 대한 단계 수를 요구한다. 다시 말해 오차 범위를 절반씩 줄여 나가는 구조이기 때문에 매우 안정적인 선형 수렴(linear convergence)을 제공한다. 여기서 선형 수렴이라는 용어는 반복 과정에서 오차가 고정된 배율(이 경우에는 $\frac12$)로 계속 줄어드는 형태를 가리킨다.

이 과정을 보다 시각적으로 살펴보기 위해, 구간이 절반씩 줄어드는 단계를 다음과 같은 다이어그램으로 나타낼 수 있다.

{% @mermaid/diagram content="flowchart TB
A((a\_0)) -- f(a\_0)\*f(x\_1)<0 --> B((x\_1))
A -- f(a\_0)\*f(x\_1)>0 --> C((b\_0))
B -- 중점 계산 --> D((x\_2))
C -- 중점 계산 --> D
style A fill:#f9f,stroke:#333,stroke-width:1px
style B fill:#f9f,stroke:#333,stroke-width:1px
style C fill:#f9f,stroke:#333,stroke-width:1px
style D fill:#f9f,stroke:#333,stroke-width:1px" %}

#### 추가적인 이분법 해석

이분법은 연속함수 $f(x)$의 특정 구간에서 근을 찾는 알고리즘적 접근 중에서 가장 간단명료한 방법이다. 구간이 절반씩 줄어드는 이유는 함숫값의 부호 변화를 일으키는 점(실제로는 참해 $\alpha$)을 중심으로 왼쪽 또는 오른쪽의 절반 구간을 선택함으로써, 마치 '현미경 확대'처럼 목표 근에 대한 탐색 범위를 체계적으로 축소해 나가는 것이다. 이때 핵심 전제는 연속성에 의한 사잇값 정리(Intermediate Value Theorem)다.

$$
\text{(사잇값 정리)} \quad f \text{가 } \[a,b] \text{에서 연속이고 } f(a),f(b)<0 \text{이면,}\\
\exists \alpha \in \[a,b]: f(\alpha)=0.
$$

이 정리는 구간 내부에 적어도 한 개의 근이 존재함을 보장한다. 이분법은 바로 이 $\alpha$가 들어 있는 구간을 단계마다 반으로 줄이면서 접근한다.

#### 오차 경계 설정과 해석

예를 들어 $\[a\_n,b\_n]$를 $n$번째 단계에서의 근 탐색 구간이라 하고, $x\_n$을 이 구간의 중점이라 하자. 그러면 $|b\_n - a\_n| = \frac{|b\_0 - a\_0|}{2^n}$가 되고,

$$
x\_n = \frac{a\_n + b\_n}{2}
$$

로 정의한다. 진정한 해 $\alpha$가 $\[a\_0,b\_0]$ 안에 유일하다고 가정하면, 매 반복마다 $\alpha$는 $\[a\_n,b\_n]$ 안에 반드시 존재하게 되고, 따라서

$$
|x\_n - \alpha| \le \frac{|b\_n - a\_n|}{2} = \frac{|b\_0 - a\_0|}{2^{n+1}}
$$

와 같은 오차 상한선을 얻는다. 이로부터 임의의 $\varepsilon > 0$에 대해 $|x\_N - \alpha| < \varepsilon$를 만족하려면

$$
\frac{|b\_0 - a\_0|}{2^{N+1}} < \varepsilon
$$

를 충족하는 정수 $N$ 이상에서 반복을 멈추면 된다. 양변에 로그를 취하면

$$
N+1 > \log\_2 \Bigl(\frac{|b\_0 - a\_0|}{\varepsilon}\Bigr)
$$

이고, 이를 만족하는 최소 정수 $N$을 구하면 원하는 정밀도의 근사 해를 얻게 된다.

#### 간단한 이분법 구현 예시 (Python)

여기서는 실제로 이분법을 구현해 볼 수 있는 간단한 Python 스크립트를 제시한다. 코드에서는 구간 $\[a,b]$를 설정하고, 근을 찾을 때까지 반복하며 구간을 업데이트한다.

```python
def bisection_method(f, a, b, tol=1.0e-7, max_iter=100):
    fa = f(a)
    fb = f(b)
    if fa * fb > 0:
        raise ValueError("f(a)와 f(b)의 부호가 같으므로 이분법 적용 불가")
    for i in range(max_iter):
        x = 0.5*(a + b)
        fx = f(x)
        if abs(fx) < tol:
            return x
        # 이분법 구간 업데이트
        if fa * fx > 0:
            a = x
            fa = fx
        else:
            b = x
    return 0.5*(a + b)

# 실행 예시
if __name__ == "__main__":
    import math

    # 간단한 예: f(x) = x^2 - 2, 근은 sqrt(2) 또는 -sqrt(2)
    root = bisection_method(lambda x: x**2 - 2, 0, 2)
    print("이분법으로 찾은 근 =", root)
    print("실제 sqrt(2)와의 차이 =", abs(root - math.sqrt(2)))
```

이 코드를 실행하면, $f(a) f(b) \le 0$를 만족하는 최초의 구간에 대하여 이분법을 수행하여 근사 해를 찾는다. 위의 예시는 $f(x) = x^2 - 2$가 0이 되는 지점인 $\sqrt{2}$ 부근을 탐색하며, 함수값의 오차가 $10^{-7}$ 이하가 될 때까지만 반복을 수행한다. $f(a) f(b) > 0$인 경우에는 이분법을 적용할 수 없으므로 예외가 발생한다.

이처럼 이분법은 상당히 단순한 구조 덕에 매우 안정적으로 작동하지만, 각 단계마다 구간을 절반씩 줄여 나가는 데 걸리는 반복 횟수 자체는 그렇게 작은 편이 아니다. 다른 고차 방법(예: 뉴턴-라프슨, 할선법 등)은 수렴 속도가 더 빠를 수 있지만, 특정 전제 조건(예: 미분 가능성, 초기값 선택, 기울기의 소멸 등에 대한 문제)이 만족되지 않으면 발산할 가능성도 있다. 반면 이분법은 연속함수의 부호 변화만 포착하면 무조건 수렴한다는 점에서 매우 강력하다.

#### 다중 근 존재 시의 이분법 적용

이분법은 어떤 구간에서 함숫값이 0으로 바뀌는 지점을 찾는 과정에서, 구간의 양 끝점에서 부호가 달라야만 적용 가능하다. 그런데 실제 문제에서 해당 구간 안에 여러 개의 근이 존재하면, 이분법은 '하나의 근'을 찾아내는 데 유용할 수 있어도, 구간 내의 모든 근을 찾기 위해서는 구간 분할 전략을 다시 고려해야 한다. 예컨대 $\[a, b]$에서 $f(a)f(b)<0$인 지점이 여러 구간에 걸쳐 나타나면, 각 구간마다 이분법을 병렬로 적용하여 여러 근을 동시에 찾거나, 또는 구간을 세밀하게 조사하여 각각의 부호 변환 구간을 분리해내야 한다. 이를 테면

$$
\[a, b] = \[a, c\_1] \cup \[c\_1, c\_2] \cup \dots \cup \[c\_{m-1}, b],
$$

같은 식으로 쪼개어, 각 구간별로 $f(\cdot)$의 부호가 바뀌는지 확인한 뒤 이분법을 각각 적용할 수 있다. 이렇듯 여러 구간에서 동시에 이분법을 수행하면, 이론적으로 모든 근을 누락 없이 찾을 수 있지만, 실제로는 근의 개수를 미리 알기 어렵거나, 부호 반전이 아주 작은 구간에서만 일어나면 탐지가 쉽지 않다. 따라서 일반적으로는 '근이 있을 것으로 예상되는 구간'을 사전에 파악한 뒤 거기에만 이분법을 적용하게 된다.

#### 근의 중복성(Multiplicity)에 관한 이분법의 특성

이분법은 함숫값의 부호만을 이용하므로, 어떤 근 $\alpha$가 중복근(예: 2차 이상, $f(\alpha)=0$이면서 $f'(\alpha)=0$인 경우)인지 아닌지는 이 방법만으로 확인하기 어렵다. 만약 $\alpha$가 중복근이라 해도, 이분법은 단지 '부호 변화가 일어나는 지점'인지 아닌지만 살필 뿐이므로, 엄밀히는 $f(a)f(b)<0$를 만족해야만 적용할 수 있다. 예를 들어, $f(x)=(x-1)^2$ 같은 함수는 $\[0, 2]$에서 $f(0)=1$, $f(2)=1$이므로 부호가 변하지 않는다. 이분법은 여기서 부호 변화 조건을 만족하지 않으므로 적용할 수 없으며, 근 $x=1$을 놓친다. 즉, 부호 변화가 없는 중복근은 이분법의 일반적인 형태로는 검출이 불가능하다.

#### 절대/상대 오차를 동시에 사용하는 정지 기준

이분법 과정에서 반복 종료 시점을 설정할 때, $|b\_n - a\_n|$이 충분히 작아지면 멈추는 방식이 보통 쓰인다. 그러나 문제 상황에 따라서는 $|x\_n - \alpha|$가 어느 값 이하(절대 오차 제어)인지, 혹은 $\frac{|x\_n - \alpha|}{|\alpha|}$가 어느 값 이하(상대 오차 제어)인지 확인하는 편이 더 유리할 수 있다. 그러나 이분법은 해의 위치 $\alpha$를 사전에 모른다는 전제에서 동작하기 때문에, 상대 오차 제어는 직접적으로 적용하기 어렵다. 그렇더라도 실제 계산 현장에서는 해가 0에 근접하지 않다고 가정할 수 있으면, 상대 오차 제어가 유의미해진다. 또, $|f(x\_n)|$ 자체가 매우 작은지를 체크하는 함수값 기반의 정지 기준도 쓰지만, 이 함숫값 기준은 해가 중복근일 때 바닥에서 바로 0이 되지 않고, 부동소수점 오차 영향 등을 거쳐 예기치 못한 오차를 발생시킬 수도 있음을 염두에 두어야 한다.

#### 부동소수점 연산과 이분법

수치해석적으로 중요한 점은, 이분법이 비교적 단순한 형태로 구성되어 있음에도 불구하고, 부동소수점 연산 과정에서의 오차가 누적될 수 있다는 사실이다. 일반적으로 이분법은 덧셈과 나눗셈 연산을 통해 중점을 계산하기 때문에, $a$와 $b$가 매우 큰 수이거나 매우 작은 수일 때 상대 오차가 커지는 현상이 발생할 수 있다. 그러나 다른 비선형 방정식 근사 기법과 비교해 볼 때, 이분법은 그 구조상 연산 횟수가 $O(\log(\frac1\varepsilon))$로 늘어나는 대신, 각 단계에서 $f(x)$를 한 번씩만 평가하고, 구간 길이를 단순히 절반으로 줄이므로, 반올림 오차가 비교적 누적되기 어려운 편에 속한다. 게다가 중점 $x\_n=\frac12(a\_n+b\_n)$의 계산에 앞서, $a\_n$과 $b\_n$ 자체가 그다지 많이 변하지 않는다면, 덧셈 연산에서 발생하는 '유효숫자 손실'이 심각해질 가능성도 낮은 편이다.

물론 극단적으로 $a, b$가 엄청난 크기의 실수거나, $f(x)$가 매우 민감하게 변동하는 구간에 대해서는 주의가 필요하다. 특정 상황에서는 이분법보다 정밀도를 높일 수 있는 다른 방법(뉴턴법, 이분-뉴턴 혼합법 등)을 고민해 봐야 한다.

#### 하이브리드 기법과 이분법

더 빠른 수렴을 위해, 이분법과 다른 고차방법(뉴턴법, 할선법 등)을 혼합하는 전략도 종종 사용된다. 일반적으로 고차 방법은 각 단계에서 기울기(미분) 정보를 활용해 근을 예측하거나, 두 점에서의 기울기를 사용해 근을 추정하므로, 수렴 속도가 훨씬 빠른 '이차 수렴' 혹은 '초선형 수렴'을 달성할 수 있다. 반면 초기 추정치가 적절하지 않거나, 미분계수가 0에 가까워지는 등의 문제가 발생하면 발산하거나 수렴이 둔화되기도 한다. 이때 '안정적으로 구간을 좁히는 이분법'과 '빠른 수렴 속도를 갖는 고차 방법'을 결합하여, 먼저 이분법으로 충분히 작은 구간을 확보한 뒤, 이후 그 구간 안에서 뉴턴법을 적용하면 '안정성 + 고속 수렴'을 동시에 노릴 수 있다. 이를 보통 하이브리드 기법(hybrid method)이라고 부른다.

#### 이분법에서의 시작 구간 설정

이분법을 원활하게 적용하기 위해서는 우선 함숫값이 서로 다른 부호를 나타내는 구간 $\[a\_0, b\_0]$을 찾는 일이 필수적이다. 그러나 실전 문제에서는 함숫값의 부호 변화를 보장하는 구간을 자동으로 구하기가 쉽지 않다. 다음과 같은 방식으로 '브래킷팅(bracketing)'을 시도할 수 있다. 예를 들어, $a\_0$를 정해두고, 어떤 고정된 증분 $\Delta > 0$를 더하면서 $a\_0 + \Delta, a\_0 + 2\Delta, \dots$ 순으로 이동하며 $f(a\_0 + k\Delta)$가 $f(a\_0)$와 다른 부호가 되는 지점을 찾는 것이다. 이때

$$
f(a\_0 + m\Delta), f(a\_0 + (m+1)\Delta) < 0
$$

를 만족하는 정수 $m$이 존재한다면, $\[a\_0 + m\Delta, a\_0 + (m+1)\Delta]$를 시작 구간으로 삼아 이분법을 적용한다.

이 방법은 단순히 한 방향으로만 탐색하므로, 만약 근이 음의 무한대 쪽 또는 양의 무한대 쪽에 멀리 존재할 경우 매우 긴 시간이 걸릴 수도 있다. 경우에 따라서는 등비 급수적으로 확장하는 방식($\Delta$ 대신 $c^k$ 형태로 증가시키는 등)도 고려할 수 있다. 중요한 건, 실제 해가 존재할 것으로 추정되는 범위를 체계적으로 조정하면서 '부호 변화'가 일어나는 지점을 찾아내야 한다는 점이다.

#### 함수의 단조성과 이분법

만약 $f(x)$가 어떤 구간에서 단조증가(혹은 단조감소)함을 알고 있다면, $f(a\_0)$와 $f(b\_0)$의 부호가 다를 때 그 구간 내에는 오직 한 개의 근만 존재한다는 사실을 보장할 수 있다. 이 경우 이분법은 단순히 그 근 하나에만 집중하여 수렴하며, 근이 여러 개인 상황보다 훨씬 해석과 구현이 쉬워진다. 단조성을 확인할 때는 보통 $f'(x)$의 부호가 구간 전체에서 일정하게 유지되는지 조사한다.

예를 들어, $f'(x)>0$인 구간에서는 $f(x)$가 단조증가함을 알 수 있다. 그러면 $f(a\_0)f(b\_0)<0$가 성립하면 오직 하나의 근이 존재하고, 따라서 이분법으로 그 근을 찾는 과정이 명확해진다. 반면, $f'(x)$가 구간 중간에 0이 되는 지점이 있다면, 거기서 $f(x)$의 단조성이 깨어질 수 있으므로, 이분법을 적용하기 전에 구간을 더 잘게 분할해볼 필요가 생긴다.

#### 비표준 이분법 변형

순수한 형태의 이분법은 단순히 중점 $x\_n = \frac12 (a\_n + b\_n)$만 사용하지만, 몇몇 변형 기법에서는 중점을 대신하여 함수값 등을 반영한 ‘가중 중점’을 취하기도 한다. 예컨대 ‘이분-할선 혼합법’(Regula Falsi와 유사한 형태)에서는, 중점 대신

$$
x\_n = \frac{f(b\_n),a\_n - f(a\_n),b\_n}{f(b\_n) - f(a\_n)}
$$

와 같이 두 점에서의 함수값 비율에 따라 선형보간을 시행한다. 이 경우, 순수 중점보다는 해에 조금 더 가까운 지점을 선택하여, 때때로 수렴 속도를 다소 향상시킨다. 다만 이 경우에도 근이 멀리 치우친 상황에서는 개선이 크지 않을 수 있고, 일반화된 방법(할선법, 뉴턴법 등)과 비교하면 여전히 상대적으로 느린 편이다.

이처럼 이분법의 핵심 아이디어인 '부호가 다른 구간을 절반씩 줄여가며 좁히기'라는 골격 위에, 보다 빠른 수렴을 위해 함수값의 정보를 약간 가미하는 여러 변형이 존재한다. 그러나 어떤 변형이든 이분법의 안정적 특성(구간이 계속 좁아진다는 점, 그리고 종국적으로 수렴한다는 점)을 해치지 않도록 주의 깊게 설계해야 한다.

#### 계산 효율 관점에서의 장단점

이분법의 가장 큰 장점은 구현이 간단하고, 연속함수의 부호 변화만 보장되면 무조건 수렴한다는 '견고함'이다. 또, 각 단계마다 $f(x)$를 한 번만 평가하면 되므로, 함수 평가의 비용이 비싼 문제라면 이분법처럼 '평가 횟수를 최소화하면서 서서히 구간을 줄여가는' 전략이 오히려 더 경제적일 수 있다. 특히 고차 방법(예: 뉴턴법)이 매 단계에서 미분이나 또는 여러 점에서의 함숫값이 필요할 때, 이분법은 각각의 반복에서 함숫값 한 번만 계산하기 때문에, 특정 상황에선 이분법이 더 효율적일 수도 있다.

그러나 이분법은 각 단계가 구간을 딱 절반으로만 나누므로, 원칙적으로 '선형 수렴'을 벗어나지 못한다. 기하급수적이라 말해도, $O(\log\frac1\varepsilon)$단 만에 충분한 정밀도로 들어가는 것은 사실이지만, 중간 과정에서의 오차 감소 속도는 뉴턴법 등과 비교하면 훨씬 느린 편이다. 예컨대 뉴턴법이 두 자리, 세 자리씩 오차를 줄여나갈 때(이차 수렴), 이분법은 한 자리씩 줄이는(선형 수렴) 모습에 가깝다.

***

이분법은 '부호 변화'가 보장되는 연속함수 구간에서 근을 찾는 가장 기본적인 알고리즘 중 하나이며, 간결한 구현과 안정성으로 인해 널리 활용된다. 구간을 반으로 줄여 가는 과정으로 인해 반복 횟수는 $\log\_2$ 스케일로 증가하지만, 그 결과 수렴이 항상 보장되는 큰 장점이 있다. 이 방법을 탄탄한 기반으로 삼으면, 이후 더 고급 기법(뉴턴법, 할선법, 하이브리드 기법)을 이해하고 응용하는 데에 유리하다.