暇なので復習するシリーズ

問題 1.36

問題1.22で示した基本のnewlineとdisplayを使い、 生成する近似値を順に印字するようfixed-pointを修正せよ。

(define (average x y)
  (/ (+ x y) 2))

(define tolerance 0.00001)

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

let の次に guess を出力する display と、１行に１つずつ値を表示したいので newline を入れます。

次にx log(1000)/log(x)の不動点を探索することで、x^x = 1000の解を見つけよ。

(define (ex1-36a)
  (fixed-point (lambda (x) (/ (log 1000) (log x))) 5))

そのまま書けば完成です。
4^4 = 256、5^5 = 3125 なので、x^x = 1000 の解は 4.xxx になると予想できます。
したがって予測値の初期値は 4 か 5 にするのが適切でしょう。

gosh> (ex1-36a)
5
4.29202967422018
4.741863119908242
4.438204569837609
4.635299887107611
4.50397811613643
4.589989462723705
4.53301150767844
4.570475672855484
4.545720389670642
4.562024936588171
4.551263234080531
4.55835638768598
4.553676852183342
4.55676216434628
4.554727130670954
4.556069054770006
4.555184018843625
4.5557676565438205
4.555382746639082
4.55563658243586
4.555469180245326
4.555579577900997
4.5555067722873686
4.5555547860484085
4.555523121789556
4.555544003742869
4.555530232469306
4.555539314360711

x^x = 1000 の解は x ≒ 4.555539314360711 です。

検証してみます。

gosh> (expt 4.555539314360711 4.555539314360711)
1000.0090819416978

平均緩和を使った時と使わない時のステップ数を比べよ。

(define (ex1-36a)
  (fixed-point (lambda (x) (/ (log 1000) (log x))) 5))

(define (ex1-36b)
  (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 5))

ex1-36a が平均緩和法を使わない版、ex1-36b が使う版です。

gosh> (ex1-36a)
5
4.29202967422018
4.741863119908242
4.438204569837609
4.635299887107611
4.50397811613643
4.589989462723705
4.53301150767844
4.570475672855484
4.545720389670642
4.562024936588171
4.551263234080531
4.55835638768598
4.553676852183342
4.55676216434628
4.554727130670954
4.556069054770006
4.555184018843625
4.5557676565438205
4.555382746639082
4.55563658243586
4.555469180245326
4.555579577900997
4.5555067722873686
4.5555547860484085
4.555523121789556
4.555544003742869
4.555530232469306
4.555539314360711

gosh> (ex1-36b)
5
4.64601483711009
4.571611286076025
4.558294317536066
4.556006022881116
4.555615799731297
4.555549342575593
4.555538027101999
4.5555361005218895

平均緩和法を使用すると明らかにステップ数が少なくなっている事が確認できます。
「平均緩和法を使用すると不動点探索で収束を助けることが多い」を実証しました。