SICPを読む(26) 1.3.3(2) 関数の不動点の探索

SICP読んでる人のブログを見ると「楽しい」と言いながら読んでいる人が多い。

こんなに難しい本を読んでいるのに「楽しい」と感じてしまうSICPの魔力は凄いと思う。

SICPはムズいけど、楽しいのだ。

不動点

前回はf(x)=0の時の方程式の解。

今回は「不動点」

f(x)=x

を満たすとき、xを不動点という。

gnuplotで見ると、

gnuplot> plot x

との交点こそが、「不動点」である。

求め方は、

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

こんな感じ。

難しそうだけど、再帰で考えれば簡単。

関数の中に関数があって・・・と、関数の入れ子になってるだけ。

収束すれば、不動点が出る。発散したり、振動すると無限ループになるので要注意。

コーディング

理論がわかった所で早速コーディングに入る。

(define tolerance 0.0001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

nextをあらかじめ求めているので、ちょっとわかりにくい。

cosの不動点

探索してみよう。

(fixed-point cos 1.0) ; 0.7390547907469174

むむ・・・。本当に不動点なのだろうか・・・。gnuplotで確認してみる。

gnuplot> plot x
gnuplot> replot cos(x)

replotで前回のグラフと重ね合わせが出来るみたい。

右クリックでどんどん拡大すると、大体0.73あたり。間違いなさそうです。

sin(y) + cos(y)の不動点

(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0)

再び、gnuplot

gnuplot> plot x
gnuplot> replot sin(x) + cos(x)
gnuplot> replot cos(x)

cosと重ねると、位相のズレが確認出来ます。gnuplot便利っすね!!

平方根の不動点

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))
(sqrt 2)

無限ループ。

なので、平均緩和法を使う。

両辺にyを足して2で割ることで、緩い近似を作る。

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y))) 1.0))
(sqrt 2) ; 1.4142

2点の間を取ることで、うまく探索出来ました。

ステップ数については練習問題で考察することにします。