Почему эти немного разные методы поиска корней дают разные результаты?

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 является фиксированной точкойкарта у -> х / (у ^ 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)))) (извините, если мой синтаксис выключен, мой шлейф очень, очень ржавый).Это делает алгоритм менее восприимчивым к диким флуктуациям преобразования.

Второй, тем не менее, применяет (average-damp (lambda (y) (/ x (expt y 2)))) дважды - то есть, он демпфирует преобразование один раз и затем повторяет полученную функцию.Одного применения average-damp достаточно для предотвращения расхождения последовательности, но недостаточно для ее фактического сближения.Это фактически сходится к колеблющемуся состоянию, подпрыгивая назад и вперед между 1.672645084943273 и 2.8804350135298153.Однако демпфированное преобразование применяется дважды на каждом шаге, поэтому fixed-point видит только все остальные элементы последовательности - эта подпоследовательность сходится к последнему, даже если последовательность в целом не сходится.