Операторы с псевдоразреженными матрицами и их приложения

Оглавление
Глава I. Операторы с псевдоразреженными матрицами. Общая теория.....................................42
§1. Классы ПРМ. Определения и примеры.................42
1.1. Индексные зоны..............................42
1.2. Функция расползания.........................42
1.3. Классы ПРМ с экспоненциальным убыванием 43
1.4. Классы ПРМ с субэкспоненциальным убыванием 43
1.5. Алгебры ПРМ.................................44
1.6. Примеры ПРМ.................................45
1.7. Наполненность алгебр ПРМ....................47
1.8. Доказательства лемм и теорем .............50
1.9. Доказательство теоремы 1.1................58
1.10. Доказательство теоремы 1.1 для произвольного р 65
1.11. Доказательство теоремы 1.2.................68
1.12. Доказательство теоремы 1.3.................73
1.13. Доказательство теоремы 1.4.................76
§2. Оценки Ьи и С^Я-разложений ПРМ....................76
2.1. Формулировки теорем.........................76
2.2. Вспомогательные леммы.......................79
2.3. Доказательства теорем 2.1 и 2.2.............80
1
-2-
2.4. Доказательства теорем 2.3 и 2.4..............82
§3. Оценки обратных матриц, Ы1 и (311-разложений
хорошо обусловленных псевдоразреженных матриц конечных порядков........................83
3.1. Индексные зоны . ............................84
3.2. Функция расползания..........................84
3.3. Инверсно замкнутые классы с экспоненциальным убыванием...................................85
3.4. Инверсно замкнутые классы с субэкспонен-
циальным убыванием..........................85
3.5. Замечания о доказательствах теорем 3.1-3.5 87
3.6. Об оценках Ьи и С^Я-разложений разреженных матриц......................................87
3.7. Примеры инверсно замкнутых классов ... 89
3.8. Инверсно замкнутые классы для многоуровневых псевдоразреженных матриц ... 90
3.9. Оценки Ьи-факторизаций в случае приближенных вычислений.............................92
§4. Оценки блочных факторизаций модельных эллиптических краевых задач..........................95
4.1. Оценки элементов точных факторизаций . 97
§5. Оценки неполных факторизаций модельных эллиптических краевых задач.........................105
5.1. Вспомогательные леммы...................105
л
5.2. Оценки элементов матриц <3* 119
Глава II. Теория методов неполной факторизации . . . 124 §6. Методы неполной факторизации для хорошо обусловленных разреженных систем........................124
6.1. Неполная точечная факторизация..........124
6.2. Неполная блочная факторизация...........132
-3-
§7. Методы неполной факторизации для эллиптических краевых задач................................139
7.1. Доказательство теоремы 7.1.................139
7.2. Доказательство теоремы 7.2.................141
7.3. Доказательство оценок снизу ...............150
Глава III. Метод конечных элементов Гачеркина для
систем сингулярно возмущенных уравнений
первого порядка.............................160
§8. Постановка краевой задачи и основной результат 160
8.1. Постановка краевой задачи..................160
8.2. Разбиение отрезка [—1,1] и аппроксимаци-
онные пространства.........................162
8.3. Галеркинская задача и основная теорема . . 165
§9. Схема доказательства теоремы 8.1...................165
9.1. Галеркинский проектор......................165
9.2. Представление галеркинского проектора
через биортогональные базисы ..............166
9.3. Завершение доказательства теоремы 8.1. . . 171
§10. Вспомогательные результаты и доказательства
лемм..............................................175
10.1. Аппроксимационные свойства пробных
пространств .............................. 175
10.2. Доказательство леммы 9.1...................184
10.3. Доказательства лемм 10.2 и 10.3............190
§11. Равномерная линейная независимость функций Гу 192
11.1. Равномерная линейная независимость В-
сплайнов...................................193
11.2. Некоторые свойства нормированных функций Гу.......................................197
11.3. Схема доказательства СРЛН функций Гу. 200
-4
11.4. Равномерная линейная независимость
группы Л\......................................201
11.5. Равномерная отделимость группы А2. . . .205 §12. Построение и свойства биортогональных базисов. 212
§13. Доказательство леммы 9.5.............................222
Глава IV. Метод конечных элементов Галеркина для
линейных и квазилинейных сингулярно возмущенных эллиптических краевых задач . . 235 §14. Постановки задач. Основные результаты и указания к численной реализации..............................235
14.1. Постановки исходных задач......................235
14.2. Дискретизация и постановки галеркин-ских задач.......................................236
14.3. Базисы в пространствах Б и указания к численной реализации...............................240
§15. Галеркинские проекторы и их свойства.................241
15.1. Определение галеркинского проектора. . . .241
15.2. Представление гааеркинского проектора через биортогонааьные базисы и квазиоптимальность ...................................242
15.3. Существование биортогональных базисов. 243
15.4. Дальнейшие свойства биортогональных базисов ...........................................249
§16. Построение биортогональных базисов для линейных задач в одномерном случае...................251
16.1. Дискретные решения.............................251
16.2. Построение биортогонашных базисов к функциям В.......................................258
16.3. Завершение построения биортогональных базисов..........................................259
-5-
§17. Построение биортогональных базисов в двумерном случае ..................................... 261
§18. Завершение доказательства теоремы 14.1........267
18.1. Аппроксимационные свойства пространства Е...........................................267
18.2. Доказательство теоремы 14.1................269
Глава V. Метод конечных элементов Галеркина для
сингулярно возмущенных параболических
начально краевых задач......................271
§19. Постановки задач и формулировки результатов. . 271
19.1. Постановки задач...........................271
19.2. Формулировка основного результата для
нелинейных систем.........................272
19.3. Линейные задачи............................273
§20. План доказательства теорем 19.1 и 19.2........274
20.1. Дискретная функция Грина...................274
§21. Доказательство оценок (20.8) 280
21.1. Некоторые свойства разреженных матриц . 280
21.2. Некоторые свойства базисных функций
пробных пространств.......................282
21.3. Дискретные функции Грина в подобластях 286
21.4. Доказательство оценок (20.8) 288
§22. Функции Грина в подобластях......................289
22.1. Теорема о частичных функциях Грина. . . . 289
22.2. Два вспомогательных оператора..............291
§23. Проверка условий теоремы 22.1................... 298
23.1. Проверка условий теоремы 22.1 для подпространств Н....................................298
23.2. Схема оценивания функции Грина в одномерном случае....................................298
-6-
23.3. Доказательство леммы 23.2.................
23.4. Доказательство оценок (20.3) в двумерном случае..........................................
304
309
Обозначения
2 -множество целых чисел 2+ -множество целых неотрицательных чисел И - множество вещественных чисел
€ - малый положительный параметр /г - сеточный параметр
С, С\,С2, • • • - обозначения положительных констант, не зависящих от £, А
Если ДЛЯ некоторой величины 7 имеют место оценки |7| < С\Р1 то будем писать 7 = 0(/?), а. если 0 < С\\р\ < |7| < Сг!/?!, то
Пусть а = {aj Е Rn. Тогда символ \а\ обозначает вектор из Rn с элементами |а, |.
Пусть А = {atJ} - пх n-матрица. Тогда символ |А| обозначает п х n-матрицу с элементами
Lp,lp - пространства Лебега 1 < р < оо с нормой || ||р Пусть Л = {&ij} - конечная или бесконечная матрица, определяющая ограниченный оператор в 1р. Тогда || А ||р - норма оператора А, || А ||= тах{|| А ||ь || А Ц«,} cond(A) =|| А Ц2Ц А~1 Ц2 спектральное число обусловленности матрицы или оператора, suppA = {(», j) е Z2 : dij ф 0}
7 = О*(0)
-7-
I - единичная матрица или оператор 6^ - символ Кронекера
Умножение бесконечных матриц понимается в смысле суперпозиции соответствующих операторов в 1р. т. е. V = А\Ач означает, что Лц =
О = Л‘а^{С1,С2, • • • ,бп} - обозначение диагональной или блочно- -диагональной матрицы
£ = ЬН<Иад{—Ир, Ер, < р < п - обозначение трехдиаго-
нальной или блочно- -трехдиагональной матрицы (блоки и отсутствуют).
£,£>()
О, £ < О
Аббревиатуры
ПРМ - псевдоразреженные матрицы
СЛАУ - система линейных алгебраических уравнений
ММП - метод матричной прогонки
МСГ - метод сопряженных градиентов
ДБПФ - дискретное быстрое преобразование Фурье
Введение
Настоящая работа посвящена исследованию введенных автором классов конечных или бесконечных матриц, названных псевдоразреженными матрицами, и их приложений. Актуальность темы обусловлена приложениями полученных результатов к двум классам задач вычислительной математики.
Первый класс задач - математическое обоснование методов неполной факторизации (МНФ) решения систем линейных алгебраических уравнений (СЛАУ) с разреженными матрицами
-8-
(РМ) высоких порядков. Это направление, начиная с 50-х годов, интенсивно развивалось в работах Н.И. Булеева, В.П. Ильина, В.П. Гинкина, В.К. Артемьева, а позднее - в работах О. Axels-son’a, R. Beauvens’a, Van der Vorst’a, J. Golub'a, A.K). Еремина, И.Е. Капорина, Л.Ю.Колотилиной, P. Conçus’a, J. Meurant’a, T. Manteuffel’a, Y. Notay, T. Chan’a, P. Vassilevski [3],[20],[21], [27],[37],[36],[65], [6G],[68],[69],[93],[90],[96], [91],[72],[73] и многих других математиков. Итоги этих исследований подведены в монографиях [34],[65], где приводится подробная библиография. Однако неисследованным оставался вопрос о зависимости скорости сходимости итераций МИФ в зависимости от структуры допустимого заполнения предобуславливателей. В связи с этим следует упомянуть также монографии [60],[114] О.Эстербю, 3. Златева, в которой изучаются так называемые барьерные методы, суть которых в том, что все элементы, возникающие в процессе факторизации РМ, меньшие заданного барьера е « 1, полагаются равными нулю. Эти методы также следует отнести к МНФ. Для данного класса методов до последнего времени не было ни теоретического доказательства сходимости ни оценок погрсшнсти предобуславливателей.
Второй класс задач - алгоритмы метода конечных элементов для сингулярно возмущенных краевых задач и теория априорных Loo- оценок погрешности таких методов. Отметим, что наиболее развитой для таких задач является теория разностных схем, которой посвящены работы Н.С. Бахвалова, А.М. Ильина, В.Б. Андреева, И.П. Боглаева, В.Н. Задорина, К.В. Емельянова, В.Н. Игнатьева, В.Д. Лисейкина, Макарова В.Л. и Гуминского В.В., Г.И. Шишкина, H.H. Яненко, E. Gartland’a, P. Hemker’a,
D. Iierceg’a, J.J.H. Millcr’a, O’Riordan’a, K. Surla, M. Stynes’a, R. Vulanovic’a [1], [17],[18],[25], [30],[31],[39],[42],[52]-[57],[25],[98],
-9-
[109],[113] и других математиков. Начиная с основополагающих работ Н.С. Бахвалова и А.М. Ильина [И],[33], работы по разностным схемам традиционно делятся на два направления: экспоненциально подогнанные схемы на равномерных и квазиравномерных сетках и разностные схемы, на неравномерных сетках, сгущающихся в области пограничного слоя. Второе направление интенсивно развивается в последние годы в работах В.Б. Андреева, Г.И. Шишкина, К.В. Емельянова, А.И. Задорина, Н.В. Коптевой, И.А. Савина, D. Ilerceg’a, М. Stynes’a, G. Sun’a, R. Vulanovic’a и др. [2],[26],[31],[45],[87],[109], [113],[52]-
[57].
Работы по методу конечных элементов для СВЗ также можно разделить на две группы: схемы на квазиравномерных сетках с использованием экспоненциально подогнанных базисных функций (Б.М. Багаев [5]-[8], Б.М. Багаев и В.В. Шайдуров [4], И.П. Боглаев [15] -[16], Р. Hemkcr,P.P.N. de Groen [86],[85], Gartland E. [82],[84], J.J.H.Miller, O’R.iordan, M. Stynes, [43],[104]-[108], W.Scymchak, I.Babushka [102], A.H.Schatz, L.B.Wahlbin [100]) и схемы на адаптирующихся к погранслою сетках ( U. Asher,R. Weiss, K. Ringhover [61]-[63],[97], E. Gartland [83], J.E.Flaherty [81]). Отметим, что второе направление для метода конечных элементов развито существенно меньше, чем первое, причем нам представляются важными следующие аспекты:
1) Использование оптимальных сеток Н.С. Бахвалова (широко используемые кусочно-равномерные сетки Г.И. Шишкина несколько более грубы).
2) Получение оценок по-
грешности в Loo или С-норме (более традиционные для метода конечных элементов оценки в интегральных либо энерге-
-10’
тических нормах не гарантируют аппроксимации пограничного слоя). Отметим, ЧТО Хоо-теория метода конечных элементов для нежестких задач была развита в 70-е - 80-е годы в работах Л.МИ^сйе, Р. КаПегега, К.8сои’а, А.Н. ЭсЬ^г’а, Ь. \УаЫЫп’а, V. ТЬотсе [95],[94],[103], [77],[101],[110]. Построение ее аналогов для сингулярно возмущенных уравнений оказывается существенно более сложным из-за сильной неравномерности расчетной сетки и невозможности выделить простую главную часть оператора задачи.
3) Разработка и обоснование безытерационных схем МКЭ для эллиптических и параболических СВЗ с числом пространственных переменных п > 1 в областях с криволинейной границей ( разработанные в этом случае разностные схемы [54] предполагают использование декомпозиции области с перестройкой разностной сетки в зонах налегания в процессе итераций).
4) Построение схем МКЭ повышенного (> 2) порядка сходимости.
Построение таких схем и составляет содержание глав 3-5 настоящей диссертации.
Основными и важнейшими компонентами математического аппарата решения поставленных задач являются
а) в случае методов неполной факторизации для СЛАУ с соп<1(А) = 0(1) - оценки элементов матриц, обратных к разреженным матрицам или матрицам, для которых задан закон убывания их элементов в зависимости от расположения (в простейшем случае - убывание от главной диагонали), а также элементов их Ы1 и <3#-разложений;
б) в случае методов неполной блочной факторизации для эллиптических задач - оценки убывания элементов блоков точных и неполных факторизаций;
-11-
в) в случае методов конечных элементов для сингулярно возмущенных краевых задач - оценки убывания элементов матриц, обратных к матрицам Грама специальных базисов в конечномерных галеркинских пространствах.
Таким образом для решения этих задач необходима теория оценок элементов матриц, обратных к РМ, опенок элементов их Ыт и (^^-факторизаций, а также теория аналогичных оценок для более общих, чем РМ, классов матриц с заданным законом убывания элементов, который сохраняется при обращении или факторизации. Такие бесконечные матрицы, которые могут вообще не иметь нулевых элементов, но большинство их элементов малы при абсолютной величине, причем закон распределения малых элементов сохраняется при обращении или факторизации, названы автором пссвдоразреженными матрицами (ПРМ).
Вопросы, связанные с оценками элементов обратных матриц в связи с задачами вычислительной алгебры или теории аппроксимации ставились и раньше. Однако, в основном изучались трехдиагональные или блочно-трехдиагональные матрицы [11],[35],[47],[89],[93],[92], [111], либо ленточные матрицы [73]-[76],[78], [111],[112]. В [71] в связи с задачами оценок погрешности среднеквадратичной аппроксимации изучались матрицы, обратные к ленточным матрицам Грама, составленных из В-сплайнов на квазиравномерных разбиениях. В [9] рассматривались бесконечные матрицы, элементы которых определенным образом убывают при удалении от главной диагонали, и доказывались аналогичные оценки для элементов обратных матриц. Эти оценки близки к более ранним результатам автора [123] или являются их частными случаями. Отдельные результаты (случай экспоненциального убывания или убывания бы-
-12-
стрее любой степени от главной диагонали) были получены в
[58],[59],[14]. Результаты об оценках элементов обратных матриц для РМ обшей структуры, а также об оценках элементов Ьи и фЯ-факторизаций в литературе практически отсутствуют. Можно отметить работу [92], но в ней оценки обратных матриц и факторизаций для для блочно-трехдиагональных систем зависят от числа обусловленности и являются грубыми в части ££/-факторизаций. По-прежнему весьма актуальным является высказывание, что ’’утверждения и предположения о методах разреженных матриц, как правило, не удается доказать математически” ([60], С. 14).
В связи с этим целями настоящей работы являются
1) Построение теории оценок элементов обратных матриц, Ыт и фЯ-факторизаций, охватывающей весьма широкий класс РМ общей структуры, а также более широкие: чем РМ классы матриц, точные оценки блочно- треугольных факторизаций дискретизаций модельных эллиптических краевых задач, матриц обратных к матрицам Грама базисов конечноэлементных пространств на сильно неравномерных триангуляциях.
2) Применение этой теории к решению обсуждавшихся выше двух классов задач.
Перейдем к изложению основных результатов диссертации по главам. Диссертация состоит из пяти глав и трех приложений.
В первой главе реализается обозначенная выше цель для хорошо обусловленных (соп(1(А) = 0(1)) РМ общей структуры.
В §1 вводятся и изучаются классы псевдоразреженных матриц (ПРМ), для которых закон убывания элементов сохраняется при переходе к обратным матрицам. В соответствии с терминологией, принятой в теории банаховых алгебр, мы бу-
-13-
дем называть последнее свойство наполненностью класса или алгебры ПРМ.
Пусть 5 С 22 - некоторое множество, такое, что если (М) £ 5, то 0*» 0 € 5, и (М) £ £ Для всех * ^ Через С = {#у, г,7 Е 2} обозначим бесконечную матрицу, элементы #у которой равны единице при (а,^') Е 5 и нулю в противном случае.
Определение 1.1. Множество 5 будем называть порождающим, а матрицу С - структурно-порождающей.
Предположим, что число элементов в любой строке (столбце) матрицы О конечно и ограничено константой, не зависящей от номера строки (столбца). Тогда для любого п определена степень Очевидно, Сп обладает теми же свойствами, что и <5.
Положим 5[ = 5,5а- = виррСк \ 8иррСк~^, к > 2. Пусть 5^ = {(г,;) Е 22 : («,;) $ 5а, V А: Е ДГ}. Тогда 22 = 51 и 52 и • • • и 5оо. Множества 5а будем называть индексными зонами или просто зонами. Пусть
<?, = и 5а, д0 = 0, ^ = и 5а.
\<к<и к>и
1.1. Функция расползания
Пусть А = {ау,г,^ Е 2} - бесконечная матрица, а 5а - те же, что и выше. Через Рк{А) = {йу} обозначим матрицу, элементы которой таковы, что йу = при (г,^) Е 5а и А,;* = О при (?‘7>;) ^ 5а- Пусть Е = {ег-;-,г,^ Е 2”} - бесконечная матрица, все элементы которой равны единице. Через /г : N -^ N обозначим функцию, значение которой й(&) равно максимальному числу ненулевых элементов в отдельно взятой строке (столбце) матрицы Рк(Е). Функцию Н будем называть функцией расползания множества 5.
-14-
1.2. Классы ПРМ с экспоненциальным убыванием Зафиксируем некоторое порождающее множество 5. Обозначим через Е(Б) класс бесконечных матриц А таких, что
II Рк(А) ||< С\ ехр(-7*), к Е N. Роо(А) = 0 (0.1)
при некоторых С\ = С\(А) и 7 = 7(А) > 0.
1.3. Классы ПРМ с субэкспонснциальным убыванием Введем в рассмотрение функцию / : N —» N такую, что
/(А:) > 0,/(А) стремится к нулю монотонно при А —> оо и
и1™,1ехр(-чп)//(п) = о (0.2)
для любого 7 > 0;
Е Дп)А(и) < с, (0.3)
П=1
где /г - функция расползания множества 5. Обозначим через £>(/,5) класс бесконечных матриц Л = {а^} таких, что
М < СгЦк), (г,Я 6 5а, А е ЛГ; Рос (А) = 0,^ = С\{А). (0.4)
В пункте 1.4 классы ПРМ рассматриваются как алгебры от-
носительно операции суперпозиции. Классы ПРМ, как подалгебры алгебры В(1Р) ограниченных операторов в /р, обозначим Р(/>5,р) и £(5,р), а как подалгебры ГЬ<,,<<*,В(/р) - В(/,5,0) и В(5,0).
В пункте 1.5 приводятся примеры классов ПРМ с различными законами убывания элементов и оцениваются их функции расползания. Здесь мы ограничимся лишь одним примером. Пример 1.1.
Трехдиагональные структурно-порождающие матрицы. Пусть 5 = {(м) € 22 : |г - Ц < 1}. Очевидно, что 5а = {(г,;) е 22 : |* — .Я = А 4- 1} при А > 2, а функция расползания
-15-
имеет вид /г(1) = 3, к(к) = 2, к > 2. Этот пример описывает классы матриц с убыванием элементов при удалении от главной диагонали: А Е Е(Б) |а,Д < С\ ехр(—7|г — Л), А Е £>(/,£) <=> |ау| < С*1/(|г - ;|), г ф у |ай| < С\}{\) при некото-рых С\ > 0,7 > 0.
1.6. Наполненность алгебр ПРМ
Случай убывания элементов от главной диагонали. В
этом случае (см. пример 1.1) удается дать почти исчерпывающий ответ на вопрос о наполненности алгебр ПРМ.
Пусть / : N -» II - монотонно убЫВАМЩАЯ функция, удовлетворяющая условию (0.3) при к(п) = 2.
Теорема 1.1. Для наполненности алгебры £>(/, 5,р) из примера 1.1 при любом р Е [1,оо] необходимо, чтобы для функции / выполнялись условия (0.2),(0.3), и условие
Е /(*)/("-*)< С/(п). (0.5)
к=1
и достаточно, чтобы выполнялись условия (0.2),(0.3) и для некоторой функции : ЛГ -> Я такой, что (1(1) —> 0 при / —> оо, для всех п, / Е N имели место соотношения
Е /(*)/(« ~ к) < <*(0/(Л)- (°-6)
к=1
В замечании 1.3 приводятся несколько примеров функций (в частности, степенных), удовлетворяющих условиям (0.2),(0.6).
Наполненность алгебр £(5,р) из примера 1.1 вытекает из теоремы 1.2 (см. ниже).
Общий случай. В общем случае вопрос о наполненности алгебр ПРМ решается с помощью оценок функции расползания.
Теорема 1.2. Пусть для некоторой функции <?(/?) : (0,1) -»
[1,+оо) и констант Сз > 0,£ > 0, к Е (0,1) при всех /3 Е
-16-
(0,1), к Є N справедливы неравенства
Нк) < д(Р)ехр(рк), (0.7)
я(Р)<Сгех р{6/Ц*). (0.8)
Тогда алгебра Е(3,2) наполнена. Более того, для любых констант Сі,С2,Сз,<5,7,/с Є (0,1) найдутся такие константы С\ и 7і, зависящие лишь от указанных величин и не зависящие от 5, что если А Є Е(5,2),|| А ||2< С2, матрица А удовлетворяет условию (0.1), а функция расползания множества 5 - условиям (0.7), (0.8), то для матрицы Л“1 справедливы оценки
II Рк(А~1) ||< С4ехр(—7і*)> к Є N. (0.9)
Теорема 1.3. Пусть Н(к) < С ехр(£ки) при некоторых С >
0,( > 0, и Є (0,1/2). Тогда найдутся такие д, Сз > 0,£ > 0,ас Є (0,1), что выполнены условия (0.7),(0.8) для Н{к).
Для формулировки теорем о классах 1)(/,5,р) дополнительно к условиям (0.2),(0.3) наложим на функцию / следующие условия
(А). Найдется такая функция с1(т), монотонно стремящаяся к нулю при т —> оо, что
(*/2) +оо
2 £/(/)/(*-/)М0 + 2 Е (/(0)*М0 < <*Н/(*),
1=т /=[*/2]+1
1 < т < [Л:/2] + 1.
Пусть (Іі(т) = Е^п+1 /(ПЖП)* Зафиксируем некоторые т Є А,7 > 0, (^ > 0. Обозначим через ті наименьшее из натуральных чисел, для которых
(1(ті) < фіі(пг)/(тах(ехр(-к'у/ггі)//(к))). (0.10)
-17-
Существование такого ті вытекает из условия (0.2). Функцию, осуществляющую соответствие т, 0,7 —» ті, обозначим М{т,ф, 7).
(В). Для любых ^>,7 > О
Ііт (1][т) шах (/(& — М(т,ф.^))Н(к\) = 0. т->ос ^ 7 Л>2М(т:0,7) ))
Теорема 1.4. Пусть функции /, к таковы, что выполнены условия (0.2),(0.3),(А),(В). Тогда если Л - функция расползания множества 5, то алгебра £)(/, 5,0) наполнена. Более того, для любых констант С, С\, С2 найдется такая константа 64 = С4(С,СьС2,Л,/), зависящая лишь от указанных величин и не зависящая от 5, что если а Є £>(/, 5,0),|| А“1 ||< С'*2 и А удовлетворяет условию (0.4), то для элементов аг;- матрицы А-1 справедливы оценки
|ау|<С4/(*), (і,і)€5ь /с Є А. (0.11)
Теорема 1.5. Пусть для некоторых 0 > 0,7 > 0 7 > /3 + 1, Л(к) < С6(* + 1)^, /(к) = (* + І)“7.
Тогда для функций /,к выполнены условия (0.2),(0.3),(А),(В).
В §2 изучаются Ы1 и фЛ-разложения ПРМ из §1. Здесь доказано, что закон убывания элементов ПРМ сохраняется при переходе к Ы1 и С^Я- факторизациям.
В §3 результаты §1 и 2 переносятся на классы псевдоразре-женных матриц конечных порядков. Соответствующие определения и формулировки теорем аналогичны аналогичны определениям §§1 и 2, а сами теоремы вытекают из теорем §§1 и 2. Принципиально новый результат получен в п. 3.8, где рассматриваются многоуровневые матрицы.
-18-
В п. 3.9 доказаны теоремы об оценках Ы1 -разложений в (случае возможных округлений элементов ПРМ в процессе вычислений.
В случае приближенных вычислений процесс построения приближенного Ьи~разложения можно записать в виде
£(1)А(1) -> Ь(2и(2) -* » = їй « Ш = А.
(0.12)
Определение 3.4. Пусть А Є ££(7,5, Сі, С2, Сз, а) для некоторых 7,Сі,С2,Сз,а. Будем говорить, что для матрицы А промежуточный рост (а, 5)-структурно ограничен константами 7і и С, если для любых натуральных V < п справедливы оценки II Рк>а{Ьм) ||< Сехр(-7!^), II Рк,0(А{1,)) ||< Сехр(-7іА:).
Определение 3.5. Алгоритм приближенного построения ££/-разложения А = ЬО будем называть алгоритмом типа Г(є) (или ГА'(є)), если АС-разложение строится метоом Гаусса (или с помощью компактной схемы ) с возможными округлениями лишь тех элементов промежуточных матриц АМ и которые
по модулю не больше £, а округление возможно лишь в сторону уменьшения модуля.
Обозначим через М(7і,С,а,£о) (или МК(і\,С,а,Єо)) множество квадратных матриц, допускающих Ы1-разложение, для которых любой алгоритм типа Г(є) (или Г К (є) реализуем при є Є (0,б“о], причем промежуточный рост в любом таком алгоритме (а, 5)-структурно ограничен константами 71 и С.
Теорема 3.13. Для любых 7,Сі,С2,Сз найдутся такие 7і,С'4,£,что сели А Є ££(7,£,Сі,С2,Сз,а) и является М-матрицей, то А € М(7і,С4, а, є)Г\МК(71, С4, а,б) при є Є (0,Єо]-
Теорема 3.14. Пусть А является Я-матрицей (см. при-
л л
ложение) и для соответствующей М-матрицы А имеем А Є
-19-
М("у, С, о:, є) П £/L(7,CьC2,Cз,a) (или А Є МК(^,С,а,є) П £Т(7,СьС2,Сз,а)).Тогда для некоторой С\ = 64(7, С, будет А Є М(7, С4, а,е) (или А Є М/С (7, С\,а,е)).
В §§4-5 с точки зрения псевдоразрежснности изучаются точные и неполные блочные факторизации модельной элиптиче-ской краевой задачи. Здесь получены асимптотически точные оценки элементов.
Рассмотрим модельную краевую задачу
Ми = -Аи = /(я, у), и\і = О
(0.13)
в единичном квадрате П:[0,1]х[0,1].
Здесь Г-граница П. Аи = д2и/дх2 + д2и/ду2. Пусть п > 4 натуральное число. Пусть 0 = Хц < ... < = 1,0 = уо < ... <
2/„+1 = - XI = у1+1 - у1 = к = 1/(п + 1). Аппроксимируем
оператор (0.13) выражением (Ми)(х{, ?/^) ~ (—Щ-\,з — +
4— щ^+^/Н2. Перенумеруем компоненты сеточной функции:
иц = ^1,^21 = 112, = ип,и 12 = Ип+ь«22 = ип+2,
' ’ * 7 ^1П = ^п(п —1) 7 ‘ * 7 иПП = ип‘2‘ (^*^)
и умножим каждое разностное уравнение на к2. Тогда получим СЛАУ АП = Д где
А =
Еі -Рі ••• 0
— Д Е’2 — Д * *
0
(0.15)
••• -Яп Еп /
Еі,ПіуРі -квадратные матрицы порядка ті,= Д= /, / - единичная матрица.
-20-
Рассмотрим блочную факторизацию матрицы А
А = (П + С)С-1(С + Г), (0.16)
(Ог 0 0 \ ' 0 0 0 '
0 ••• 0 -о, 0 0
, D =
; : ’ * • : } 0 • •
, 0 0 ••• С п ) 0 . -А. 0
( 0 -я •• 0 \
F = ; * •. • . 1
0 0 •• -я* -1
0 •• 0 /
где (п х п) -матрицы (3; определяются с помощью метода матричной прогонки:
= Ейй8+1 = Е$+1 - £>5+1^7^5,,9 = 1,2, ...,п — 1 (0.18)
Определим неполную блочную факторизацию матрицы А без диагональной компенсации формулами
А = (В + д)д~1(д + Е), (0.19)
Л л А Л
где С = <Ь'а£(([г1, ...,СП), В и Г - матрицы (0.18), а С?,- определяются формулами
($1 = ^1,6,+1 = Е3+1 - 1)6+1(0?71)^^5, 5 = 1,2, 1. (0.20)
Здесь символ (к) означает взятие (2к + 1)-диагональной части матрицы, т.е. если В = {6у}, то = {6у,*}, 6,-^* = Ьу при
I* “ Л < = 0 Для I* ~ Л > *•
Кроме того рассмотрим неполную факторизацию матрицы
А с диагональной компенсацией (см. [34])
а = (£> + ё)ё-*(ё+*•), ё = Лвр{ёь ■ • •, ё»},
-21-
<?, = 6,-0$, 5! = 0, 5,+1е = (Д+1(?Г1^-Д+1((6;+^)-1)^^)е,
(0.21)
(здесь и далее е -вектор с единичными компонентами, 5,- диагональные матрицы, в Е [0,1] - компенсационный параметр).
Теорема 4.1. В разложении (0.16)-(0.17) для элементов матриц С~1 = {д^Р} справедливы формулы
9ь1] =
( (1 + |г-Я)3 (1 */*> >’
1 < < Зп/4
тш{п + 1-»,8,1 + |г-Л} _ .
(1 + |*-Л)> 1 е1) 1
п/4 < г, 7 < п,
где г5 = г, = 0*(1).
Для элементов неполных факторизаций справедливы следующие оценки.
Теорема 5.2. Найдутся такие константы С2 > 0, о? Е (0,1/2), не зависящие от п, что для элементов ма"
Л Л
триц (?„, С“ справедливы оценки
С2 (* - |* - Л + 1)'
|5у>| ^
(1 + |г-Л)2 *«
С2 (*-|*-Я + 1)‘
(1 + |» - Л)2
к°
•, 0 < |г - Л < А:, -> 0 < |г - Ц < к,
С2
: П\9> |* ~Я> к
к°/2(1 + |г — ,/|)2 Вторая глава- посвящена методам неполной факторизации для СЛАУ с РМ высоких порядков.
В §6 строится теория МНФ (барьерных методов и методов исключения по позициям) для хорошо обусловленных РМ (сопс1(А) = 0(1)). В п. 6.1. изучаются точечные факторизации.
-22-
Зафиксируем некоторый инверсно замкнутый класс E(S) (определение см. в §3). Пусть А - разреженная квадратная матрица высокого конечного порядка га, А Е £(7,S,Ci,C‘2,a) для некоторых С\ > 0, Съ > 0, а Е «Д, и кроме того supp А С 5”>а.
Методы неполной факторизации с экономией машинной памяти. Методы, рассматриваемые в данном пункте, позволяют экономить намять ЭВМ при запоминании сомножителей факторизации матрицы А. Если системы с матрицей А нужно решать многократно, то эти методы дают выигрыш и во времени.
Методы искусственного ограничения заполнения..
а) Метод Гаусса.
Пусть А Е 2££(7,5, С\, С2, С3, от). Рассмотрим следующий алгоритм.
Ш а г 1. Фиксируем ко Е N.
к0
Ш а г 2. Определяем заполнение Q^0tQ = U S”a.
Ш а г 3. Полагаем г = 1.
Ш а г 4. Вычисляем элементы и Iji, j > i LU-разложения. Вычисляем (г -f 1)-ю промежуточную матрицу метода Гаусса.
Ш а г 5. Запоминаем лишь те элементы Ujj и /у,-, для которых (г, j) Е Qh0,a- Остальные считаем равными нулю и не запоминаем.
Ш а г 6. Полагаем i = г +1 и переходим к шагу 4, если г < гг.
Замечание 6.1. Реализация шага 2 возможна с помощью теоретикографовых алгоритмов (см. [44]).
Обозначим через L U сомножители полученной неполной LU-факторизации. Пусть А = LU.
Теорема 6.1. Для любых 7 > 0,С1,С2,Сз найдутся такие константы Cß, С7, С& и 71 >0, что
II L- L ||< Се exp(~7i^0), || U - Ü ||< C6exp(~7iA:o).
-23-
|| А-А ||< С7ехр(-7і^).
Кроме того найдется такое А.*! = &і(т? 61,62,63) Є что при Лт0 > А;і имеем
II -4-1 - А~х ||< С8ехр(-7і&о)-
б)Компактная схема метода Гаусса.
Рассмотрим следующий
алгоритм для А Є ЕЦч,5,61,62,63,а). Шаги 1-3,6 - тс же, что и в п. а).
Ш а г 4. Вычисляем элементы гіу и /у,-, j > і Ы1-разложения по формулам компактной схемы [23],с. 175.
Ш а г 5. Если і > 2, то полагаем щ,і-і = = 0,& =
1,2,-,і — 2 при (і-1,*) £С?0та-
Очевидно, что построенная факторизация совпадает с факторизацией из п. а) и для нее справедлива теорема 6.1.
в) Метод отражения.
Рассмотрим следующий алгоритм для А £ £(7,5,Сі,62, а). Шаги 1-3,6 - те же, что и в п. а).
Ш а г 4. Вычисляем матрицы А^ и по методу отражений
[12],гл. 3 §3.
Ш. а г 5. Если і > 2, то для элементов гг_і ОЯ-
</*
разложения (С^ = Рг) полагаем = 0,гу - • = 0 при
_ *}
Обозначим через <3 и Я, сомножители неполной факторизации.
Теорема 6.2. Для любых 7 > 0,61,62 найдутся такие константы 66,67,65 и 7і > 0, что
\\Q-Q ||< 6бехр(—уїЛо), || Я - Д ||< 66ехр(-71^0)-|| А - А ||< 67ехр(—7іко).
-24'
Кроме того найдется такое к\ = &і(7,Сі,С2) Є ЛҐ, что при ко > &і имеем
II Л“1 - Л-1 ||< С8ехр(-71^о).
Барьерные методы.
г)Метод Гаусса.
Пусть А е ^Ь(7,5,Сі,С2,Сз,а). Рассмотрим следующий алгоритм.
Ш а г 1. Фиксируем е > 0.
Ш а г 2. Полагаем г = 1.
Ш а г 3. Вычисляем элементы и# и , 7 > г Ь(7-разложения
и элементы промежуточной матрицы А^г+}\ Запоминаем лишь те элементы Пц и /;1-, для которых | Щ | > є у \ljil > є.
Ш а г 4. Полагаем г := і + 1.
Ш а г 5. Если і < п — 1, то переходим к шагу 3.
Пусть Ь и 0 - сомножители полученной факторизации.
Теорема 6.3. Для любых 7 > 0, С^Сг, С'з, /с Є (0,1) найдутся такие константы Сб,С7, что при є Є (0,1), &о = іпах{[7-11п(Сб/е)] + 1,1} имеют место включения зиррЬ С <220,а и справедливы оценки || Ь - Ь ||< С\еКу || II - V ||< С\ек.
д)Компактная схема метода Гаусса.
Рассмотрим следующий алгоритм
для А Є ЕЬ^уБуСіуСїуСгуСх). Шаги 1,2,4,5 - те же, что и в п. г).
Ш а г 3. Вычисляем элементы и 1^ по формулам компактной схемы. Для к = 1,2, • • • , г — 2 полагаем щ,і~і = 0,/,_1э* = 0, если |и*,і-і| < |(*—і,л| < £• Построенная факторизация совпа-
дает с факторизацией из п. а), и для нее справедлива теорема
6.3.
е)Метод отражения.
-25-
Рассмотрим следующий алгоритм для А Е £(7, Й, С'ьС^а)-Шаги 1,2,4,5 - те же, что и в п. г).
Ш а г 3. Вычисляем матрицы А**) и по методу отражений [12],гл. 3 §3. Если г > 2, то для элементов ,
^Я-разложения = Рт) полагаем = 0, = 0» если
\П-^\<еМ->н\<£._
Обозначим через (} и Я сомножители неполной факторизации.
Теорема 6.4. Для любых 7 > 0,СьС2,к Е (0,1) найдутся такие константы Сб,С'7, что при е Е (0,1),&о =
та.х{[7-11п(Сб/е)]-Ы, 1} имеют место включения эиррС} С виррЯ С , и справедливы оценки |[ (5 - С) ||< С\ек,
II Я-Я \\<С7'ек.
Методы неполной факторизации с экономией памяти и времени.
Методы исключения по позициЯоМ. Общая суть этих методов состоит в том, что в процессе преобразования матриц ненулевые элементы могут возникать лишь на заранее выделенных позициях.
ж)Метод Гаусса.
Пусть А Е £>£(7,5,С1, С2,Сз,а). Рассмотрим алгоритм, который назовем Г1; шаги 1-3,6 те же, что и в п. а).
Ш а г и 4-5. Вычисляем элементы аЦ промежуточной матрицы А^ следующим образом: если (&,.?) € <2*0>а, то вычисляем по обычным формулам метода Гаусса, а если (&,^‘) £ <У£0,а> то полагаем щ = 0.
з)Компактная схема
Рассмотрим алгоритм, который назовем Г2; шаги 1-3,6 те же, что и в п. б).
Шаги 4-5. Для ; = г,г 4- 1, • • •, п выполняем следующие
-26-
действия: если (г,^) Є <2*о,а> то вычисляем по формулам компактной схемы, а если (г, і) Є <5* а, то полагаем = 0. =
0.
Теорема 6.5. Для любых 7,С\єоЄ (0,1) найдется такое к\ = О(1п£о *)> что ПРИ 6 € (0,£Го], &о > &і для любой Л Є М(7, С, ск,£о) (или Л Є М/С(7, С, а-, £•())) алгоритм Г1 (или Г2) является алгоритмом типа Г(б'о) (или Г&'(єо)).
Барьерные методы.
и)Метод Гаусса.
Пусть Л Є ЕЬ(у, 5, Сі,С2,Сз, а). Рассмотрим следующий алгоритм, который назовем ГЗ; шаги 1,2,4,5 те же, что и в п. г).
ПІ а г 3. Вычисляем элементы щ и Г//"-разложения и в
методе Гаусса, но для каждого вновь вычисленного элемента проверяем условие < £, І/7ІІ < 6. Если оно выполнено,
полагаем соответствующий элемент равным нулю.
Теорема 6.6. Пусть Л Є М(7,С,а,є). Тогда при всех і =
1,2,• • • ,п — 1 имеем зиррї№ С (?20,а,виррЛ(|) С <У*0і*, где &0 = тах{1,[7-11п(С/е)] + 1}.
к)Компактная схема.
Рассмотрим алгоритм Г4; шаги 1,2,4,5 те же, что и в п. г).
Ш а г 3. Вычисляем элементы и по формулам компактной схемы. Если какой-то из вычисленных элементов по модулю меньше е. полагаем его равным нулю.
Теорема 6.7. Пусть Л Є М/С(7, С, о, є). Тогда виррЬ С виррй С (Зпк0іа, где ко = шах{1, [7-11п(С/є)] + 1}.
В п. 6.2 на основе результатов п. 3.8 получены аналогичные результаты для неполных блочных факторизаций.
В §7 получены точные оценки чисел обусловленности предо-бусловленных матриц в зависимости от структуры допустимого ззаполнения для модельной эллиптической краевой задачи.
-27-
Рассмотрим методы неполной факторизации (0.19)-(0.21) для СЛАУ (0.15). Пусть К\ = А“1 А, К% = А-1 А. В §7 будут установлены следующие утверждения.
Теорема 7.1. Найдутся такие константы С\ > 0,С*2 > 0, что при всех тг > 4,Ат < п справедливы оценки
2 2
< сопЛ(Кх) < СгП-г
Теорема 7.2. Найдутся такие константы С\ > 0,6*2 > 0, что при всех п > А.к < у/п, 0 — 1 справедливы оценки
< соп<1(К2) < С2р
причем оценка снизу справедлива при всех к £ [1, гг], 0 £ [0,1].
В главах 3-5 рассматривается метод конечных элементов для сингулярно возмущенных краевых задач. При этом получение априорных оценок погрешности приближенных решений основано на оценках норм оргтогональных в Ь2 проекторов на конечноэлементные галеркинские пространства в операторных нормах пространств С(О,) или £оо(^)* Эти оценки, в свою очередь, сводятся к изучению структуры матриц, обратных к матрицам Грама, составленных из специальных базисов конечноэлементных галеркинских пространств.
Покажем это на примере модельной задачи
Ьеи = ей' - Щи = и(1) = 0,А(0 > А0 > 0.
Следуя идеям Н.С.Бахвалова [10],^ построим специальное разбиение отрезка [—1,1], сгущающееся в зонах погранслоев. Пусть а = 1 — Зс|/п£(/Ао. Определим сначала вспомогательную
-28-
функцию д(£) равенством
д{ь) = £ 6 (-а., а]
Ъе
Ло
+ а + ^ехр (^7^) , Ь е (а, 1].
Простая проверка показывает, что д(Ь) - монотонная непрерывно дифференцируемая функция на отрезке [—1,1]. Положим А = а + 3(1 - е)!Ло. Функция д(Ь) взаимно однозначно отображает отрезок [—1,1] в отрезок [—А, А]. Вначале построим кусочно-равномерные разбиения Дг отрезка [—А, А].
Положим
Получили, таким образом, разбиение отрезка [О, А]. На отрезке [~А,0] разбиение Дг Определим ТОЧКаМИ Т_2т, Т_2т+1, • • •) го = 0 симметричным образом.
Наконец, положим
Точки ti и дают интересующее нас разбиение Д отрезка
Пусть 5(Д, 2,1) - пространство параболических сплайнов дефекта 1 на разбиении Д. Приближенное решение задачи будем искать в конечномерном подпространстве Е = Е(е,т) непрерывных функций и = и(£) 6 5(Д,2,1) и удовлетворяющих краевым условиям. Так определяется пробное подпространство. Тестовое подпространство ^ = Е(е, т) определяется равенством ^ = ЬСЕ.
т0 =0, Т1= а/т,..., гт = а,
Т{ = т;_ 1 + (А — а)/тп (г = т + 1,..., 2т).
и = 9 ‘(г>) (* = -2т> ■••,2т).
-29-
Метод Галсркина состоит в отыскании такого элемента ит Є Ет, что для любого г\п Є Рт
(Ье11т,ит) = (/, Ут)
ИЛИ же
(1/Єит 1/£ІІ£) Тго) = О,
где - точное решение исходной задачи, (г/, г?) - скалярное произведение в 1ъ[—1,1]. Отсюда получаем, что Ь€ит = Р£/, где Р£ - ортогональный в Ь2 проектор на Р. Следовательно,
|| ?іт “ Цоо<|| ||і^оо—|| Ре/ ~ / ||оо<
(7(1+ II Р. 11^0 II / - / ІІОО,
^ Л
где / - наилучшее приближение / в Рт. Используя аппроксима-ционные свойства пространств сплайнов, (см. приложение 2),
А д
получаем, что || / — / Ст , откуда
|| ?/т — щ ||оо^ От (1+ || Р£ ||)>
и доказательство оценки погрешности 0(т~2) сводится к доказательству оценок
II Ре іите^оо< Си
где С, Сі не зависят от £:, т.
Пусть Рі, • • •, Р4т+1 - некоторый базис в Р и Лі, • • •, Л4ГП+і -биортогонаяьный к нему в Р2 базис, (т.е. (Аг-, Р,) = 8^, ^ -символ Кронекера). Тогда ортопроектор Ре может быть представлен в виде
4т+1
РеІ= Е (/,Я)М*)і 1=1
откуда
4т+1
іисо^л+ц^ Е КЛРОІ II • (0.22)
і=1
-30-
Поэтому, если
С
(1 + |г - «|)2ЛУ2’
(0.23)
ТО
и опенка нормы проектора сводится к оценке последней суммы, которая в силу свойств разбиения оценивается величиной порядка 0(1).
В пространстве Е удается построить базис, для которого первая оценка (0.23) легко доказывается. Если теперь искать функции А,- в виде А,- = o^jFjJ то вектор коэффициентов а = {сг,} совпадает с г-м столбцом матрицы Г-1, где Г - псев-доразреженная матрица со степенным убыванием элементов от главной диагонали. Далее, используя результаты главы 1, легко доказать, что матрица Г-1 обладает теми же свойствами, что и Г, из чего легко получается вторая оценка (0.23).
В действительности, в главе 3 оценивается не ортогональные, а так называемый гаяеркинские проекторы на Е, оценки которых позвояют установить, что галеркинские приближения дают порядок аппроксимации О(^), который совпадает с порядком наилучшего приближения в пространстве Е. Однако идеи, методы и схема оценивания этих проекторов совпадают с изложенными.
Сформулируем теперь основные результаты глав 3-5.
В главе 3 на отрезке [-1,1] рассматривается задача
х‘(-1) = ■ • • = ж*(-1) = хк+1(1) = ■■■ = Х"(1) = 0. (0.25)
Ьх = ех - А^)х = <2(£),
(0.24)
-31-
Здесь х = (ar1,... ,хп)т в Rn, A(t) и d(t) - гладкие матрица и вектор-функция класса С3[—1,1], е - малый положительный параметр.
Будем предполагать, что при всех t Е [—1,1] собственные значения А,-(£) (г = 1,2,... ,п) матрицы A(t) различны и удовлетворяют неравенствам
Ai(t) < Л2(*) < • • • < Ak(t) < 0 < A*+i W < • • • < A„(f).
Тогда существует такое положительное Aq, что
|Ai(t)| > А0 (г = 1,2,... ,п).
Если через bi(t) (г = 1,2...,п) обозначить собственные векторы матрицы А(£), отвечающие собственным значениям А,-(£), а через B(t) - матрицу со столбцами &i(t),..., 6„(t), то матрица B(t) приводит A(t) к диагональному виду, т.е.
B~\t)A(t)B(t) = diag{\i(t),A„(t)}.
Представим #(£) в блочном виде
BJDИ М \ #21 #22
где #ц, #22 - квадратные матрицы k-ro порядка и (п — к)-го порядка соответственно. Предположим, что
<ktBn(-l)detBii(l)(tetBn(-l)detBn{l) Ф 0.
Как показано в [22], краевая задача (0.24)-(0.25) при всех малых е имеет единственное решение X.
Из асимптотического разложения решения задачи (0.24)-(0.25), построенного в [22], что существуют такие числа £о > 0