Решение упражнения 1.36 из SICP
Добавим отладочную печать в процедуру 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), что обычно предпочтительно.
Полезно запомнить этот прием.
Write a comment