📈

ニュートン法とは

1 min read 1

この記事ではニュートン法というアルゴリズムについて紹介しています
ニュートン法は、golangのチュートリアルで登場するのですが何を言っているのかよくわからなかったのでまとめてみました。
ニュートン法は\sqrt{2}など本来値を求められない無理数の値をコンピューターを用いて近似的に求めるのに求めるためのアルゴリズムです。

ニュートン法とは

ニュートン法とはxが実数の時

f(x) = 0

となるxを求めるときに、x_1に適当な値をとったときに次の漸化式[1]を使うとxを求められる(xの解に収束する)というものです。[2]

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

問題

\sqrt{2}を計算で求めなさい・

解法

求める解をxと置くと次の式が成り立ちます。

x^2 = 2

そのため、これを関数に置き換えると次のようになります。

f(x) = x^2 - 2

そして求めるのは次の式を満たすxの値です。

f(x)=0

これは先程登場したf(x)=0の形になっているのでニュートン法を使うことができます。
はじめにf(x)の導関数を求めると

f'(x)=2x

となり、漸化式は

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \\ x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}\\ x_{n+1}=\frac{1}{2}(x_n+\frac{2}{x_n})

となります
じっさいに、x_1=1としてx_{10}まで試してみると

1.5 2.25
1.4166666666666665 2.006944444444444
1.4142156862745097 2.0000060073048824
1.4142135623746899 2.0000000000045106
1.414213562373095 1.9999999999999996
1.414213562373095 1.9999999999999996
1.414213562373095 1.9999999999999996
1.414213562373095 1.9999999999999996
1.414213562373095 1.9999999999999996
1.414213562373095 1.9999999999999996
1.414213562373095
コード
func Sqrt(x float64) float64 {
        xn := float64(1)
        for i := 0; i < 10; i++ {
                xn = (0.5)*(xn+x/xn)
                fmt.Println(xn, xn*xn)
        }
        return xn
}

いい感じの精度で求められていることがわかります。

脚注
  1. 前の項から次の項を求める式 ↩︎

  2. f'(x)f(x)の導関数(xにおけるグラフの傾き)を表します ↩︎

Discussion

Hidden comment
ログインするとコメントできます