Posted on 2007-05-15 18:44
dennis 閱讀(720)
評論(0) 編輯 收藏 所屬分類:
計(jì)算機(jī)科學(xué)與基礎(chǔ)
本節(jié)內(nèi)容介紹了將高階過程用于一般性過程，舉了兩個例子：區(qū)間折半查找方程根和找出函數(shù)不動點(diǎn)。習(xí)題也是圍繞這兩個問題展開。今天工作上遇到了比較郁悶的事情，這周末確定要加班，心情實(shí)在糟糕!-_-，先做兩題吧，有空再繼續(xù)。
習(xí)題1.35，證明黃金分割率φ是變換x->x+1/x的不動點(diǎn)，并利用這個事實(shí)通過過程fixed-point計(jì)算出φ
值。
這道題目很簡單了，根據(jù)黃金分割的定義，φ滿足方程：φ的平方=φ+1；兩邊同除以φ，得到方程：
φ=φ+1/φ。根據(jù)函數(shù)不動點(diǎn)定義f(x)=x，可以得到φ就是變換x->x+1/x的不動點(diǎn)。利用fixed-point過程寫出：
(fixed-point (lambda (x) (+ x (/ 1 x))) 1.0)
習(xí)題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)的不動點(diǎn)，并比較平均阻尼方式和非平均阻尼方式的計(jì)算步數(shù)。
首先，請看非平均阻尼方式(直接看截圖了)，我們以2作為初始猜測值：
可以看到，非平均阻尼方式執(zhí)行了33步才計(jì)算出了x值。
再看平均阻尼方式，方程x=log(1000)/log(x)可以轉(zhuǎn)化為：
x=(1/2)(x+log(1000)/log(x))
看看結(jié)果：
僅僅執(zhí)行了9步就完成了計(jì)算，大概是非平均阻尼方式的1/3(在不同機(jī)器上可能結(jié)果不同，可平均阻尼一定快于不用平均阻尼）。
由此可見：使用平均阻尼技術(shù)比不用平均阻尼技術(shù)收斂的快得多。