📂수치해석

바이섹션 메소드

메소드 ¹

연속함수 $f$ 가 폐구간 $[a,b]$ 에서 $f(a) f(b) < 0$ 이라고 하자. 허용오차는 $\varepsilon$ 이다. $f(c) = 0$ 를 만족하는 $c \in [a,b]$ 는 다음과 같이 구할 수 있다.

---

Step 1.

$$c:= {{a+b} \over {2}}$$

---

Step 2.

$b-c \le \varepsilon$ 이면 $c$ 를 반환한다.

---

Step 3.

$f(b) f(c) < 0$ 이면 $a:=c$, 아니면 $b:=c$ 이라 둔다. 그 후 Step 1. 으로 돌아간다.

설명

중간값 정리의 대표적인 응용으로써, 해가 존재하는 구간을 계속 절반으로 줄여가며 방정식 $f(x) = 0$ 의 근사해를 찾는 방법이다. 당장 해를 구해야하는 방정식이 있는데 아무런 라이브러리도 없다면 즉석에서 짜서 쓸 수도 있을 정도로 간단하다.

주어진 조건이 사실상 폐구간에서 정의된 연속함수라는 것밖에 없다는 점과 사용자가 지정하는 범위 안에서 해를 찾는다는 점이 매력적이지만 수렴차수가 리니어하다는 단점이 있다. 이 때문에 보통 간단한 방정식은 뉴턴-랩슨 메소드를 써서 풀게 된다.

구현

아래는 R로 작성된 예제 코드다.

IVT<-function(f,a,b) {f(a)*f(b)<0}
 
Bisect<-function(f,a,b,tol=10^(-8))
{
  if(!IVT(f,a,b)) {stop("Wrong Interval")}
  
  c<-b
  if (a>b) {b<-a; a<-c}
  
  c=(a+b)/2
  if(abs(f(c))<tol) {return(c)}
  
  while(1)
  {
    c=(a+b)/2 #Step 1.
    if(abs(b-c)<tol) {break} #Step 2.
    if(IVT(f,c,b)) {a=c} else {b=c} #Step 3.
  }
  
  return(c)
}
 
f<-function(x) {x^3 + 8}
Bisect(f,-7,7)
 
g<-function(x) {x^6 - x - 1}
Bisect(g,0,3)
 
h<-function(x) {exp(x)-1 }
Bisect(h,-pi,pi)
Bisect(h,-2,-1)