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

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

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

Answer 1

本质的区别在于哪个函数被重复两次。在正确的例子中，average-damp 应用了两次，最终效果是增加了阻尼； ((repeatedaverage-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 之间来回反弹。然而，阻尼变换在每一步应用两次，因此定点只能看到序列的所有其他元素 - 该子序列收敛到后者，即使序列作为一个整体未能收敛。