8.3. РЕКУРРЕНТНО ГЕНЕРИРУЕМЫЕ ИТЕРАЦИОННЫЕ ФУНКЦИИ

В этом параграфе изучается класс ИФ, генерируемых рекуррентно. Начнем с примера. Пусть где

Отметим, что, во-первых, вычисление легко реализуемо на ЭВМ; во-вторых, вычисление требует вычисления значений и одного значения Ниже покажем, что

8.3.1. Еще одна теорема итерационного исчисления.

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

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

Доказательство 1. Покажем, что выполняются условия теоремы 2.2. Заметим, что Далее, нетрудно проверить, что Докажем по индукции, что Предположим, что где

I — произвольное целое, Представим выражение для в виде

Продифференцировав раз по переменной х, получим

где биномиальные коэффициенты. Положим в (8.16). Из предположения индукции и условия следует, что

По теореме 2.14

поэтому из (8.16) следует равенство Поскольку то следовательно, Индукция проведена и теорема доказана.

Доказательство 2. Заметим, что С учетом теоремы 2.4 имеем

Ввиду теоремы 2.5 найдется функция , такая, что причем Поэтому

Отсюда следует, что

где К — ограниченная в окрестности точки а функция. По теореме 2.11 найдется такая функция что

причем Из (8.17) и (8.18) с учетом определения получаем

Поскольку в соответствии с теоремой 2.7 порядок равен

Отметим, что построенная в теореме обобщает ИФ Ньютона; первая сводится к последней при

Пример 8.1. Положим

Согласно предыдущей теореме, ИФ

имеет третий порядок. Эта ИФ вычисляет на каждой итерации значения в точках и значение в точке

8.3.2. Обобщение предыдущей теоремы.

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

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

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

где ряд (8.23) также соответствующим образом усечен (подробности, относящиеся к (8.23), см. в п. 5.1.1). Например,

поэтому

Общая формула для выводится следующим образом. Положим Очевидно,

Заметим, что

С учетом тождеств

получаем, что

Поэтому

Заметим, что при соотношения (8.21) означают, что суть ИФ порядка Положив в (8.24), получим формулу Шрёдера для ИФ порядка Заметим, что (8.24) проще преобразовать в многочлен от и, чем в многочлен от Полученные результаты объединяет

Лемма 8.1. Пусть заданная функция, -функция, удовлетворяющая условиям причем а не присутствует в представлении для явно. Тогда

где произвольная функция, имеющая непрерывных производных.

Ниже приводятся выражения для , в виде многочленов от :

Особый интерес представляет случай тогда и (8.24) принимает вид

С учетом выражений для отсюда получаем

Таким образом, доказана

Лемма 8.2. Пусть - функция, удовлетворяющая условиям

и не зависящая от а явно. Тогда

где

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

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

причем по теореме Положим

(функция будет выбрана ниже); при этом

Предположим, что удовлетворяет соотношению

где Ввиду теоремы 2.11 справедливо представление

причем Сопоставив (8.30), (8.31) и (8.32), получаем

Поскольку в силу теоремы 2.7 порядок равен

Осталось предложить способ построения функции удовлетворяющей соотношениям (8.31). Заметим, что

где Кроме того,

Поэтому для выполнения (8.31) достаточно потребовать, чтобы

Но способ построения функций, удовлетворяющих условиям (8.36), предложен в лемме 8.1. Таким образом, доказана

Теорема 8.2. Пусть натуральное число, функция не тождественна константе, Предположим, что произвольная ИФ порядка Положим где удовлетворяет соотношению для некоторого Тогда где

8.3.3. Примеры.

В этом пункте мы приведем примеры полученных однократным применением теоремы (8.2). Повторное применение этой теоремы, приводящее к рекуррентному методу построения ИФ, рассматривается в

Пример 8.2. Пусть Ввиду Поэтому порядок ИФ

равен Если то совпадает с ИФ из теоремы 8.1.

Пример 8.3. Пусть выполнены условия предыдущего примера, но Тогда

причем порядок равен Очевидно, при при

Пример 8.4. Пусть выполнены все условия предыдущего примера и при этом Заметим, что

Поэтому порядок ИФ

также равен

Пример 8.5. Пусть Положим Ввиду

имеет порядок, равный Очевидно, при при

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

Пример 8.6. Пусть удовлетворяют условиям примера 8.2, причем Тогда (8.37) принимает вид

С учетом равенства формулу (8.38) можно представить в виде

где через и обозначены соответственно константы асимптотики погрешности

8.3.4. Рекуррентное построение итерационных функций.

Рассмотрим ИФ

фигурировавшую в теореме 8.1 и примере 8.2. Положим тогда предыдущее соотношение принимает вид

Очевидно, порядок из левой части (8.41) превышает на единицу порядок из правой части этого соотношения. Так, если то порядок равен двум. Следовательно, порядок получаемый в результате процедуры

равен Напомним, что константа асимптотики погрешности равна Последовательное применение правила (8.39) приводит к соотношению

Отметим, что константа асимптотики погрешности (8.43) зависит только от . В соответствии с результатами § 8.1, порядок равен Эту ИФ удобно использовать для нахождения нулей функций, удовлетворяющих обыкновенным дифференциальным уравнениям второго порядка.

Оценим величину последовательного уменьшения значений с ростом Из соотношений

получаем

Рекуррентная процедура (8.42) построения легко реализуема на ЭВМ. Нетрудно выписать выражение для этой ИФ и в явном виде:

Приведем геометрическую интерпретацию данной ИФ. Выражение задает точку пересечения с осью абсцисс касательной, построенной в точке . В свою очередь задает пересечение с осью абсцисс прямой, проходящей через точку параллельно касательной, построенной в точке Из наглядных соображений очевидно, что условия сходимости для совпадают с условиями сходимости для ИФ Ньютона. Отметим, что можно использовать двумя способами; как ИФ для небольших (например, или как

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

Отметим сходство выражения (8.40) с выражением

Последнее индуцирует рекуррентную процедуру

Однако имеют первый порядок для любого причем

Построенные таким способом ИФ обсуждаются в работах Ostrowski [8.3-1, Appendix G], Bodewig [8.3-2]. Различие между процедурами (8.42) и (8.44) состоит только в том, что в первой используется а во второй . Однако первая приводит к ИФ порядка в то время как вторая — к ИФ первого порядка. Здесь мы наблюдаем, как непрерывный переход от приводит к скачкообразному изменению порядка.

Полученная выше оценка

погрешности приближения позволяет осуществить следующую экстраполяционную процедуру. Очевидно,

Выразив из последнего соотношения а, получим

Формула (8.46) указывает на целесообразность рассмотрения ИФ

Нетрудно показать, что Заметим, что соотношение (8.47) по форме идентично -формуле Эйткена. В то время как формула Эйткена обычно эффективна для последовательностей, сходящихся с линейной скоростью, формула (8.47) увеличивает скорость сходимости используя свойства погрешности этой ИФ (подробности см. в приложении

Перечислим преимущества ИФ, порождаемых процедурой (8.42):

a) эти ИФ позволяют преодолеть ограничение а) из § 8.1.

А именно, они имеют порядок хотя на каждой итерации вычисляется значений и одно значение

b) при построении ИФ этого типа сколь угодно высокого порядка вычисление производится однократно, что удобно при расчетах на ЭВМ. Это также облегчает проведение вычислений на калькуляторах;

c) поскольку функция выражается рекуррентной формулой, ее вычисление на ЭВМ сводится к обычному циклу.

d) выражение для погрешности позволяет использовать простую экстраполяционную формулу (8.47);

e) в случае кратного нуля следует в (8.42) заменить на Полученная в результате ИФ имеет порядок для нулей любой кратности и требует вычисления на каждой итерации значений значений и одного значения ;

f) константа асимптотики погрешности одноточечной порядка обычно зависит от а константа асимптотики погрешности. зависит для произвольного от ;

g) метод построения позволяет легко обобщить ее на случай решения систем уравнений. Для этого достаточно заменить на где — соответствующая матрица Якоби.

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

h) данный метод построения легко обобщается на случай абстрактных пространств.

Выше была подробно рассмотрена процедура (8.42) рекуррентного построения ИФ, основанная на Разнообразные процедуры рекуррентного построения ИФ могут быть сформированы и на основе ИФ, фигурирующей в теореме 8.2. Рассмотрим лишь одну из возможностей.

В примере 8.4 отмечалось, что ИФ

имеет порядок при Следовательно, при при Эту ИФ можно положить в основу рекуррентной процедуры

Нетрудно видеть, что Кроме того, в частности при преодолеваются оба ограничения а), b) из § 8.1.

Пусть определяются из условий

Нетрудно показать, что

где