不動点探し

SICP を飛ばし飛ばし読んでいる。これは、不動点を求める関数を使って平方根を求める、というもの。以下は適当メモ。

関数 f の不動点とは、 x = f x となるような x のこと。ここで y^2 = x という式を考えると、例えば sqrt 2 は、 y^2 = 2 となるような y を求めることになる。 この式を y = x/y と変形し、さらに y = (¥a -> x / a) y と変形すると、(¥a -> x / a) という関数の不動点を求めることが、a の平方根を求めることになることがわかる。

ところが、(¥a -> x / a) の不動点をそのまま求めようとすると、無限ループに陥ってしまう。なので、 y = x/y を少し変形して、 (y+y)/2 = (y+x/y)/2 としてみる。つまり、 y = (¥a -> (y+x/a)/2) y である。これだとループに陥らずに値を求めることができる。

fixpoint f init accu = g $ iterate f init
    where g (a:b:cs) | abs (a-b) > accu = g (b:cs)
                     | otherwise        = a

mysqrt x = fixpoint (\y -> (y+x/y)/2) 1 0.0000000001

Main> mysqrt 2
1.4142135623746899
Main> sqrt 2
1.4142135623730951
Main>