2分法の変更点

追加された行はこの色です。
削除された行はこの色です。
2分法へ行く。
2分法の差分を削除


*2分法 [#l8fa53d5]
関数&ref(rf_bisection.eq1.gif,nolink,70%);を区間&ref(rf_bisection.eq2.gif,nolink,70%);を考えたとき，
&ref(rf_bisection.eq3.gif,nolink,70%);と&ref(rf_bisection.eq4.gif,nolink,70%);の符号が異なる場合(&ref(rf_bisection.eq5.gif,nolink,70%);)，区間&ref(rf_bisection.eq2.gif,nolink,70%);内に少なくとも1つの解が存在する．
区間&ref(rf_bisection.eq2.gif,nolink,70%);の中点での関数値&ref(rf_bisection.eq6.gif,nolink,70%);を求め，その値の符号が&ref(rf_bisection.eq4.gif,nolink,70%);と同じならば，
解は&ref(rf_bisection.eq7.gif,nolink,70%);内に存在する．
このとき，解の存在する区間は&ref(rf_bisection.eq8.gif,nolink,70%);になっている．
同様にして，&ref(rf_bisection.eq7.gif,nolink,70%);の中点での関数値を使うことで，解の存在区間は&ref(rf_bisection.eq9.gif,nolink,70%);となる．
この作業を繰り返すことで方程式の解を求める方法を2分法(bisection method)と呼ぶ．


|&ref(bisection.jpg,,100%);|
|CENTER:図1 2分法|


図1は2分法で近似解を求める手順を示している．
現在の解の存在区間を&ref(rf_bisection.eq10.gif,nolink,70%);とする．
&ref(rf_bisection.eq10.gif,nolink,70%);は&ref(rf_bisection.eq2.gif,nolink,70%);で初期化される．
中点を&ref(rf_bisection.eq11.gif,nolink,70%);とする．
図1では&ref(rf_bisection.eq12.gif,nolink,70%);であるので，解は&ref(rf_bisection.eq13.gif,nolink,70%);に存在するので，
&ref(rf_bisection.eq14.gif,nolink,70%);とする．
次の中点を&ref(rf_bisection.eq15.gif,nolink,70%);であり，
図1では&ref(rf_bisection.eq16.gif,nolink,70%);であるので，解は&ref(rf_bisection.eq17.gif,nolink,70%);に存在する．
これを反復して，&ref(rf_bisection.eq18.gif,nolink,70%);と求めていく．

2分法の手順を以下に示す．
+&ref(rf_bisection.eq19.gif,nolink,70%);, &ref(rf_bisection.eq20.gif,nolink,70%);とする．
+中点&ref(rf_bisection.eq21.gif,nolink,70%);における関数値&ref(rf_bisection.eq22.gif,nolink,70%);を求める．
+&ref(rf_bisection.eq23.gif,nolink,70%);の場合&ref(rf_bisection.eq24.gif,nolink,70%);，&ref(rf_bisection.eq25.gif,nolink,70%);の場合&ref(rf_bisection.eq26.gif,nolink,70%);とする．
+2に戻る

反復を終了するための収束条件は以下となる．
#ref(rf_bisection.eq27.gif,nolink,70%)


2分法のコード例を以下に示す．
#code(C){{
/*!
 * 2分法(bisection method)
 * @param[in] func 関数値を与える関数ポインタ
 * @param[in] xl,xr 探索範囲
 * @param[out] x 解
 * @param[inout] max_iter 最大反復数(反復終了後,実際の反復数を返す)
 * @param[inout] eps 許容誤差(反復終了後,実際の誤差を返す) 
 * @return 1:成功,0:失敗
 */
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;
}
}}
2分法 の変更点
