(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))

1.0 2.0)

1.89306640625

Нахождение неподвижных точек функций

Число х называется неподвижной точкой (fixed point) функции f, если оно удовлетворяет уравнению f (х) = х. Для некоторых функций f можно найти неподвижную точку, начав с какого-то значения и применяя f многократно:

f (x),f (f (x)),f (f (f (х))),...

- пока значение не перестанет сильно изменяться. С помощью этой идеи мы можем составить процедуру fixed-point, которая в качестве аргументов принимает функцию и начальное значение и производит приближение к неподвижной точке функции. Мы многократно применяем функцию, пока не найдем два последовательных значения, разница между которыми меньше некоторой заданной чувствительности:

(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)))

(if (close-enough? guess next) next

(try next))))

(try first-guess))

Например, с помощью этого метода мы можем приближенно вычислить неподвижную точку функции косинус, начиная с 1 как стартового приближения:57

(fixed-point cos 1.0) .7390822985224023

Подобным образом можно найти решение уравнения y = siny + cosy:

(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0)

.2587315962971173

Процесс поиска неподвижной точки похож на процесс, с помощью которого мы искали квадратный корень в разделе 1.1.7. И тот, и другой основаны на идее последовательного улучшения приближений, пока результат не удовлетворит какому-то критерию. На самом деле мы без труда можем сформулировать вычисление квадратного корня как поиск неподвижной точки. Вычислить квадратного корня из произвольного числа х означает найти такое y, что y2 = х.

57Попробуйте во время скучной лекции установить калькулятор в режим радиан и нажимать кнопку cos, пока не найдете неподвижную точку.

Переведя это уравнение в эквивалентную форму y = x/y, мы обнаруживаем, что должны найти неподвижную точку функции58 y - x/y, и, следовательно, мы можем попытаться вычислять квадратные корни так:

(define (sqrt x)

(fixed-point (lambda (y) (/ x y))

1.0))

К сожалению, этот поиск неподвижной точки не сходится. Рассмотрим исходное значение yi. Следующее значение равно y2 = x/yi, а следующее за ним y3 = x/y2 = x/(x/yi) = yi .В результате выходит бесконечный цикл, в котором два значения y1 и y2 повторяются снова и снова, прыгая вокруг правильного ответа.

Один из способов управлять такими прыжками состоит в том, чтобы заставить значения изменяться не так сильно. Поскольку ответ всегда находится между текущим значением y и x/y, мы можем взять новое значение, не настолько далекое от y, как x/y, взяв среднее между ними, так что следующее

значение будет не х/у, а -(у + х/у). Процесс получения такой последовательности есть всего лишь процесс поиска неподвижной точки у i-> -(у + х/у).

(define (sqrt x)

(fixed-point (lambda (y) (average y (/ x y)))

1.0))

(Заметим, что у = -(у + х/у) всего лишь простая трансформация уравнения

y = x/y; чтобы ее получить, добавьте y к обоим частям уравнения и поделите пополам.)

После такой модификации процедура поиска квадратного корня начинает работать. В сущности, если мы рассмотрим определения, мы увидим, что последовательность приближений к квадратному корню, порождаемая здесь, в точности та же, что порождается нашей исходной процедурой поиска квадратного корня из раздела 1.1.7. Этот подход с усреднением последовательных приближений к решению, метод, который мы называем торможение усреднением (average damping), часто помогает достичь сходимости при поисках неподвижной точки.

Упражнение 1.35.

Покажите, что золотое сечение ф (раздел 1.2.2) есть неподвижная точка трансформации x - 1 + 1/x, и используйте этот факт для вычисления ф с помощью процедуры fixed-point.

Упражнение 1.36.

Измените процедуру fixed-point так, чтобы она печатала последовательность приближений, которые порождает, с помощью примитивов newline и display, показанных в упражнении 1.22. Затем найдите решение уравнения xx = 1000 путем поиска неподвижной точки x - log(1000)/log(x). (Используйте встроенную процедуру Scheme

58 - (произносится «отображается в») - это математический способ написать lambda. y - x/y означает (lambda (y) (/ x y)), то есть функцию, значение которой в точке y есть x/y.

log, которая вычисляет натуральные логарифмы.) Посчитайте, сколько шагов это занимает при использовании торможения усреднением и без него. (Учтите, что нельзя начинать fixed-point со значения 1, поскольку это вызовет деление на log(1) = 0.)

Упражнение 1.37.

a. Бесконечная цепная дробь (continued fraction) есть выражение вида

/= *1

Г) Жа

°2 + ж

В качестве примера можно показать, что расширение бесконечной цепной дроби при всех N и Di, равных 1, дает 1/ф, где ф - золотое сечение (описанное в разделе 1.2.2). Один из способов вычислить цепную дробь состоит в том, чтобы после заданного количества термов оборвать вычисление. Такой обрыв - так называемая конечная цепная дробь (finite continued fraction) из k элементов, - имеет вид

/=

1 +-Ж

Предположим, что n и d - процедуры одного аргумента (номера элемента i), возвращающие Ni и Di элементов цепной дроби. Определите процедуру cont-frac так, чтобы вычисление (cont-frac n d k) давало значение k-элементной конечной цепной дроби. Проверьте свою процедуру, вычисляя приближения к 1/ф с помощью

(cont-frac (lambda (i) 1.0) (lambda (i) 1.0)

k)

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

b. Если Ваша процедура cont-frac порождает рекурсивный процесс, напишите вариант, который порождает итеративный процесс. Если она порождает итеративный процесс, напишите вариант, порождающий рекурсивный процесс.

Упражнение 1.38.

В 1737 году швейцарский математик Леонард Эйлер опубликовал статью De functioni-bus Continuis, которая содержала расширение цепной дроби для e - 2, где e - основание натуральных логарифмов. В этой дроби все Ni равны 1, а Di последовательно равны 1, 2,1, 1, 4,1,1, 6,1,1, 8,.. .Напишите программу, использующую Вашу процедуру cont-frac из упражнения 1.37 для вычисления e на основании формулы Эйлера.

Упражнение 1.39.

Представление тангенса в виде цепной дроби было опубликовано в 1770 году немецким математиком Й.Х. Ламбертом:

tgrr =-

1--3

х

х2 5- ...

где x дан в радианах. Определите процедуру (tan-cf x k), которая вычисляет приближение к тангенсу на основе формулы Ламберта. K указывает количество термов, которые требуется вычислить, как в упражнении 1.37.

x