[수치해석] 이분법(bisection method)

이번 포스팅에서는 방정식의 근을 찾는 방법 중 하나인

 

이분법(bisection method)에 대해 알아보겠습니다.

(출처: Chapra의 응용수치해석 3rd edition, Steven C. Chapra 저)

 이분법(bisection method)

이분법이란 근을 탐색하는 방법 중 하나로 탐색 구간을 항상 반으로 나눠 찾습니다.

 

구간을 반으로 나눠 찾는다는 점에서 이분법이라는 이름이 붙게 되었고,

 

구간의 양 끝점에서의 함수값을 계산하여 곱했을 때

 

부호가 양수이냐 음수이냐를 확인하여 근의 존재 유무를 판단합니다.

 이분법(bisection method) 계산 방법

구간을 반으로 나눠 근의 존재 유무를 판단한다는 방법적인 면으로 인해

 

계산하는 방법은 매우 간단합니다.

 

1) 탐색 구간 $[x_l, x_u]$을 선정합니다.

 

2) 구간의 양 끝점에서의 함수 값을 계산한 후 곱하여 음수인지 양수인지 확인합니다.

 

만약 양수이면 근이 존재하지 않으므로 1)로 돌아가고, 음수이면 3)을 진행합니다.

 

구간 내 근이 존재할 조건:

$$f(x_l) f(x_u) < 0 $$

 

3) 추정근($x_r$)을 계산합니다. 이 때 추정근은 구간 양 끝값의 평균입니다.

 

$$x_r = \frac{x_l+x_u}{2}$$

 

4) 이전 단계에서 탐색했던 추정근 $x_r$과 이번 단계에서 계산한 추정근 $x_{r,new}$ 사이의 오차를 계산합니다.

 

$$E_a = \left\vert \frac{x_{r,new}-x_r}{x_{r,new}} \right\vert × 100 $$

 

5) 오차를 계산하여 정해진 허용오차 $E_s$와 비교하여 클 경우

 

$x_{r,new}$를 $x_u$ 혹은 $x_l$로 두고 2)부터 다시 진행합니다.

 

만약 작을 경우 탐색을 종료하고 근사해를 $x_{r,new}$로 선정합니다.

 

탐색을 종료할 조건:

$$E_a < E_s$$

 

 

여기까지 이분법에 대해 알아보았습니다.