2分法 (bisection method)

2分法(bisection method)とは

f(x) = 0の解を求める方法の1つ

考え方

例えば以下のような多項式方程式があったとする。

上記の式の解を求めたい。こんな場合に使えるのが2分法。(ただし、速度は遅い)
2分法では次のような手順で求める。

• 適当な2点a,bを決める
• 線分a,bの中点cをとる
• f(c) > 0ならc → bに、f(c) < 0なら c → aに置き換える
• 手順2,3を繰り返す

イメージ

実装

手順1〜4をC言語に落とし込めばOK

/* f(x) */
double f( double x ) {
    return exp(x) - x * x - 2.0;
}

・・・

    do {
        c = (a + b) * 0.5;
        if ( f(c) * f(a) < 0.0 ) {
            b = c;
        } else {
            a = c;
        }
    } while( fabs(b-a) > 1.0e-12 );