メメメモモ

プログラミング、筋トレ、ゲーム、etc

ニュートン・ラフソン法

ニュートン・ラフソン法(ニュートン法)は、関数f(x)とx軸が交わる点の近似値を反復計算により得る方法です。
この方法を用いる際の注意点は次のようなものです。

  • 関数f(x)がx軸と交わる
  • 定義域の範囲で微分可能(接線が引ける)
  • 接線がx軸と交わる
  • 適切な初期値を与える


上記の条件を満たす必要があります。


ニュートン・ラフソン法のアルゴリズムの流れは次のようになります。

  1. 初期値x0を与える
  2. 座標(x0, f(x0))を通る接線とx軸の交点を得る。この交点をx1とする
  3. x1を初期値として、処理を繰り返す


初期値から、接線とx軸の交点を求める式が次のようになります。
x_{n+1}=x_n - \frac{f(x_n)}{f^\prime(x_n)}


この式を使用して新たな接線とx軸の交点を繰り返し求めていきます。

f(x)=x^2-2の解を求める

f(x)=x^2-2の解を求めます。
プログラムを書く前に毎段階として、f^\prime(x)を求めて、式に代入します。
x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n}


この式を用いて解を求めるのが次のプログラムになります。

#!/usr/bin/env perl                                                             
use strict;
use warnings;

newton_method(1, 100);

sub newton_method {
    my ($SHOKITI, $KURIKAESHI) = @_;
    my $x_p = $SHOKITI;
    my $x_s;

    for my $i (0..$KURIKAESHI) {
        $x_s = $x_p - ($x_p*$x_p - 2) / (2 * $x_p);
        print $i . " : " . $x_p . " -> " . $x_s . "\n";
        if (abs($x_s - $x_p) < 0.000000001) {
            print "精度の限界まで計算しました。\n";
            last;
        }
        $x_p = $x_s;
    }
}


結果は出力は下記のようになりました。

0 : 1 -> 1.5
1 : 1.5 -> 1.41666666666667
2 : 1.41666666666667 -> 1.41421568627451
3 : 1.41421568627451 -> 1.41421356237469
4 : 1.41421356237469 -> 1.4142135623731
精度の限界まで計算しました。