이분법(Bisection method)에 관한 알고리즘 정리

위키백과 <이분법>

위의 설명대로 이분법이다.

이분법 알고리즘은 조건을 만족하는 임의의 두 점 사이에 있는 해를 찾는 것으로,

함수가 연속한다면 수렴하지만, 1차 수렴으로서 속도가 느린 방법이다.

1. 함수 f(x)에서 임의의 두 점 a, b를 선택 (단 f(a)<f(b) and f(a)×f(b)<0 를 만족하는 수)

2. 두 점 a와 b를 양분하는 중심점 f 를 구한다.

3. f(a)×f(f)<0 이면 b를 f로 치환하고 (b=f;) 아닐경우는 a를 f로 치환한다(a=f).

4. f(f) 의 해가 설정해 놓은 값보다 작을경우 계산을 종료한다. 그리고 두 점 a와 b의 차가 설정해 놓은 값보다 작을 경우도 계산을 종료한다.

아래는 좀 정리가 안된 느낌이지만... y=x^2-2의 함수에 대한 소스코드 예시...

완전히 정확한 수는 아니지만, a=1,b=5 를 입력하면 14번째정도에서 얼추 1.414... 가 나온다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <stdio.h> #include <math.h>   double graph(double x); double graph2(double x, double y);   double graph(double x){         return (x*x)-2.0;     }   double graph2(double x, double y){         return graph(x)*graph(y);     }   int main (int argc, const char * argv[]) {       double a,b,c,d,e,k=0;     printf("Input number (f(a)<f(b) and f(a)×f(b)<0):");     while(1){         scanf("%lf %lf",&a,&b);         c = graph(a);         d = graph(b);         e = graph2(a,b);         if(c<d && e<0){             break;           }else{             printf("One more time!\n");         }     }     printf("Scanned data: a:%0.3lf, b:%0.3lf\n",a,b);       double f=0,g;     g=b-a;     while(g>0.0001){ //        printf("start!\n");         f=(a+b)*0.5;                 if(graph2(a,f)<0){             b = f;         }else{             a = f;         }                 if(fabs(graph(f))<0.0001){             break;         }else{             k++;         }         printf("%0.lf\n",k);     }         printf("The solution is %lf\n",f);     return 0; }