SICP 1.45

01-31

SICP問題1.45的解答與說明

http://deltam.blogspot.jp/2015/08/sicp145ex145.html

回答之前先來複習一下平均阻尼法和搜尋不動點。

搜尋不動點，尋找的就是x=f(x)這個點。計算y=f(x)，然後計算f(y)得到y，如此反覆。劃成圖則是如下圖紅線那樣的軌跡。

但是這種方法有時無法奏效。如果函數f(x)是圍繞y=x軸對稱的曲線，那麼搜尋不動點的嘗試會沿著同一軌跡不斷循環，無法到達不動點。

這個時候如果使用平均阻尼法，就會使得函數圖像不再圍繞y=x軸對稱了。變形之後，就可以正常搜尋不動點了。

題目中說「這一計算過程對於四次方根卻行不通，一次平均阻尼不足以使對y? $frac{x}{y^3}$ 的不動點搜尋收斂」。但是只有函數圍繞y=x軸對稱的時候才會不收斂。既然已經做了一次平均阻尼，那麼函數圖像已經不是軸對稱的了，實際上是可以收斂的。只是和立方根相比，收斂得非常慢。（一次平均阻尼算四次方根，算百萬次才精確到了0.01的級別。二次平均阻尼的話算百萬次已經變得非常非常精確了）

#lang racketnn(define (square n)n (* n n))nn(define tolerance 0.00001)nn(define (fixed-point f first-guess)n (define (close-enough? v1 v2)n (< (abs (- v1 v2)) tolerance))n (define (try guess)n (let ((next (f guess)))n (if (close-enough? guess next)ntnextnt(try next))))n (try first-guess))nn(define (average . numbers) n (/ (apply + numbers) (length numbers)))nn(define (repeated f n)n (if (= n 1)n (lambda (x) (f x))n (lambda (x) (f ((repeated f (- n 1)) x)))))nn(define (average-damp f)n (lambda (x) (average x (f x))))nn(define (fast-expt b n)n (cond ((= n 0) 1)nt((even? n) (square (fast-expt b (/ n 2))))nt(else (* b (fast-expt b (- n 1))))))nn;(fixed-point ((repeated average-damp 1) (lambda (y) (/ 100000000.0 (fast-expt y 1)))) 1.0)n;(fixed-point ((repeated average-damp 2) (lambda (y) (/ 100000000.0 (fast-expt y 3)))) 1.0)n;(fixed-point ((repeated average-damp 3) (lambda (y) (/ 100000000.0 (fast-expt y 7)))) 1.0)n(fixed-point ((repeated average-damp 4) (lambda (y) (/ 100000000.0 (fast-expt y 15)))) 1.0)n;可見，求解四次方根至少需要兩次平均，求解8次方根需要三次，求解16次方根需要4次平均。n;https://www.zhihu.com/question/28838814n ((repeated ((repeated average-damp 1) (lambda (y) (/ 10.0 (fast-expt y 3)))) 1200002) 100)n;1.7777057962924898n ((repeated ((repeated average-damp 1) (lambda (y) (/ 10.0 (fast-expt y 3)))) 1200001) 100)n;1.7788535796486555nn ((repeated ((repeated average-damp 2) (lambda (y) (/ 10.0 (fast-expt y 3)))) 1200001) 100)n;1.7782794100389228n ((repeated ((repeated average-damp 2) (lambda (y) (/ 10.0 (fast-expt y 3)))) 1200002) 100)n;1.7782794100389228n

為什麼四次方根的一次平均阻尼計算會這麼慢？

搜尋四次方根的不動點的情形如下。進行一次平均阻尼後的函數如圖所示。搜尋不動點的軌跡形成了一個螺旋。

與之相比，進行了兩次平均阻尼後，搜尋不動點的軌跡立刻向距離不動點很近的地方移動。

直觀上也會覺得，肯定是下面的搜尋能更早到達不動點呢。

那麼，什麼曲線能讓搜索早點收斂，對搜尋不動點有利呢？比較上面兩個圖像，可見曲線的最低點的位置（函數極小值）是很重要的。

如果曲線最低點在不動點的右側，那麼搜尋軌跡是螺旋。如果曲線最低點在不動點的左側，那麼很快收斂。也就是說，最低點橫坐標的值<=不動點橫坐標的值即可。