이분법 문서 원본 보기

[[ 분류: 수치 해석]]

== 개요 == 
수학에서 이분법은 근이 반드시 존재하는 폐구간을 이분한 후, 이 중 근이 존재하는 하위 폐구간을 선택하는 것을 반복하여서 근을 찾는 알고리즘이다. 간단하고 견고하며 해의 대략적 위치를 안다면 일정 오차 내에 있는 1개의 해는 무조건 도출이 가능하나, 상대적으로 느린 방식이다. 이분법은 근이 존재한다는 것 자체를 전제로 구간을 설정하는 것이므로 근이 존재할 가능성은 100%이므로 방정식이 간단하고 근 자체가 가장 중요한 목적인 경우 가장 적합한 방법이다. 

== 알고리즘 ==
기본적인 방법은 [a, b]에서 연속인 함수 f에 대하여 ''f''(''a'')''f''(''b'') < 0,인 폐구간 [''a'',''b'']에 대해서 계속해서 <math>\frac{\left|b+a\right|}{2}</math>을 하여 나오는 또다른 수를 하나의 폐구간 끝점으로 잡은 새로운 폐구간을 만든다. 이와 같은 방법으로 계속 ''n''번을 시행하게 되면 점점 함수 <math> f(x) = 0 \ </math>를 만족하는 ''x''에 다가가게 된다. 이런 방법을 이분법이라 한다.

이분법은 ''f''(''a'') 와 ''f''(''b'') 가 다른 부호를 갖는 2개의 초기값 ''a'' 와 ''b''를 필요로 한다. [[중간값 정리]]에 의하여 연속함수 ''f'' 는 폐구간 [''a'', ''b'']에 대해서 최소한 한 개의 해를 가지게 되며, 이를 해 구간이라고 한다. 이제 중간 값 ''c'' = (''a''+''b'') / 2 를 구한다. ''c''가 해가 아닌 이상—가능성은 아주 희소하지만, 가능하다--, 2가지의 가능성이 있다. 첫째, ''f''(''a'') 와 ''f''(''c'') 가 다른 부호를 가지며 해 구간이다. 둘째, ''f''(''c'') 와 ''f''(''b'') 가 다른 부호를 가지며 해 구간이다. 2가지 가능성 중 해 구간을 선택(이분)한 후, 선택된 해 구간에 대해서 이분법 과정을 계속 반복한다. 이럴 경우 각 반복시마다 해 구간--''f'' 가 0값을 가지는 값을 가지고 있는 구간—의 범위가 50%로 줄어든다. 목표로 하는 오차값 이하로 폐구간이 줄어들 때까지 이 과정을 반복한다.{{Sfn|Abdelwahab Kharab|Ronald B. Guenther|p=41|2013}} 찾고자 하는 값의 범위를 반복시마다 반으로 줄여서 찾는 전산 과학 분야의 [[이진 검색]]과 유사하다.

명시적으로 ''f''(''a'') ''f''(''c'') < 0 이면 ''c''를 ''b''의 새 값으로, ''f''(''b'') ''f''(''c'') < 0 이면 ''c''를 ''a''의 새 값으로 치환한다. 두 경우 다 새로운 ''f''(''a'') 값과 ''f''(''b'') 값은 서로 다른 부호를 가지게 되며, 그래서 이 새로운 작은 구간에서 다시 이분법을 적용할 수 있다. 허용 오차를 ε, n번째 구간을 <math>[a_n, b_n]</math>이라고 할 때, 다음 조건이 만족될 때까지 반복한다.{{Sfn|Abdelwahab Kharab|Ronald B. Guenther|p=41|2013}}
:<math>|a_n - b_n| <\epsilon </math>
또는 <math>\frac{|a_n - b_n|}{|a_n|} <\epsilon \quad or \quad |f(a_n)| < \epsilon</math>

실제로 구현시에는 중간 값인 ''c'' 가 실제로 해인 경우를 고려해야 한다.
=== 간단한 구현 ===
# 근의 좌우에 있는 두점 a, b 를 low와 high의 초기값으로 한다.
# low 와 high의 중점 x 를 구한다.
# f(x)를 구하여 부호를 판별한다. 부호가 음수이면, low = x, 양수이면 high = x 가 된다.
# f(x)가 0 혹은 정해진 EPS보다 작을때까지 2를 반복한다. EPS는 |low-high|/|low| 이다.