ニュートン・ラフソン法

2分法は指定した区間内の解は必ず求めるものの，解の収束は遅い． 関数が連続で微分可能関数であるならば，関数の勾配値を用いることで収束を早めることができる．

解の初期値をとする． での関数の接線は，

となる．この接線が軸と交差する()点は，

を次の近似値として同様の処理を繰り返すことで解に近づいていく．図2はこの手順を示したものである． この方法をニュートン・ラフソン法(Newton-Raphson method)，もしくは単にニュートン法(Newton method)と呼ぶ． ニュートン法の式は以下となる．

反復回数を多くすると限りなくの解に近づく． 反復を終了するための収束条件は，

となる．

ニュートン法は2分法と異なり解のある区間でなく初期近似値1つだけを指定するだけでよく，収束も速い． しかし，だけでなくその微分値も必要で，初期値によっては解へ収束しない場合もある．

図2 ニュートン法

ニュートン法のコード例を以下に示す．

/*!
 * ニュートン・ラフソン法(Newton-Raphson method)
 * @param[in] func 関数値を与える関数ポインタ
 * @param[inout] x 探索開始位置を受け取り，解を返す
 * @param[inout] max_iter 最大反復数(反復終了後,実際の反復数を返す)
 * @param[inout] eps 許容誤差(反復終了後,実際の誤差を返す) 
 * @return 1:成功,0:失敗
 */
int newton(double func(const double), double dfunc(const double), 
           double &x, int &max_iter, double &eps)
{
    double f, df, dx;
    int k;
    for(k = 0; k < max_iter; ++k){
        f = func(x);
        df = dfunc(x);
        x = xn-f/df;

        // 収束判定
        dx = fabs(f/df);
        if(dx < eps || fabs(f) < eps){
            max_iter = k; eps = dx;
            return 1;
        }
    }

    max_iter = k; eps = dx;
    return 0;
}