Итерационные методы решения сеточных уравнений с седловым оператором тема автореферата и диссертации по математике, 01.01.07 ВАК РФ



■' /

*у / ^

Московский Государственный Университет имени М.В. Ломоносова

Механико — математический факультет

На правах рукописи

7.

у ^

ЧИЖОНКОВ ЕВГЕНИЙ ВЛАДИМИРОВИЧ

ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ С СЕДЛОВЫМ ОПЕРАТОРОМ

Специальность 01.01.07 — вычислительная математика

Диссертация на соискание ученой степени доктора физико - математических наук

.диум ВАК России

т, ,1й С" 19 № ^¿М

Москва \ д ученую степсшь Д^Ж

г..

"и'

■ -наук

начальник управления ВАК России

Оглавление

Введение 8

1 Общие сведения и вспомогательные результаты 32

1.1 Краткие сведения о методах релаксации........33

1.1.1 Общие понятия ..................33

1.1.2 Метод Якоби ...................34

1.1.3 Метод SOR ....................36

1.1.4 Метод SSOR....................38

1.2 Задачи, приводящие к системе сеточных уравнений с седловым оператором...................41

1.2.1 Обобщенная задача Стокса ...........41

1.2.2 Уравнения Ламе в теории упругости и слабо-сжимаемая жидкость...............43

1.2.3 Смешанный подход при решении эллиптических уравнений ..................45

1.2.4 inf - sup условие .................47

1.3 Вспомогательные утверждения.............49

1.3.1 Две задачи на собственные значения......50

1.3.2 Базис специального вида из собственных векторов ........................53

1.4 Резюме...........................55

2 Модифицированные методы релаксации для систе-

мы уравнений типа Стокса 57

2.1 Модифицированный метод Якоби (MJOR).......57

2.1.1 Построение метода................58

2.1.2 Спектр оператора перехода ...........59

2.1.3 Необходимое и достаточное условие сходимости .........................61

2.1.4 Задача асимптотической оптимизации.....64

2.2 Модифицированный метод SOR (MSOR).......67

2.2.1 Построение метода................67

2.2.2 Спектр оператора перехода ...........68

2.2.3 Необходимое и достаточное условие сходимости .........................71

2.2.4 Задача асимптотической оптимизации.....73

2.3 Модифицированный метод SSOR (MSSOR).....76

2.3.1 Построение метода................76

2.3.2 Спектр оператора перехода ...........78

2.3.3 Необходимое и достаточное условие сходимости .........................81

2.3.4 Задача асимптотической оптимизации.....82

2.4 Трехпараметрический метод типа SOR (3MSOR) ... 83

2.4.1 Построение метода................83

2.4.2 Спектр оператора перехода ...........84

2.4.3 Задача асимптотической оптимизации.....87

2.4.4 Частный случай— {¡3,т) - метод .......97

2.5 Резюме...........................100

3 Оценки погрешности для методов MJOR и MSOR 101

3.1 Оценки погрешности из общей теории итерационных

методов ........................... 102

3.1.1 Оптимальный одношаговый метод.......102

3.1.2 Метод Ричардсона с чебьппевскими параметрами ........................103

3.1.3 Полуитерационный метод Чебышева......104

3.1.4 Стационарный трехслойный метод.......105

3.1.5 Методы сопряженных направлений.......106

3.2 Оценка погрешности для метода MJOR.......108

3.2.1 Преобразование формул.............108

3.2.2 Начальное приближение .............110

3.2.3 Оценка погрешности...............110

3.3 Оценка погрешности для метода MSOR с постоянными параметрами....................112

3.3.1 Преобразование формул.............112

3.3.2 Начальное приближение .............114

3.3.3 Полином ошибки .................115

3.3.4 Оценка погрешности...............116

3.4 Оценки погрешности для метода MSOR с переменными параметрами....................118

3.4.1 Преобразование формул.............119

3.4.2 Оценка погрешности для р типа метода Ричардсона ......................121

3.4.3 Наилучшая оценка погрешности для р.....122

3.4.4 Наилучшая оценка погрешности для и.....124

3.5 Резюме...........................129

4 Методы типа MSOR для системы уравнений с параметром 130

4.1 Явный метод MSOR (MSORe) .............130

4.1.1 Построение метода................131

4.1.2 Спектр оператора перехода...........131

4.1.3 Необходимое и достаточное условие сходимости .........................134

4.1.4 Задача асимптотической оптимизации.....136

4.2 Неявный метод MSOR (iMSORe) ............138

4.2.1 Построение метода................138

4.2.2 Спектр оператора перехода...........139

4.2.3 Необходимое и достаточное условие сходимости .........................141

4.2.4 Задача асимптотической оптимизации.....144

4.3 Резюме...........................145

5 Оценки погрешности для метода MSORe 147

5.1 Оценка погрешности для метода MSORe с постоянными параметрами...................148

5.1.1 Преобразование формул.............148

5.1.2 Начальное приближение .............150

5.1.3 Полином ошибки .................151

5.1.4 Оценка погрешности...............152

5.2 Оценки погрешности для метода MSORe с переменными параметрами ...................154

5.2.1 Преобразование формул.............155

5.2.2 Оценка погрешности для р типа метода Ричардсона ......................157

5.2.3 Наилучшая оценка погрешности для р.....158

5.2.4 Наилучшая оценка погрешности для и.....161

5.3 Резюме...........................165

6 Оптимизация в методах симметризации с предобу-словливанием 166

6.1 Оптимизация для системы уравнений типа Стокса . 166

6.1.1 Спектр равносильной задачи ..........167

6.1.2 Минимизация числа обусловленности .....169

6.1.3 Наилучшая оценка погрешности ........170

6.2 Оптимизация для системы уравнений с параметром . 171

6.2.1 Спектр равносильной задачи ..........171

6.2.2 Минимизация числа обусловленности .....174

6.2.3 Наилучшая оценка погрешности ........177

6.3 Оптимизация для системы, равносильной системе типа Стокса .........................177

6.3.1 Спектр равносильной задачи ..........178

6.3.2 Минимизация числа обусловленности .....181

6.3.3 Наилучшая оценка погрешности ........184

6.4 Резюме...........................185

I Оценки нижней границы спектра для оператора давления, ассоциированного с задачей Стокса 186

1.1 Область прямоугольной формы.............188

1.1.1 Оценка сверху...................190

1.1.2 Оценка снизу ...................192

1.1.3 Основной результат ...............197

1.2 Область типа многоугольника..............199

1.2.1 Сингулярность собственных функций.....199

1.2.2 Основной результат ...............202

1.3 Область кольцевой формы................203

1.3.1 Асимптотический анализ ............210

1.4 Область типа кольцевой трубы .............211

1.4.1 Асимптотический анализ ............217

. 1.5 Резюме...........................218

II Численное исследование нижней границы спектра для оператора давления в областях прямоугольной

формы 219

II. 1 MAC - схемы для первой краевой задачи Стокса . . . 22Q

11.1.1 Вычислительные аспекты ............220

11.1.2 Схема 1.......................222

И.1.3 Схема 2.......................224

11.1.4 Схема 3.......................226

11.1.5 Результаты расчетов...............227

11.2 МКЭ - схемы для первой краевой задачи Стокса . . . 230 И.2.1 Схема 4.......................230

11.2.2 Схема 5.......................233

11.2.3 Результаты расчетов...............237

11.3 Интегральное уравнение.................238

11.3.1 Вывод уравнения .................239

11.3.2 Построение формулы Грина...........242

11.3.3 Метод решения и результаты расчетов .... 245

11.4 Резюме...........................249

Литература 250

Введение

Применение различных приближенных методов для отыскания реи о ° -I

шении уравнении математической физики, как правило, приводит к необходимости решать системы линейных алгебраических уравнений, обладающих следующей спецификой: большая размерность вектора неизвестных, плохая обусловленность и ленточная структура матрицы системы. Отмеченные свойства порождают приоритетное развитие итерационных методов решения таких систем, называемых сеточными. Библиография работ по этой тематике не поддается учету, однако достаточно полное представление о современном состоянии теории итерационных методов решения сеточных уравнений можно получить из следующих изданий: Young D.M. Iterative Solution of Lager Linear Systems (1971) [100], Map-чук Г.И. Методы вычислительной математики (1977) [32], Самарский A.A., Николаев E.G. Методы решения сеточных уравнений (1978) [44], Hackbusch W. Multi - Grid Methods and Applications. (1985) [89], Дьяконов Е.Г. Минимизация вычислительной работы. Асимптотически оптимальные алгоритмы для эллиптических задач (1989) [12].

Решение сеточных уравнений с седловым оператором привлекло внимание исследователей в области численного анализа отно-

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

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

Отметим в условно - хронологическом порядке авторов, внесших заметный вклад в построение и исследование алгоритмов решения седловых задач : Arrow К., Hurwicz L., Uzawa H., Crouzeix M., Temam R., Girault V., Raviart P.A., Langer U., Queck W., Bank R.E., Welfert B.D., Yserentant H., Bramble J.H., Pasciak J.E., Elman H., Golub G., Silvester D.J., Wathen A. за рубежом, Кобельков Г.M., Дьяконов Е.Г., Бахвалов H.С., Пальцев Б.В., Ольшанский М.А. в нашей стране. Однако, несмотря на представительность библиографии, следует обратить внимание на отсутствие до настоящего времени в литературе сколь - нибудь систематического изложения теории итерационных методов решения седловых систем, содержащей как анализ сходимости, так и сравнение вычислительной эффективности различных алгоритмов. Кроме того, отметим чрезвычайную редкость, не только решений, но и самих постановок

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

Приведем краткое изложение основных идей построения алгоритмов в этой области, для единообразия будем использовать алгебраическую терминологию. Рассмотрим вещественную систему линейных алгебраических уравнений Ьгх = Р с параметром £ > О следующего вида

где А = Ат > О, С = Ст >0 — квадратные матрицы размеров 7Уи х и ТУр х Мр, а В — прямоугольная, в общем случае, матрица размера ]Уи х . Предполагается невырожденность матрицы Ь£ при любом г > 0, что делает ее седловым оператором [12]. Системой типа Стокса будем называеть наиболее важный частный случай задачи (0.1) — = Р (е = 0). Ограничимся при перечислении библиографии только им, как наиболее сложным и принципиальным (т.к. из е > 0 немедленно следует сЫ;(£е) ф 0).

С точки зрения приложений, самым распространенным подходом к решению задачи — Р является построение алгоритмов типа Удзавы (Цгад^а). В самой простой форме [66] его можно записать следующим образом:

Здесь ть — вещественный переменный итерационный параметр.

Для случая постоянного параметра г*. = г 11.Тетат [46] получил достаточное условие сходимости метода (0.2) в дифференциальной форме:

(0.1)

(0.2)

0 < т < 2.

Наличие здесь абсолютной постоянной, равной двум, связано с тем, что в дифференциальном случае спектр оператора ВТА~1В принадлежит отрезку [7,1],7 > 0.

Этот результат улучшил M.Crouzeix [80], получив также в дифференциальном случае достаточное условие сходимости следующего вида:

0 < Щтк) < sup(г*.) < 2 . * к

В этой же работе, видимо впервые, было отмечено, что алгоритм Удзавы (0.2) эквивалентен методу простой итерации для системы уравнений с симетричной положительно определенной матрицей А0 = ВТА~1В:

Р~-V- + A,Vk = BTA~1f + g = f (0.3)

п

Такая форма записи позволяет использовать результаты общей теории итерационных методов для знакоопределенных матриц: выбор оптимальных последовательностей параметров и соответствующие оценки скорости сходимости. В частности, в [80] приведены формулы для параметров и оценки погрешностей для оптимального одношагового метода, циклического ¿-шагового метода и полуитерационного метода Чебышева.

Далее V.Girault и P.A.Raviart в книге [87] доказали сходимость методов наискорейшего спуска и сопряженных градиентов для решения системы

Aöp = f (0.4)

в абстрактном банаховом пространстве, а U.Langer и W.Queck [92] получили оценки их скоростей сходимости для сеточных систем, возникающих при аппроксимации задачи Стокса в гидродинамике.

Дальнейшее развитие этого подхода заключается в построении различными способами для конкретных сеточных систем операто-

ров предобусловливания С таких, что отношение констант эквивалентности Г/7 в матричном неравенстве 7 С < А0 < ГС минимально. Следует отметить, что здесь в полной мере используется специфика конкретных задач, и, поэтому, эта тематика — неисчерпаема. Приведем несколько примеров. Для задачи Стокса с параметром

—Ди + gradp 4- а и = Г в О,

а1уи = 0 в П (0.5)

и = 0 на дО

возникающей при неявной дискретизации по времени нестационарной первой краевой задачи Стокса, ХСаЬох^ и Л.Р.СЬаЬаг^ [73] предложили, а М.А.Ольшанский [38] обосновал использование оператора предобусловливания с постоянными эквивалентности 7 и Г, не зависящими как от шагов сетки, так и от параметра а. Для различных дискретизаций классической задачи Стокса (а — 0) Н.С.Е1тап и С.Н.СоЫЬ [85] проанализировали диагональные и трехдиагональные операторы предобусловливания. Для классической задачи Стокса в области типа вытянутого прямоугольника М.А.Ольшанский [94] предложил оператор предобусловливания с постоянными, не зависящими как от шагов сетки, так и от отношения сторон прямоугольника. Различные варианты операторов предобусловливания многосеточного типа в сочетании с вариационными методами решения возникающих систем рассматривали Я-Уег^Ь [97] и Н.С.Е1тап [84].

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

малых числах Рейнольдса. Даже при решении линеаризованной задачи оператор перехода является несимметризуемым [86], и вся имевшаяся ранее теория выбора итерационных параметров и получения оценок скорости сходимости становится неприменимой. Вторая проблема связана с необходимостью обращения на каждой итерации оператора А. Хотя здесь трудность носит другой характер (трудоемкость этой операции может быть сравнима с трудоемкостью решения исходной задачи в целом, например, когда матрица А возникает при дискретизации бигармонического оператора), попытка ее преодоления за счет обращения спектрально

- эквивалентного оператора также приводит к несимметризуемо-сти оператора перехода в методах типа Удзавы. Наиболее продвинутые результаты в этих направлениях получили J.H.Bramble, J.E.Pasciak и A.T.Vassilev [70], [71], работы которых служат наилучшей иллюстрацией к сказанному. Приведенные в них оценки скорости сходимости получены в несколько искусственной метрике и весьма далеки от предельных.

Для преодоления первой из указанных проблем еще в книге К.Arrow, L.Hurwicz, H.Uzawa [66] был предложен алгоритм Эрроу

- Гурвица

А- + Аик + Врк =/

(0.6)

+ Вт ик+1 = д

т

содержащий два итерационных параметра и являющийся обобщением алгоритма Удзавы на случай т ф 1. Оператор перехода в этом методе является несимметризуемым, зависимость его собственных значений от итерационных параметров — нелинейной. Следствием этого является чрезвычайно малое количество работ по исследованию этого метода, при этом использование в них энер-

т

рк+1 _ рк а-:—

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

Один из первых результатов получил M.Crouzeix [80], доказав в дифференциальном случае достаточное условие сходимости следующего вида:

0 < т < 1, 0 < т/а < 2.

Далее R.Temam [46] получил другое достаточное условие сходимости метода (0.6) в дифференциальной форме:

0 < т < 2а/(а + 1), Va > 0.

Наконец, W.Queck [95] попытался минимизировать оценку сверху для скорости сходимости в пред обусловленном методе Эрроу -Гурвица. В наших обозначениях оптимальные параметры выглядят так: Topt = 1/2, aopt = 1. Если обозначить погрешность решения на А;-ой итерации через ук = (vk,rk) = (ик — и,рк — р), где (и,р) — точное решение задачи Lqz = F, и определить норму погрешности как \\у\\2 = (г>,г>)/4 + (г,г), то метод (0.6) будет сходиться с оценкой погрешности

uuif^tfh

если спектр оператора ВТА~1В принадлежит отрезку [7,1],7 > 0.

Важным направлением исследований является также построение операторов предобусловливания для матрицы исходной системы L0. Диагональное и блочное предобусловливание анализировали в своих работах A.Wathen и D.Silvester [98], [99]. Многосеточный метод с диагональным предобуславливанием рассматривал В.В.Шайдуров [62]. В этом же ряду следует отметить работу J.H.Bramble, J.E.Pasciak [69], в которой для предобусловленной системы уравнений, равносильной исходной, удалось ввести искусственную метрику такую, что полученная матрица стала в ней симметричной и знакоопределенной.

Предпринимались попытки построения итерационных методов с модельными седловыми операторами. Видимо впервые, оценки скорости для их сходимости получены Е.Г.Дьяконовым [13]. Аналогичные исследования провели позднее R.E. Bank, B.D.Welfert, H.Yserentant Н. [68]. Сочетание модельных седловых операторов с итерациями в подпространстве и методом фиктивных областей проанализировано в работах Н.С.Бахвалова [6], [67].

По - видимому, первым удачным алгоритмом, допускающим обобщения на близкие, даже нелинейные, задачи был предложенный Г.М.Кобельковым (¡3, т) - метод, использующий блочно - треугольную факторизацию оператора исходной задачи [22], [23]. К сожалению, даже в линейном случае условия сходимости этог�