BiSection Method는 간단하게 구현할 수 있는 탐색 기법이지만, 처음에 설정된 구간이 적절하지 않은 경우 불필요한 계산이 많아진다는 단점이 있다. 이에 비해 False Position Method(Linear Interpolation)은 훨씬 효율적인 근을 구하는 방법이다.
False Position Method는 탐색하고자 하는 구간 [a, b]에서 f(a)와 f(b)를 연결하는 직선이 y = 0과 만나는 지점에서부터 탐색을 시작한다. 다음에 선택되는 구간은 f(a)와 f(b)를 연결하는 직선이 y = 0과 만나는 교점 c에서의 함수값 f(c)와 f(b)를 연결하는 직선과, y = 0과의 교점이다. 즉, BiSection Method가 주어진 구간에서 중간점을 구하는 방식으로 근을 탐색하는 것에 비해, 좀 더 효율적으로 근과 가까운 점을 구하여 다음 구간으로 설정한다. 예를 들어, [a, b] 구간에서 False Position Method를 적용하여 근을 구하고자 한다면, f(a(k)), f(b(k))를 구한다. 그리고 보간점 c(k) = { f(b(k)) * a(k) - f(a(k)) * b(k) } / { f(b(k)) - f(a(k)) }를 구한 뒤, f(a(k))와 f(c(k))가 같은 부호를 가지고 있는지 확인한다. 만약 같은 부호를 가지고 있다면 다음에 탐색해야 하는 구간은 a(k + 1) = c(k), b(k + 1) = b(k)가 되며, 다른 부호를 가지고 있다면 a(k + 1) = a(k), b(k + 1) = c(k)가 된다. 이 과정을 계산 결과가 0이 되거나, 근사값이 충분히 가까워졌다고 생각될때까지 반복한다.
이 방법은 선형 보간 방법(Linear Interpolation Method)이라고도 알려져 있다. 대부분의 경우, BiSection Method에서 사용된 계산량을 크게 줄일 수 있다. 하지만, 이 방법은 함수값이 특정 구간에서 급격하게 변하는 함수의 경우 좋지 않은 효율을 보일 경우도 있다.
Reference
http://en.wikipedia.org/wiki/False_position_method
False Position Method는 탐색하고자 하는 구간 [a, b]에서 f(a)와 f(b)를 연결하는 직선이 y = 0과 만나는 지점에서부터 탐색을 시작한다. 다음에 선택되는 구간은 f(a)와 f(b)를 연결하는 직선이 y = 0과 만나는 교점 c에서의 함수값 f(c)와 f(b)를 연결하는 직선과, y = 0과의 교점이다. 즉, BiSection Method가 주어진 구간에서 중간점을 구하는 방식으로 근을 탐색하는 것에 비해, 좀 더 효율적으로 근과 가까운 점을 구하여 다음 구간으로 설정한다. 예를 들어, [a, b] 구간에서 False Position Method를 적용하여 근을 구하고자 한다면, f(a(k)), f(b(k))를 구한다. 그리고 보간점 c(k) = { f(b(k)) * a(k) - f(a(k)) * b(k) } / { f(b(k)) - f(a(k)) }를 구한 뒤, f(a(k))와 f(c(k))가 같은 부호를 가지고 있는지 확인한다. 만약 같은 부호를 가지고 있다면 다음에 탐색해야 하는 구간은 a(k + 1) = c(k), b(k + 1) = b(k)가 되며, 다른 부호를 가지고 있다면 a(k + 1) = a(k), b(k + 1) = c(k)가 된다. 이 과정을 계산 결과가 0이 되거나, 근사값이 충분히 가까워졌다고 생각될때까지 반복한다.
이 방법은 선형 보간 방법(Linear Interpolation Method)이라고도 알려져 있다. 대부분의 경우, BiSection Method에서 사용된 계산량을 크게 줄일 수 있다. 하지만, 이 방법은 함수값이 특정 구간에서 급격하게 변하는 함수의 경우 좋지 않은 효율을 보일 경우도 있다.
Reference
http://en.wikipedia.org/wiki/False_position_method
