2分法

関数を区間を考えたとき，との符号が異なる場合()，区間内に少なくとも1つの解が存在する．区間の中点での関数値を求め，その値の符号がと同じならば，解は内に存在する．このとき，解の存在する区間はになっている．同様にして，の中点での関数値を使うことで，解の存在区間はとなる．この作業を繰り返すことで方程式の解を求める方法を2分法(bisection method)と呼ぶ．

図1 2分法

図1は2分法で近似解を求める手順を示している．現在の解の存在区間をとする．はで初期化される．中点をとする．図1ではであるので，解はに存在するので，とする．次の中点をであり，図1ではであるので，解はに存在する．これを反復して，と求めていく．

2分法の手順を以下に示す．

, とする．
中点における関数値を求める．
の場合，の場合とする．
2に戻る

反復を終了するための収束条件は以下となる．

2分法のコード例を以下に示す．


int bisection(double func(const double), double xl, double xr, double &x, int &max_iter, double &eps)
{
    double f = func(xl);
    double fmid = func(xr);
 
        if(f*fmid >= 0.0) return 0.0;
 
    int k;
    double dx = fabs(xr-xl), xmid;
    for(k = 0; k < max_iter; ++k){
        xmid = 0.5*(xl+xr);            dx *= 0.5;
 
                fmid = func(xmid);
 
                if(dx < eps || fmid == 0.0){
            x = xmid;
            max_iter = k; eps = dx;
            return 1;
        }
 
                if(f*fmid < 0){
            xr = xmid;
        }
        else{
            xl = xmid;
            f = fmid;
        }
    }
 
    max_iter = k; eps = dx;
    return 0;
}

Menu