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 被应用了两次，具有更多阻尼的净效应； ((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 只看到序列的每个其他元素 - 该子序列收敛到后者，即使序列作为一个整体未能收敛。