Решение упражнения 1.36 из SICP

24 October, 2007 (20:26) | Решения упражнений

Добавим отладочную печать в процедуру fixed-point следующим образом:

(define tolerance 0.00001)
(define (fixed-point f first-guess) 
  (define (close-enough? v1 v2) 
    (< (abs (- v1 v2)) tolerance)) 
  (define (try guess iteration) 
    (display iteration) 
    (display ":t") 
    (display guess) 
    (newline) 
    (let ((next (f guess))) 
         (if (close-enough? guess next) 
             next 
             (try next (+ iteration 1))))) 
  (try first-guess 1))

Определим функции, неподвижные точки которых будем находить (f – это выбор “в лоб”, а g задействует торможение усреднением):

(define (f x) (/ (log 1000) (log x)))
(define (g x) 
  (define (average x y) (/ (+ x y) 2)) 
  (average x (/ (log 1000) (log x))))

Теперь вычислим корень уравнения xx = 1000 путем поиска неподвижной точки для функций f и g:

> (fixed-point f 2.0) 
1: 2.0 
2: 9.965784284662087 
3: 3.004472209841214 
4: 6.279195757507157 
5: 3.759850702401539 
6: 5.215843784925895 
7: 4.182207192401397 
8: 4.8277650983445906 
9: 4.387593384662677 
10: 4.671250085763899 
11: 4.481403616895052 
12: 4.6053657460929 
13: 4.5230849678718865 
14: 4.577114682047341 
15: 4.541382480151454 
16: 4.564903245230833 
17: 4.549372679303342 
18: 4.559606491913287 
19: 4.552853875788271 
20: 4.557305529748263 
21: 4.554369064436181 
22: 4.556305311532999 
23: 4.555028263573554 
24: 4.555870396702851 
25: 4.555315001192079 
26: 4.5556812635433275 
27: 4.555439715736846 
28: 4.555599009998291 
29: 4.555493957531389 
30: 4.555563237292884 
31: 4.555517548417651 
32: 4.555547679306398 
33: 4.555527808516254 
34: 4.555540912917957 
4.555532270803653
> (fixed-point g 2.0) 
1: 2.0 
2: 5.9828921423310435 
3: 4.922168721308343 
4: 4.628224318195455 
5: 4.568346513136242 
6: 4.5577305909237005 
7: 4.555909809045131 
8: 4.555599411610624 
9: 4.5555465521473675 
4.555537551999825

Как видим, в случае использования торможения усреднением процесс сходится быстрее, то есть зачастую можно получить результат с заданной точностью за меньшее число итераций (в данном случае за 9 против 34), что обычно предпочтительно.

Полезно запомнить этот прием.

Comments

Comment from Irv
Date: January 9, 2016, 8:29 pm

(define (fixed-point f guess)  
  (define (try x n)
    (let [(y (f x))]
      (if (~= x y)
          ((lambda ()
             (display "result ")
             (display y)
             (newline)
             (display "steps ")
             (display n)               
             (newline)))
          ((lambda ()
             (display "approximation ")
             (display x)
             (newline)
             (try y (+ 1 n))))
          )))
  (try guess 1))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
(fixed-point (lambda (x) (* .5 (+ x (/ (log 1000) (log x))))) 2.0)

34 и 9 – сходится

Comment from Irv
Date: January 9, 2016, 8:31 pm

(define (~= a b) ; approximately equals
  (< (abs (- a b)) 0.00001 ))

(define (fixed-point f guess)  
  (define (try x n)
    (let [(y (f x))]
      (if (~= x y)
          ((lambda ()
             (display "result ")
             (display y)
             (newline)
             (display "steps ")
             (display n)               
             (newline)))
          ((lambda ()
             (display "approximation ")
             (display x)
             (newline)
             (try y (+ 1 n))))
          )))
  (try guess 1))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
(fixed-point (lambda (x) (* .5 (+ x (/ (log 1000) (log x))))) 2.0)

Write a comment