为什么这些稍微不同的寻根方法会产生不同的结果？
考虑这两种稍微不同的计算五次根的方法：
(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。现在我有了正确的方法，我的代码可以工作，但我不明白为什么我的错误方法是错误的。
Consider these two slightly different methods for computing fifth roots:
(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))
Both attempt to compute fifth roots by an average dampened search for a fixed point, since a fifth root of x is a fixed point of the map y -> x/(y^4). I've defined
(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))))
Trying both methods, we get
> (fifth-root-right 32)
2.000001512995761
> (fifth-root-wrong 32)
2.8804315666156364
Why does the second method give fail to correctly compute fifth roots? Stranger still, if we try this wrong method on fourth or third roots, it works correctly:
(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
For reference, this code attempts to solve Exercise 1.45 in Structure and Interpretation of Computer Programs. Now that I have the right method, my code works, but I don't understand why my wrong method is wrong.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
本质的区别在于哪个函数被重复两次。在正确的例子中，
average-damp应用了两次，最终效果是增加了阻尼；((repeatedaverage-damp 2) f)在数学上减少为(lambda (x) (+ (* 0.75 x) (* 0.25 (fx))))（如果我的语法不对，我很抱歉，我的 lisp 非常非常生疏）。这使得算法不易受到变换的剧烈波动的影响。然而，第二个应用了
(average-damp (lambda (y) (/ x (expt y 2))))两次 - 也就是说，它阻尼变换一次，然后重复结果函数。average-damp的一种应用仅足以防止序列发散，但不足以真正使其收敛。它实际上收敛到振荡状态，在1.672645084943273和2.8804350135298153之间来回反弹。然而，阻尼变换在每一步应用两次，因此定点只能看到序列的所有其他元素 - 该子序列收敛到后者，即使序列作为一个整体未能收敛。The essential difference is in what function is being repeated twice. In the correct one,
average-dampis being applied twice, with the net effect of more damping;((repeated average-damp 2) f)reduces, mathematically, to(lambda (x) (+ (* 0.75 x) (* 0.25 (f x))))(apologies if my syntax is off, my lisp is very, very rusty). This makes the algorithm less susceptible to the wild fluctuations of the transformation.The second one, though, applies
(average-damp (lambda (y) (/ x (expt y 2))))twice - that is, it damps the transformation once and then repeats the resulting function. One application ofaverage-dampis just enough to keep the sequence from diverging but not enough to actually make it converge. It actually converges to an oscillating state, bouncing back and forth between1.672645084943273and2.8804350135298153. However, the damped transformation is applied twice at every step, sofixed-pointonly sees every other element of the sequence - that subsequence converges to the latter, even though the sequence as a whole fails to converge.