§ 2. Теория итерационных двухслойных схем общего вида

1. Итерационная схема с чебышевским набором параметров.

Пусть дано операторное уравнение

где линейный оператор, заданный в гильбертовом пространстве заданный и искомый векторы из

Для приближенного решения уравнения (1) применяется двухслойная итерационная схема

с произвольным начальным вектором Предполагается, что операторы удовлетворяют требованиям

где постоянные энергетической эквивалентности операторов

Из (3) и (4) следует положительная определенность оператора А.

Всюду в этом параграфе будем считать, что оператор В не зависит от номера итерации

Изучение сходимости итераций по схеме (2) сводится к оценке при решения и однородного уравнения

Неявная схема (2) эквивалентна явной схеме (см. гл. VI)

где С — один из операторов

или

Из (6) находим

где разрешающий оператор есть операторный полином степени

В силу условий (3) и (4) оператор С — самосопряженный, с границами и

Поэтому норма операторного полинома оценивается по формуле (см. Л. В. Канторович и Г. П. Акилов [1]):

Параметры находятся из условия минимума или как будет показано ниже, выражаются через нули полиномов первого рода П. Л. Чебышева .

Нам понадобятся некоторые свойства полиномов П. Л. Чебышева (см. В. Л. Гончаров [1])

Для вычисления полиномов высоких степеней можно использовать рекуррентное соотношение

Справедлива формула

которая доопределяет при

Корнями полинома очевидно, являются числа

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

Ставится задача — среди таких полиномов найти полином, наименее отклоняющийся от нуля на отрезке (т. е. имеющий наименьший шахп и нормированный к 1 при Линейная замена

позволяет свести эту задачу к построению полинома, наименее отклоняющегося от нуля в промежутке и принимающего значение 1 в точке где

Решением последней задачи (см. В. Гончаров [1]) является полином

где полином Чебышева первого рода. Максимум отклонения от нуля равен

Подставляя сюда выражение (13) для получаем

Введем обозначения

и преобразуем

В результате получим

Потребуем, чтобы полиномы (15) и совпадали:

Полином обращается в нуль при где определяется по формуле (14). Из (17) следует

Тем самым доказана Теорема 1. Пусть дан полином

где произвольные параметры.

Тогда достигается при следующих значениях параметров:

При таком выборе справедлива оценка

Таким образом задача об отыскании (задача о минимаксе) полностью решена.

Вернемся к схеме (2). Из теоремы 1 следует, что для нормы разрешающего оператора определяемого формулой (9), имеет место неравенство

если параметры выбраны согласно (18).

При этом справедлива оценка решения задачи (6)

которой соответствует следующая априорная оценка для решения задачи (5):

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

При получаем следующую оценку для числа итераций при котором

Так, например, если рассматривается разностная аппроксимация задачи Дирихле для уравнения Лапласа в квадрате на квадратной сетке, (см. гл. IV, § 2), то

Схему (2) с указанной в (18) последовательностью параметров часто называют схемой Ричардсона.

При исследовании сходимости итераций вместо неявной схемы (2) достаточно рассматривать явную схему

или

которая соответствует уравнению

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

Однако на самом деле вычисления ведутся с конечным числом знаков и на каждом этапе вычислений появляются ошибки округления, которые приводят к неустойчивости при достаточно больших итерационной схемы с параметрами (18).

Неустойчивость схемы (2) с параметрами (18) можно проиллюстрировать на следующем простом примере, сосчитанном на машине БЭСМ-4 (расчеты проведены Д. А. Гольдиной). Пример. Требуется решить систему разностных уравнений

В этом случае

Возьмем 20 уравнений и положим Теоретическая оценка показывает, что для получения решения задачи с точностью достаточно взять где Параметры тьтг, выбираем по формуле (18) при

Результаты вычислений на БЭСМ-4 даны в таблице 1. В первой строке указан номер итерации к, во второй строке — величина

Итерационный процесс расходится, и при наступает аварийный останов машины.

Таблица 1 (см. скан)

Если брать параметры в обратном порядке, т. е. положить в формуле то неустойчивость итерационной схемы выражена более сильно и аварийный останов наступает при (см. таблицу 2).

Таблица 2 (см. скан)

Ошибки округления можно трактовать как возмущение правой части уравнения на каждом шаге. Итерационная схема (2) с параметрами (18) неустойчива по правой части. Причиной неустойчивости является тот факт, что норма оператора оператора перехода от итерации к итерации, при отрицательных может быть больше единицы, так как

и

В то же время

Установим эти формулы. Так как то Учитывая, что найдем

Подставим сюда что Тогда получим Отсюда видно, что при при Если и где наименьшее число, для которого и выполняется условие то Поэтому и погрешность округления, появившаяся при определении будет увеличиваться с ростом от до Пусть так что

Предположим, что Тогда

Теорема 1 фактически выражает устойчивость схемы (2) по начальным данным. В случае реального вычислительного процесса, как показывают приведенные выше примеры, необходимо исследовать устойчивость итерационной схемы по правой части, а также устойчивость по начальным данным при переходе от для любого Как было показано в гл. V, § 2, устойчивость по правой части есть следствие равномерной устойчивости по начальным данным, т. е. устойчивости при переходе от любого к любому где

Требование равномерной устойчивости по начальным данным гарантирует вычислительную устойчивость итерационной схемы. Поясним это утверждение. В результате ошибок округления находится не решение задачи (20), а решение задачи Чтобы оценить величину погрешности вычислений надо найти оценку решения задачи

через Из (21) следует (см. гл. V, § 2)

где

Достаточно убедиться в том, что величины ограничены для всех Заметим, что уравнение устойчиво по правой части с константой Предполагая, что получим

где

Потребуем, чтобы т. е.

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

Параметры будем определять по формуле

где выбирается из множества нулей полинома Чебышева:

Рассмотрим сначала случай, когда есть степень числа 2:

Основной принцип построения «устойчивой» последовательности параметров в случае, когда кратно состоит в выделении групп по 4 параметра Этой четверке параметров соответствует произведение (блок)

где

Будем определять по формулам

где Последовательность задана, если указаны параметра

При построении устойчивой последовательности будем исходить из минимального

и рассмотрим последовательно множества из параметров Эти множества строятся по рекуррентным формулам

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

Из формул для видно, что

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

Формулируем правило для вычисления При определении для

следует найти по формуле

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

Таким образом, надо находить лишь при и пользоваться указанным только что правилом при переходе от

Проиллюстрируем это правило. Итак, задано Полагая найдем

Чтобы найти возьмем формулу для и увеличим входящие в нее индексы 3 и 1 на

Далее, положим и определим

Применяя затем правило сдвига на Сразу напишем

и т. д. Если, например, то остается лишь найти четные

Если то нужно вычислить еще 8 параметров нечетных номеров. Имеем

Правило сдвига индексов вправо на дает:

Перейдем теперь к доказательству устойчивости схемы (2) с последовательностью параметров

Множеству соответствует произведение операторов

где

Нам понадобится норма произведения Так как есть полином степени относительно самосопряженного оператора то вычисление нормы

сводится к нахождению максимума полинома

Найдем выражение для Начнем с Вводя обозначения получаем

где

(см. скан)

Учитывая затем, что

находим искомую норму

где

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

Отсюда и из формулы для видно, что

Сравнивая формулы для видим, что если

Рассмотрим сначала выражение

так как

Аналогично найдем

Учитывая, что при и

получим

Поэтому для последовательно получим

и, наконец,

Полагая получаем

Полагая теперь в получим Применяя развитые выше методы, можно показать, что

Таким образом, для решения задачи (21) верна оценка

Приведем некоторые результаты расчета по явной схеме с параметрами где «устойчивый» набор. Рассматривается тот же пример:

Число уравнений В этом случае

Таблица 3 (см. скан)

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

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

Укажем без доказательства устойчивые наборы для

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

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

2. Основная теорема для стационарных схем.

Схемы с постоянными В их

обычно называют стационарными. Для и получаем однородное уравнение и операторами для которых выполнены условия (3), (4). Оно эквивалентно явной схеме

с оператором или

В этом случае где — постоянный самосопряженный (так как оператор и, следовательно,

Задача об отыскании сводится к задаче об отыскании нижней грани нормы оператора перехода 5. Эта задача хорошо известна и для конечномерного случая решена в § 1 (лемма 1). В произвольном гильбертовом пространстве имеет место аналогичная

Теорема 2. Пусть и выполнены условия

Тогда при достигается при

где

Доказательство. Так как 5 самосопряженный оператор, то

где

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

и, следовательно,

Функция как было показано в § 1, достигает минимума при и равна т. е.

что и требовалось доказать.

Следствие. Для схемы (23) при оптимальном значении параметра верны оценки

Замечание 1. Теорема 2 следует из теоремы 1, если положить При этом и

Замечание 2. Теорема 2 следует из необходимого и достаточного условия -устойчивости схемы (24) (см. гл. VI, § 1):

и условия ограниченности С,

В самом деле, Из равенств сразу получаем и

Для выбора оптимального итерационного параметра и вычисления достаточно знать постоянные эквивалентности операторов (т. е. границы оператора С). Поэтому отыскание при заданных является основной задачей теории. В следующих двух пунктах приведены примеры нахождения нижней грани нормы оператора перехода для операторов специального вида.

3. Вычисление нормы оператора перехода двухслойной схемы с весами.

Рассмотрим оператор

где Это оператор перехода схемы Требуется найти оптимальное значение из условия Представим в виде

где

Найдем границы оператора С или границы оператора Будем предполагать, что

Так как

так что

Воспользуемся теперь формулой или

т. е. Подставляя это значение со в (27), находим

Таким образом

Тот же результат можно получить, если записать схему с оператором перехода (25) в канонической форме

Отсюда и из (26) сразу находим

т. е. Дальнейшие рассуждения, приводящие к (28), остаются без изменения.

4. Неявный метод переменных направлений для случая неперестановочных операторов.

Перейдем ко второму, более сложному примеру применения теоремы 2. Пусть

где самосопряженные и неперестановочные операторы с границами

Для решения уравнения в этом случае применяют двухпараметрическую схему переменных направлений

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

Обозначая после исключения получим уравнение

с оператором перехода

Введем обозначения

Теорема 3. Пусть выполнены условия (29), где

Тогда для оператора перехода (32) при значениях параметров

верна оценка

т. е. для итерационной схемы (30) имеет место оценка

Доказательство. Нетрудно видеть, что из условий (34) следует положительность величин Произведем преобразование

так что Постоянная выбирается из условия

В результате преобразования (37) оператор (32) принимает вид

где

Для определения и оценки представим схему последовательности двух схем

каждую из которых запишем в каноническом виде

Параметр для обеих схем один и тот же. Учитывая, что неравенства

где

Пользуясь формулой по аналогии с предыдущим пунктом, находим

Из (38) и (39) следуют формулы (35) для итерационных параметров и

Теорема доказана.

Замечание. Теорема 3 остается справедливой, если вместо потребовать

При этом возможен

Пример. В квадрате рассмотрим задачу Дирихле для эллиптического уравнения

где граница квадрата. Пусть

квадратная сетка с шагом

Сформулируем разностную задачу Дирихле:

где граница сетки.

Для решения этой задачи применим метод переменных направлений (29), где формально положим

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

Рассмотрим оператор

Для погрешности где номер итерации, получаем задачу (30).

Операторы неперестановочны и имеют границы

так что

Поэтому справедлива оценка (36), где

Скорость сходимости итераций равна

число итераций при есть

Обратимся снова к схеме (29). Исключим из уравнений (30) величину

Запишем эту схему в каноническом виде

Если неперестановочны, то В не является самосопряженным оператором и поэтому к (40) нельзя применить теорему 2.

Лемма 1. Оператор (32) можно представить в виде

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

где дается формулой определяются согласно (35).

Доказательство. Первое утверждение леммы доказывается непосредственным вычислением. Докажем второе утверждение. Согласно теореме для любого т. е.

Отсюда получаем

Решая неравенство

получаем или

Отсюда и из (44) следуют неравенства (42), (43).

Замечание. Если перестановочны, то -самосопряженный оператор и из оценки следует

где юг даются теоремой 2.

Таким образом, нам в этом случае известны постоянные эквивалентности операторов .

5. Факторизованные итерационные схемы.

Оператор В в итерационной схеме естественно выбирать в некотором допустимом семействе операторов так, чтобы 1) отношение было максимальным минимальным), 2) В был экономичным оператором (число действий минимально в некотором смысле, например, по порядку относительно при При построении В обычно исходят из некоторого оператора (регуляризатора, ср. гл. VII, § 2), энергетически эквивалентного А и В:

Тогда справедливы неравенства

с постоянными

Зная можно пользоваться теоремой 2.

Оператор выбирается обычно как регуляризатор для нестационарной задачи (задачи Коши) с тем же оператором А. Примеры выбора демонстрировались в предыдущей главе.

Свойством экономичности обладает факторизованный оператор где экономичные операторы.

Предположим, что самосопряженный оператор можно представить в виде суммы

Рассмотрим два случая:

1) неперестановочны, но сопряжены друг другу (треугольные операторы)

так что

2) самосопряженные и перестановочные операторы

Каждый случай исследуем отдельно. Рассмотрим сначала факторизованный оператор с треугольными операторами

параметр. Очевидно, что

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

Будем предполагать, что оператор удовлетворяющий условиям (45), выбран и

Нетрудно заметить, что

Лемма 2. При любых и любых справедливо операторное неравенство

В самом деле для любого

Оценка (51) принадлежит Е. С. Николаеву.

Лемма 3. Пусть справедливы условия (50). Тогда выполняется операторное неравенство

Действительно, Из (51) и (52) следует, что выполнены неравенства (46) с

Параметр со выберем из условия максимума отношения

Вычислим производную

Отсюда видно, что максимум достигается при

так как

Найдем значение при

Подставляя в (53), определим

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

Для числа итераций при получаем следующую оценку

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

Теорема 4. Если выполнены условия (50), то итерационная схема (2) с и факторизованным оператором

сходится в и так что

где вычисляется по формуле (56). Для числа итераций при имеет место оценка

Пример. Рассмотрим задачу Дирихле для уравнения Лапласа в единичном квадрате. Оператор А равен

На сетке введем скалярное произведение и норму

и определим операторы

Пусть пространство сеточных функций, заданных на и равных нулю на границе Операторы сопряжены в друг другу, так как Следовательно, Вычислим постоянные входящие в условия (50). Так как то нижняя грань есть наименьшее собственное значение, . Далее,

так как

(см. гл. IV). Таким образом, Зная находим

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

Определение новых итераций из уравнения сводится к последовательному решению «одномерных» уравнений вида Заметим, что использование «треугольных» операторов позволяет получать явные формулы (формулы бегущего счета) для определения В самом деле, уравнение

имеет вид

откуда находим

Выбираем левый нижний угол области и берем пограничный узел, такой, что и лежат на границе сетки и, следовательно, известны. По формуле (57) определяем и дальше движемся либо по строкам, либо по столбцам. Аналогично убеждаемся, что из уравнения

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

6. Факторизованный оператор В с перестановочными операторами

Пусть где удовлетворяют тем же требованиям, что и операторы в п. 4. Перечислим эти требования (см. теорему 3):

Кроме того, мы предполагаем, что операторы перестановочны:

Рассмотрим схему (23) с факторизованным оператором

где вещественные параметры. Предполагается, что связаны неравенствами

Наша задача — определить постоянные

Для этого надо использовать результаты п. 4, где рассматривалась задача

(схема (40) с Оператор перехода для этой схемы представим в виде (32) (с заменой на Так как самосопряжены и перестановочны, то В — самосопряженный оператор.

Используем теорему 3 для вычисления постоянных эквивалентности операторов Учитывая перестановочность операторов схему (63) можно записать в виде

Из (58), в силу теоремы 3, следует оценка при выбранных согласно (35), эквивалентная неравенству

где определяется по формуле (36). Так как константы вычислены, то к Схеме (63) можно применить теорему 2. Тем самым доказана

Теорема 5. Пусть выполнены условия (58), (59), (45). Тогда итерационная схема (23) с факторизованным оператором (60) при оптимальных значениях определяемых по формулам (35), сходится со скоростью так что

где

дается формулой (36), а параметр определяется, в соответствии с теоремой 2, по формуле

Замечание. Так же, как и в теореме 3, вместо условия можно потребовать

Пример 1. Рассмотрим тот случай, когда регуляризатор совпадает с оператором так что а операторы имеют совпадающие границы:

Тогда

и скорость сходимости итерации (ср. с п. 5)

Пример 2. Рассмотрим случай, когда т. е. а одно из чисел равно нулю, например, («смешанная» задача). Тогда

Вычисления дают

Скорость сходимости

Сравнение с примером 1 показывает, что число итераций в случае смешанной задачи примерно в 1,5 раза больше.