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

Главы 8 и 9 посвящены теоретическим вопросам, относящимся к многоточечным ИФ. В данной главе рассматриваются разнообразные методы построения многоточечных ИФ. Среди них — построение ИФ на основе изучаемой в § 8.2 интерполяционной формулы специального вида и рекуррентные методы построения ИФ, обоснование которых проводится в теоремах 8.1 и 8.2.

8.1. ПРЕИМУЩЕСТВА МНОГОТОЧЕЧНЫХ ИТЕРАЦИОННЫХ ФУНКЦИЙ

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

Теорема 5.3 утверждает, что всякая одноточечная ИФ порядка зависит явно от Отсюда следует, что эффективность использования информации одноточечными ИФ не может превышать единицы. Таким образом, a) если то зависит явно по меньшей мере от

При переходе к одноточечным ИФ с памятью эти ограничения ослабляются весьма незначительно.

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

каждой итерации. Очевидно, эти ИФ «преодолевают» ограничение Сведения о порядке и эффективности использования информации данными ИФ приведены в табл. 8.1.

Таблица 8.1. Характеристики некоторых многоточечных ИФ

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

Мы предполагаем, что читателю известны формулы Рунге — Кутты, занимающие видное место среди методов численного решения обыкновенных дифференциальных уравнений (см., например, Hildebrand [8.1-1, pp. 233-239], Kunz [8.1-2, pp. 183- 189], Levi, Baggott [8.1-3, pp. 96-108]). Характерной чертой методов Рунге — Кутты является рациональный выбор точек, в которых производятся очередные вычисления. Представляется, что эффективность многоточечных ИФ также обусловлена удачным выбором набора точек для очередных вычислений.

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

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

Рассмотрим последний аспект более подробно. Предположим, что Тогда нетрудно показать, что ИФ вида

имеет порядок Здесь выражение «расшифровывается» следующим образом: вычисляем подставляем для исключения членов, зависящих от и затем вновь подставляем х вместо а. Если в выражении для отсутствуют производные выше первого порядка, а в выражении для производные выше второго порядка, то не зависит от производных выше второго порядка. Предположим, что является решением дифференциального уравнения второго порядка; тогда объемы информационных запросов совпадают, ибо можно вычислить из дифференциального уравнения после вычисления (естественно, последнее целесообразно только в том случае, если вычисление из уравнения обходится «дешевле», чем непосредственное вычисление).

Некоторые из выводимых ниже ИФ содержат свободные параметры, что. позволяет учесть дополнительные требования. В частности, мы будем предъявлять два следующих требования:

a) вычисления должны производиться в «приемлемых» точках;

b) для функций обладающих простым расположением нулей, константа асимптотики погрешности должна быть достаточно мала.

Как явствует из теоремы 2.4, многоточечные ИФ можно получать суперпозицией двух или большего числа одноточечных ИФ. Если одноточечные ИФ соответственно порядка то ИФ вида имеет порядок Например, если их, то ИФ

их имеет четвертый порядок. Кроме того,

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

Во многих работах (см. приложение D) изучалась ИФ вида

Очевидно, ИФ вида (8.2) является многоточечной. Было показано, что если то при при В то же время эффективность использования информации этой ИФ невелика. ИФ вида (8.2) часто путают с -процессом Эйткена (подробности см. в приложении D).