Example5.3

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 を使って、立方根を求める関数を書きなさい。


名前:
コメント:

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2011年02月24日 08:34
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。