5.4. ОСНОВНАЯ ТЕОРЕМА ОБ ОДНОТОЧЕЧНЫХ ИТЕРАЦИОННЫХ ФУНКЦИЯХ

Напомним некоторые понятия, введенные в п. 1.2.4 и используемые в этом параграфе. Объем информационного запроса ИФ определяется количеством элементов новой информации, используемых в ходе одной итерации. Принадлежность к классу

ИФ порядка с объемом информационного запроса обозначается а эффективность использования информации определяется как Если то называется оптимальной. В этом параграфе рассматриваются как простые, так и кратные нули. Если порядок не зависит от кратности нуля, то порядок называется независимым от кратности.

Знакомый с конкретными ИФ читатель наверняка заметил, что одноточечные ИФ порядка зависят явным образом от и от по крайней мере первых производных функции Таким образом, объем информационного запроса одноточечной ИФ порядка не может быть меньше Ниже мы приводим строгое доказательство этого факта, послужившего основанием для сформулированного в определения оптимальности ИФ. Доказательство весьма простое, а сам результат относится к «фольклору» численного анализа. Значение этого результата состоит в том, что он стимулирует поиск ИФ, эффективность использования информации которыми превышает единицу. Многоточечные ИФ и ИФ с памятью не подпадают под действие этой основной теоремы об одноточечных ИФ. Напомним, что изучавшиеся в § 5.1, имеют порядок Чтобы сосредоточить внимание на данном свойстве на протяжении этого параграфа будем вместо писать

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

Доказательство. Существование оптимальных ИФ всех порядков следует из того, что (класс определяется в (1.18)). Пусть некоторая одноточечная ИФ. Вследствие теоремы 2.10 любая ИФ порядка представима в виде где ограниченная в окрестности а функция. В таком случае не может содержать члены, зависящие от Положим и используем для представление (5.2):

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

Покажем, что для многоточечных ИФ теорема 5.3 неспра ведлива. Заметим, что

Поскольку отличается от только членами порядка следовательно, имеет третий порядок. В то же время вторая производная не входит в выражение для явно — она аппроксимирована производными более низкого порядка. Отметим, что вычисляет новую информацию в точках и является примером многоточечной ИФ (см. гл. 8, 9). Как уже отмечалось, для одноточечных ИФ подобная аппроксимация производных невозможна.

Рассмотрим случай кратных корней.

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

Доказательство. Положим Очевидно, имеет только простые нули, причем производные зависят только от Применив теорему 5.3, получим требуемое утверждение. I

Отметим, что доказанное следствие гарантирует существование оптимальных ИФ, порядок которых не зависит от кратности. Составленная из подобных ИФ базовая последовательность приведена в § 7.3.

Наибольший интерес представляет случай, когда неизвестно. Заметим, что имеет только простые нули. Подстановка и вместо в любую оптимальную одноточечную ИФ порядка приводит снова к ИФ порядка Следовательно, существуют ИФ любого порядка с эффективностью использования информации для нулей произвольной кратности, не зависящие явно от Эти вопросы будут рассмотрены более подробно в гл. 7.