読者です 読者をやめる 読者になる 読者になる

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

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 切片を求める。これを繰り返すことで、真の解に近づけていく。反復回数が多いほど精度が上がっていく。グラフでは下記のようになる。

 

f:id:bambinya:20170124231411p:plain

 

この反復処理は、 \displaystyle x_1  \displaystyle x_0 で表す漸化式を求めるとfor文で書ける。

 \displaystyle x_1  \displaystyle x_0 で表す式を求める。

接線の傾きは微分で求められる。

 f(x) = x^2 - k

 f'(x) = 2x

 \displaystyle x_0 の時の接線の傾きは 2\displaystyle x_0 であり、これはyの変化量をxの変化量で割ったものと等しい。下記を参照のこと。

 

f:id:bambinya:20170124223222p:plain

 

式にすると、

 2\displaystyle x_0 = \frac{\displaystyle x_0^2 - k} {\displaystyle x_0 - \displaystyle x_1}

両辺に {\displaystyle x_0 - \displaystyle x_1}をかけて整理すると、以下の式が得られる。

 \displaystyle x_1 = \frac{\displaystyle x_0^2 + k}{2\displaystyle x_0}

( \displaystyle x_1  \displaystyle x_0 で表す漸化式。 k is given.)

この漸化式を用いて、Goでfor文を書くと次のようになる。

 

関数とループを使った簡単な練習として、 ニュートン法 を使った平方根の計算を実装してみましょう。( ...

 

おしまい。