Главная > Математика > Введение в теорию разностных схем
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 3. Итерационные двухслойные схемы для несамосопряженных уравнений

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

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

где несамосопряженные операторы,

Для решения уравнения рассмотрим схему переменных направлений (29) из § 2, п. 4 с параметрами

Для погрешности точнее, для получим уравнение (31) из § 2 с оператором (32) из § 2. При переходе от (30) из § 2 к (31), (32) из § 2 не требуется ни перестановочности ни их самосопряженности (предполагается лишь разрешимость задачи, т. е. существование операторов

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

Лемма 1. Пусть несамосопряженный оператор и выполнены условия (1). Тогда при любом справедлива оценка

Доказательство. Вычислим

Используя условия (1), имеем

Обозначая получим

что и дает оценку (2). Таким образом

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

Итак, имеет место оценка

если где Пусть Тогда Скорость сходимости итераций как показывает сравнение с п. 3, 4 § 2, в 2 раза меньше, чем в случае

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

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

2. Случай несамосопряженного оператора перехода.

Рассмотрим теперь уравнение

где А — положительно определенный несамосопряженный линейный оператор, заданный на вещественном гильбертовом пространстве

Для решения уравнения (3) будем пользоваться двухслойной итерационной схемой (2) из § 2 с самосопряженным положительно определенным оператором В. Выше было показано, что неявная схема (2) из § 2 эквивалентна явной схеме

при Эта схема, очевидно, соответствует уравнению где

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

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

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

— любой элемент.

Предполагая, что получаем

Выбирая из условия минимума трехчлена, находим

Таким образом, если для несамосопряженного оператора С выполнены условия (5), (6), то справедлива оценка

Улучшить эту оценку путем выбора не удается.

3. Оценка ... при увеличении объема информации.

Объем информации относительно оператора может быть увеличен заданием трех чисел вместо двух При этом оценка для улучшается и переходит в оценку для при Приближенное решение этой задачи было получено Ганом [2].

Здесь дается точное решение задачи о минимуме (см. А. А. Самарский [25]).

Представим С в виде суммы двух операторов, симметричного и кососимметричного

где С — сопряженный к С оператор, так что Обратимся к уравнению (4):

где произвольное число.

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

где заданные числа. Перейдем к оценке решения уравнения (4):

Наша задача — выбрать параметры и так, чтобы норма была минимальной. Так как самосопряженный оператор с границами и то, согласно теореме 2 из § 2,

Рассмотрим второе слагаемое в правой части неравенства (11):

так как

Итак, мы имеем

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

Условие дает

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

и решаем его:

(второй корень непригоден, так как он может быть отрицательным при некоторых значениях параметров Введем обозначение так что

Преобразуем подкоренное выражение откуда получим

Найдем теперь Учитывая, что получаем

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

Теорема 1. Пусть и выполнены условия (10):

Тогда при где

для нормы оператора перехода схемы (4) верна оценка

Замечание. Пусть С задан в комплексном гильбертовом пространстве

Тогда теорема 1 сохраняет силу.

Теорема . Пусть ,

- заданные числа. Тогда при для неявной схемы (2) из § 2 верны оценки

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

Тогда выполнены условия (18) с постоянными

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

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

Двухслойную итерационную схему

можно трактовать как метод поправок

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

находится поправка подставляя которую в (20), определяем итерацию При этом возникает вопрос о выборе Ранее мы имели дело с двумя формулами

(см. § 2, п. 1), или

где постоянные эквивалентности операторов А и В:

В случае несамосопряженного оператора А мы получили два типа оценок для скорости сходимости итераций и два типа формул для в зависимости от объема информации (даны или

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

или формулой метода минимальных поправок

(при метод минимальных невязок; М. А. Красносельский, С. Г. Крейн [1]).

Дадим вывод формулы (23). Пусть А — несамосопряженный положительно определенный оператор, В — самосопряженный положительно определенный оператор на гильбертовом пространстве Исходное уравнение (3) заменим эквивалентным уравнением

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

где

Переход от (24) к (21) осуществляется при помощи подстановок где Действуя затем на (24) оператором получим (20). Подставив в (25)

получаем формулу (23). Более просто формулу (23) можно получить из условия ортогональности где

или из условия минимума

Дифференцируя это выражение по находим (23) из условия равенства нулю производной.

Сходимость метода наискорейшего спуска (см. Л. В. Канторович [1]) и метода минимальных невязок (см. М. А. Красносельский, С. Г. Крейн [1]) доказана для случая где самосопряженный оператор.

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

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

Нам понадобится следующая основная

Лемма 3. Пусть С — несамосопряженный оператор с границами

и пусть существуют числа удовлетворяющие условию

и такие, что справедлива оценка

Тогда имеет место неравенство

Доказательство. По условию

для всех

Отсюда находим

или

По условию Вычислим

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

так что

Подставляя это значение в (30), получаем

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

Нетрудно убедиться, что и при или лемма сохраняет силу»

Теорема 3. Пусть С— несамосопряженный оператор, и выполнены условия

Тогда метод минимальных невязок

сходится со скоростью где

так что справедлива оценка

Доказательство. Будем исходить из уравнения для невязки Вычислим квадрат нормы

Условия (27) и (28) (см. теорему 1) выполнены при Поэтому верна оценка (29), пользуясь которой получаем

Если оператор С самосопряжен, то и мы получаем оценку

Такая оценка была получена М. А. Красносельским и С. Г. Крейном [1].

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

Введем обозначение Тогда для получим уравнение

Формула для примет вид

После этого повторяются рассуждения, приводящие к доказательству теоремы 3. В результате получаем оценку

Таким образом для метода наискорейшего спуска верна та же оценка

что и для явной схемы с постоянным

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

2. Для неявной схемы скорейшего спуска имеем

5. Двухступенчатый метод.

Рассмотрим уравнение

Для поправки получаем уравнение

Оператор В задается либо конструктивно, в явном виде (например, В есть факторизованный оператор

или

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

и выполнена одна из групп условий (18), (5), (6) при или условия (32) при

Для вычисления поправок уравнение

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

Итак, пусть дан некоторый метод внутренних итераций. Пусть разрешающий оператор этого метода, так что да) или где итерация номера точное решение уравнения (33). Если выполнены условия

то в силу самосопряженности будем иметь:

Подставляя в (33) и полагая дай получаем

где

Если перестановочны то легко находятся постоянные эквивалентности В самом деле,

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

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

где I — номер итерации, последовательность параметров, оператор положительно определен.

Чтобы свести эту схему к явной схеме перестановочность не нужна. Достаточно положить

и мы получим схему

где

Применим к (33) оператор

где точное решение уравнения (33). Для разности имеем

или

Отсюда находим

После подстановки этого выражения в (33) получим

где самосопряженный оператор.

Условие окончания итераций выполнено, если

Покажем, что где имеют значения, найденные ранее. Для этого рассмотрим

так как Отсюда и из оценок для следует

или Для внешних итераций

параметр можно выбирать одним из следующих способов.

I. Если самосопряженный оператор, то

1) используется чебышевская последовательность параметров где «устойчивый» набор, указанный в § 2, п. 1. При этом

II. Если несамосопряженный оператор и выполнены условия леммы 2, то полагаем

где определяется по формулам (16) с Если постоянные (см. лемму 2) эквивалентности операторов неизвестны или оцениваются слишком Грубо, можно вычислять

1) либо по формуле для неявного метода наискорейшего спуска

2) либо по формуле метода минимальных поправок

как в случае самосопряженного так и в случае несамосопряженного оператора.

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

Зная определим по формуле (23) параметр

В силу теоремы 1 имеет место оценка

где даны формулой (16), Если то

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

В частности, если есть сумма конечного числа попарно перестановочных самосопряженных положительных операторов, то для решения уравнения (33) можно

применить метод переменных направлений с циклическим набором параметров (см. § 1), или же с набором параметров по Жордану, если

Если оператор разностной задачи Дирихле в -мерном параллелепипеде, то условие будет выполнено после

итераций, где шаг сетки.

Если где самосопряженные, но неперестановочные операторы (например, в ступенчатой области), то внутренние итерации можно проводить по продольно-поперечной схеме (см. § 1). Далее, в случае т. е. когда «треугольные» операторы, используем неявную схему с факторизованным оператором При этом берется упорядоченная чебышевская последовательность параметров

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

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

Однако, в ряде случаев этот метод является весьма экономичным.

Двухступенчатый метод для решения дифференциальных уравнений рассматривался Л. В. Канторовичем [2], Б. А. Самокишем [1] и др., а для разностных эллиптических уравнений — Е. Г. Дьяконовым [2], [7], Ганом [1], [2], С. Г. Михлиным [1]. При этом в качестве регуляризатора выбирался разностный оператор Лапласа, а внутренним итерационным процессом для решения уравнения являлся метод переменных направлений с циклическим набором итерационных параметров.

Комбинация вариационного метода с методом переменных направлений рассматривалась Г. И. Марчуком [2], С. К. Годуновым и Г. П. Прокоповым [1].

<< Предыдущий параграф Следующий параграф >>
Оглавление