Post

Bisection Method

Posted
By suyeonnnh
24 min read
Bisection Method

Bisection Method

수치해석에서 자주 만나는 문제 중 하나는 방정식의 해를 구하는 일이다. 특별한 형태의 방정식은 손으로 풀 수 있지만, 고차 대수방정식이나 초월방정식에서는 해를 정확한 식으로 나타내기 어려운 경우가 많다. 이때는 해석적인 방법 대신 계산을 반복하여 해에 가까운 값을 구한다.

수학적으로 정확한 해를 정해(exact solution) 또는 참값이라고 하고, 수치적 방법으로 얻은 값을 수치해(numerical solution) 또는 근사값이라고 한다. 수치해석은 단순히 계산값을 얻는 데서 끝나지 않는다. 그 값이 참값에 얼마나 가까운지, 계산을 언제 멈추어도 되는지까지 함께 다룬다.

가장 익숙한 예로 $\sqrt{2}$를 생각할 수 있다. 한 변의 길이가 1인 정사각형의 대각선 길이를 $x$라고 하면 피타고라스 정리에 의해

\[x^2=2\]

를 만족한다. 근의 공식을 쓰면 해는 $x=\sqrt{2}$라고 말할 수 있다. 그런데 $\sqrt{2}$라는 기호만으로는 그 수의 크기를 바로 느끼기 어렵다. 보통은

\[\sqrt{2}\approx 1.4142\]

처럼 소수 근삿값으로 나타낼 때 훨씬 다루기 쉽다. 체중계가 60kg을 보여줄 때도 마찬가지다. 그 값이 몸무게의 완전한 참값이라기보다 측정 장치가 보여주는 근삿값에 가깝지만, 일상생활에서는 충분히 쓸 수 있다. 방정식의 해도 정확한 값을 구하지 못하더라도, 필요한 정도로 가까운 값을 구하면 의미가 있다.

근 찾기 문제는 보통 다음 형태로 쓴다.

\[f(x)=0\]

여기서 방정식을 만족하는 $x$를 함수 $f$의 근(root)이라고 한다. 그래프로 보면 근은 함수가 $x$축과 만나는 점이다.

예를 들어

\[2x-3=0\]

은 손으로 바로 풀 수 있다. 하지만

\[x^5+3x-1=0\]

또는

\[\cos x-x=0\]

처럼 미지수가 고차항, 삼각함수, 지수함수 안에 들어가면 손으로 정확한 해를 구하기 어렵다. 이런 문제에서는 적당한 기준을 정하고 계산을 반복하면서 해에 가까운 값을 찾는다. 이런 계산 방법을 반복법(iterative method)이라고 한다.

이분법은 반복법 중 가장 기본적인 방법이다. 처음에 근이 들어 있는 구간을 잡고, 그 구간을 반으로 나눈 뒤, 근이 들어 있는 절반만 남긴다. 이 과정을 반복하면 구간이 점점 줄어들고, 그 구간의 중점이 근사해가 된다.

이분법의 기본 원리

이분법은 중간값의 정리에서 출발한다. 함수 $f$가 구간 $[a,b]$에서 연속이고 양 끝점의 함수값 부호가 다르면, 그 사이 어딘가에서 함수값이 0이 되어야 한다.

조건은 다음과 같이 쓴다.

\[f(a)f(b)<0\]

이 식은 $f(a)$와 $f(b)$의 부호가 서로 다르다는 뜻이다. 함수가 끊어지지 않는다면, 그래프가 $x$축의 위쪽에서 아래쪽으로 가거나 아래쪽에서 위쪽으로 가는 동안 반드시 $x$축을 지난다.

Theorem 1.1. 중간값의 정리

함수 $f:[a,b]\to\mathbb{R}$가 폐구간 $[a,b]$에서 연속이고

\(f(a)f(b)<0\) 이면,

\(f(c)=0\) 인 점 $c\in(a,b)$가 적어도 하나 존재한다.

중간값의 정리는 근이 존재한다는 사실을 알려준다. 다만 근이 정확히 어디 있는지는 알려주지 않는다. 이분법은 그 다음 단계에서 구간을 반씩 줄이며 근의 위치를 좁혀간다.

초기 구간을 $[a,b]$라고 하자. 이때 중점은

\[m=\frac{a+b}{2}\]

이다. $f(m)$의 부호를 확인한 뒤, 부호가 바뀌는 쪽의 구간만 남긴다.

조건남기는 구간다음 단계에서 바꾸는 값
$f(a)f(m)<0$$[a,m]$$b\leftarrow m$
$f(m)f(b)<0$$[m,b]$$a\leftarrow m$
$f(m)=0$$m$이 해반복 종료

이 과정을 한 번 할 때마다 구간의 길이가 절반으로 줄어든다. 처음 구간 길이가 $b-a$였다면, 한 번 뒤에는 $(b-a)/2$, 두 번 뒤에는 $(b-a)/4$가 된다. 계산은 느리지만 안정적이다. 매 단계에서 근이 들어 있는 구간을 버리지 않기 때문이다.

Bisection Algorithm

  1. 함수 $f(x)$가 $[a,b]$에서 연속이고, $f(a)$와 $f(b)$의 부호가 다르다고 가정한다.

    \[f(a)f(b)<0\]

  2. 구간의 중간점 $c$를 계산한다.

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

  3. $f(c)$의 부호를 확인한다.

    • $f(a)f(c)<0$이면 새 구간은 $[a,c]$
    • 그렇지 않으면 새 구간은 $[c,b]$

  4. 원하는 정확도에 도달할 때까지 같은 과정을 반복한다.

조금 더 수식 중심으로 쓰면 다음과 같다. 초기 구간 $[a_0,b_0]$가

\[f(a_0)f(b_0)<0\]

을 만족한다고 하자. $n$번째 단계의 중점은

\[m_n=\frac{a_n+b_n}{2}\]

이다. 새 구간은 부호에 따라 아래처럼 정한다.

\[\begin{cases} [a_{n+1},b_{n+1}]=[a_n,m_n], & f(a_n)f(m_n)<0, \\ [a_{n+1},b_{n+1}]=[m_n,b_n], & f(a_n)f(m_n)>0. \end{cases}\]

실제 계산에서는 $f(m_n)=0$이 정확히 나오는 경우가 많지 않다. 그래서 허용 오차를 정해두고, 그 기준에 도달하면 계산을 멈춘다.

\[|b_n-a_n|<\mathrm{TOL}\]

또는

\[|f(m_n)|<\mathrm{TOL}\]

여기서 $\mathrm{TOL}$은 tolerance의 줄임말로, 허용 오차를 뜻한다.

의사코드로 쓰면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

입력: 함수 f, 초기 구간 [a,b], 허용 오차 TOL, 최대 반복 횟수 MaxIter

만약 f(a)f(b) >= 0 이면
    이분법을 적용할 수 없다

반복:
    m = (a+b)/2

    만약 |f(m)| < TOL 또는 (b-a)/2 < TOL 이면
        m을 근사해로 반환한다

    만약 f(a)f(m) < 0 이면
        b = m
    아니면
        a = m

Example

$\sqrt{2}$를 이분법으로 구해보자. 방정식은

\[x^2=2\]

이고, 근 찾기 문제로 쓰면

\[f(x)=x^2-2=0\]

이다. 먼저

\[1^2=1<2<2^2=4\]

이므로 $\sqrt{2}$는 1과 2 사이의 수다. 초기 구간을 $[1,2]$로 잡을 수 있다.

\[f(1)=1^2-2=-1\] \[f(2)=2^2-2=2\]

양 끝의 부호가 다르므로 이 구간 안에 근이 있다.

첫 번째 중점은

\[m_0=\frac{1+2}{2}=1.5\]

이다.

\[f(1.5)=1.5^2-2=0.25\]

$f(1)$은 음수이고 $f(1.5)$는 양수다. 부호가 바뀌는 구간은 $[1,1.5]$이므로 다음 구간은 $[1,1.5]$다.

다음 중점은

\[m_1=\frac{1+1.5}{2}=1.25\]

이고,

\[f(1.25)=1.25^2-2=-0.4375\]

이다. 이번에는 $f(1.25)$가 음수이고 $f(1.5)$가 양수이므로 다음 구간은 $[1.25,1.5]$다.

한 번 더 계산하면

\[m_2=\frac{1.25+1.5}{2}=1.375\]

이고,

\[f(1.375)=1.375^2-2=-0.109375\]

이므로 다음 구간은 $[1.375,1.5]$가 된다.

이 과정을 표로 정리하면 다음과 같다.

반복현재 구간 $[a,b]$중점 $m$$f(m)$다음 구간
0$[1,2]$1.5000000.250000$[1,1.5]$
1$[1,1.5]$1.250000-0.437500$[1.25,1.5]$
2$[1.25,1.5]$1.375000-0.109375$[1.375,1.5]$
3$[1.375,1.5]$1.4375000.066406$[1.375,1.4375]$
4$[1.375,1.4375]$1.406250-0.022461$[1.40625,1.4375]$
5$[1.40625,1.4375]$1.4218750.021729$[1.40625,1.421875]$
6$[1.40625,1.421875]$1.414063-0.000427$[1.414063,1.421875]$
7$[1.414063,1.421875]$1.4179690.010635$[1.414063,1.417969]$

이미 알고 있는 값은

\[\sqrt{2}\approx 1.41421356\]

이다. 몇 번만 반복해도 구간이 이 값 근처로 좁혀진다.

이번에는 다른 예제로

\[f(x)=x^5+3x-1\]

을 보자. 초기 구간을 $[0,0.5]$로 잡으면

\[f(0)=-1\]

이고,

\[f(0.5)=0.5^5+3(0.5)-1=0.53125\]

이다. 부호가 다르므로 이 구간 안에 근이 있다. 허용 오차를 $0.001$로 두면 계산 과정은 다음처럼 나온다.

nabc$b-c$
10.25000000000.50000000000.37500000001.2500e-01
20.25000000000.37500000000.31250000006.2500e-02
30.31250000000.37500000000.34375000003.1250e-02
40.31250000000.34375000000.32812500001.5625e-02
50.32812500000.34375000000.33593750007.8125e-03
60.32812500000.33593750000.33203125003.9063e-03
70.32812500000.33203125000.33007812501.9531e-03
80.33007812500.33203125000.33105468759.7656e-04

마지막 줄에서 $b-c$가 $0.001$보다 작아졌다. 이 기준에서는 근사해를

\[x\approx 0.3311\]

정도로 볼 수 있다.

Convergence and Error

이분법으로 만들어지는 구간을

\[[a_0,b_0],\ [a_1,b_1],\ [a_2,b_2],\ \cdots\]

라고 하자. 각 단계의 구간은 이전 단계의 구간 안에 들어간다.

\[[a_{n+1},b_{n+1}]\subset [a_n,b_n]\]

이런 형태의 구간열은 축소구간 정리와 연결된다.

Theorem 1.2. 축소구간 정리

폐구간의 수열 ${[a_n,b_n]}$에 대하여

\([a_{n+1},b_{n+1}]\subset [a_n,b_n]\) 이면,

\(\bigcap_{n=1}^{\infty}[a_n,b_n]\ne\varnothing\) 이다.

이 정리는 닫힌 구간들이 계속 안쪽으로 줄어들면, 모든 구간에 공통으로 들어 있는 점이 적어도 하나 존재한다는 뜻이다. 이분법에서는 각 단계의 구간이 근을 포함하도록 잡히므로, 이 성질이 근의 존재성과 수렴성을 설명하는 데 쓰인다.

이분법에서 구간 길이는 반복할 때마다 반씩 줄어든다. 처음 구간의 길이가 $b-a$라면

\[b_1-a_1=\frac{b-a}{2}\]

이고,

\[b_2-a_2=\frac{b-a}{2^2}\]

이다. $n$번 반복하면

\[b_n-a_n=\frac{b-a}{2^n}\]

이 된다.

참근을 $p$, $n$번째 중점을 $m_n$이라고 하자. $p$는 항상 현재 구간 $[a_n,b_n]$ 안에 있다. 중점에서 실제 근까지의 거리는 현재 구간 길이의 절반보다 클 수 없다.

Theorem 1.3. 이분법의 오차

함수 $f(x)$가 폐구간 $[a,b]$에서 연속이고

\[f(a)f(b)<0\]

이면, 이분법에 의해 만들어진 수열 ${m_n}$은 해 $p$에 수렴한다. 이때

\(|m_n-p|\leq \frac{b-a}{2^n}\) 이 성립한다.

반복 번호를 0부터 세는지 1부터 세는지에 따라 분모의 지수가 한 칸 달라 보일 수 있다. 핵심은 반복할 때마다 오차의 상한이 절반씩 줄어든다는 점이다.

반복 횟수도 미리 계산할 수 있다.

Theorem 1.4. 이분법의 반복 횟수

처음 구간 $[a,b]$에서 시작하여 근을 포함하는 구간의 길이를 $\varepsilon$보다 작게 만들고자 한다. 이때 필요한 반복 횟수 $n$은 다음을 만족하면 충분하다.

\[n\geq \left\lceil \log_2\left(\frac{b-a}{\varepsilon}\right) \right\rceil\]

Proof

이분법에서는 한 번 반복할 때마다 근을 포함하는 구간의 길이가 절반으로 줄어든다. 따라서 $n$번 반복한 뒤의 구간 길이는

\[\frac{b-a}{2^n}\]

이다. 이 길이가 오차 한계 $\varepsilon$보다 작거나 같으면 되므로

\[\frac{b-a}{2^n}\leq \varepsilon\]

을 만족해야 한다.

양변을 정리하면

\[2^n\geq \frac{b-a}{\varepsilon}\]

이고, 양변에 로그를 취하면

\[n\ln 2\geq \ln(b-a)-\ln(\varepsilon)\]

이다. 따라서

\[n\geq \frac{\ln(b-a)-\ln(\varepsilon)}{\ln 2}\]

를 얻는다.

같은 식은 밑이 2인 로그로

\[n\geq \log_2\left(\frac{b-a}{\varepsilon}\right)\]

라고 쓸 수 있다. 반복 횟수는 정수이므로 실제 계산에서는 올림을 하여

\[n\geq \left\lceil \log_2\left(\frac{b-a}{\varepsilon}\right) \right\rceil\]

로 정한다.

예를 들어 $[1,2]$에서 시작해 구간 길이를 $10^{-4}$보다 작게 만들고 싶다면

\[n\geq \left\lceil \log_2\left(\frac{1}{10^{-4}}\right) \right\rceil =\left\lceil \log_2(10000) \right\rceil =14\]

번 정도 반복하면 된다.

아래 Python 코드는 $f(x)=x^2-2$의 근을 이분법으로 구하고, 중간점이 근으로 가까워지는 모습을 그래프로 저장한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.font_manager as fm

# Windows 기준 한글 폰트 설정
font_path = "C:/Windows/Fonts/malgun.ttf"
font_prop = fm.FontProperties(fname=font_path)


def f(x):
    return x**2 - 2


def bisection(a, b, tol):
    if f(a) * f(b) >= 0:
        print("이분법은 적용할 수 없습니다.")
        return None, None

    steps = []

    while (b - a) / 2.0 > tol:
        midpoint = (a + b) / 2.0
        steps.append(midpoint)

        if f(midpoint) == 0:
            return midpoint, steps
        elif f(a) * f(midpoint) < 0:
            b = midpoint
        else:
            a = midpoint

    return (a + b) / 2.0, steps


root, steps = bisection(0, 2, 0.0001)
print(f"이분법으로 구한 해: {root}")

x = np.linspace(0, 2, 400)
y = f(x)

plt.figure(figsize=(8, 5))
plt.plot(x, y, label="함수 $f(x)=x^2-2$", color="blue")
plt.axhline(0, color="black", linewidth=0.8)
plt.axvline(root, color="red", linestyle="--", label=f"이분법 근사해 = {root:.5f}")

for m in steps:
    plt.plot(m, f(m), "ro", markersize=4)

plt.title("이분법을 이용한 방정식의 근 찾기", fontproperties=font_prop)
plt.xlabel("x", fontproperties=font_prop)
plt.ylabel("f(x)", fontproperties=font_prop)
plt.legend(prop=font_prop)
plt.grid(True)
plt.tight_layout()

plt.savefig("bisection_method_graph.png")
plt.show()

이분법 그래프

MATLAB에서는 이분법을 함수로 만들어두면 다른 방정식에도 재사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

function [x, iter] = bisection(f, a, b, TOL, MaxIter)
% 이분법에 의해 f(x)=0의 해를 [a,b]에서 구한다.
% TOL     : 허용 오차
% MaxIter : 최대 반복 횟수
% f       : 함수 이름 또는 함수 핸들
% x       : 근사해
% iter    : 반복 횟수

if nargin < 5
    MaxIter = 100;
end

if nargin < 4
    TOL = 1.e-5;
end

fa = feval(f, a);
fb = feval(f, b);

if fa * fb > 0
    error('It must be f(a)*f(b)<0');
end

for k = 1:MaxIter
    xm = (a + b) / 2;
    fm = feval(f, xm);
    err = (b - a) / 2;

    if abs(fm) < TOL || abs(err) < TOL
        break;
    elseif fm * fa > 0
        a = xm;
        fa = fm;
    else
        b = xm;
    end
end

x = xm;
iter = k;
end

사용 예시는 다음과 같다.

1
2
3
4
5

f = @(x) x.^2 - 2;
[x, iter] = bisection(f, 0, 2, 1.e-5, 100);

fprintf('x = %.10f\n', x)
fprintf('iter = %d\n', iter)

다음은 $x^5+3x-1=0$을 $[0,0.5]$에서 푸는 MATLAB 예제다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

clear; clc; clf;

f = 'x^5+3*x-1';

a = 0;
b = 0.5;
c = (a + b) / 2;
tol = 0.001;
n = 1;

fprintf(' n        a          b          c        b-c \n')

while b - c > tol
    x = b;
    xb = eval(f);

    x = c;
    xc = eval(f);

    if xb * xc < 0
        a = c;
    else
        b = c;
    end

    c = (a + b) / 2;

    fprintf('%2.0f %12.10f %12.10f %12.10f %12.4e \n', ...
            n, a, b, c, b-c)

    n = n + 1;
end

문자열과 eval을 쓰는 방식은 책 예제에서 자주 보이지만, 새로 코드를 짠다면 함수 핸들을 쓰는 편이 더 낫다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

clear; clc;

f = @(x) x.^5 + 3*x - 1;

a = 0;
b = 0.5;
c = (a + b) / 2;
tol = 0.001;
n = 1;

fprintf(' n        a          b          c        b-c \n')

while b - c > tol
    xb = f(b);
    xc = f(c);

    if xb * xc < 0
        a = c;
    else
        b = c;
    end

    c = (a + b) / 2;

    fprintf('%2.0f %12.10f %12.10f %12.10f %12.4e \n', ...
            n, a, b, c, b-c)

    n = n + 1;
end

Pros and Cons

이분법의 가장 큰 장점은 안정성이다. 함수가 연속이고 처음에 $f(a)f(b)<0$을 만족하는 구간을 잡았다면, 반복 과정에서 근을 포함하는 구간을 계속 유지한다. 미분값도 필요하지 않다. 복잡한 방법으로 들어가기 전에 근이 있는 구간을 확인하거나, 다른 근 찾기 방법의 초기 단계로 쓰기 좋다.

오차를 관리하기도 쉽다. 구간 길이가 반복마다 절반으로 줄어들기 때문에 원하는 정확도를 얻기 위해 몇 번 반복해야 하는지 계산할 수 있다. 빠르지만 조건에 민감한 방법과 비교했을 때 이분법이 갖는 분명한 장점이다.

한계도 있다. 먼저 $f(a)f(b)<0$을 만족하는 초기 구간을 찾아야 한다. 함수가 복잡하면 이 구간을 찾는 일부터 번거로울 수 있다. 초기 구간이 넓으면 계산 시간도 길어진다. 가능한 한 근이 들어 있을 만한 작은 구간을 잡는 편이 좋다.

수렴 속도도 느린 편이다. 구간이 반씩 줄어드는 것은 안정적이지만, 근에 가까워졌다고 해서 갑자기 빨라지지는 않는다. 높은 정확도가 필요하면 반복 횟수가 늘어난다. 실제 응용에서는 이분법의 단점을 보완하기 위해 뉴턴법, 할선법 같은 다른 알고리즘을 함께 사용한다.

부호가 바뀌지 않는 근도 찾기 어렵다. 예를 들어

\[f(x)=(x-1)^2\]

은 $x=1$에서 근을 갖지만, 근의 양쪽에서 함수값이 모두 0 이상이다. 부호 변화가 없으므로 이분법의 기본 조건을 만족시키기 어렵다. 복소근도 이분법의 대상이 아니다. 이분법은 실수 구간에서 부호 변화를 이용하는 방법이다.

한 구간 안에 근이 여러 개 있을 수도 있다. 이분법은 그중 하나로 수렴할 수 있지만, 구간 안의 모든 근을 알려주지는 않는다. 여러 근을 찾으려면 구간을 나누어 따로 확인해야 한다.

이분법은 빠른 방법이라기보다 믿을 수 있는 방법에 가깝다. 중간값의 정리로 근의 존재를 확인하고, 구간을 절반씩 줄이면서 근사해를 만든다. 정확한 해를 모르는 상황에서 근사해를 어떻게 만들고, 그 근사해의 오차를 어떻게 관리하는지 보여주는 기본적인 예시다.

References

  • 이관수. 『공학도를 위한 수치해석』. 세화, 2014.
  • 김학윤. 『수치해석 입문』. 영미디어, 1999.
  • 권순학. 『수치해석 기초: MATLAB 활용』. 영남대학교 출판부, 2016.
  • 이창영. 『수치해석의 기본』. 교문사(청문각), 2008.
  • 박태희. 『MATLAB을 이용한 알기 쉬운 수치해석』. 생능출판, 2018.
Numerical Analysis
Bisection Method Numerical Analysis 수치해석 근찾기 근사해 Python MATLAB
This post is licensed under CC BY 4.0 by the author.