Posted on 2007-05-15 18:44
dennis 閱讀(715)
評論(0) 編輯 收藏 所屬分類:
計算機科學與基礎
本節內容介紹了將高階過程用于一般性過程，舉了兩個例子：區間折半查找方程根和找出函數不動點。習題也是圍繞這兩個問題展開。今天工作上遇到了比較郁悶的事情，這周末確定要加班，心情實在糟糕!-_-，先做兩題吧，有空再繼續。
習題1.35，證明黃金分割率φ是變換x->x+1/x的不動點，并利用這個事實通過過程fixed-point計算出φ
值。
這道題目很簡單了，根據黃金分割的定義，φ滿足方程：φ的平方=φ+1；兩邊同除以φ，得到方程：
φ=φ+1/φ。根據函數不動點定義f(x)=x，可以得到φ就是變換x->x+1/x的不動點。利用fixed-point過程寫出：
(fixed-point (lambda (x) (+ x (/ 1 x))) 1.0)
習題1.36解答：
首先修改fixed-point過程，使它輸出每次猜測的近似值：
(define tolerance 0.00001)
(define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance))
(define (try f guess)
(newline)
(display guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try f next))))
(define (fixed-point f first-guess)
(try f first-guess))
使用了newline和display基本過程，然后要求x->log(1000)/log(x)的不動點，并比較平均阻尼方式和非平均阻尼方式的計算步數。
首先，請看非平均阻尼方式(直接看截圖了)，我們以2作為初始猜測值：
可以看到，非平均阻尼方式執行了33步才計算出了x值。
再看平均阻尼方式，方程x=log(1000)/log(x)可以轉化為：
x=(1/2)(x+log(1000)/log(x))
看看結果：
僅僅執行了9步就完成了計算，大概是非平均阻尼方式的1/3(在不同機器上可能結果不同，可平均阻尼一定快于不用平均阻尼）。
由此可見：使用平均阻尼技術比不用平均阻尼技術收斂的快得多。