二分法

説明

$f(x)=0$の重根ではない解が$x$のある区間$(a,b)$でただ一つだけ存在しているものとする。
方程式の解$a$は区間$(a,b)$の間にあるので、

$$\begin{array}{r}f(a)・f(b)<0\end{array}$$

区間$(a,b)$の中点を$c$とすると、

$$\begin{array}{r}c=\frac{a+b}{2}\end{array}$$ $$\begin{array}{r}f(a)・f(c)<0であれば、解aは区間(a,c)に存在\\ f(b)・f(c)<0であれば、解aは区間(c,b)に存在\end{array}$$

$f(a)f(c)<0$であれば、区間$(a,c)$について中点をとり、$f(b)f(c)<0$であれば、区間$(c,b)$について中点をとるというように繰り返し中点を取り、解の存在する区間を狭めていく。

区間が十分狭くなるまで、この作業を続ける。

$$\begin{array}{r}|b-a|<ϵ\end{array}$$

フローチャート

以下は二分法のフローチャートの例である。

プログラム

以下はC言語での二分法の例である。

#include <stdio.h>
#include <math.h>
 
#define EPS .0001
 
double nibun(double, double);
double func_y(double);
 
int main(int argc, char **argv)
{
    double a = 0.0, b = 1.0;
    double x;
 
    printf("initial value a=%6.3lf\n", a);
    printf("initial value b=%6.3lf\n", b);
    x = nibun(a, b);
    printf("x=%6.3lf\n", x);
 
    return 0;
}
 
double nibun(double a, double b)
{
    double c;
    do {
        c = (a + b) / 2.0;
        if ((func_y(c) * func_y(a)) < 0.0)
            b = c;
        else
            a = c;
    } while (fabs(a - b) > EPS);
    return (c);
}
 
double func_y(double x)
{
    double y;
    y = pow(x, 3.0) + x - 1.0;
    return (y);
}