Pythonプログラミングイントロダクション(3) ニュートンラフソン法ってなんだ?

2019–10–26

前回に引き続き、3章をみていきます。この章は算術プログラムの章で、近似について学べます。 前回は浮動小数点について書きました。今回はニュートンラフソン法についてです。

ニュートンラフソン法とは

ニュートンと同じ時期にラフソンと言う人も同じ手法を発見したのでニュートンラフソン法と言うそうです。

ある関数f(x)があるとき、f(x) = 0となるxの近似値を求める場合を考えます。このとき推定値をguessとしたとき、 下記の値は元々の推定値よりさらに良い近似値になると言う定理がニュートンラフソン法です。

\[ guess - \frac{p(guess)}{p'(guess)} \]

下記は先日1章を読んだときに出てきた25の平方根の近似を求めたプログラムですが、何気にニュートンラフソン法を使っていました。

x = 25
g = 3

while abs(x - g * g) > 1:
    g = (g + x / g) / 2

return g	  

今回の場合だと下記のf(x)の解を求めれば良いことになります。

\[ f(x) = x^2 - 25 \]

つまりニュートンラフソン法により、より良い近似値を求める式は下記になります。この式は上記Pythonプログラムのwhile文中の記述と同じですね。

\[ guess - \frac{guess^2 - 25}{2 * guess} = \frac{guess + \frac{25}{guess}}{2} \]

ニュートンラフソン法の説明についてはこちらのページが非常にわかりやすかったです。 考え方としてはある関数f(x)の近似値を求める時、最初の推定値の時のf(x)の接線とx軸の交点が、最初の推定値よりもより良い推定値になるという考え方です。 式で考えると下記のようになります。まずは接線の傾きを考えます。接線の傾きは関数を微分したものになります。

\[ guessの時の接線の傾き = f'(guess) \]

この接線とy軸との交点をa、x軸との交点をbとしたとき、

\[ f(guess) = f'(guess)guess + a \]

\[ 0 = f'(guess)b + a \]

上記からbを求めると

\[ f(guess) = f'(guess)guess - f'(guess)b \]

\[ b = \frac{f(guess)guess - f(guess)}{f'(guess)} \]

\[ b = guess - \frac{f(guess)}{f'(guess)} \]

これでニュートンラフソン法の式が導かれました。

まとめ

3章の中からニュートンラフソン法について取り上げました。 式で考えるより図で考えた方が非常に直感的でわかりやすいので、是非参考ページも見てみてください。