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

Глава VIII. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ РАЗНОСТНЫХ ЭЛЛИПТИЧЕСКИХ УРАВНЕНИЙ

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

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

В § 1 этой главы мы рассматриваем современные экономичные итерационные схемы, применяемые для решения разностной задачи Дирихле в прямоугольнике.

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

§ 1. Двухслойные итерационные схемы для разностной задачи Дирихле

1. Итерационные схемы.

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

при стремится к решению стационарной задачи

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

где - отклонение от стационарного решения, стремится к нулю при и любой функции

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

так что где символ Кронекера, а

Тогда решение задачи (3) имеет вид (см. А. Н. Тихонов и А. А. Самарский [6], гл. VI):

В силу условия имеем

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

Требование , где любое число, будет, очевидно, выполнено при

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

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

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

Будем рассматривать А как линейный оператор, заданный на некотором линейном нормированном пространстве заданный произвольный вектор из .

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

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

Обычно к итерационным схемам предъявляется естественное требование: решение уравнения (4) при произвольном должно удовлетворять уравнению (5), т. е.

Так как и не зависит от то это уравнение и уравнение (4) будут выполнены, если потребовать

Выражая через перепишем (5) в канонической форме

Чтобы определить отсюда последовательно надо задать начальное приближение Итак, получаем задачу

Итерационная схема (6) при любых точно аппроксимирует уравнение (4) на его решении и. Это значит, что

разность где точное решение уравнения решение задачи (7), удовлетворяет однородному уравнению

Говорят, что итерационный процесс (схема) (7) сходится, если

где - некоторая норма.

Сравнивая (6) с двухслойной схемой, рассмотренной в мы видим, что одношаговая итерационная схема по форме совпадает с двухслойной схемой для нестационарных уравнений вида

Поэтому вместо слов «одношаговая итерационная схема» можно говорить «двухслойная итерационная схема».

Таким образом, любой итерационный процесс вида (6) сводится к решению нестационарной задачи.

Различие между итерационными схемами и схемами для нестационарных задач заключается в следующем:

1) при любых решение и исходной задачи (4) удовлетворяет уравнению (6),

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

Параметр можно рассматривать как шаг (переменный в общем случае) по фиктивному времени

Обычно задается некоторая точность с которой надо найти приближенное решение задачи (4). Если то требуется, чтобы выполнялось условие

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

Так как точное решение и неизвестно, то условие (9) неудобно для практической проверки. Его можно заменить одним из условий

где -невязка в уравнении (4) при подстановке вместо и. Если при некотором выполнено одно из условий (10) или (11), то считается, что требуемая точность достигнута, и вычисление последующих приближений прекращается. В могут фигурировать, вообще говоря, разные

В общем случае в качестве меры сходимости итераций принимается отношение «II и т. д., так что например, требования (9) и (11) заменяются требованием

Уравнению (4) можно поставить в соответствие большое число итерационных схем (6) с любыми Как следует выбирать

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

Общий объем вычислений равен где число действий для вычисления итерации номера или где среднее число действий для одной итерации. Если удовлетворяет требованию экономичности (например, где число узлов сетки в случае разностного эллиптического уравнения), то задача о минимуме сводится к задаче о минимуме числа итераций

Запишем (6) в виде

Отсюда видно, что зависит только от вида Укажем пичные формы экономичных операторов:

1) - единичный оператор (явная схема (6)),

2) - треугольный оператор (с треугольной матрицей),

3) - факторизованный оператор вида где экономичные операторы.

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

Мы остановимся подробно на итерационных схемах для разностной задачи Дирихле.

2. Схема простой итерации (явная схема).

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

Соответствующая разностная задача Дирихле имеет вид

где

— сетка с шагами граница сетки. Задача (14) подробно исследована в гл. IV, § 1.

Простейшей двухслойной итерационной схемой является явная схема (метод Якоби) с постоянным параметром:

Так как определяется по явной формуле то число итераций зависит только от параметра который выбирается из условия минимума числа итераций (такая задача решается точно). Чтобы иайти рассмотрим устойчивость по начальным данным однородного уравнения с однородными граничными условиями и произвольными начальными данными

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

линейный оператор, заданный на

В гл. IV, § 2 было показано, что А является линейным самосопряженным оператором, и

где

Здесь 6— наименьшее, наибольшее собственные значения оператора так что собственное значение номера оператора А. Оценка (17) является точной.

Задача (16) эквивалентна операторному уравнению

Решая (19) относительно получим

где — оператор перехода. Из (20) находим

где разрешающий оператор. Оценим

так как поскольку (см. гл. I, § 3). Итерации сходятся, если Требование будет, как видно из (22), выполнено, если т. е.

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

Чем меньше тем меньше (тем больше скорость сходимости). зависит от Выберем из условия минимума Так как то равна модулю наибольшего собственного значения оператора 5:

Из определения 5 (20) следует, что где собственное значение оператора В результате мы приходим к следующей задаче минимакса: найти то значение параметра при котором достигается

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

Лемма 1. Если

Доказательство. Рассмотрим функции Они изображены на рис. убывает при и возрастает при убывает при и возрастает при Так как то кривые пересекаются в точке причем Приравнивая эти выражения: находим

Рис. 20.

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

Подставляя сюда вместо их значения (18), находим

В случае квадратной сетки, т. е. при имеем Схема (15) принимает вид

Подсчитаем число итераций, достаточное для достижения точности Для простоты предположим, что тогда Формула (27) дает

Оценим асимптотический порядок для числа итераций при :

т. е. число итераций пропорционально числу узлов сетки и является величиной Так как то общее число действий

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

В настоящее время имеются методы, которые обеспечивают точность

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

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

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

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

3. Неявный метод переменных направлений (продольно-поперечная схема).

Рассмотрим задачу (14). В качестве итерационной схемы возьмем продольно-поперечную схему с переменным шагом по времени для уравнения теплопроводности (1):

где и - промежуточное значение (подитерация), а произвольное начальное приближение,

числа. Эта схема была рассмотрена для уравнения теплопроводности в гл. VII,

§ 1. Так как в данном случае граничное значение не зависит то для вычисления поправка не вводится, и . В гл. VII был описан алгоритм решения методом прогонки системы алгебраических уравнений (31), (32). Он сводится к последовательному решению по строкам уравнений вида

и по столбцам уравнений вида

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

Для вычисления одной итерации требуется арифметических действий. Ускорение сходимости итераций, по сравнению с явной схемой, достигается за счет соответствующего выбора параметров Каждое из уравнений (31) и (32) аппроксимирует задачу (14) точно. Поэтому для погрешности и получим однородную задачу

Рассмотрим сеточное пространство введенное в предыдущем пункте, и обозначим где любой вектор из Операторы А, и обладают, как показано в гл. IV, § 2, следующими свойствами:

1) самосопряженные операторы,

2) положительно определенные и ограниченные операторы: или

где

3) операторы и перестановочны.

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

Перепишем задачу (33) в виде

Задан произвольный вектор 2° из

Исключая, как было показано в гл. получим факторизованную схему

В силу перестановочности отсюда следует:

где оператор перехода, равный

Применяя формулу (38), найдем

где разрешающий оператор, равный

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

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

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

где и собственные числа, соответствующие одному и тому же собственному вектору.

Пусть собственное значение номера оператора Тогда будем иметь (номера опускаем)

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

причем

где определяются по формулам (35). Из (40) получим оценку

Норма оператора согласно (42) и (44), равна

Так же, как и в п. 2, мы приходим к следующей задаче минимакса: найти такой набор параметров чтобы норма оператора была минимальна при заданном Заменим в непрерывными аргументами При этом правая часть в (46), вообще говоря, увеличится и знак равенства в (46) следует заменить знаком -С. В результате мы приходим к следующей задаче минимакса: найти такие положительные числа любое заданное число), при которых достигается

Точное решение этой задачи найдено Жорданом (см. Вашпресс [3]). Мы изложим основные этапы его рассуждений (без обоснования заключительного этапа). Кроме того, мы дадим приближенное решение задачи минимакса; это решение может

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

4. Выбор итерационных параметров.

Две системы параметров выбираются в (31), (32) потому, что собственные значения операторов расположены на разных отрезках. Если то выбирается одна система параметров т. е.

Если же то с помощью дробно-линейного преобразования переменных задачу (47) можно свести к задаче минимакса для случая, когда спектры операторов лежат на отрезке где Тогда вместо двух параметров можно взять один параметр. Итак, рассмотрим функцию

где

Вместо введем новые переменные меняющиеся на отрезке где Для этого положим

где - постоянные, подлежащие определению. Требуя, чтобы при при получим четыре уравнения для

Прежде, чем решать эти уравнения, преобразуем функцию

где

Вернемся к системе уравнений (49). Выразим через

Подставив (52) в (49), получим два уравнения:

Введем вместо новую постоянную так что Тогда уравнения (53) преобразуются к виду

Перемножая эти равенства, исключим и найдем

Зная определим из (54) и из (52):

Нетрудно убедиться в том, что Таким образом, преобразована к виду (50). Так как входят в (50) симметрично, а меняются на одном и том же отрезке, то полагаем

Тогда вместо (47) получаем задачу о нахождении минимакса

1) Выбор параметров «по Жордану». Решение задачи (57) найдено Жорданом и приводится в статье Вашпресса [3]. Оно довольно громоздко и мы не будем его излагать. Приведем здесь лишь формулы для вычисления оптимальных параметров Пусть задана точность итерационного процесса и пусть известны границы операторов

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

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

получим для вычисления формулу

Теперь остается определить, согласно (51), искомые параметры

При этих значениях параметров для задачи (31), (32) справедлива оценка

После этого можно приступать к решению задачи (31), (32). Рассмотрим частный случай: Формула (55) дает:

При этом и преобразование (48) примет вид и Условие дает

2) Циклический набор параметров. Другой, более грубый, способ выбора параметров для разностной задачи Дирихле в квадрате на квадратной сетке был предложен в 1955 году Писменом и Рэкфордом [1] (см. также А. А. Самарский, В. Б. Андреев [1]). Преобразование, проведенное в начале этого пункта, сводит задачу для прямоугольника с к задаче для квадрата с квадратной сеткой. Поэтому, достаточно рассмотреть задачу о минимаксе функции (заменим в на

Набор параметров представляет собою циклов параметров так что где

Параметры выберем так, чтобы

где не зависит от

Лемма 2. Пусть даны функция

и два числа Тогда

Найдем Так как при при то принимает наибольшее значение либо при либо при

Из леммы 2 следует, что, если условие

выполнено хотя бы для одного при любых , то

Последовательность выберем так, чтобы для каждого нашлось хотя бы одно значение такое, что выполняется (63) и, следовательно, (64).

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

(числа подлежат определению). Тогда любое значение 1] будет принадлежать некоторому отрезку т. е.

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

Потребуем, чтобы выполнялись условия

где и положительные числа, не зависящие от Отсюда находим

Требования будут выполнены, если

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

Из (65) определим последовательность Так как то

Таким образом, образуют убывающую геометрическую прогрессию. Из (67) видно, что число параметров

равно частности, для задачи Дирихле в квадрате на квадратной сетке с шагом имеем следовательно, После итераций с параметрами в силу (64) справедлива оценка

где

и любые числа, удовлетворяющие условию

Проведем теперь циклов с набором параметров определенных выше, полагая

В силу (69) имеем Отсюда следует, что

Условие

будет выполнено при Отсюда находим

Таким образом для решения задачи (31), (32) после циклов с набором параметров (по ним из формул (59) находятся где определяются согласно (67) и (73), для общего числа итераций верна оценка

где постоянная, зависящая от параметров и Так как то убывает с убыванием Поэтому при фиксированном число минимально, если минимально Минимум очевидно, достигается при Отсюда находим и

Минимум находится численно:

Сравнение (74) с (58) показывает, что циклический набор параметров не является оптимальным. Однако асимптотические

порядки формул (74) и (58) совпадают (с точностью до множителя):

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