수치해석: 비선형 방정식의 수치해석법 - 직접탐색법 (2분법)

함수 f(x)에 대해서, f(x) = 0 을 만족하는 x 값을 함수 f(x)의 근이라고 부른다.

X-Y 좌표평면에 놓고 봤을 때, y = f(x)의 곡선과 y = 0인 직선..

즉, x 좌표축과의 교점이 함수 f(x)의 근이라고 할 수 있다.

주어진 함수 f(x)의 근을 구하는 수치해석적 방법 중 2분법에 대해 알아보자.

직접탐색법 - 2분법

2분법은 근을 포함하는 구간을 임의로 정한 다음, 

구간을 절반씩 줄여나가면서 반복적으로 근을 탐색하는 방법이다.

그럼, 정의한 구간에서 근이 포함되는가를 알아야 하는데,

대수학에서 사용하는 중간값 정리를 통해 알 수 있다.

예를 들어, 

의 함수가 있다고 가정하자.

(이 함수의 근이 -3 이라는 것쯤은 누구나 쉽게 계산할 수 있다.)

임의의 폐구간으로 [-5, -2]를 지정했을 때,

이므로, 이 구간에는 근이 하나 이상 존재한다는 것을 알 수 있다.

이 함수에서 지정한 폐구간인 [-5, -2]의 중간인 -3.5의 값 f(-3.5)를 구하면,

이고, 다시 중간값의 정리를 적용했을 때, [-3.5, -2] 구간에서 근이 존재하는 것을 알 수 있다.

여기서 다시, [-3.5, -2]의 중간인 -2.75의 값 f(-2.75)를 구하면,

이고, 다시 중간값의 정리를 적용하면, [-3.5, -2.75] 구간에서 근이 존재하는 것을 알 수 있다.

같은 방법을 반복하면서 구간을 점점 좁혀나가다보면, 어느새 근에 수렴하게 된다.

정리하자면, 구간 [x1, x2]를 중간값 x를 중심으로

[x1, x]와 [x, x2]로 2분한 다음, 중간값 정리에 따라 근을 포함하는 쪽을 골라서 새로운 [x1, x2]로 정의하고,

이런 연산을 수렴 판정 조건을 만족할 때까지 되풀이 하면서 근을 구하는 방법이 2분법이다.

2분법에서는 연산이 반복될수록, 구간이 절반으로 줄어들게 되는데, n번째의 구간 폭을 Δn이라고 하면,

의 관계식을 얻을 수 있고, 수열 Δn은 0에 수렴하게 된다.

지금까지 살펴본 2분법을 이용하여, 다음 함수의 근을 구해보자.

먼저, 이 함수를 그래프로 그려보면,

으로, 하나의 근이 존재하는 것을 확인할 수 있고, 근의 위치 부분을 확대했을 때,

와 같이 0과 1 사이에 근이 존재하는 것을 알 수 있다.

참고로, MS Mathematics를 이용하여 이 함수의 근을 구하면 아래와 같다.

LabVIEW를 이용하여 위 함수의 근을 구하는 프로그램을 작성하였다.

< 프로그램 시연 영상 (마우스로 클릭하면 보입니다.) >

시연 영상에서 확인할 수 있듯이, [0, 1]의 폐구간을 초기 구간으로 지정하고 돌렸을 때,

수렴 판정 조건 (error)이 작아지면 작아질수록, 좀 더 정확한 근의 값을 얻을 수 있는 대신

연산의 반복 횟수가 증가하는 것을 확인할 수 있다.