ニュートン法を使って、平方根を求めるアルゴリズムを書いてみよう

Goのプレイグラウンドで遊んでたら、フロー制御の章でニュートン法を使って平方根を求めましょう( A Tour of Go )と言われたので調べた。

ニュートン・ラフソン法(Newton-Raphson method)ともいう。

与えられた関数 $f$ について $f(x)=0$ になる $x$ の近似解を求める方法である。

例えば、 $x^2-2=0$ の解である $\sqrt{2}$ は無理数(1.41421356...)である。有効桁数があるコンピューターは、この値を誤差なく持つことは不可能であるが、ニュートン法を用いて計算を繰り返すことで、型が持つ有効桁数の範囲で解に近い値を求めることができる。

やってみよう

Goの問題は、引数として与えられる数( $k$ とする)の平方根( $x$ とする)を求めるアルゴリズム sqrt(k float64)(x float64) を書くというものである。ニュートン法を使って解いてみよう。

引数として与えられた $k$ の平方根 $x$ を求めることから、

$k = x^2$ 　より

$x^2 - k = 0$ という方程式を解けば平方根が求まる。

$k = 2$ のときを例に解法を説明する。以下は $x^2 - 2$ の曲線とその接線のグラフである。接線は解 $x$ ( $= \sqrt{ 2 }$ )よりも大きな値を適当にとり( $\displaystyle x_0$ とする)、引いた。

f:id:bambinya:20170124225900p:plain

上の図から分かるように、接線の $x$ 切片 $\displaystyle x_1$ は、 ${\displaystyle x_0} {\displaystyle \gt} {\displaystyle x_1} {\displaystyle \gt} x(= \sqrt{ 2 } )$ という値をとる。この性質を使い、次は $\displaystyle x_1$ を元に曲線の接線を引き、 $x$ 切片を求める。これを繰り返すことで、真の解に近づけていく。反復回数が多いほど精度が上がっていく。グラフでは下記のようになる。