Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 19
Текст из файла (страница 19)
y 7→ x/y означает(lambda (y) (/ x y)), то есть функцию, значение которой в точке y есть x/y.82Глава 1. Построение абстракций с помощью процедур1(y + x/y) всего лишь простая трансформация уравнения y = x/y;2чтобы ее получить, добавьте y к обоим частям уравнения и поделите пополам.)После такой модификации процедура поиска квадратного корня начинает работать.В сущности, если мы рассмотрим определения, мы увидим, что последовательность приближений к квадратному корню, порождаемая здесь, в точности та же, что порождаетсянашей исходной процедурой поиска квадратного корня из раздела 1.1.7. Этот подход сусреднением последовательных приближений к решению, метод, который мы называемторможение усреднением (average damping), часто помогает достичь сходимости припоисках неподвижной точки.(Заметим, что y =Упражнение 1.35.Покажите, что золотое сечение φ (раздел 1.2.2) есть неподвижная точка трансформации x 7→1 + 1/x, и используйте этот факт для вычисления φ с помощью процедуры fixed-point.Упражнение 1.36.Измените процедуру fixed-point так, чтобы она печатала последовательность приближений,которые порождает, с помощью примитивов newline и display, показанных в упражнении 1.22.
Затем найдите решение уравнения xx = 1000 путем поиска неподвижной точкиx 7→ log(1000)/ log(x). (Используйте встроенную процедуру Scheme log, которая вычисляет натуральные логарифмы.) Посчитайте, сколько шагов это занимает при использовании торможенияусреднением и без него. (Учтите, что нельзя начинать fixed-point со значения 1, поскольку этовызовет деление на log(1) = 0.)Упражнение 1.37.а. Бесконечнаяцепная дробь (continued fraction) есть выражение видаN1f=N2D1 +D2 +N3D3 + .
. .В качестве примера можно показать, что расширение бесконечной цепной дроби при всех Ni иDi , равных 1, дает 1/φ, где φ — золотое сечение (описанное в разделе 1.2.2). Один из способоввычислить цепную дробь состоит в том, чтобы после заданного количества термов оборвать вычисление. Такой обрыв — так называемая конечная цепная дробь (finite continued fraction) из kэлементов, — имеет видN1f=N2D1 +NkD2 + . . .DkПредположим, что n и d — процедуры одного аргумента (номера элемента i), возвращающие Ni иDi элементов цепной дроби.
Определите процедуру cont-frac так, чтобы вычисление (contfrac n d k) давало значение k-элементной конечной цепной дроби. Проверьте свою процедуру,вычисляя приближения к 1/φ с помощью(cont-frac (lambda (i) 1.0)(lambda (i) 1.0)k)1.3. Формулирование абстракций с помощью процедур высших порядков83для последовательных значений k.
Насколько большим пришлось сделать k, чтобы получить приближение, верное с точностью 4 цифры после запятой?б. Если Ваша процедура cont-frac порождает рекурсивный процесс, напишите вариант, который порождает итеративный процесс. Если она порождает итеративный процесс, напишите вариант, порождающий рекурсивный процесс.Упражнение 1.38.В 1737 году швейцарский математик Леонард Эйлер опубликовал статью De functionibusContinuis, которая содержала расширение цепной дроби для 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 году немецким математиком Й.Х. Ламбертом:xtg x =x21−x23−5 − ...где x дан в радианах. Определите процедуру (tan-cf x k), которая вычисляет приближение ктангенсу на основе формулы Ламберта. K указывает количество термов, которые требуется вычислить, как в упражнении 1.37.1.3.4. Процедуры как возвращаемые значенияПредыдущие примеры показывают, что возможность передавать процедуры в качестве аргументов значительно увеличивает выразительную силу нашего языка программирования. Мы можем добиться еще большей выразительной силы, создавая процедуры,возвращаемые значения которых сами являются процедурами.Эту идею можно проиллюстрировать примером с поиском неподвижной точки, обсуждаемым в конце раздела 1.3.3.
Мы сформулировали новую версию процедуры вычис√ления квадратного корня как поиск неподвижной точки, начав с наблюдения, что xесть неподвижная точка функции y 7→ x/y. Затем мы использовали торможение усреднением, чтобы заставить приближения сходиться. Торможение усреднением само по себеявляется полезным приемом. А именно, получив функцию f , мы возвращаем функцию,значение которой в точке х есть среднее арифметическое между x и f (x).Идею торможения усреднением мы можем выразить при помощи следующей процедуры:(define (average-damp f)(lambda (x) (average x (f x))))Average-damp — это процедура, принимающая в качестве аргумента процедуру f ивозвращающая в качестве значения процедуру (полученную с помощью lambda), которая, будучи применена к числу x, возвращает среднее между x и (f x).
Например,84Глава 1. Построение абстракций с помощью процедурприменение average-damp к процедуре square получает процедуру, значением которой для некоторого числа x будет среднее между x и x2 . Применение этой процедуры кчислу 10 возвращает среднее между 10 и 100, то есть 5559 :((average-damp square) 10)55Используя average-damp, мы можем переформулировать процедуру вычисленияквадратного корня следующим образом:(define (sqrt x)(fixed-point (average-damp (lambda (y) (/ x y)))1.0))Обратите внимание, как такая формулировка делает явными три идеи нашего метода: поиск неподвижной точки, торможение усреднением и функцию y 7→ x/y.
Полезносравнить такую формулировку метода поиска квадратного корня с исходной версией,представленной в разделе 1.1.7. Вспомните, что обе процедуры выражают один и тотже процесс, и посмотрите, насколько яснее становится его идея, когда мы выражаемпроцесс в терминах этих абстракций. В общем случае существует много способов сформулировать процесс в виде процедуры. Опытные программисты знают, как выбрать теформулировки процедур, которые наиболее ясно выражают их мысли, и где полезныеэлементы процесса показаны в виде отдельных сущностей, которые можно использоватьв других приложениях.
Чтобы привести простой пример такого нового использования,заметим, что кубический корень x является неподвижной точкой функции y 7→ x/y 2 ,так что мы можем немедленно обобщить нашу процедуру поиска квадратного корня так,чтобы она извлекала кубические корни60 :(define (cube-root x)(fixed-point (average-damp (lambda (y) (/ x (square y))))1.0))Метод НьютонаКогда в разделе 1.1.7 мы впервые представили процедуру извлечения квадратного корня, мы упомянули, что это лишь частный случайметода Ньютона (Newton’smethod).
Если x 7→ g(x) есть дифференцируемая функция, то решение уравненияg(x) = 0 есть неподвижная точка функции x 7→ f (x), гдеf (x) = x −g(x)Dg(x)а Dg(x) есть производная g, вычисленная в точке x. Метод Ньютона состоит в том, чтобыприменить описанный способ поиска неподвижной точки и аппроксимировать решение59 Заметьте, что здесь мы имеем комбинацию, оператор которой сам по себе комбинация. В упражнении 1.4уже была продемонстрирована возможность таких комбинаций, но то был всего лишь игрушечный пример.Здесь мы начинаем чувствовать настоящую потребность в выражениях такого рода — когда нам нужно применить процедуру, полученную в качестве значения из процедуры высшего порядка.60 См. дальнейшее обобщение в упражнении 1.451.3.
Формулирование абстракций с помощью процедур высших порядков85уравнения путем поиска неподвижной точки функции f .61 Для многих функций g придостаточно хорошем начальном значении x метод Ньютона очень быстро приводит крешению уравнения g(x) = 062 .Чтобы реализовать метод Ньютона в виде процедуры, сначала нужно выразить понятие производной.
Заметим, что «взятие производной», подобно торможению усреднением,трансформирует одну функцию в другую. Например, производная функции x 7→ x3 естьфункция x 7→ 3x2 . В общем случае, если g есть функция, а dx — маленькое число, топроизводная Dg функции g есть функция, значение которой в каждой точке x описывается формулой (при dx, стремящемся к нулю)Dg(x) =g(x + dx) − g(x)dxТаким образом, мы можем выразить понятие производной (взяв dx равным, например,0.00001) в виде процедуры(define (deriv g)(lambda (x)(/ (- (g (+ x dx)) (g x))dx)))дополненной определением(define dx 0.00001)Подобно average-damp, deriv является процедурой, которая берет процедуру вкачестве аргумента и возвращает процедуру как значение.
Например, чтобы найти приближенное значение производной x 7→ x3 в точке 5 (точное значение производной равно75), можно вычислить(define (cube x) (* x x x))((deriv cube) 5)75.00014999664018С помощью deriv мы можем выразить метод Ньютона как процесс поиска неподвижной точки:(define (newton-transform g)(lambda (x)(- x (/ (g x) ((deriv g) x)))))(define (newtons-method g guess)(fixed-point (newton-transform g) guess))61 Вводные курсы анализа обычно описывают метод Ньютона через последовательность приближений xn+1 =xn − g(xn )/Dg(xn ). Наличие языка, на котором мы можем говорить о процессах, а также использование идеинеподвижных точек, упрощают описание этого метода.62 Метод Ньютона не всегда приводит к решению, но можно показать, что в удачных случаях каждая итерация удваивает точность приближения в терминах количества цифр после запятой.
Для таких случаев методНьютона сходится гораздо быстрее, чем метод половинного деления.86Глава 1. Построение абстракций с помощью процедурПроцедура newton-transform выражает формулу, приведенную в начале этого раздела, а newtons-method легко определяется с ее помощью. В качестве аргументовона принимает процедуру, вычисляющую функцию, чей ноль мы хотим найти, а такженачальное значение приближения. Например, чтобы найти квадратный корень x, мы можем с помощью метода Ньютона найти ноль функции y 7→ y 2 − x, начиная со значения163 . Это дает нам еще одну форму процедуры вычисления квадратного корня:(define (sqrt x)(newtons-method (lambda (y) (- (square y) x))1.0))Абстракции и процедуры как полноправные объектыМы видели два способа представить вычисление квадратного корня как частный случай более общего метода; один раз это был поиск неподвижной точки, другой — методНьютона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
