수치적으로 해를 찾는 알고리즘 1 - Bisection Method

방정식의 해를 구할 때 보통은 손으로 직접 식을 변형하고 정리하여 해를 구하곤 한다.

예를 들어 다음과 같은 간단한 1차 함수의 $y=0$ 에서의 해를 구하고자한다면

$$y=3x+2$$

1. 이 함수를 $y=0$ 과 연립시킨다.

2. $0=3x+2$ 에서 양변에 $-2$ 를 더한 후 양변을 $3$ 으로 나누어준다.

3. $x=-{\displaystyle \frac{2}{3}}$ 라는 해를 얻어낸다.

 

이와 같은 절차를 거쳐 해를 구할 수 있다.

참고로 여기서 2번은 양변에 어떤 실수를 더하거나 빼거나 곱하거나 $0$ 이 아닌 수를 나누어도

등식은 여전히 성립한다는 정리를 이용한 것이다.

하지만 우리가 실생활에서 접하는 함수들은 위와 같이 같은 간단한 풀이법을 가지는 것만 존재하지는 않는다.

가령 함수 $y=x^2-4\sin x$ 가 있을 때 $y=0$ 의 해는 어떻게 구할 것인가?

 

대수적으로 $x^2-4\sin x=0$ 의 해를 구하는 법은 아직 밝혀진 바 없지만

$x^2-4\sin x$ 에 결과가 점점 더 $0$ 에 가까워지게 하는 $x$ 값들을 대입해가며

점점 더 실제 근에 가까운 근을 얻어내는 수치적인 방법은 존재한다.

이번 글에서는 수치적으로 해를 찾는 여러가지 방법 중 첫 번째로 Bisection method 를 소개할 것이다.

 

 

 

---

■ Bisection Method 개요

 

Bisection method는 연속함수에서 중간값 정리를 응용한 알고리즘이다.

 

어떤 연속 함수 $y=f(x)$ 가 있고 방정식 $f(x)=0$ 의 해를 구하고자 한다고 하자.

만약 어떤 두 점 $x=a$ 와 $x=b$ ($a<b$) 에서 $f(a),f(b)$ 값을 조사해보았는데

$f(a)f(b)<0$ 을 만족했다고 하자.

그러면 $f$ 는 중간값 정리에 의해 열린 구간 $(a,b)$ 에서 반드시 하나 이상의 해를 가진다.

기본적인 것을 설명하기 위해 임의로 잡은 $a,b$ 사이에는 단 하나의 근만 존재한다고 가정한다.

 

이제 구간을 반으로 나눠서 살펴보자.

$a,b$ 의 한가운데 값인 $m=a+{\displaystyle \frac{b-a}{2}}$ 를 잡은 후

두 구간 $(a,m)$, $(m,b)$ 에 대해 같은 과정을 반복한다.

 

$f(a)f(m)<0$ 이면 근은 더 좁은 왼쪽 범위인 $(a,m)$ 에 존재한다는 말이고

$f(b)f(m)<0$ 이면 근은 더 좁은 오른쪽 범위인 $(b,m)$ 에 존재한다는 말이다.

($f(a)f(m)$ 과 $f(m)f(b)$ 이 동시에 음수인 경우는 존재하지 않는다.

$f(a)<0$ 이면 $f(m)>0$ 이어야 하는데 이러면 $f(b)<0$ 이어야 한다.

이는 가정이였던 $f(a)f(b)<0$ 에 모순이 된다. $f(a)>0$ 인 경우도 마찬가지로 증명된다.)

이 과정을 원하는 정확도까지 근사될 때까지 반복하여 근의 근사치를 얻으면 된다.

 

 

 

 

정말 쉽게 요약하자면 다음과 같다.

1. 어떤 구간에 해가 하나 존재한다는 것이 확인 됨.

2. 그 구간을 반으로 나눠 왼쪽, 오른쪽 중 어디에 근이 존재하는지 살펴본다.

3. 근이 존재하는 쪽으로 시야를 좁혀서 2번으로 돌아가 반복한다.

 

 

 

Bisection method 알고리즘의 수도 코드(pseudo code)는 다음과 같다.

while (b-a) > tol do
	m = a + (b-a)/2
	if sign(f(a)) = sign(f(B))
		a = m
	else
		b = m
	end
end

 

참고로 pseudo code란 실제 프로그래밍 언어로 작성한 것은 아니지만
대충 사람이 읽기 편하면서도 간결하고 프로그래밍언어스럽게 적은 코드를 뜻한다.

위 코드에서 tol은 tolerence(참을 수 있는 정도)의 줄임말로, 원하는 정확도를 얘기한다.

예를들어 tol = 0.1 이라면, 해가 존재하는 구간이 0.1 보다 좁을 정도로 정확해질 때까지 반복하겠다는 뜻이다.

 

 

---

 

■ MATLAB 코드

 

함수 스크립트

function [answer] = bisection_method(func, a, b, tol)

% 원하는 정확도가 될 때까지 반복할 것임
while b-a > tol

    % m으로 a와 b의 한가운데 값을 택함
    m = a + (b-a)/2;

    % f(a) 와 f(m) 의 부호가 같다면 f(a)f(m) 는 양수임
    % 부호가 달라야 두 점 사이에 근이 존재함
    if func(a) * func(m) > 0
        a = m;
    else
        b = m;
    end
end

% 충분히 좁혀진 범위 중 왼쪽 끝을 답으로 낼 것이다.
% 이 경우 오차는 최대 (b-a) 이다.
answer = a;

end

 

메인 스크립트

%% 초기 조건 

% f가 x에 대한 함수이고 f = x^2 - 4sin(x) 라고 정의함
f = @(x) x.^2 - 4*sin(x);
% 원하는 정확도
tol = 0.0001;
% 시작할 구간
a = 1; b = 3;

answer = bisection_method(f, a, b, tol)

 

아래는 메인 스크립트의 실행 결과이다.

 

 

Wolfram Alpha로 계산한 실제 값은 약 1.93375 로 제대로 구해진 것을 확인할 수 있다.

참고로 tol 값을 더 작게 설정해도 matlab 실행창에서 보이는 값은 소수점으로 최대 4자리까지가 기본이라서

더 자세한 값으로 좁혀지는 것을 관찰할 수 없으므로 자세한 값이 나오는 것을 보려면 따로 설정해주어야 한다.

 

여담이지만 컴퓨터 관련 전공자라면 아마 눈치 챘겠지만,

Bisection method algorithm은 정렬된 정수에서 원하는 값을 찾는 이분탐색법의 실수에서의 확장 버전에 불과하다.

 

 

---

 

■ Bisection Method 의 수렴률(Convergence rate)

 

$x_k$ 가 Bisection method 을 $k$ 번 반복 후 얻은 값이라고 하고 $x^{\ast }$ 가 실제 해라고 하자.

그러면 $k$ 번 반복 후 실제 해와 근사 해 사이의 오차 $e_k$ 는 다음과 같다.

$$e_k=x_k-x^{\ast }$$

매 반복마다 관찰하는 구간이 반으로 줄어드므로 $e_{k+1}$ 는 $e_k$ 의 최대 ${\displaystyle \frac{1}{2}}$ 배이다.

$$|e_{k+1}|\le {\displaystyle \frac{|e_k|}{2}}$$

 

한편 수렴률은 어떤 수 $r$ 에 대해 다음 식을 만족하는

$$\underset{k\to \mathrm{\infty }}{lim}{\displaystyle \frac{|e_{k+1}|}{|e_k{|}^r}}=C$$

양의 상수 $C$ 가 존재할 때 $r$ 값으로 정의된다.

$\underset{k\to \mathrm{\infty }}{lim}{\displaystyle \frac{|e_{k+1}|}{|e_k|}}\le {\displaystyle \frac{1}{2}}$ 이므로 오차를 최대로 잡을 때 $C={\displaystyle \frac{1}{2}}$ 에 대해 $r=1$ 을 택할 수 있다.

따라서 수렴률은 $1$ 이고 이런 경우 수렴률(Convergence rate) 은 linear 하다고 한다.

참고로 수렴률이 $2,3$ 인 경우는 각각 quadratic, cubic 이라고 한다.

 

아무튼 Bisection method 는 매 반복마다 오차 크기가 최대 ${\displaystyle \frac{1}{2}}$ 배씩 감소해간다는 것이 결론이다.