1.36

练习 1.36 请修改 fixed-point，使它能打印出计算中产生的近似值序列，用练习 1.22 展示的 newline 和 display 基本过程。而后通过找出$x\mapsto log(1000)/log(x)$的不动点的方式，确定$x^x=1000$的一个根（请利用 Scheme 的基本过程 log，它计算自然对数值）。请比较一下采用平均阻尼和不用平均阻尼的计算步数。（注意，你不能用猜测 1 去启动 fixed-point，因为这将导致除以 log(1)=0。)

令 $f = log(1000)/log(x)$，要找出不动点，可以通过从某个初始猜测出发，反复地应用 f：

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

直到值的变化不大时，就可以找到它的一个不动点。

不使用平均阻尼技术

(define tolerance 0.00001)

(define (fixed-point f x)

(define (close-enough? v1 v2)

(< (abs (- v1 v2)) tolerance))

(define (iteration f x count)

(display count)

(display " guess x = ")

(display x)

(newline)

(if (close-enough? x (f x))

x

(iteration f (f x) (+ count 1))))

(iteration f x 0))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 100)

使用平均阻尼技术

$x \mapsto log(1000)/log(x)$

$$x + x \mapsto log(1000)/log(x) + x$$

$$(x + x) / 2 \mapsto (log(1000)/log(x) + x) / 2$$

$$x \mapsto (log(1000)/log(x) + x) / 2$$

(define tolerance 0.00001)

(define (fixed-point f x)

(define (close-enough? v1 v2)

(< (abs (- v1 v2)) tolerance))

(define (iteration f x count)

(display count)

(display " guess x = ")

(display x)

(newline)

(if (close-enough? x (f x))

x

(iteration f (f x) (+ count 1))))

(iteration f x 0))

(fixed-point (lambda (x) (/ (+ x (/ (log 1000) (log x))) 2)) 100)

结论

可以看出，使用了平均阻尼技术之后，计算步数比不使用平均阻尼技术的计算步数少了三分之二左右！