Exercise 1.37

文責:@naoiwata

解答

無限の連分数の一般項は 第 k 項において以下のように表せる.

\(f(N_{i}, D_{i}) = \frac{N_i}{D_{i} + f(N_{i+1}, D_{i+1})}\)

これを再帰的プロセスまたは反復的プロセスを使って S 式に書き換えたものが解となる.

;; 再帰的プロセス
(define (cont-franc n d k)
  (define (cont-franc-iter i)
    (if (= k i)
        (/ (n i) (d i))
        (/ (n i) (+ (d i) (cont-franc-iter (+ i 1))))))
  (cont-franc-iter 1))

;; 反復的プロセス
(define (cont-franc n d k)
  (define (cont-franc-iter i sum)
    (if (= k i)
        sum
        (cont-franc-iter (+ i 1) (/ (n i) (+ (d i) sum)))))
  (cont-franc-iter 1 0))

;; 1/phi を求める手続き
(cont-franc
  (lambda (i) 1.0)
  (lambda (i) 1.0)
  k)

実行コード

また, \(\frac{1}{\phi }\) を求める手続きを使って, 4 桁の精度の近似を得る為には k はどのくらい大きくしなければならないかを調べる. 1 ~ 30 までの k に対して計算した結果を下に示す.

(define (test f n)
  (map
    (lambda (i)
      (newline)
      (display i)
      (display " : ")
      (display (f i)))
    (iota n 1)))

(test
  (lambda (k)
    (cont-franc
      (lambda (i) 1.0)
      (lambda (i) 1.0)
    k))
   20)

;;  1 : 1.0
;;  2 : 0.5
;;  3 : 0.6666666666666666
;;  4 : 0.6000000000000001
;;  5 : 0.625
;;  6 : 0.6153846153846154
;;  7 : 0.6190476190476191
;;  8 : 0.6176470588235294
;;  9 : 0.6181818181818182
;; 10 : 0.6179775280898876
;; 11 : 0.6180555555555556
;; 12 : 0.6180257510729613
;; 13 : 0.6180371352785146
;; 14 : 0.6180327868852459
;; 15 : 0.6180344478216819
;; 16 : 0.6180338134001252
;; 17 : 0.6180340557275542
;; 18 : 0.6180339631667064
;; 19 : 0.6180339985218034
;; 20 : 0.6180339850173578
;; 21 : 0.6180339850173578
;; 22 : 0.6180339901755971
;; 23 : 0.6180339882053251
;; 24 : 0.618033988957902
;; 25 : 0.6180339886704432
;; 26 : 0.6180339887802426
;; 27 : 0.6180339887383031
;; 28 : 0.6180339887543225
;; 29 : 0.6180339887482037
;; 30 : 0.6180339887505407

結果から, \(\frac{1}{\phi }\) の 4 桁の精度の近似を得る為には k は 11 以上である必要があると分かる.