2

5 乗根を計算するための次の 2 つのわずかに異なる方法を検討してください。

(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 の 5 乗根は写像 y -> x/(y^4) の不動点であるため、どちらも不動点の平均減衰検索によって 5 乗根を計算しようとします。定義しました

(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

2 番目の方法で 5 乗根を正しく計算できないのはなぜですか? 奇妙なことに、この間違った方法を 4 乗根または 3 乗根で試しても、正しく機能します。

(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を解こうとしています。正しい方法ができたので、コードは機能しますが、間違った方法が間違っている理由がわかりません。

4

1 に答える 1

3

本質的な違いは、どの関数が 2 回繰り返されるかです。正しいものでaverage-dampは、 が 2 回適用され、正味の減衰効果が大きくなります。((repeated average-damp 2) f)数学的には(lambda (x) (+ (* 0.75 x) (* 0.25 (f x))))(私の構文が間違っている場合は申し訳ありません。私の Lisp は非常に錆びています)。これにより、アルゴリズムは変換の激しい変動の影響を受けにくくなります。

ただし、2 番目のものは(average-damp (lambda (y) (/ x (expt y 2))))2 回適用されます。つまり、変換を 1 回減衰させてから、結果の関数を繰り返します。を 1 回適用するaverage-dampだけで数列が発散しないようにするのに十分ですが、実際に収束させるには十分ではありません。実際には振動状態に収束し、 と の間を行ったり来たりし1.672645084943273ます2.8804350135298153。ただし、減衰変換はすべてのステップで 2 回適用されるためfixed-point 、シーケンスの他のすべての要素のみが表示されます。シーケンス全体が収束に失敗しても、そのサブシーケンスは後者に収束します。

于 2011-02-23T02:54:32.630 に答える