为什么这些稍有不同的寻根方法会产生不同的结果？

Question

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

(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的结构和解释的计算机程序。既然我有了正确的方法，我的代码就可以工作了，但我不明白为什么错误的方法是错误的。

Answer 1

本质上的区别在于什么功能被重复了两次。在正确的示例中，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只看到序列的所有其他元素--即子序列收敛到后者，即使序列作为一个整体不能收敛。