ГЛАВА 5. ОДНОТОЧЕЧНЫЕ ИТЕРАЦИОННЫЕ ФУНКЦИИ

Эта глава посвящена теоретическим вопросам, относящимся к одноточечным ИФ. Все ИФ этого класса имеют целый порядок. В § 5.1 подробно рассматривается конкретная базовая последовательность Использование в качестве эталона позволяет выявить ряд характерных свойств всех одноточечных ИФ. Теорему 5.3 мы считаем основной теоремой об одноточечных ИФ.

5.1. БАЗОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ

Напомним определение базовой последовательности. Базовой Последовательностью ИФ называется бесконечная последовательность ИФ, член которой имеет порядок Техника по строения базовых последовательностей рассматривается в работах Bodewig [5.1-1], Curry [5.1-2], Ehrmann [5.1-3], Е. Schroder [5.1-4], Schwerdtfeger [5.1-5], Whittaker [5.1-6], Durand [5.1-7], Householder [5.1-8, Chap. 3], Korganoff [5.1-9, Chap. 3], Ludwig [5.1-10], Ostrowski [5.Ы1, Appendix J], Zajta [5.1-12], а также в работах других авторов. Из теоремы 2.6 следует, что различные ИФ порядка отличаются друг от друга только членами порядка Поэтому знание свойств какой-либо одной ИФ порядка позволяет вывести многие свойства произвольной ИФ этого порядка. Зная свойства базовой последовательности ИФ, можно вывести многие свойства ИФ произвольного порядка. В п. 5.1.1 мы изучим базовую последовательность ИФ относительно простой структуры, удобную для сравнений.

5.1.1. Формула для E2.

ИФ были введены и изучались в п. 4.2.2; в случае они не имеют «памяти». Ввиду особой важности ИФ используем для них специальное обозначение Условия сходимости порождаемой итерационной последовательности были сформулированы в п. 4.2.2; здесь мы предполагаем выполнение этих условий. В отличие от общего случая, потребовавшего сложных рассуждений, доказательство того, что имеет порядок оказывается почти тривиальным.

Для независимости относящегося к материала нам придется снова привести здесь отдельные сведения. Пусть не обращается в нуль в окрестности а, а производная непрерывна в этой окрестности. Тогда функция обратима, причем

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

где расположено между у и Положим при этом

или

Кроме того,

где

В (5.2) функция записана в виде ряда по степеням В приложениях иногда бывает удобнее представление в виде ряда по степеням и, где Этот ряд имеет вид

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

получаем

Поэтому

Формально полагая в получаем соотношение

Свойства рассматриваются в п. 5.1.3.

Предположим, что не обращается в нуль в окрестности нуля. В силу равенства (5.5)

Поскольку имеем

Пусть . Тогда (5.8) принимает вид

Таким образом, порядок итерационной функции равен а ее константа асимптотики погрешности равна Поскольку объем информационного запроса также равен то эффективность использования информации этой ИФ равна единице. Следовательно, образуют оптимальную базовую последовательность (определения этих терминов были даны в п. 1.2.4).

Нетрудно видеть, что где

В работе Bodewig [5.1-13] открытие приписывается Эйлеру (Euler [5.1-14]). Советские исследователи отдают первенство в этом вопросе Чебышеву, написавшему в студенческие годы работу «Calcul des racines d’une equation», удостоенную серебряной медали. С этой работой, выполненной в 1837 или 1838 г., нам не удалось ознакомиться

Покажем, что предложенная в работе Е. Schroder [5.1-15]j формула задает эквивалентную ИФ. В самом деле,

Поэтому (5.2) можно представить в виде

что совпадает с формулой Шрёдера из указанной работы; ср. с формулой для ряда Бирмана, предложенной в книге Hildebrand [5.1-16, р. 25].

5.1.2. Один пример.

В некоторых случаях удается показать, что полученный из формальных соображений ряд (5.7) сходится к а. Метод решения квадратных уравнений с помощью рядов изучается в работе Е. Schroder [5.1-17].

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

В этом случае (5.2) принимает вид

В частности,

При из последнего соотношения получается формула Ньютона — Херона для приближенного вычисления квадратных корней. Формула (5.9) была выведена в статье с использованием биномиального разложения. При получаем соотношения

При эта геометрическая прогрессия сходится к В статье отмечается, что (5.10) можно использовать для деления чисел с многократной точностью.

Построение аппроксимаций посредством итераций рассматривается в работе ].

5.1.3. Свойства Es.

Выше мы определили соотношениями

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

Несколько первых можно вычислить непосредственно из этого уравнения.

Явное представление для выводится с помощью формулы для производной обратной функции

где , а суммирование ведется по всевозможным наборам неотрицательных целых для которых

(подробности см. в приложении В). Если то полагаем для всех Из определения и (5.12) следует Теорема 5.1. Пусть

где и суть взаимно обратные функции. Тогда

где и суммирование ведется по всевозможным наборам неотрицательных целых для которых

Значения для некоторых приведены в табл. 5.1. Заметим, что зависят от производных функции и не зависят от самой Поэтому

Таблица 5.1. Выражения для

где а внутренняя сумма берется по всевозможным набором неотрицательных целых

Заменяя верхний предел суммирования во внешней сумме на получаем формальное представление для а в виде бесконечного ряда.

Приведем формулы для при малых

Сформулируем несколько очевидных следствий теоремы 5.1.

Следствие а. многочлен от переменных

Следствие Ь. Многочлен, выражающий через совпадает с многочленом, выражающим через

Следствие с. Сумма коэффициентов этого многочлена равна единице.

Доказательство. Пусть Очевидно, при все равны единице. Обратная для функция имеет вид и если то . Легко подсчитать, что при все равны единице.

Следствие d. А присутствуют в формуле для только в виде

Для удобства приложений введем обозначение

Тогда

Следствие е. Справедливо представление

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

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

С помощью оператора восходящей разности А это уравнение можно записать в виде

В леммах 5.1, 5.2 и теореме 5.2 мы воспользуемся тем обстоятельством, что имеет порядок Следующая лемма устанавливает связь между константами асимптотики погрешности и произвольной ИФ порядка

Лемма 5.1. Пусть —произвольная ИФ порядка с константой асимптотики погрешности С. Положим Тогда

Доказательство. Положим и воспользуемся теоремой 2.8, заметив, что константа асимптотики погрешности для равна

Более полезный результат содержит

Лемма 5.2. Пусть произвольная ИФ порядка с константой асимптотики погрешности С,

Тогда

Доказательство. Из предыдущей леммы с учетом равенства получаем

Пример 5.2. Рассмотрим ИФ Хэлли которая будет получена в п. 5.2.1. Поскольку нетрудно показать, что Поэтому

Для ИФ целого порядка порядок и константу асимптотики погрешности можно вычислять с помощью теоремы 2.2, которую, однако, удобно применять только для простейших ИФ. Следующая теорема позволяет находить порядок и константу асимптотики погрешности ИФ путем сравнения с Эта теорема окажется особенно полезной в гл. 9.

Теорема 5.2. Итерационная функция имеет порядок в том и только том случае, если существует и не равен нулю предел

Кроме того, этот предел равен константе асимптотики погрешности функции

Доказательство. На основании (5.6) заключаем, что Поэтому

Учитывая, что получаем

Отметим, что в формулировке теоремы 5.2 участвуют ИФ, порядки которых различаются на единицу, в то время как в формулировках лемм 5.1 и 5.2 фигурируют ИФ одинакового порядка.

В п. 5.5.1 используется

Лемма 5.3.

Доказательство. Ввиду (5.18)

откуда после очевидных упрощений получаем

Поскольку

Равенство завершает доказательство. Я

Пример 5.3. Пусть Тогда

и вместе с тем