2

考虑这两种稍微不同的计算第五根的方法：

(define (fifth-root-right x)
  (fixed-point-of-transform (lambda (y) (/ x (expt y 4)))
                            (repeated average-damp 2)
                            1.0))

(define (fifth-root-wrong x)
  (fixed-point (repeated 
                (average-damp (lambda (y) (/ x (expt y 4)))) 
                2)
               1.0))

两者都试图通过对固定点的平均衰减搜索来计算第五个根，因为 x 的第五个根是映射 y -> x/(y^4) 的一个固定点。我已经定义

(define (average-damp f)
  (lambda (x) (average x (f x))))
(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)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))
(define (repeated f n)
  (if (= n 1) 
      f
      (compose f (repeated f (- n 1)))))
(define (compose f g) (lambda (x) (f (g x))))

尝试这两种方法，我们得到

> (fifth-root-right 32)
2.000001512995761
> (fifth-root-wrong 32)
2.8804315666156364

为什么第二种方法无法正确计算第五个根？更奇怪的是，如果我们在第四或第三根上尝试这种错误的方法，它会正常工作：

(define (fourth-root x)
  (fixed-point (repeated 
                (average-damp (lambda (y) (/ x (expt y 3)))) 
                2)
               1.0))

(define (cube-root x)
  (fixed-point (repeated 
                (average-damp (lambda (y) (/ x (expt y 2)))) 
                2)
               1.0))


> (fourth-root 16)
1.982985155172348
> (cube-root 8)
2.0000009087630515

作为参考，此代码尝试解决计算机程序的结构和解释中的练习 1.45。现在我有了正确的方法，我的代码可以工作，但我不明白为什么我的错误方法是错误的。

4

1 回答 1

3

本质区别在于重复两次的功能。在正确average-damp的情况下，应用了两次，最终产生了更多的阻尼效果；((repeated average-damp 2) f)在数学上减少到(lambda (x) (+ (* 0.75 x) (* 0.25 (f x))))（如果我的语法关闭，我很抱歉，我的 lisp 非常非常生锈）。这使得算法不太容易受到变换的剧烈波动的影响。

但是，第二个应用(average-damp (lambda (y) (/ x (expt y 2))))了两次——也就是说，它抑制了一次转换，然后重复生成的函数。的一种应用average-damp仅足以防止序列发散，但不足以使其真正收敛。1.672645084943273它实际上收敛到一个振荡状态，在和之间来回弹跳2.8804350135298153。然而，阻尼变换在每一步都应用了两次，因此fixed-point 只能看到序列的每个其他元素——即使序列作为一个整体未能收敛，子序列也会收敛到后者。

于 2011-02-23T02:54:32.630 回答