Итерационные методы решения седловых задач: Монография

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

Ю.В. Быченков, Е.В. Чижонков

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

Москва БИНОМ. Лаборатория знаний 2010

УДК 519.6 ББК 22.19 Б95 Б95

Быченков Ю. В. Итерационные методы решения седловых задач / Ю. В. Быченков, Е. В. Чижонков. — М. : БИНОМ. Лаборатория знаний, 2010. — 349 с. : ил. — (Математическое моделирование). ISBN 978-5-9963-0118-8 Впервые в одной книге рассматриваются все известные итерационные методы для больших систем линейных алгебраических уравнений блочной структуры, которые имеют в качестве решения седловую точку: подробно анализируются идеи построения, условия сходимости и вопросы оптимизации. Результаты анализа представлены в виде удобных для использования формул. Имеющееся приложение ориентировано на применение теории для численного моделирования в гидродинамике и смежных областях. Для научных работников в области вычислительной математики, аспирантов и студентов, а также для инженеров и исследователей в прикладных областях. УДК 519.6 ББК 22.19

Первый тираж издания осуществлен при финансовой поддержке Российского фонда фундаментальных исследований по проекту № 09-01-07025 Научное издание Серия: «Математическое моделирование» Быченков Юрий Владимирович Чижонков Евгений Владимирович ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЕДЛОВЫХ ЗАДАЧ Ведущий редактор М. С. Стригунова Художественный редактор Н. А. Новак Технический редактор Е. В. Денюкова Корректор Д. И. Мурадян Оригинал-макет подготовлен М. Ю. Копаницкой в пакете LATEX 2ε Подписано в печать 30.03.10. Формат 60×90/16. Усл. печ. л. 22. Тираж 600 экз. Заказ Издательство «БИНОМ. Лаборатория знаний» 125167, Москва, проезд Аэропорта, д. 3 Телефон: (499) 157-5272, e-mail: [email protected], http://www.Lbz.ru

ISBN 978-5-9963-0118-8

c БИНОМ. Лаборатория знаний,  2010

ОГЛАВЛЕНИЕ

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

Часть I. Релаксационные методы

..................

7

Вводные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Основные обозначения и постановка задачи . . . . . . . . Метод Узавы — сопряженных градиентов . . . . . . . . . . . Вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . 1.3.1. Две задачи на собственные значения . . . . . . . . 1.3.2. Базис специального вида из собственных векторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3. Полезное начальное приближение . . . . . . . . . . . 1.4. Библиография и комментарии . . . . . . . . . . . . . . . . . . . .

8 8 10 13 14 15 17 19

Глава 2. Модифицированные методы релаксации. Общий анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1. Сведения о методах релаксации . . . . . . . . . . . . . . . . . . . 2.1.1. Общие понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2. Метод Якоби . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3. Метод SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4. Метод SSOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Модифицированный метод Якоби (MJOR) . . . . . . . . . 2.2.1. Построение метода . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Спектр оператора перехода . . . . . . . . . . . . . . . . . 2.2.3. Условие сходимости . . . . . . . . . . . . . . . . . . . . . . . 2.2.4. Задача асимптотической оптимизации . . . . . . . 2.2.5. Оптимизация в подпространстве . . . . . . . . . . . . 2.3. Модифицированный метод SOR (MSOR) . . . . . . . . . . . 2.3.1. Спектр оператора перехода . . . . . . . . . . . . . . . . . 2.3.2. Условие сходимости . . . . . . . . . . . . . . . . . . . . . . . 2.3.3. Задача асимптотической оптимизации . . . . . . . 2.4. Модифицированный метод SSOR (MSSOR) . . . . . . . . . 2.4.1. Спектр оператора перехода . . . . . . . . . . . . . . . . .

22 22 22 23 25 26 28 28 29 31 33 38 40 40 41 43 45 46

Глава 1. 1.1. 1.2. 1.3.

Оглавление 345

2.4.2. Условие сходимости . . . . . . . . . . . . . . . . . . . . . . . 2.4.3. Задача асимптотической оптимизации . . . . . . . 2.5. Трехпараметрический метод (3MSOR) . . . . . . . . . . . . . 2.5.1. Спектр оператора перехода . . . . . . . . . . . . . . . . . 2.5.2. Задача асимптотической оптимизации . . . . . . . 2.5.3. Частный случай: (β, τ )-метод . . . . . . . . . . . . . . . 2.5.4. Задача асимптотической оптимизации (β, τ ) — метода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . Глава 3. Оценки погрешности методов MJOR и MSOR . . . . . . 3.1. Оценки из общей теории . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Оптимальный одношаговый метод . . . . . . . . . . 3.1.2. Циклический метод с чебышевскими параметрами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3. Полуитерационный метод Чебышева . . . . . . . . 3.1.4. Стационарный трехслойный метод . . . . . . . . . . 3.1.5. Методы сопряженных направлений . . . . . . . . . 3.2. Погрешность метода MJOR в случае постоянных параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1. Преобразование формул . . . . . . . . . . . . . . . . . . . 3.2.2. Начальное приближение . . . . . . . . . . . . . . . . . . . 3.2.3. Оценка погрешности с постоянными параметрами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Погрешность метода MJOR в случае переменных параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. Погрешность метода MSOR в случае постоянных параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1. Преобразование формул . . . . . . . . . . . . . . . . . . . 3.4.2. Начальное приближение . . . . . . . . . . . . . . . . . . . 3.4.3. Полином ошибки . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4. Оценка погрешности . . . . . . . . . . . . . . . . . . . . . . . 3.5. Погрешность метода MSOR в случае переменных параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1. Преобразование формул . . . . . . . . . . . . . . . . . . . . 3.5.2. Выбор параметров для p, как в циклическом методе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3. Выбор параметров для p, как в трехслойных методах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.4. Выбор параметров для u, как в трехслойных методах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Библиография и комментарии . . . . . . . . . . . . . . . . . . . .

49 49 50 50 51 52 54 55 58 59 59 59 60 61 61 63 63 64 65 66 71 71 73 73 74 76 76 78 78 80 84

346

Оглавление

Глава 4. Релаксационные методы для системы с параметром . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1. Явный метод типа MSOR (MSORe) . . . . . . . . . . . . . . . . 4.1.1. Построение метода . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2. Спектр оператора перехода . . . . . . . . . . . . . . . . . 4.1.3. Условие сходимости . . . . . . . . . . . . . . . . . . . . . . . 4.1.4. Задача асимптотической оптимизации . . . . . . . 4.2. Неявный метод типа MSOR (IMSORe) . . . . . . . . . . . . . 4.2.1. Построение метода . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2. Спектр оператора перехода . . . . . . . . . . . . . . . . . 4.2.3. Условие сходимости . . . . . . . . . . . . . . . . . . . . . . . 4.2.4. Задача асимптотической оптимизации . . . . . . . 4.3. Погрешность метода MSORe в случае постоянных параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1. Преобразование формул . . . . . . . . . . . . . . . . . . . 4.3.2. Начальное приближение . . . . . . . . . . . . . . . . . . . 4.3.3. Полином ошибки . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.4. Оценка погрешности . . . . . . . . . . . . . . . . . . . . . . . 4.4. Погрешность метода MSORe в случае переменных параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1. Преобразование формул . . . . . . . . . . . . . . . . . . . 4.4.2. Выбор параметров для p, как в циклическом методе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3. Выбор параметров для p, как в трехслойных методах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.4. Выбор параметров для u, как в трехслойных методах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . Глава 5. Методы для нормальных уравнений . . . . . . . . . . . . . . . 5.1. Оптимизация метода для базовой системы . . . . . . . . . 5.1.1. Спектр оператора равносильной задачи . . . . . 5.1.2. Минимизация числа обусловленности . . . . . . . 5.1.3. Наилучшая оценка погрешности . . . . . . . . . . . . 5.2. Оптимизация метода для системы с параметром . . . . 5.2.1. Спектр оператора равносильной задачи . . . . . 5.2.2. Минимизация числа обусловленности . . . . . . . 5.2.3. Наилучшая оценка погрешности . . . . . . . . . . . . 5.3. Оптимизация метода для случая равносильной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1. Спектр оператора равносильной задачи . . . . . 5.3.2. Минимизация числа обусловленности . . . . . . .

86 86 86 87 88 90 91 91 91 93 95 96 96 98 98 99 100 100 102 103 105 108 109 110 110 111 112 113 113 115 118 118 119 121

Оглавление 347

5.3.3. Наилучшая оценка погрешности . . . . . . . . . . . . 124 5.4. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . 124

Часть II. Обобщенные методы . . . . . . . . . . . . . . . . . . . . . .

125

Глава 6. 6.1. 6.2. 6.3. 6.4.

126 126 128 131 134 134

Предварительные результаты . . . . . . . . . . . . . . . . . . . . . Классы оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Что происходит с алгоритмом Узавы? . . . . . . . . . . . . . . Нерегулярные задачи с седловой точкой. . . . . . . . . . . . Вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . 6.4.1. Сведения из анализа . . . . . . . . . . . . . . . . . . . . . . . 6.4.2. Спектральные свойства одного пучка операторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.3. Свойства некоторых классов функций . . . . . . . 6.5. Ключевые этапы построения и анализа алгоритмов . 6.6. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . .

Глава 7. Блочно треугольное предобусловливание (GMSOR). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1. Формулировка метода и его свойства. . . . . . . . . . . . . . . 7.2. Симметричная регулярная задача: оптимизация в классе K1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3. Симметричная регулярная задача: оптимизация в классе K2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4. Симметричная нерегулярная задача: оценка в классе K2s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5. Несимметричная регулярная задача: оценка в классе K3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . .

140 149 156 161 163 163 165 171 178 180 184

Глава 8. Блочно диагональное предобусловливание . . . . . . . . . . 187 8.1. Обобщенный метод MJOR (GMJOR) . . . . . . . . . . . . . . . 187 8.1.1. Формулировка метода . . . . . . . . . . . . . . . . . . . . . . 187 8.1.2. Связь спектров операторов перехода GMJOR и GMSOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 8.1.3. Оптимизация метода в классах K1 , K2 , K3 , K2s 189 8.1.4. Случай β = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 8.2. Обобщенный метод Ланцоша (GMLan) . . . . . . . . . . . . . 194 8.2.1. Построение метода . . . . . . . . . . . . . . . . . . . . . . . . . 194 8.2.2. Оптимизация в классе K1 . . . . . . . . . . . . . . . . . . . 196 8.2.3. Оптимизация в классе K2 . . . . . . . . . . . . . . . . . . . 202 8.2.4. Оценка в классе K2s . . . . . . . . . . . . . . . . . . . . . . . . 210 8.3. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . . 211

348

Оглавление

Глава 9. Симметризация специального вида . . . . . . . . . . . . . . . . 9.1. Обобщенный метод Bramble–Pasciak (GMBP) . . . . . . . 9.1.1. Построение метода . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.2. Оптимизация метода в классе K1 . . . . . . . . . . . . 9.1.3. Оптимизация метода в классе K2 . . . . . . . . . . . . 9.1.4. Оценка в классе K2s . . . . . . . . . . . . . . . . . . . . . . . . 9.2. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . .

214 215 215 218 221 224 225

Глава 10. Модельные седловые операторы . . . . . . . . . . . . . . . . . . . 10.1. Неконструктивный подход . . . . . . . . . . . . . . . . . . . . . . . . 10.1.1. Построение методов . . . . . . . . . . . . . . . . . . . . . . . . 10.1.2. Оценка в классе K1 . . . . . . . . . . . . . . . . . . . . . . . . 10.1.3. Оценка в классе K2 . . . . . . . . . . . . . . . . . . . . . . . . 10.1.4. Оценка в классе K2s . . . . . . . . . . . . . . . . . . . . . . . . 10.2. Конструктивное предобусловливание. . . . . . . . . . . . . . . 10.2.1. Построение методов . . . . . . . . . . . . . . . . . . . . . . . . 10.2.2. Оценка в классе K2 . . . . . . . . . . . . . . . . . . . . . . . . 10.2.3. Оценка в классе K2s . . . . . . . . . . . . . . . . . . . . . . . . 10.3. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . .

228 228 228 230 232 235 236 236 236 241 242

Глава 11. Методы попеременных симметричных и кососимметричных итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1. Стационарный метод (GPHSSI) . . . . . . . . . . . . . . . . . . . . 11.1.1. Формулировка метода . . . . . . . . . . . . . . . . . . . . . . 11.1.2. Безусловная сходимость метода . . . . . . . . . . . . . 11.1.3. Оптимизация в классе K2 . . . . . . . . . . . . . . . . . . . 11.2. HSS-предобусловливание . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.1. Построение методов . . . . . . . . . . . . . . . . . . . . . . . . 11.2.2. Оценка спектра в классе K2 . . . . . . . . . . . . . . . . . 11.2.3. Анализ сходимости методов чебышевского типа и GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . . Глава 12. Нелинейные задачи и блочно треугольное предобусловливание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1. Уравнения с кососимметричным возмущением . . . . . . 12.1.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.2. Оценка скорости сходимости . . . . . . . . . . . . . . . . 12.2. Уравнения с сильно монотонным оператором . . . . . . . 12.2.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . 12.2.2. Вспомогательные факты и утверждения . . . . . 12.2.3. Оценка скорости сходимости . . . . . . . . . . . . . . . . 12.3. Библиография и комментарии . . . . . . . . . . . . . . . . . . . . .

244 245 245 245 247 252 252 254 256 263 265 265 265 268 277 277 279 281 284

Оглавление 349

Часть III. Приложение к гидродинамике . . . . . . . . .

286

Глава 13. Inf-sup неравенство и смежные вопросы . . . . . . . . . . . . 13.1. О задаче Стокса и спектре Коссера . . . . . . . . . . . . . . . . 13.2. Неравенства Фридрихса и Корна в двухмерном случае . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3. Точные значения и оценки снизу константы Ладыженской . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.4. Анизотропия области . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.5. Угловые точки на границе . . . . . . . . . . . . . . . . . . . . . . . . 13.6. Разное . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.6.1. Обобщенная задача Стокса . . . . . . . . . . . . . . . . . 13.6.2. Уравнения Ламе в теории упругости и слабосжимаемая жидкость . . . . . . . . . . . . . . . . . . . . . . . 13.6.3. Смешанный подход для эллиптических уравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.6.4. Другие применения . . . . . . . . . . . . . . . . . . . . . . . .

289 290 292 293 297 299 303 303 305 305 307

Глава 14. Численный анализ LBB-условия . . . . . . . . . . . . . . . . . . . 14.1. Задача с гладким решением . . . . . . . . . . . . . . . . . . . . . . . 14.2. Задача с негладким решением . . . . . . . . . . . . . . . . . . . . . 14.2.1. Схема 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.2. Схема 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.3. Вычислительные аспекты . . . . . . . . . . . . . . . . . . . 14.2.4. Расчеты для квадратной области . . . . . . . . . . . . 14.2.5. Расчеты для прямоугольной области. . . . . . . . .

308 308 313 313 314 315 316 319

Глава 15. Численный анализ роли оператора βBC −1 B T в сходимости GMSOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.1. Алгоритм численной оптимизации . . . . . . . . . . . . . . . . . 15.2. Задача о квадратной каверне . . . . . . . . . . . . . . . . . . . . . . 15.3. Обтекание тела в трубе . . . . . . . . . . . . . . . . . . . . . . . . . . .

322 323 324 326

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329