5.3 例 : 関数の不動点探索

数 x は次の条件を満たす時に、関数 f の 不動点 と呼ばれます。

f(x) = x .

いくつかの関数 f では、初期推定値から始めて、値が変化しなくなる (あるいは変化が小さな許容量以下になる) まで f を繰り返し適用することで不動点を求めることができます。それは、数列

x, f(x), f(f(x)), f(f(f(x))), ...

が、f の不動点に収束すれば可能です。このアイデアを取り入れたのが次の「不動点を求める関数」です。

val tolerance = 0.0001 def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance def fixedPoint(f: Double => Double)(firstGuess: Double) = { def iterate(guess: Double): Double = { val next = f(guess) if (isCloseEnough(guess, next)) next else iterate(next) } iterate(firstGuess) }

このアイデアを平方根を求める関数の再設計に応用します。sqrt の仕様から始めましょう。

sqrt(x) = y ただし y * y = x = y ただし y = x / y

したがって sqrt(x) は関数 y=> x / y の不動点です。このことは sqrt(x) は不動点の反復で計算できることを示しています。

def sqrt(x: double) = fixedPoint(y => x / y)(1.0)

しかし実際にやってみると、計算は収束しないことが分かります。現在の推定値を追跡する print 文付きの不動点関数を実装してみます。

def fixedPoint(f: Double => Double)(firstGuess: Double) = { def iterate(guess: Double): Double = { val next = f(guess) println(next) if (isCloseEnough(guess, next)) next else iterate(next) } iterate(firstGuess) }

すると sqrt(2) は次のようになります。

2.0 1.0 2.0 1.0 2.0 ...

このような振動を抑える一つの方法は、推定値の急激な変化を防ぐことです。これは元の数列上で、続く値を 平均 すれば可能です。

scala> def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0) sqrt: (Double)Double scala> sqrt(2.0) 1.5 1.4166666666666665 1.4142156862745097 1.4142135623746899 1.4142135623746899

実際、fixedPoint 関数を展開すると、前に 4.4 節で定義した不動点の定義と全く同じになります。

前の例では、もし関数を引数として渡すことができれば、言語の表現力が大幅に強化される、ということを示しました。次の例では、関数を返す関数もたいへん有用であることを示します。

不動点の繰り返しをもう一度考えてみましょう。√(x) が関数 y => x / y の不動点であることから始めました。次いで、続く値を平均することで繰り返しを収束させました。この 平均による減衰 というテクニックは一般的ですから、別の関数で包むことにします。

def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

averageDump を使って、平方根関数を次のように再設計できます。

def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)

Exercise 5.3.1 Write a function for cube roots using fixedPoint and averageDamp. } これはアルゴリズムの要素を可能な限り明確に表現しています。

演習 5.3.1 fixedPoint と averageDump を使って、立方根を求める関数を書きなさい。