Newton法 - haskonの日記

章1.1.3にでてくるNewton法をやってみます。
Newton法とは、数xの平方根の値の予測値yがあれば、yとx/yの平均値とるという計算でさらにより路側値が得られるというものらしい。
とりあえず、本どおりに実装。

goodEnough guess x = (abs ( x - (guess * guess) )) < 0.001
improve guess x = (( x / guess ) + guess) / 2
sqrtIter guess x 
	|goodEnough guess x = guess
	|otherwise = sqrtIter ( improve guess x ) x
sqrt' x = sqrtIter 1 x

 *Main> sqrt' 3
 1.7321428571428572
 *Main> sqrt' 4
 2.0000000929222947

このやりかたでは、非常に大きい値や小さいあたいではうまくいかないらしいので、guessの変化に注目し、変化が予測値にくらべ非常に小さくなったときに停止するように作ろうというのが問題1.7。自分なりの実装。

sqrt' x = sqrtIter 1 x
goodEnough17 guess x = (abs ( 1( guess - ( improve guess x ))) < 0.0001
sqrtIter17 guess x
	|goodEnough17 guess x = guess
	|otherwise = sqrtIter17 ( improve guess x ) x
sqrt17 x = sqrtIter17 1.0 x

で、確認のためにnobsunさんのschemeでの解答を見てみると、ちょっと違う。実際に動かしてみると

 *Main> sqrt17 4
 2.0000000929222947
 *Main> sqrt17 1.0E-6
 1.0338412392442034e-3
 *Main> sqrt17 1.0E29
 3.162277660168379e14

大きい値(1.0E29)ならいっしょだが、小さい値(1.0E-6)だとダメみたい。そうか。このやりかただと、小さい値にたいして、差が小さい値とはいえないのね。なので、実装を直してみる。

goodEnough17 guess x = (abs ( 1 -( guess / ( improve guess x )))) < 0.0001
sqrtIter17 guess x
	|goodEnough17 guess x = guess
	|otherwise = sqrtIter17 ( improve guess x ) x
sqrt17 x = sqrtIter17 1.0 x
 *Main> sqrt17 1.0E-6
 1.0000001533016628e-3

これで大丈夫。問題1.8は、立方根版の実装。近似の式は、

   x/y^2+2y
   --------
      3

となるらしい。実装は、

improve18 guess x = ( ( x / (guess * guess) ) + (2 * guess)) / 3
goodEnough18 guess x = (abs ( 1-(guess / ( improve18 guess x )))) < 0.0001
qubicroot guess x 
	| goodEnough18 guess x = guess
	| otherwise = qubicroot ( improve18 guess x ) x
qubic x = qubicroot 1.0 x

 *Main> qubic 2
 1.259933493449977
 *Main> qubic 8
 2.000004911675504

nobsunさんの結果とあわないなぁ。近似の式の書き方がちがうからか。自分の解釈ならこういう式になったんだけど。naoya_tさんの解答も式が違うし。どれが正しいんだろう？