4.4.4 Блочная структура программ на lisp’е

Заметим, кстати, что сначала описываются все применяемые функции и в конце происходит обращение к рекурсивному вызову, что и организует процесс вычисления. Такие вложенные определения придают программам «блочную» структуру. Это важный принцип для написания больших программ. Неудобства такой блочной функции в том, что внутренние функции не доступны снаружи. Это надо иметь в виду, если обращаться к функции TRACE.

Но блочная структура предоставляет и дополнительные удобства. Аргумент a находится в той же области определения, что и вспомогательные функции, поэтому не нужно передавать его явно, что даёт возможность несколько упростить все определения.

> (define (squ3 a)

(define (acceptable? x)

(< (abs (-(sqr x) a)) 0.000001))

(define (improve x)

(/ (+ x (/ a x)) 2 ))

(define (squ-iter x)

(if (acceptable? x) x (squ-iter (improve x)) ))

(squ-iter 1.0) )

> (squ3 2)

1.4142135623746899

Для сравнения, снова вызовем встроенную функцию.

> (sqrt 2)

1.4142135623730951

Результат получился приемлемым, но его можно и улучшить, если изменить критерий допустимости:

вычисления надо прекратить, если два последовательных приближения станут отличаться меньше, чем на заданный допуск, т.е.

Тогда,

• во-первых, вместо (acceptable? x) надо вызывать функцию, например, (near? x1 x2), реализующую этот критерий,

• значит, во-вторых, подправить зависимую от нее функцию (squ-iter x)

Это выльется в следующий текст:

> (define err 0.000001)

> (define (near? x1 x2)

(< (abs (- x1 x2)) err))

Эти два определения нужно оставить внешними, что даст большую гибкость, хотя функция вычисления корня и будет по-прежнему зависеть от них.

> (define (squ4 a)

(define (improve x)

(/ (+ x (/ a x)) 2 ))

(define (squ-iter x)

(let ((x1 (improve x)))

(if (near? x1 x) x1 (squ-iter x1))))

(squ-iter 1.0))

Надо обратить внимание на применение функции let, которая локально связывает очередное уточнение.

> (squ4 2)

1.414213562373095

Результат оказался не плох.

4.4.5 Построение функционала для метода Ньютона

Р ассмотрим общую задачу.

Использованный нами метод извлечения квадратного корня фактически представляет собой частный случай метода поиска корней уравнений известного как метод Ньютона (или метод касательных).

Е го суть такова. Если f(x) – дифференцируемая функция, то решение уравнения f(x) = 0 может быть получено как предел последовательности приближений, определяемой рекуррентным соотношением

Общая схема процедуры, реализующей метод Ньютона, схожа с той, что была использована для вычисления квадратного корня squ4. Надо только задать s - стартовое значение для вычисления корня и изменить функцию improve.

> (define err 0.00001)

> (define (near? x1 x2)

(< (abs (- x1 x2)) err))

> (define (newton-method f df s)

(define (improve x)

(- x (/ (f x) (df x))) )

(define (newton-iter x)

(let ((y (improve x)))

(if (near? y x) y

(newton-iter y))))

(newton-iter s)

)

Обратим внимание, чтобы вызвать нашу функцию, для вычисления корня уравнения надо обязательно задать три параметра:

1. саму функцию (f)

2. её производную (df)

3. начальное значения для итерации (s)

Вычисление квадратного корня можно представить как решение уравнения x² - a = 0 , то есть как поиск нуля функции x.(x² - a). Поскольку производная этой функции - x.2*x, то вызов функции можно записать:

> (define (sqrt1 a)

(newton-method (lambda (x) (-(sqr x) a))

(lambda (x) (* 2 x))

1.0))

> (sqrt1 2)

1.4142135623746899

Неудобство метода Ньютона - необходимость знать производную функции. Однако, её можно заменить приближённой оценкой.

Если dx - достаточно малое число, то функция Df в точке x, определяется как

Она дает приближённое значение производной функции f. 

Обратите внимание, что производная, отображает одну функцию в другую функцию. Таким образом, мы можем выразить идею «производной» как функции высшего порядка.

Сначала проверим работу только производной.

> (define dx 0.00001)

> (define (deriv f)

(lambda (x) {/ [- (f (+ x dx)) (f x)] dx} ))

> ((deriv [lambda (x) (sqr x)]) 1)

2.00001000001393

> ((deriv [lambda (x) (sqr x)]) 0.5)

1.0000099999962764

Объединяя эту функцию с newtons-method, получаем разновидность этого метода, которая носит имя - метода секущих (англ. - secant).

> (define (sqrt2 a)

(secant-method2 (lambda (x) (-(sqr x) a)) a))

> (define (secant-method2 f a)

(newton-method2 f ((deriv f) a) 1.0))

Надо подправить функцию на newton-method2, поскольку теперь производная здесь не вычисляется, а берётся её числовое значение

> (define (newton-method2 f df s)

Теперь df это – численное значение !!!

(define (improve x)

(- x (/ (f x) df)) )

(define (newton-iter x)

(let ((y (improve x)))

(if (near? y x) y

(newton-iter y))))

(newton-iter s) )

Это стало

> (sqrt1 2)

1.4142135623746899

А это было:

> (sqrt2 2)

1.4142103894663087

> (sqrt 2) ; А это - сравнение со встроенной функцией

1.4142135623730951

Такой метод сходится не так быстро, как метод Ньютона, но гораздо удобнее на практике, особенно, в случаях сложных функций.

Мы рассмотрели функционалы числовых функций, которые реализовывали численные методы. Продолжим теперь разговор о нечисленных функционалах.

Page 14 of 14