이분법(비선형 방정식의 수치 해법)

이분법이란?


  • 비선형 방정식의 수치 해법 중 하나

  • 중간값 정리 : 닫힌 구간 $[a,b]$에서 연속 함수 $f(x)$ 에서 $f(a)f(b)<0$ 이라면 $f(\alpha)=0$ $\alpha $는 구간 $ [a, b] $ 내에 있습니다
  • $f(a)f(b)<0$가 되는 $a,b$ 를 찾아, 중점 $c=(a+b)/2$를 새로운 끝점으로서 계산을 반복한다.



  • 산법



    초기값



    $x_{a_0},x_{b_0}$ : 적절한 방법으로 결정한다. 그러나 $f(x_{a_0})f(x_{b_0})<0$

    반복 절차



    $x_{c_n}=(x_{a_n}+x_{b_n})/2$ $,$ $(n=1,2,\cdots)$
    $f(x_{c_n})f(x_{a_n})<0$이면 $x_{a_{n+1}}=x_{a_n}$ $,$ $x_{b_{n+1}} =x_{c_n}$
    $f(x_{c_n})f(x_{a_n})>0$이면 $x_{a_{n+1}}=x_{c_n}$ $,$ $x_{b_{n+1}} =x_{b_n}$

    정지 규칙



    $|x_{a_n}-x_{b_n}|<\varepsilon$일 때 반복 중지
    그러나,$\varepsilon$은 적당하게 준다.

    샘플 코드



    $f(x)=x^2-1$ , 초기값 $a=0.5,b=2$로 이분법을 사용하여 해를 구하는 프로그램.
    $f(a)f(b)<0$ 의 확인이나 넣지 않은 거버가바코드

    bisection_method.c
    #include<stdio.h>
    #include<math.h>
    
    double f (double x) {
      return x*x-1;
    }
    
    double bisection_method (double a, double b) {
      double c;
      while (fabs(a - b) > 1e-10) {
        c = (a + b) / 2;
        if (f(c) == 0) { break; }
        if (f(a) * f(c) < 0) { b = c; }
        if (f(a) * f(c) > 0) { a = c; }
      }
      return c;
    }
    
    int main (void) {
      double alpha;
      alpha = bisection_method(0.5, 2);
      printf("%f\n", alpha);
      return 0;
    }
    

    실행 결과
    1.000000
    

    특징


  • $f^{\prime}(x)$ 계산 불필요
  • 쉽고 직관적 인

  • 반드시 해에 수렴
  • 연속이면 반드시 해에 수렴

  • 오차는 구간폭 이하($|x_b-x_a|$)
  • 초기값 2개 필요

  • Newton법 , 할선법에 비해 반복 횟수가 증가
  • 수렴 속도: 1차
  • 한 번의 계산으로 구간이 절반이됩니다 = 오차가 절반이됩니다

  • 좋은 웹페이지 즐겨찾기