뿌리를 찾는 이러한 약간 다른 방법으로 인해 다른 결과가 나타나는 이유는 무엇입니까?

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))))으로 줄어 듭니다 (구문이 꺼지면 사과하겠습니다. 내 혀짤임이 매우 녹슬 었습니다). 이로 인해 알고리즘은 변환의 거친 변동에 덜 민감합니다.

그러나 두 번째 것은 (average-damp (lambda (y) (/ x (expt y 2))))을 두 번 적용합니다. 즉, 변환을 한 번 감쇠 한 다음 결과 함수를 반복합니다. average-damp의 한 응용 프로그램은 시퀀스가 ​​분기되지 않도록하기에 충분하지만 실제로 수렴되도록하려면 충분하지 않습니다. 실제로는 진동 상태로 수렴하여 1.672645084943273과 2.8804350135298153 사이를왔다 갔다합니다. 그러나 댐핑 된 변환은 매 단계마다 두 번 적용되므로 fixed-point은 시퀀스가 ​​전체적으로 수렴되지 않더라도 시퀀스의 다른 모든 요소 (하위 시퀀스가 ​​후자로 수렴) 만 봅니다.