理系学生日記

おまえはいつまで学生気分なのか

問題1-45

n乗根の計算で、平均緩和を何回かしないと収束しないことがあるらしい。
こんなの作ってしらべた。

(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)))
      (display guess)
      (newline)
      (if (close-enough? guess next)
	  next
	  (try next))))
  (try first-guess))

(define (average-damp f)
  (lambda (x)
    (/ (+ x (f x)) 2)))

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define (repeated f n)
  (define (sub-repeated n)
    (if (= n 0)
	f
	(compose f (sub-repeated (- n 1)))))
  (lambda (x)
    ((sub-repeated (- n 1)) x)))

(define (n-average-damping-root n m x first-guess)
  (fixed-point ((repeated average-damp m)
		(lambda (y)
		  (/ x (expt y (- n 1)))))
	       first-guess))

これで、n-average-damping-rootに対して、xを2^nに、first-guessを1.0にしたときの結果がこちら。

n 収束するための平均緩和必要回数
3 1
4 2
5 2
6 2
7 2
8 3
9 3
10 3
11 3
12 3
13 3
14 3
15 3
16 4

どうも、m=\sqrt nでいけるぽい。
つーわけで、ホントのn乗根を求める関数。

(define (n-root n x first-guess)
  (let ((m (floor (sqrt n))))
    (fixed-point ((repeated average-damp m)
		  (lambda (y)
		    (/ x (expt y (- n 1)))))
		 first-guess)))

収束するまで遅いので、初期値(first-guess)に3を渡した。

gosh> (n-root 16 65536 3.0)
3.0
2.812785457282565
2.6377367973089667
2.4748456266926095
2.3252862223193755
2.1929939143600716
2.0873223176370694
2.0227088232732235
2.0018155067539998
2.0000122969214313
2.0000000005670335
2.0