ニュートン法とは

この記事ではニュートン法というアルゴリズムについて紹介しています
ニュートン法は、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$におけるグラフの傾き）を表します