Операторы с псевдоразреженными матрицами и их приложения тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Глава I. Операторы с псевдоразреженными матрицами. Общая теория.

§1. Классы ПРМ. Определения и примеры.

1.1. Индексные зоны.

1.2. Функция расползания.

1.3. Классы ПРМ с экспоненциальным убыванием

1.4. Классы ПРМ с субэкспоненциальным убыванием

1.5. Алгебры ПРМ.

1.6. Примеры ПРМ.

1.7. Наполненность алгебр ПРМ.

1.8. Доказательства лемм и теорем

1.9. Доказательство теоремы 1.1.

1.10. Доказательство теоремы 1.1 для произвольного р.

1.11. Доказательство теоремы 1.2.

1.12. Доказательство теоремы 1.3.

1.13. Доказательство теоремы 1.4.

§2. Оценки Ъи и С^11-разложений ПРМ.

2.1. Формулировки теорем.

2.2. Вспомогательные леммы.

2.3. Доказательства теорем 2.1 и 2.2.

2.4. Доказательства теорем 2.3 и 2.4.

§3. Оценки обратных матриц, LU и QR-разложений хорошо обусловленных псевдоразреженных матриц конечных порядков.

3.1. Индексные зоны

3.2. Функция расползания.

3.3. Инверсно замкнутые классы с экспоненциальным убыванием.

3.4. Инверсно замкнутые классы с субэкспоненциальным убыванием.

3.5. Замечания о доказательствах теорем 3.1-3.

3.6. Об оценках LU и QR-разложений разреженных матриц.

3.7. Примеры инверсно замкнутых классов

3.8. Инверсно замкнутые классы для многоуровневых псевдоразреженных матриц

3.9. Оценки LU-факторизаций в случае приближенных вычислений

§4. Оценки блочных факторизаций модельных эллиптических краевых задач.

4.1. Оценки элементов точных факторизаций

§5. Оценки неполных факторизаций модельных эллиптических краевых задач.

5.1. Вспомогательные леммы.

5.2. Оценки элементов матриц G¿

Глава И. Теория методов неполной факторизации

§6. Методы неполной факторизации для хорошо обусловленных разреженных систем.

6.1. Неполная точечная факторизация.

6.2. Неполная блочная факторизация.

§7. Методы неполной факторизации для эллиптических краевых задач.

7.1. Доказательство теоремы 7.1.

7.2. Доказательство теоремы 7.2.

7.3. Доказательство оценок снизу

Глава III. Метод конечных элементов Галеркина для систем сингулярно возмущенных уравнений первого порядка.

§8. Постановка краевой задачи и основной результат

8.1. Постановка краевой задачи.

8.2. Разбиение отрезка [—1,1] и аппроксимаци-онные пространства.

8.3. Галеркинская задача и основная теорема

§9. Схема доказательства теоремы 8.1.

9.1. Галеркинский проектор.

9.2. Представление галеркинского проектора через биортогональные базисы

9.3. Завершение доказательства теоремы 8.1.

§10. Вспомогательные результаты и доказательства лемм.

10.1. Аппроксимационные свойства пробных пространств.

10.2. Доказательство леммы 9.1.

10.3. Доказательства лемм 10.2 и 10.3.

§11. Равномерная линейная независимость функций Fij

11.1. Равномерная линейная независимость В-сплайнов.

11.2. Некоторые свойства нормированных функций F^.

11.3. Схема доказательства CPJIH функций Fij.

11.4. Равномерная линейная независимость группы А\.

11.5. Равномерная отделимость группы А^.

§12. Построение и свойства биортогональных базисов.

§13. Доказательство леммы 9.5.

Глава IV. Метод конечных элементов Галеркина для линейных и квазилинейных сингулярно возмущенных эллиптических краевых задач

§14. Постановки задач. Основные результаты и указания к численной реализации.

14.1. Постановки исходных задач.

14.2. Дискретизация и постановки галеркин-ских задач.

14.3. Базисы в пространствах Р и указания к численной реализации.

§15. Галеркинские проекторы и их свойства.

15.1. Определение галеркинского проектора.

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

15.3. Существование биортогональных базисов.

15.4. Дальнейшие свойства биортогональных базисов

§16. Построение биортогональных базисов для линейных задач в одномерном случае.

16.1. Дискретные решения.

16.2. Построение биортогональных базисов к функциям В.

16.3. Завершение построения биортогональных базисов.

§17. Построение биортогональных базисов в двумерном случае

§18. Завершение доказательства теоремы 14.1.

18.1. Аппроксимационные свойства пространства Е.

18.2. Доказательство теоремы 14.1.

Глава V. Метод конечных элементов Галеркина для сингулярно возмущенных параболических начально краевых задач.

§19. Постановки задач и формулировки результатов.

19.1. Постановки задач.

19.2. Формулировка основного результата для нелинейных систем.

19.3. Линейные задачи.

§20. План доказательства теорем 19.1 и 19.2.

20.1. Дискретная функция Грина.

§21. Доказательство оценок (20.8)

21.1. Некоторые свойства разреженных матриц

21.2. Некоторые свойства базисных функций пробных пространств.

21.3. Дискретные функции Грина в подобластях

21.4. Доказательство оценок (20.8)

§22. Функции Грина в подобластях.

22.1. Теорема о частичных функциях Грина.

22.2. Два вспомогательных оператора.

§23. Проверка условий теоремы 22.1.

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

23.2. Схема оценивания функции Грина в одномерном случае.

23.3. Доказательство леммы 23.2.

23.4. Доказательство оценок (20.3) в двумерном случае.

Обозначения а] - целая часть вещественного числа а N - множество натуральных чисел

АГ2'" = {(г,;) е ТУ2 : 1 < г,^ < п} Z -множество целых чисел

-множество целых неотрицательных чисел Я - множество вещественных чисел е - малый положительный параметр /г - сеточный параметр

С? Съ Сг, • • • - обозначения положительных констант, не зависящих от е, К

Если для некоторой величины 7 имеют место оценки ¡7( < С|/3|, то будем писать 7 = 0(/3), а если 0 < С\\(5\ < |7| < С21|? то

7 = 0*((3)

Пусть а = {аг} 6 Я". Тогда символ |а| обозначает вектор из Яп с элементами |аг-|.

Пусть А = {а0-} — п х п-матрица. Тогда символ |А| обозначает п х п-матрицу с элементами

Ьр, 1Р - пространства Лебега 1 < р < оо с нормой || ||р Пусть А = {а^} - конечная или бесконечная матрица, определяющая ограниченный оператор в 1Р. Тогда || А ||р - норма оператора А, || А ||= тах{|| А ||ь || А Н^} сопс1(А) =|| А 112Ц А~1 Ц2 спектральное число обусловленности матрицы или оператора, виррА = {{г,]) Е г2 : ау- ф 0} - единичная матрица или оператор

- символ Кронекера Умножение бесконечных матриц понимается в смысле суперпозиции соответствующих операторов в 1Р1 т. е. И = А1А2 означает, что йц = £кег а\как]

С = й1ад{0\, • • •, Сгп} - обозначение диагональной или блочно- -диагональной матрицы №сИад{—Пр,Ер1—Ер}, 1 < р < п - обозначение трехдиаго-нальной или блочно- -трехдиагональной матрицы (блоки и Рп отсутствуют).

ПРМ - псевдоразреженные матрицы

СЛАУ - система линейных алгебраических уравнений

ММП - метод матричной прогонки

МСГ - метод сопряженных градиентов

ДБПФ - дискретное быстрое преобразование Фурье

Первый класс задач - математическое обоснование методов неполной факторизации (МНФ) решения систем линейных алгебраических уравнений (СЛАУ) с разреженными матрицами > о

О, t < О

Аббревиатуры

Введение

РМ) высоких порядков. Это направление, начиная с 50-х годов, интенсивно развивалось в работах Н.И. Булеева, В.П. Ильина, В.П. Гинкина, В.К. Артемьева, а позднее - в работах О. Axels-son'a, R. Beauvens'a, Van der Vorst'a, J. Golub'a, А.Ю. Еремина, И.Е. Капорина, Л.Ю.Колотилиной, P. Concus'a, J. Meurant'a, T. Manteuffel'a, Y. Notay, T. Chan'a, P. Vassilevski [3],[20],[21], [27],[37],[36],[65], [66],[68],[69],[93],[90],[96], [91],[72],[73] и многих других математиков. Итоги этих исследований подведены в монографиях [34],[65], где приводится подробная библиография. Однако неисследованным оставался вопрос о зависимости скорости сходимости итераций МНФ в зависимости от структуры допустимого заполнения предобуславливателей. В связи с этим следует упомянуть также монографии [60],[114] О.Эстербю, 3. Златева, в которой изучаются так называемые барьерные методы, суть которых в том, что все элементы, возникающие в процессе факторизации РМ, меньшие заданного барьера г « 1, полагаются равными нулю. Эти методы также следует отнести к МНФ. Для данного класса методов до последнего времени не было ни теоретического доказательства сходимости ни оценок погрешнсти предобуславливателей.

Второй класс задач - алгоритмы метода конечных элементов для сингулярно возмущенных краевых задач и теория априорных Loo- оценок погрешности таких методов. Отметим, что наиболее развитой для таких задач является теория разностных схем, которой посвящены работы Н.С. Бахвалова, A.M. Ильина, В.Б. Андреева, И.П. Боглаева, В.Н. Задорина, К.В. Емельянова, В.Н. Игнатьева, В.Д. Лисейкина, Макарова В.Л. и Гуминского В.В., Г.И. Шишкина, H.H. Яненко, Е. Gartland'a, P. Hemker'a, D. Herceg'a, J.J.H. Miller'a, O'Riordan'a, К. Surla, M. Stynes'a, R. Vulanovic'a [1], [17],[18],[25], [30],[31],[39],[42],[52]-[57],[25],[98],

109],[113] и других математиков. Начиная с основополагающих работ Н.С. Бахвалова и A.M. Ильина [11],[33], работы по разностным схемам традиционно делятся на два направления: экспоненциально подогнанные схемы на равномерных и квазиравномерных сетках и разностные схемы, на неравномерных сетках, сгущающихся в области пограничного слоя. Второе направление интенсивно развивается в последние годы в работах В.Б. Андреева, Г.И. Шишкина, К.В. Емельянова, А.И. Задорина, Н.В. Коптевой, И.А. Савина, D. Herceg'a, М. Stynes'a, G. Sun'a, R. Vulanovic'a и др. [2],[26],[31],[45],[87],[109], [113],[52]-[57].

Работы по методу конечных элементов для СВЗ также можно разделить на две группы: схемы на квазиравномерных сетках с использованием экспоненциально подогнанных базисных функций (Б.М. Багаев [5]-[8], Б.М. Багаев и В.В. Шайдуров [4], И.П. Боглаев [15] -[16], Р. Hemker,P.P.N. de Groen [86],[85], Gartland E. [82],[84], J.J.H.Miller, O'Riordan, M. Stynes, [43],[104]-[108], W.Scymchak, I.Babushka [102], A.H.Schatz, L.B.Wahlbin [100]) и схемы на адаптирующихся к погранслою сетках ( U. Asher,R. Weiss, К. Ringhover [61]-[63],[97], Е. Gartland [83], J.E.Flaherty [81]). Отметим, что второе направление для метода конечных элементов развито существенно меньше, чем первое, причем нам представляются важными следующие аспекты:

1) Использование оптимальных сеток Н.С. Бахвалова (широко используемые кусочно-равномерные сетки Г.И. Шишкина несколько более грубы).

2) Получение оценок погрешности в Loo или С-норме (более традиционные для метода конечных элементов оценки в интегральных либо энергетических нормах не гарантируют аппроксимации пограничного слоя). Отметим, что ^оо-теория метода конечных элементов для нежестких задач была развита в 70-е - 80-е годы в работах Л.ШэсЬе, Р. ЫаШгег'а, И.Бсои'а, А.Н. БЫ^г'а, Ь. Wahlbin'a, V. ТЬотее [95],[94],[103], [77],[101],[110]. Построение ее аналогов для сингулярно возмущенных уравнений оказывается существенно более сложным из-за сильной неравномерности расчетной сетки и невозможности выделить простую главную часть оператора задачи.

3) Разработка и обоснование безытерационных схем МКЭ для эллиптических и параболических СВЗ с числом пространственных переменных п > 1 в областях с криволинейной границей ( разработанные в этом случае разностные схемы [54] предполагают использование декомпозиции области с перестройкой разностной сетки в зонах налегания в процессе итераций).

4) Построение схем МКЭ повышенного (> 2) порядка сходимости.

Построение таких схем и составляет содержание глав 3-5 настоящей диссертации.

Основными и важнейшими компонентами математического аппарата решения поставленных задач являются а) в случае методов неполной факторизации для СЛАУ с соп<1(А) = 0(1) - оценки элементов матриц, обратных к разреженным матрицам или матрицам, для которых задан закон убывания их элементов в зависимости от расположения (в простейшем случае - убывание от главной диагонали), а также элементов их Ьи и ф#-разложений; б) в случае методов неполной блочной факторизации для эллиптических задач - оценки убывания элементов блоков точных и неполных факторизаций; в) в случае методов конечных элементов для сингулярно возмущенных краевых задач - оценки убывания элементов матриц, обратных к матрицам Грама специальных базисов в конечномерных галеркинских пространствах.

Таким образом для решения этих задач необходима теория оценок элементов матриц, обратных к РМ, оценок элементов их LU и Q-R-факторизаций, а также теория аналогичных оценок для более общих, чем РМ, классов матриц с заданным законом убывания элементов, который сохраняется при обращении или факторизации. Такие бесконечные матрицы, которые могут вообще не иметь нулевых элементов, но большинство их элементов малы при абсолютной величине, причем закон распределения малых элементов сохраняется при обращении или факторизации, названы автором псевдоразреженными матрицами (ПРМ).

Вопросы, связанные с оценками элементов обратных матриц в связи с задачами вычислительной алгебры или теории аппроксимации ставились и раньше. Однако, в основном изучались трехдиагональные или блочно-трехдиагональные матрицы [11],[35],[47],[89],[93],[92], [111], либо ленточные матрицы [73]-[76],[78], [111],[112]. В [71] в связи с задачами оценок погрешности среднеквадратичной аппроксимации изучались матрицы, обратные к ленточным матрицам Грама, составленных из В-сплайнов на квазиравномерных разбиениях. В [9] рассматривались бесконечные матрицы, элементы которых определенным образом убывают при удалении от главной диагонали, и доказывались аналогичные оценки для элементов обратных матриц. Эти оценки близки к более ранним результатам автора [123] или являются их частными случаями. Отдельные результаты (случай экспоненциального убывания или убывания быстрее любой степени от главной диагонали) были получены в [58],[59],[14]. Результаты об оценках элементов обратных матриц для РМ общей структуры, а также об оценках элементов Ьи и (5Я-факторизаций в литературе практически отсутствуют. Можно отметить работу [92], но в ней оценки обратных матриц и факторизаций для для блочно-трехдиагональных систем зависят от числа обусловленности и являются грубыми в части ££/-факторизаций. По-прежнему весьма актуальным является высказывание, что "утверждения и предположения о методах разреженных матриц, как правило, не удается доказать математически" ([60], С. 14).

В связи с этим целями настоящей работы являются

1) Построение теории оценок элементов обратных матриц, Ы1 и фЛ-факторизаций, охватывающей весьма широкий класс РМ общей структуры, а также более широкие: чем РМ классы матриц, точные оценки блочно- треугольных факторизаций дискретизаций модельных эллиптических краевых задач, матриц обратных к матрицам Грама базисов конечноэлементных пространств на сильно неравномерных триангуляциях.

2) Применение этой теории к решению обсуждавшихся выше двух классов задач.

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

В первой главе реализается обозначенная выше цель для хорошо обусловленных (сопв,{А) = 0(1)) РМ общей структуры.

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

Пусть 5 С - некоторое множество, такое, что если (г,^) Е 5, то г) Е 5, и (г, г) Е 5 для всех г Е Z. Через С = г, ^ Е обозначим бесконечную матрицу, элементы д^ которой равны единице при (г, £ 5 и нулю в противном случае.

Определение 1.1. Множество 5 будем называть порождающим, а матрицу С - структурно-порождающей.

Предположим, что число элементов в любой строке (столбце) матрицы конечно и ограничено константой, не зависящей от номера строки (столбца). Тогда для любого п определена степень (7™. Очевидно, Сп обладает теми же свойствами, что и С.

Положим ¿>1 = 5,= виррСк \ виррСк~1, к > 2. Пусть = {(г,7) Е : (¿,;') £ V к Е Л^}. Тогда = и 52 и • • • и 5«,. Множества Бк будем называть индексными зонами или просто зонами. Пусть а = и = 0, и = и 5*.

1.1-. Функция расползания

Пусть А = Е Z} - бесконечная матрица, а - те же, что и выше. Через Рк{А) = {%•} обозначим матрицу, элементы которой таковы, что а^ = а^ при (¿,7) Е Бк и Ац — О при (г,у) £ Пусть Е = ^ 6 - бесконечная матрица, все элементы которой равны единице. Через /г : N N обозначим функцию, значение которой к{к) равно максимальному числу ненулевых элементов в отдельно взятой строке (столбце) матрицы Рк{Е). Функцию Н будем называть функцией расползания множества 5.

1.2. Классы ПРМ с экспоненциальным убыванием Зафиксируем некоторое порождающее множество 5. Обозначим через 1?(5) класс бесконечных матриц А таких, что

II Рк{А) ||< Сх ехр(-7*;), к е N. Р^А) = 0 (0.1) при некоторых С\ = С\{А) и 7 = 7(А) > 0.

1.3. Классы ПРМ с субэкспоненциальным убыванием Введем в рассмотрение функцию / : N —> N такую, что к) > 0,/(&) стремится к нулю монотонно при к —> оо и

0.2) (0.3)

Обозначим через таких, что

Ы < СгЩ, (г,;) е € ТУ; Р^А) = 0,^ = (Л (А). (0.4)

В пункте 1.4 классы ПРМ рассматриваются как алгебры относительно операции суперпозиции. Классы ПРМ, как подалгебры алгебры В{1Р) ограниченных операторов в 1р, обозначим ^(Л^Р) и а как подалгебры С11<р<ооВ(1р) - £>(/, 5,0) и

5,0).

В пункте 1.5 приводятся примеры классов ПРМ с различными законами убывания элементов и оцениваются их функции расползания. Здесь мы ограничимся лишь одним примером. Пример 1.1.

Трехдиагоналъные структурно-порождающие матрицы. Пусть = {(¿»¿) £ Z2 : \г - Л < 1}. Очевидно, что 5* = {(г,;) € : К ~~ з\ — & + 1} при к > 2, а функция расползания

КЩ, ехр(-7п)//(п) = 0 для любого 7 > 0; оо /М%) < С,

71=1 где к - функция расползания множества 5. £>(/, 5) класс бесконечных матриц А = {%} имеет вид 1) = 3,к(к) = 2,к > 2. Этот пример описывает классы матриц с убыванием элементов при удалении от главной диагонали: А Е <==> < С1 ехр(—7|г — Л), А 6 Иа^) \ац\ < С1/(|г - Л), г ^ у \ац\ < 61/(1) при некоторых С\ > 0,7 > 0.

1.6. Наполненность алгебр ПРМ

Случай убывания элементов от главной диагонали. В этом случае (см. пример 1.1) удается дать почти исчерпывающий ответ на вопрос о наполненности алгебр ПРМ.

Пусть / : Л7" —»■ Л - монотонно у$1>тлн)ЩАЯ функция, удовлетворяющая условию (0.3) при Н(п) = 2.

Теорема 1.1. Для наполненности алгебры £)(/, из примера 1.1 при любом р Е [1, оо] необходимо, чтобы для функции / выполнялись условия (0.2),(0.3), и условие

Е/(Ц/(п-Ц<С/(п). (0.5) к=1 и достаточно, чтобы выполнялись условия (0.2),(0.3) и для некоторой функции й : N Я такой, что й{1) —> 0 при I —¥ оо, для всех п,1 € N имели место соотношения

Е1(к)1(п-к0<ад/(п). (0.6) к=1

В замечании 1.3 приводятся несколько примеров функций (в частности, степенных), удовлетворяющих условиям (0.2),(0.6).

Наполненность алгебр Е(в,р) из примера 1.1 вытекает из теоремы 1.2 (см. ниже).

Общий случай. В общем случае вопрос о наполненности алгебр ПРМ решается с помощью оценок функции расползания.

Теорема 1.2. Пусть для некоторой функции : (0,1) —> [1, -(-со) и констант Сз > 0,£ > 0, к Е (0,1) при всех /3 Е

0,1), А; £ N справедливы неравенства

Цк) < д(/?)ехр(/%;), (0.7) з(/3)<С3ехр(<У/П. (0-8)

Тогда алгебра Е($, 2) наполнена. Более того, для любых констант С1,С2,Сз,<£,7, к Е (0,1) найдутся такие константы и 71, зависящие лишь от указанных величин и не зависящие от что если А £ 2), || А ||2< С2, матрица А удовлетворяет условию (0.1), а функция расползания множества 5 - условиям (0.7), (0.8), то для матрицы А~1 справедливы оценки Рк(А~1) ||< С4ехр(—71&), к Е N. (0.9)

Теорема 1.3. Пусть к(к) < С ехр((к") при некоторых С > 0, С > 0,1/ £ (0,1/2). Тогда найдутся такие д,Сз > 0,£ > 0, ас £ (0,1), что выполнены условия (0.7),(0.8) для к{к).

Для формулировки теорем о классах 1)(/, 5,р) дополнительно к условиям (0.2),(0.3) наложим на функцию / следующие условия

А). Найдется такая функция с1(т), монотонно стремящаяся к нулю при т —» оо, что

А/2] +оо

2ЕЯ0/(*-0Л(0 + 2 £ (/(0)2М0 < <*Н/(*0,

1=т 1=[к/2]+1

1 < т < [к/2] + 1.

Пусть ¿1(771) = Е^п+1 f{n)h{n). Зафиксируем некоторые т £ Л^,7 > 0, ф > 0. Обозначим через т\ наименьшее из натуральных чисел, для которых й(гп1) < <^1(т)/(шах(ехр(-й7/т)//(&))). (0.10)

Существование такого т\ вытекает из условия (0.2). Функцию, осуществляющую соответствие т,ф,7 —>• шх, обозначим М(т,ф, 7).

В). Для любых <^>,7 > 0 lim dAm) max (f(k - M(m, Ф^))//(к)) = 0.

Теорема 1.4. Пусть функции f,h таковы, что выполнены условия (0.2),(0.3),(А),(В). Тогда если h - функция расползания множества S, то алгебра £)(/, 5,0) наполнена. Более того, для любых констант С, Сх,С2 найдется такая константа С4 — С4(С,С1,С2,Л,/), зависящая лишь от указанных величин и не зависящая от 5, что если а Е D(/, 5,0), || А'1 ||< С2 и А удовлетворяет условию (0.4), то для элементов аг;- матрицы А'1 справедливы оценки

Ы < c4f(k), (г,i) £Sk, ке N. (0.11)

Теорема 1.5. Пусть для некоторых ß > 0,7 > 0

7 > ß +1, ад < о>(* +т = (к +

Тогда для функций f,h выполнены условия (0.2),(0.3),(А),(В).

В §2 изучаются LU и QÄ-разложения ПРМ из §1. Здесь доказано, что закон убывания элементов ПРМ сохраняется при переходе к LU и QR- факторизациям.

В §3 результаты §1 и 2 переносятся на классы псевдоразреженных матриц конечных порядков. Сответствующие определения и формулировки теорем аналогичны аналогичны определениям §§1 и 2, а сами теоремы вытекают из теорем §§1 и 2. Принципиально новый результат получен в п. 3.8, где рассматриваются многоуровневые матрицы.

В п. 3.9 доказаны теоремы об оценках ¿¿/-разложений в случае возможных округлений элементов ПРМ в процессе вычислений.

В случае приближенных вычислений процесс построения приближенного ¿[/-разложения можно записать в виде

1)^(1) £,(2)А(2) Ь{п-1)А[п-1) = ьиъьи = А.

0.12)

Определение 3.4. Пусть А е ЕЬ(<у, 5, Сь С2, С3, а) для некоторых 7,С1,С2,Сз,а. Будем говорить, что для матрицы А промежуточный рост (а, 5)-структурно ограничен константами 71 и С, если для любых натуральных р < п справедливы оценки || Рк,а{Ь^) ||< Сехр(-Ък), || Рк,а(А^) ||< Сехр(-Ък).

Определение 3.5. Алгоритм приближенного построения ¿¿/-разложения А = Ь11 будем называть алгоритмом типа Г(г) (или ГК(г)), если ¿¿/-разложение строится метоом Гаусса (или с помощью компактной схемы ) с возможными округлениями лишь тех элементов промежуточных матриц А^ и которые по модулю не больше £, а округление возможно лишь в сторону уменьшения модуля.

Обозначим через С, а,£0) (или аг,£о)) множество квадратных матриц, допускающих ¿¿/-разложение, для которых любой алгоритм типа Г(е) (или ГК(е) реализуем при £ £ (0, ¿го], причем промежуточный рост в любом таком алгоритме (а, 5)-структурно ограничен константами 71 и С.

Теорема 3.13. Для любых 7, С1,С2,Сз найдутся такие 71,С4,е,что если А £ £¿(7,5,61,62,(73,0;) и является М-матрицей, то А £ прие £ (0,е0]

Теорема 3.14. Пусть А является Я-матрицей (см. при. Л /ч ложение) и для соответствующей М-матрицы А имеем А £

М(7,С,0!,г) П ЕД7,СьС2,Сз,О;) (или А € МК(ъС,а,е) П СьС'2,Сз,а)).Тогда для некоторой С4 = 64(7, С, Сх, Сг) будет А е М(7,С4,а,г) (или Л е М/((7,С4,а,£)).

В §§4-5 с точки зрения псевдоразреженности изучаются точные и неполные блочные факторизации модельной элиптиче-ской краевой задачи. Здесь получены асимптотически точные оценки элементов.

Рассмотрим модельную краевую задачу

Ми = -Au = f(x,у), w|r = О

0.13) в единичном квадрате П:[0,1]х[0,1].

Здесь Г-граница П, Аи = д2и/дх2 + д2и/ду2. Пусть п > 4 натуральное число. Пусть 0 = Жо < . < хп+\ = 1,0 = г/о < — < уп+1 = 1,жг-+1 - Хг = у 1+1 -У1 = }ь = 11(п + 1). Аппроксимируем оператор (0.13) выражением ~ (—— +

4гíг•J• — «¿+1,; — г¿г•J+l)/Н2. Перенумеруем компоненты сеточной функции:

Un = Ml, М21 = W2> • ' ' > ип\ = ип, г/12 = Un+1, и22 — г*п+2,

• • •, Щ„ = «„(„!), •••,ипп = ип 2. (0.14) и умножим каждое разностное уравнение на Д2. Тогда получим СЛАУ AU = F, где

А =

Ei -Fi ••• 0 — D2 -É/2 —F2 ' • V

0 • • • —Dn Е,I у

0.15)

Ei, Д-, Ff -квадратные матрицы порядка n, Fi = Di — 1,1 - единичная матрица.

Рассмотрим блочную факторизацию матрицы А А = (В + в^-^О + Г),

6' =

С?1 о о о с2 ••• о

О 0 ••• вп / =

I) =

О ••• о о о ••• о

-.02 о • • • о о ••. ;

О ••• -Д, О \

0.16)

0.17) V

0 0 ••• -^п—1

0 0 ••• о где (п х п) -матрицы определяются с помощью метода матричной прогонки:

С! = Дь <?*+! = Е3+1 - 5 = 1,2,., п - 1 (0.18)

Определим неполную блочную факторизацию матрицы А без диагональной компенсации формулами

А = (Я + СОб^СЧД),

0.19) где (5 = с?га^(Ст1, .,(?„), И и Д - матрицы (0.18), а определяются формулами

1 = ЕъС8+1 = Е8+1-П8+1(&-81)^Р8, 5 = 1,2,.,п — 1. (0.20)

Здесь символ (&) означает взятие (2к + 1)-диагональной части матрицы, т.е. если В = {Ь»^}, то В^ = {Ь^^}, = Ьц при \г - Л < к, Ьу,* = 0 для |г - > к.

Кроме того рассмотрим неполную факторизацию матрицы А с диагональной компенсацией (см. [34])

А = (И + в)а-\а + Д), £ = • • •, 6«}, дг = Сг-вЭ^ 5! = 0, й+1е = (Д+^Г^^Д+хС^+ЭД-^^^е,

0.21) здесь и далее е -вектор с единичными компонентами, ¿>г- диагональные матрицы, в £ [0,1] - компенсационный параметр).

Теорема 4.1. В разложении (0.16)-(0.17) для элементов матриц Ст^1 = справедливы формулы шт{г, 5,1 + |г — Л} о\

1 + |г-^|)3 1 < г,э < Зп/4 тт{п + 1 - г, а, 1 + [г - Л) 1 (1 + |г-Л)3 гг/4 < < п, где г8 = г8(1,з) = 0*(1).

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

Теорема 5.2. Найдутся такие константы > 0, а £ (0,1/2), не зависящие от п, к, что для элементов ма~ ч /ч . триц С" справедливы оценки ТТТТ-ЛТо-^-> 0 < 1г ~ А < к1

1 + |г-Л)2 ка

С2 (к-\г-Л + 1)а

1 + | г-Л)2 ка

N - Л > к 0 < \г - ¿| < к, ка/2{1 + |г — Л)2 Вторая глава посвящена методам неполной факторизации для СЛАУ с РМ высоких порядков.

В §6 строится теория МНФ (барьерных методов и методов исключения по позициям) для хорошо обусловленных РМ ([сопй{А) = 0(1)). В п. 6.1. изучаются точечные факторизации.

Зафиксируем некоторый инверсно замкнутый класс Е(в) (определение см. в §3). Пусть А - разреженная квадратная матрица высокого конечного порядка п, А Е £/(7,5, С\,С2,а) для некоторых С\ > О, С2 > 0, а Е Л, и кроме того виррА С 5"а.

Методы неполной факторизации с экономией машинной памяти. Методы, рассматриваемые в данном пункте, позволяют экономить память ЭВМ при запоминании сомножителей факторизации матрицы А. Если системы с матрицей А нужно решать многократно, то эти методы дают выигрыш и во времени.

Методы искусственного ограничения заполнения. а) Метод Гаусса.

Пусть А Е ЕЬ(7,5, Сг, Сз, а). Рассмотрим следующий алгоритм.

Ш а г 1. Фиксируем ко Е N. ко

Ш а г 2. Определяем заполнение а = II

Ш а г 3. Полагаем % — 1.

Ш а г 4. Вычисляем элементы иц и ] > г Ы1 -разложения. Вычисляем (г + 1)-ю промежуточную матрицу метода Гаусса.

Ш а г 5. Запоминаем лишь те элементы и^ и для которых £ Як0,а- Остальные считаем равными нулю и не запоминаем.

Ш а г 6. Полагаем г — г + 1 и переходим к шагу 4, если г < п.

Замечание 6.1. Реализация шага 2 возможна с помощью теоретикографовых алгоритмов (см. [44]).

Обозначим через Ь II сомножители полученной неполной Ы1-факторизации. Пусть А = Ь11.

Теорема 6.1. Для любых 7 > С^СьС^Сз найдутся такие константы Св,Ст,С8 и 71 > 0, что

L-L ||< С§ ехр(—71^0), || и-II ||< Сбехр(-71^0). A-A ||< C7exp(-7ife0).

Кроме того найдется такое к\ = k¡(j, Ci, C2, C$) E iV, что при k§ > k\ имеем

II А'1 - А"1 ||< C8exp(-7iA;o). б)Компактная схема метода Гаусса.

Рассмотрим следующий алгоритм для A Е 5, С\, С2, Сз, а). Шаги 1-3,6 - те же, что и в п. а).

Ш а г 4. Вычисляем элементы u¡j и / j¿, j > i LU-разложения по формулам компактной схемы [23],с. 175.

Ш а г 5. Если i > 2, то полагаем щ^-х — h-\,k = 0,к = 1,2, 2 при (i-l,k)ÍQnkQ¡a.

Очевидно, что построенная факторизация совпадает с факторизацией из п. а) и для нее справедлива теорема 6.1. в)Метод отражения.

Рассмотрим следующий алгоритм для A Е #(7,5, С\, С2, а). Шаги 1-3,6 - те же, что и в п. а).

Ш а г 4. Вычисляем матрицы А« и Р(0 по методу отражении [12],гл. 3 §3.

IIL а г 5. Если i > 2, то для элементов QRразложения (Q — Рт) полагаем r¿= 0, = 0 при

Обозначим через Q и R сомножители неполной факторизации.

Теорема 6.2. Для любых 7 > 0,Ci,C2 найдутся такие константы Се, С*7, С% и 7i > 0, что

II Q-Q ||< С6ехр(-7^0), || R - R ||< C6exp(-7i¿0).

М-А||<С7ехр(-71ад.

Кроме того найдется такое к\ = к\(?(,С\,С2) Е что при к0 > к\ имеем Л-1-!"1 ||<С8ехр(-71*о).

Барьерные методы. г) Метод Гаусса.

Пусть А Е ЕЬ(7, 5, Сь Сз, а). Рассмотрим следующий алгоритм.

Ш а г 1. Фиксируем е > 0.

Ш а г 2. Полагаем г = 1.

Ш а г 3. Вычисляем элементы и^ и ] > г ¿[/"-разложения и элементы промежуточной матрицы Запоминаем лишь те элементы и^ и для которых |иц \ > г, > е.

Ш а г 4. Полагаем г := г + 1.

Ш а г 5. Если г <п — 1, то переходим к шагу 3.

Пусть Ь и и - сомножители полученной факторизации.

Теорема 6.3. Для любых 7 > 0,Сх,С2,Сз, к £ (0,1) найдутся такие константы что при е Е (0,1), ко = тах{[7-11п(Сб/б:)] + 1,1} имеют место включения виррЬ С и справедливы оценки || Ь — Ь ||< С^, || и — II ||< д) Компактная схема метода Гаусса.

Рассмотрим следующий алгоритм для А Е ЕЬ(*у, 5, Сл, С2, Сз, а). Шаги 1,2,4,5 - те же, что и в п. г).

Ш а г 3. Вычисляем элементы иц и по формулам компактной схемы. Для к = 1,2, • • •, г — 2 полагаем = 0, /¿-1,* = 0, если |«£)г-1| < £,1^-1^1 < е. Построенная факторизация совпадает с факторизацией из п. а), и для нее справедлива теорема

6.3. е)Метод отражения.

Рассмотрим следующий алгоритм для А Е Е(у, 5, С\,С%а). Шаги 1,2,4,5 - те же, что и в п. г).

Ш а г 3. Вычисляем матрицы и по методу отражений [12],гл. 3 §3. Если г > 2, то для элементов , фЛ-разложения (С^ = Рт) полагаем гг-= 0, ^¿-у — 0, если

Обозначим через и Я сомножители неполной факторизации.

Теорема 6.4. Для любых 7 > 0, С^С^я € (0,1) найдутся такие константы что при е Е (0,1), ко = тах{[7-11п(Сб/е)]+1,1} имеют место включения виррС^ С виррЯ С Як0,а) и справедливы оценки || § - 0, ||< || Я-Я\\<С7£К.

Методы неполной факторизации с экономией памяти и времени.

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

Пусть А Е ЕЬ(у, 5, СьС2,Сз,а). Рассмотрим алгоритм, который назовем Г1; шаги 1-3,6 те же, что и в п. а).

Шаги 4-5. Вычисляем элементы а^- промежуточной матрицы

А® следующим образом: если (&,.?) Е Я1а,а-> то вычисляем по обычным формулам метода Гаусса, а если (&,.?') ^ Як0,а-> то полагаем а$ = 0. з)Компактная схема

Рассмотрим алгоритм, который назовем Г2; шаги 1-3,6 те же, что и в п. б).

Шаги 4-5. Для 3 = г, г + 1, • • • , п выполняем следующие действия: если (г,^) Е то вычисляем по формулам компактной схемы, а если (г, Е а, то полагаем щ = О= 0.

Теорема 6.5. Для любых 7,С, £0Е (0,1) найдется такое к\ = О^п^1), что при £ Е (0,£о],&о > Ь для любой Л Е М(у,С,а,£о) (или А Е алгоритм Г1 (или Г2) является алгоритмом типа Г(ео) (или ГК(£о)).

Барьерные методы. и) Метод Гаусса.

Пусть А Е ЕЬ(7,5, Сх, Сз, а). Рассмотрим следующий алгоритм, который назовем ГЗ; шаги 1,2,4,5 те же, что и в п. г).

Ш а г 3. Вычисляем элементы щ и 1X1-разложения и в методе Гаусса, но для каждого вновь вычисленного элемента проверяем условие < < £■ Если оно выполнено, полагаем соответствующий элемент равным нулю.

Теорема 6.6. Пусть А Е М(7, С, а,£). Тогда при всех i = 1,2, - • • ,п - 1 имеем виррЬ^ С СЦ^виррА^ С <2£0>а, где к0 = тах{1, [7-11п(С / £■)] + 1}. к) Компактная схема.

Рассмотрим алгоритм Г4; шаги 1,2,4,5 те же, что и в п. г).

Ш а г 3. Вычисляем элементы йц и I^ по формулам компактной схемы. Если какой-то из вычисленных элементов по модулю меньше е, полагаем его равным нулю.

Теорема 6.7. Пусть А Е МК(^,С,а,£). Тогда виррЬ С а, зирри С ЯЪ^ где к0 = шах{1, [7-11п(С/е)] + 1}.

В п. 6.2 на основе результатов п. 3.8 получены аналогичные результаты для неполных блочных факторизаций.

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

Рассмотрим методы неполной факторизации (0.19)-(0.21) для СЛАУ (0.15). Пусть Ki = А"1 А, К2 = А1А. В §7 будут установлены следующие утверждения.

Теорема 7.1. Найдутся такие константы С\ > 0,С2 > 0, что при всех п > 4< п справедливы оценки

Тт?

С^ < cond^) < c,-r

Теорема 7.2. Найдутся такие константы Сi > 0,С2 > 0, что при всех п > А,к < у/п, в — 1 справедливы оценки

77 7?

Сх-< cond(K2) < C2-, причем оценка снизу справедлива при всех к Е [1, п], в Е [0,1].

В главах 3-5 рассматривается метод конечных элементов для сингулярно возмущенных краевых задач. При этом получение априорных оценок погрешности приближенных решений основано на оценках норм оргтогональных в Ь2 проекторов на конечноэлементные галеркинские пространства в операторных нормах пространств C(Q) или Loo(Q). Эти оценки, в свою очередь, сводятся к изучению структуры матриц, обратных к матрицам Грама, составленных из специальных базисов конечно-элементных галеркинских пространств.

Покажем это на примере модельной задачи

Ь£и = ей' - A(t)u = f(t), i UW = 0, A(t) > A0 > 0.

Следуя идеям Н.С.Бахвалова [10], построим специальное разбиение отрезка [—1,1], сгущающееся в зонах погранслоев. Пусть а = 1 — 3s\lne\/\o. Определим сначала вспомогательную функцию g(t) равенством

Зе Ао

Й - а - iexP g(t) = { t, te (-а,а]

Зе Ао а + f е(а,1].

Простая проверка показывает, что g{t) - монотонная непрерывно дифференцируемая функция на отрезке [—1,1]. Положим А = а+ 3(1 — £:)/Ло- Функция g(t) взаимно однозначно отображает отрезок [—1,1] в отрезок [—А, А]. Вначале построим кусочно-равномерные разбиения Дг отрезка [—А, А].

Положим ц = тг-1 + (А — а)/т (г = т + 1,., 2т).

Получили, таким образом, разбиение отрезка [О, А]. На отрезке [—А, 0] разбиение Дг определим точками г2т, г2т+1,. го = 0 симметричным образом. Наконец, положим

Точки ti и дают интересующее нас разбиение А отрезка

Пусть 5(А, 2,1) - пространство параболических сплайнов дефекта 1 на разбиении А. Приближенное решение задачи будем искать в конечномерном подпространстве Е = Е(е,т) непрерывных функций и = и{Ь) Е 5(А, 2,1) и удовлетворяющих краевым условиям. Так определяется пробное подпространство. Тестовое подпространство Р = т) определяется равенством Р = ЬеЕ.

То =0, Ti = а/т,., тт — а,

U = g Н7») (г =-2m,.,2т).

-1,1].

Метод Галеркина состоит в отыскании такого элемента ит £ Ет, что для любого vm £ Fm

L£um,vm) = (f,vm) или же

Leum - L£u£,vm) = О, где и£ - точное решение исходной задачи, (и, v) - скалярное произведение в Ь2[—1,1]. Отсюда получаем, что Leum = Pef, где Р£ - ортогональный в Ь2 проектор на F. Следовательно, ит - Щ Цоо^Ц LJ1 Wl^lJ Pef - f ||oo<

C(l+ || Pe Ik-O || / - / Hoc, где / - наилучшее приближение / в Fm. Используя аппроксима-ционные свойства пространств сплайнов, (см. приложение 2), получаем, что || / — / ||оо< СтГ2, откуда

II ит - щ ||оо< Ст-2( 1+ || Р£ Ц^^), и доказательство оценки погрешности 0(т~2) сводится к доказательству оценок Ре ||loo->boo< Си где С, С\ не зависят от £, т.

Пусть Fi, • • •, F4m+i - некоторый базис в F и Ai, • • •, A4TO+i -биортогональный к нему в Ь2 базис, (т.е. (Ai,Fj) = S¡j, S¡j -символ Кронекера). Тогда ортопроектор Р£ может быть представлен в виде

4m+l

Peí = £ г=1 откуда

4т+1

II Pef IUoo[í.,í.+1]< е i(/1 I || аг- IU^.í.+j] • (0.22) г=1

Поэтому, если

Ш\<СН\/2 Ц/Ц«, || Л, ||Мм,+1]< С

1 + |г

1/2'

0.23) то

II р./ Иы«.+,1< с Е (Л1/2(1 +1»' - <|) г=1

-2 и оценка нормы проектора сводится к оценке последней суммы, которая в силу свойств разбиения оценивается величиной порядка 0(1).

В пространстве Р удается построить базис, для которого первая оценка (0.23) легко доказывается. Если теперь искать функции в виде Л,- = а^!, то вектор коэффициентов а = {с^} совпадает с г-м столбцом матрицы Г-1, где Г - псевдоразреженная матрица со степенным убыванием элементов от главной диагонали. Далее, используя результаты главы 1, легко доказать, что матрица Г-1 обладает теми же свойствами, что и Г, из чего легко получается вторая оценка (0.23).

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

Сформулируем теперь основные результаты глав 3-5.

В главе 3 на отрезке [—1,1] рассматривается задача

-1) = • • • = а;*(1) = ж*+1(1) = . = хп{1) = 0. (0.25)

Ьх = ех — А(£)х =

0.24)

Здесь х = (ж1,. >хп)т G Rn, A(t) и d(t) - гладкие матрица и вектор-функция класса С3[—1,1], е - малый положительный параметр.

Будем предполагать, что при всех t G [—1,1] собственные значения Л¿(¿) (г = 1,2,., п) матрицы A(t) различны и удовлетворяют неравенствам

Al (г) < Л2(f) < < Лk(t) < О < A*+i(i) < • • • < A„(f).

Тогда существует такое положительное Ло, что

Ai(i)|> А0 (t = l,2,.,n).

Если через bi(t) (г = 1,2., гг) обозначить собственные векторы матрицы A(t), отвечающие собственным значениям А¿(£), а через B(t) - матрицу со столбцами 6i(i),., bn(t), то матрица B(t) приводит A(t) к диагональному виду, т.е.

B~l{t)A{t)B(t) = ^{AiW, • • •, AB(i)}.

Представим B(t) в блочном виде s=(Bu Bl!), ^21 В22 ) где В22 - квадратные матрицы к-го порядка и (п — к)-го порядка соответственно. Предположим, что detBu(-l)detBii(l)detB22(-l)detB22(l) ф 0.

Как показано в [22], краевая задача (0.24)-(0.25) при всех малых г имеет единственное решение х.

Из асимптотического разложения решения задачи (0.24)-(0.25), построенного в [22], что существуют такие числа £"о > 0 и С > 0, что при всех е Е (0, £о] точное решение хе краевой задачи (0.24)-(0.25) и производные (г' = 1,2,3) удовлетворяют оценкам

М^Р))]

0.26)

В качестве разбиения отрезка [—1,выберем описанное выше разбиение А.

Прежде, чем сформулировать галеркинскую задачу, введем еще одно обозначение. Пусть / = (/ъ/2г'•?/«) и д = {9\-,9ьш'' -,9п) ~ элементы пространства (1/2[—1,1])п, т.е. Е ¿2[—1,1 ],рг € ¿2[— 1,1] для любого г = 1,2, • • •, п. Тогда их скалярное произведение определим по формуле и,д) = £ 1\ ътт. i= 1 1

Метод Галеркина приближенного решения задачи (0.24)-(0.25) состоит в отыскании такой и(£) Е Е, что для любой Е Е

Ьщу) = (0.27)

Теорема 8.1. Найдутся такие числа ео, то Е А", 7 > 0,С > 0, что при всех £ Е (0,£о],^ > ^о : £|1п£| < 7/т задача (0.27) имеет единственное решение и(Ь), причем и{1) - хе(г) \\с< С/т*.

Отметим, что в статье Макарова В.Л. и ГУминского В.В. [42] для сингулярно возмущенных систем уравнений второго порядка построены экспоненциально подогнанные схемы произвольного порядка. Однако их численная реализация требует знания жордановой структуры и базиса матрицы системы в каждой точке расчетной сетки. Для систем высоких порядков

О,

1 + £ ехр

Ао(*-1) ехр получение такой информации требует большого объема вычислений.

В главе 4 рассматриваются следующие краевые задачи

Leu = -£2и" + р(х, и) = 0, м(-1) = м(1) = 0, (0.28)

Меи = -£2Av + q{z,v) = 0,v|r = 0,z £ П С R2. (0.29)

Предполагается, что р(х, и) и д(х, и) - достаточно гладкие по совокупности аргументов функции, причем

Ри(х,и) >р20 > 0,qv(z,v) >pl > 0, (0.30) а уравнения р(х,и) = 0 и q(z,v) = 0 имеют решения щ(х) и vq(z), определенные и непрерывные при х £ [—1,1], 2 £ В случае задачи (0.29) Ü - ограниченная односвязная область в Л2, Г = dQ, - достаточно гладкая замкнутая кривая.

Через Со (О) обозначим множество функций и £ C(Q) : м|г = 0. Через || ||i будем обозначать норму в пространстве последовательностей ¿1, а через || ||р - норму в Lp(tt),p = 2,оо.

Пусть p(z,T) - расстояние от z до Г,ае = 1 — 2/pqs\ ln(e^) Пусть = {z £ Q : p(z,T) < 1 — = Q\ Область Лд будем называть центральной зоной, a - зоной пограничного слоя.- Предлоложим , что параметр е столь мал, что отрезки внутренней нормали к Г не пересекаются в

Из результатов [51] вытекает, что при сделанных предположениях задачи (0.28) и (0.29) имеют при малых е > 0 изолированные решения ие и v£, причем справедливы оценки (0 < i < 2) С(1 + г-г'[ехр(р0(^ - 1)/е) + ехр(р0(-х - 1)/е)]),' ж £[-1,1], fewi < С{1 + £~{ exp(-po/ep(z,T))), &(,)| < C,z £ От, и V

- — («1, агг), И = + € Од, где г - направление нормали к Г, проходящей через точку ф -координата вдоль кривой Г, т.е. длина дуги Г, отсчитываемая от некоторой фиксированной точки Г.

Дискретизация и постановки галеркинских задач. Вначале определим схему м,к.э. в одномерном случае. Разбиение отрезка [-1,1] - 1 = Х-2т < Х-2т+1 < ' ■ ■ < т = 1 Определим точно также, как в §14 главы 4. Пусть к = 1/га. Будем предполагать, что е\ 1п(е)| < Ск. Пробные галеркинские пространства в случае п = 1 определим точно так же, как и в главе 3, т.е.

Е = Е(е, Н) = {и € С[-1,1] : и(х) = + х € [ж*, £¿+1], i = -2 га, -2 га + 1, • • •, 2га; и(-1) = г/(1) = 0}.

М.к.э. для задачи (0.28) состоит в отыскании такой функции ит Е Е, что для любой и) £ Е

2(и'т,<ш') + (р(х,ит),т) = 0, (0.31) где скалярное произведение понимается в смысле ^(О),^ =

-1Д]

Перейдем к постановке задачи в двумерном случае. Вначале определим разбиение области О на конечные элементы. Из каждой точки линии Г проведем луч в направлении внутренней нормали к Г. На каждом из лучей отложим отрезок длины 2/рое\ 1п(ег) | = 1 — ае и разобьем его в точности так же, как разбивали отрезок [ае, 1] при дискретизации одномерной задачи. Линии, являющиеся геометрическим местом узлов, равноудаленных от Г обозначим через 7= га,га + 1,---,2га) (рис. 14.1).

Разобьем контур Г на дуги длины О* (К) и из точек деления проведем лучи ^ в направлении внутренней нормали к Г.

В результате область разобьется линиями 7* и Ц на конечные элементы каждый из которых является криволинейным четырехугольником.

Оставшуюся часть О, - область Од каким-нибудь образом разобьем на конечные элементы являющиеся треугольниками, сторонами которых будут отрезки прямых, либо дуги кривой 7„г. Будем предполагать, что разбиение Од квазиравномерно с параметром /г, т.е. тезш{ = 0*(1г2),сИатш{ = 0*(Ь).

Перейдем к определению пробных галеркинских пространств. Функции пробного пространства Е = Е(е, Н) определим, как функции из Со (О), удовлетворяющие следующим условиям. Они линейны на каждом из отрезков нормали к Г, заключенном между линиями 7* и 7^+1, и линейны на каждом из участков линии заключенном между лучами и относительно переменной к, = где фь] - отображение, переводящее каждую точку данного отрезка в ее проекцию вдоль нормали к Г, выходящей из этой точки, на хорду хь являющуюся звеном ломаной, вписанной в Г. На элементах С Од они линейны как функции 2, если все стороны - отрезки прямых, и линейны вдоль каждого из отрезков, соединяющих вершину и>{, не принадлежащую 7т, с любой точкой участка 7т, если этот участок является третьей стороной и>{.

Соответствующие рисунки приведены в главе 4.

Замечание 11/.4. Размерность Е равна числу узлов конеч-ноэлементной сетки.

Тем самым пространство Е определено. Метод Галеркина для задачи (0.29) состоит в отыскании такой функции ут £ Е, что для любой £ Е е2(У*;т, V«;) + (ф, О, ш) = 0, (0.32) где скалярное произведение понимается в смысле 1/2(0).

Основным результатом главы 4 является следующее утверждение.

Теорема 1Ц.1. Найдутся такие числа £о > 0,Ло > 0,70 > О,С >0, что для любых £ Е (0,£о]»Л Е (0, До] • е|1п(е)| < 70Л, что для любых е Е (0,£о]? к £ (0, Ло] : е\ 1п(е)| < 70Л, существуют единственные решения ит(х) задачи (0.31) и ьт(г) задачи (0.32), для которых справедливы оценки

II ит - ие ||с< СЛ2, || ут - ^ ||с< СЛ2, где || ||с - норма в С (О,).

Доказательство теоремы \ЦЛ, как и в предыдущей главе сводится к доказательству ограниченности соответствующего га-леркинского проектора.

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

Рассмотрим задачи ди + Ь£и = 0, и(х, 0) = «о(ж), и(-1) = и(1) = 0, ио(-1) = ио(1) = о,яе[-1,1],* е[о,т], (о.зз) ди + М£у = 0,у(г,0) = у0^),У\т = 0, о|г = О,* Е О С Е [0,Т]. (0.34)

Здесь Ьеи = -£2д2и/дх2+р(х,и),Меу = -£2Дг> + д(,г,?;) - операторы (0.28) и (0.29); р(х,и),д(х1и),щ(х),Ьо(х) - достаточно гладкие функции, причем для р, д выполнены условия главы 4, а уравнения р(х,ц) = = 0 имеют решения «°(ж), г;0(г), определенные и непрерывные при х Е [—1,1], г Е П. Как и в главе 4, предполагается, что О - ограниченная область с гладкой границей Г.

С помощью асимптотических методов [51], устанавливается, что при малых £ > 0 задачи (0.33) и (0.34) имеют изолированные решения ие = ие{х,£) и г>£ = имеющих экспоненциальный погранслой в окрестности границы.

Метод конечных элементов для задачи (0.33)((0.34)) состоит в отыскании такой функции ит(х, ¿)(г>го(-г, ¿)), непрерывно дифференцируемой по что при каждом £ £ [0,^1 имеет место ит(х^) Е Е1(ут(г^) Е Е2), причем для любой ют(х) Е Е1{уит(г) Е Е2) соответственно дИул ч 9 / ^Иул \ / / \ \ дГ' + 5 ^~дх ' + ит'' = '1 > '

0.35) ит(х, 0),гит) = (щ(х), ют), и>т) + £2(Уиш, + ьт),шт) = 0, * > 0;

0.36) ига(г,0),гиго) = (1;0(г),и;т), , ) - скалярное произведение в Ь2[—1,1] или Ь2(&).

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

Теорема /9.1. Найдутся такие числа £о > 0, /¿о > 0, С > 0,7о > 0, что для любых е Е (0,£о]>^ € (0,/^о] : £|1п(е)| < 7о/г существуют единственные решения ит(х,Ь),ут(г^) задач (0.35),(0.36), для которых справедливы оценки вир || ит - ие ||оо<^2, вир || Ьт - У£ ||оо<№2. *€[о ,т] <€[0,т]

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

Линейные задачи. Как и в главе 4 рассмотрим вспомогательные линейные задачи. Пусть р(х,и) = р(х,е) — /(ж),г;) = q(z,£) — где функции р(х,е) и <7(2, г) удовлетворяют условиям (0.30). Точные решения соответствующих задач (0.33) и (0.34) обозначим через й{х) и Запишем соответствующие галеркинские задачи в виде ди Р£{ит,и)т) = (/,адго), t > 0, (ит(х, 0),гит) = (и0(х),шт), (0.37) ди гит) 4- Ее(ут, гит) = (д, гит)^ > 0, (ит(г,0),г/;т) = (г;о(ж),гут), (0.38) где Ее(и,ъи) = £2(ди/дх,дш/дх) + (р(х,£)и,ги),Пе(ь,т) =

Теорема Найдутся такие числа £о > 0,/¿о > 0,7о >

0, С 0, что для любых £ Е (0,£о]>^ £ (0, /^о] : 5;

7о/г существуют единственные решения йго(ж,£),г)т(;г,£) задач (0.37),(0.38), причем при каждом Ь Е [0, Т] справедливы оценки «ш - ||оо< С{ ш| II и - йе ||оо + т| II и - Цоо), иЕЬ 1 и£Ь1 ОТ дЪ «т - ье |и< С( т|г || - г), ^ + || г; - Ц«,), (0.39) где С не зависит от £.

Доказательство этой теоремы сводится к изучению дискретных функций Грина и доказательству ограниченности семейства ортопроекторов на пространства Е. Ограниченность ор-топроекторов сводится к изучению матриц, обратных к матрицам Грама, которые, в свою очередь, изучаются методам теории ПРМ.

Дискретная функция Грина. Дискретную функцию Грина для задач (0.37) и (0.38) введем аналогично [110] ,ч.5. Вначале определим вспомогательные операторы в Е. Пусть L£)h : Е\ E\,Mejh : Е2 Е2 - такие операторы, что для любого wi G Е\ имеет место (Le^u,wi) = Fe(u,w\) и для любого w2 6 Е2 выполняется (L£,hv,w2) = D£(v,w2).

Определим при каждом у £ (—1,1) (г/ G Q - в двумерном случае) дискретную ¿-функцию Sy(x)(6y(z)) как элемент пространства Е\(Е2) такой, что для любой и £ E\(v £ Е2) : (5у(х),и(х)) =

Определение 20.1. Дискретной функцией Грина G£th{t, х, s) (H£ih(t, z, s)) задачи (0.37)((0.38)) будем называть функцию, определенную при t Е [0,T],x,s Е [—1,1] (z,s Е fl) и при каждом фиксированном s являющуюся по переменным i, х (i, z) решением задачи + L£,hG£,h = 0,i > 0; Ge>ft(0,s,e) = *,(«), (0.40) или соответственно

4- M£jhH£)h = 0,i > 0; H£!h(0,z,s) = 8z(s), (0.41)

Введем обозначения. Через Р и Q обозначим ортогональные в Ь2 проекторы на Е\ и Е2 соответственно, а через Р\ и Q\ -галеркинские проекторы для форм F£ и De из (0.37) и (0.38) (см.

§19).

Лемма 20.1. Дискретные функции Грина для задач (0.37) и (0.38) существуют, единственны и для решений этих задач справедливы представления

Г1 um(t,x) = JiG£ih(t,x,s)(Puo)(s)ds+ /0*{/Д Ge,h(t - г, X, 5)/(r, s)ds}dr, (0.42)

Vm\

1а #е,л(* - г, 8)д{т, 8)<18}<1т. (0.43)

Лемма 20.2. Для решений линейных задач п. 23.3 й£ и щ справедливы оценки sup || um - и£ ||оо< te[o,T] dü dü ( sup || Pi(w0) - Рщ Hoc + sup || —i - P-¡- Цоо X ¿e[o,T] te[Q,T] dt dt A x sup / \G£th(t,x,s)\ds + sup || Pjue - ue Ц«,, (0.44) sup || Vm - V£ ||oo< ( sup || Qi(vq) - Qvо lloo + í€[0,t] íg[0,r]

И dve dv£ SUP - Q^r oo x o ,r\ ot dt x sup [ \HSth(t,z,s)\ds+ sup || Qive - v£ Ц«, . (0.45) te[o,r¡,z£üJíl te[o,T]

Лемма 2<Э.З. Предположим, что имеют место оценки

P\\l^<C,\\Q\\l^l„<C, (0.46) л sup / \G£íh(t,x,s)\ds <С, te[o,T],x€[- i,i] 1 sup í\\H£yh(t,x,s)\ds<C. (0.47)

GtO.Tl.xGfi-7-1

Тогда справедливы оценки (0.39).

Таким образом, для доказательства теоремы 20.2 достаточно установить оценки (0.46),(0.47).

Для доказательства оценок (0.46) применяются методы ПРМ. В §21 изучаются матрицы Грама сужений базисных функций пространств Е на подобласть, содержащую зону пограничного слоя. Эти матрицы являются трехдиагональными в

I ^ V»«■' ■ '

М -¿¡Л"'.",. одномерном случае и диагонально разреженными в двумерном случае. На основе результатов главы 1 выводятся оценки элементов обратных матриц. На основе этих оценок получаются оценки дискретных ¿-функций и биортогональных базисов в подобластях. После этого оценки (0.46) норм ортопроекторов получаются из их представления через биортогональные базисы (п. 21.4).

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

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

Результаты, изложенные в диссертации, опубликованы в работах автора [115]-[13¥].

1. Андреев В.Б. О сходимости модифицированной монотонной схемы Самарского для сингулярно возмущенного уравнения // Журн. вычисл. матем. и матем. физики. - 1998. - Т. 38. -N8.-0. 1266-1278.

2. Андреев В.Б., Коптева Н.В. О равномерной по малому параметру сходимости монотонных трехточечных разностных схем // Дифференциальные уравнения. 1998. - Т. 34. - N 7. - С. 921-928.

3. Артемьев В.К., Булеев Н.И. О сходимости явной схемы неполной факторизации при решении двумерных уравнений диффузии // Вопросы атомной науки и техники. Сер. физики и техника ядерных реакторов. 1983. - Вып. 5(34). - С. 19-25.

4. Багаев Б.М.,Шайдуров В.В. Вариационно-разностное решение уравнения с малым параметром // в сб. "Дифференц. и интегро-дифференц. уравнения", Вып. 1. Новосибирск. 1977. С. 89-99.

5. Багаев Б.М. Использование асимаптотических разложений для задач с малым параметром // Асимптотич. и комбинатор. анализ. Красноярск. - 1979. - С. 5-15.

6. Багаев Б.М. Вариационно-разностное решение уравнения с малым параметром при старшей производной // Матем. модели и вычисл. методы мех. сплошн. среды. Красноярск, 1979. - 152-157.

7. Багаев Б.М. Метод Галеркина для обыкновенных дифференциальных уравнений с малым параметром // Числ. методы мех. сплош. среды. 1979. - Т. 10. - N 1. - С. 5-16.

8. Багаев Б.М. Вариационно-разностный метод решения эллиптических уравнений с малым параметром при старших производных. Дис. канд. физ.-мат. наук, Новосибирск. 1982.

9. Баскаков А.Г. О спектральных свойствах некоторых классов линейных операторов // Функ. анал. и его прил. 1995. -Т. 29. Т 2. - С. 62-64.

10. Бахвалов Н.С. К оптимизации методов решения задач при наличии пограничного слоя // Журн. вычисл. матем. и ма-тем. физики. 1969. Т.9. N4. С.841-859.

11. Бахвалов Н.С.,Орехов М.Ю. О быстрых способах решения уравнения Пуассона // Журн. вычисл. матем. и матем. физики. 1982. Т.22. N 6. С.1386-1392.

12. Беклемишев Д. В. Дополнительные главы линейной алгебры. М.: Наука, 1983.

13. Берг Й.,Лефстрем Й. Интерполяционные пространства. М.: Мир. 1980.

14. Блехер П.М. Оценки функции Грина разностных операторов в произвольных областях и их приложения. Препринт ИПМ. им . М.В. Келдыша АН СССР N 167 за 1981 г. М.: ИПМ им. М.В.Келдыша АН СССР. 1982.

15. Боглаев И. П. Вариационно-разностная схема для краевой задачи с малым параметром при старшей производной // Журн. вычисл. матем. и матем. физики. 1981. Т.21. N 4. С.887-896.

16. Боглаев И. П. Численные методы решения краевых задач для систем дифференциальных уравнений с малым параметром при старших производных// Журн. вычисл. матем. и матем. физики. 1981. Т.21. N 4. С.887-896.

17. Боглаев И. П. Численный метод' решения квазилинейного эллиптитческого уравнения с малым параметром при старших производных // Журн. вычисл. матем. и матем. физики. 1988. Т.28. N 4. С.492-502.

18. Боглаев И. П. Численное решение квазилинейного параболического уравнения с погранслоем // Журн. вычисл. матем. и матем. физики. 1990. Т.ЗО. N 5. С.716-726.

19. Бор К.де Практическое руководство по сплайнам. М.: Радио и связь, 1985.

20. Булеев Н.И. Пространственная модель турбулентного обмена. М.: Наука, 1989.

21. Гинкин В. П. О влиянии релаксации на сходимостьсхемы Ь,-факторизации при решении двумерных разностных уравнений типа диффузии // Вопросы атомной науки и техники. Сер. физика и техника ядерных реакторов. 1980. - Вып. 4(13). - С. 111-114.

22. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. -М.: Наука. 1984.

23. Годунов С.К.,Рябенький B.C. Разностные схемы. М.: Наука, 1977.

24. Дулан Э., Миллер Дж., Шилдерс У. Равномерные численные методы для задач с пограничным слоем. М.: Ми, 1983.

25. Емельянов К. В. Применение одномерных оптимальных сеток к решению двумерных задач с сингулярным возмущением // Журн. вычисл. матем. и матем. физики. 1998. - Т. 38. - N 3. - С. 425-436.

26. Еремин А.Ю.,Колотилини Л.Ю. Об одном семействе двухуровневых переобуславливаний типа неполной блочной факторизации. М. 1985. - Препринт ОВМ АН СССР. N 108.

27. Егоров Ю.В.,Шубин М.И. Итоги науки и техники. Современные проблемы математики. Фундаментальные направления. 1988. Т. 30.

28. Завьялов Ю.С.,Квасов Б.И.,Мирошниченко В.Л. Методы сплайн-функций. М.: Наука, 1980.

29. Задорин А.И. О существовании и единственности решения некоторых разностных задач для квазилинейного обыкновенного дифференциального уравнения с малым параметром //Численные методы мех. сплош. среды. 1984. - Т. 15. - N 1. - С. 33-44.

30. Задорин А.И. Численное решение краевой задачи для системы уравнений с малым параметром //Журн. вычисл. матем. и матем. физики. 1998. - Т. 38. - N 8. - С. 1255-1265.

31. Ильин A.M. Итоги науки и техники. Современные проблемы математики. Фундаментальные направления. 1988. Т. 34. С. 175-213.

32. Ильин A.M. Разностная схема для дифференциального уравнения с малым параметром при старшей производной // Мат. заметки. -1969. Т. 6. вып. 2. С. 237-248.

33. Ильин В. П. Методы неполной факторизации для решения алгебраических систем. М.: Наука, 1995.

34. Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука, 1985.

35. Ильин В. П. О скорости сходимости итераций неявных методов неполной факторизации // Журн. вычисл. матем. и матем. физики. Т. 33. - N 3. - С. 3-11.

36. Капорин И.Е. О предобуславливании метода сопряженных градиентов при решении дискретных аналогов дифференциальных задач // Дифференц. уравнения. 1990. - Т7 26. - N 7. - С. 1225-1236.

37. Колмогоров А.Н.,Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1983.

38. Лисейкин В.Д.,Петренко В.Е. Адаптивно-инвариантный метод численного решения задач с пограничными и внутренними слоями. Новосибирск. ВЦ СО АН СССР. 258 С.

39. Ломов С.А. Введение в общую теорию сингулярных возмущений. М.: Наука, 1981.

40. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. М.: Наука, 1965.

41. Миллер Дж.,Риордан Е. Метод конечных элементов для двухточечных краевых задач с сингулярными возмущениями // Числ. методы механ. сплошной среды. Новосибирск: ИТПМ АН СССР. 1983. Т. 14. N 2. С.142-154.

42. Писсанецки С. Технология разреженных матриц. М.: Мир. 1988.

43. Савин И. А. О равномерной по малому параметру точности модифицированной схемы Самарского для сингулярно возмущенного уравнения // Дифференциальные уравнения. 1997. - N 7. - С. 963-966.

44. Самарский A.A., Николаев E.H. Методы решения сеточных уравнений. М.: Наука, 1978.

45. Сандер С.А. Об одной оценке для трехдиагональных матриц // Сиб. мат. журн. 1990. - Т. 31. - N 5. - С. 171-173.

46. Соболев В.И., Люстерник Л.А. Элементы функцилналь-ного анализа. М.: Нака, 1965.

47. Съярле Ф. Метод конечных элементов для эллиптических задач. М.: Мир. 1980.

48. Треногин В.А. Развитие и приложения асимптотического метода Люстерника-Вишика // Успехи мат. наук. 1970. Т. 25 N4. С. 123-156.

49. Треногин В.А. Об асимптотике решения почти линейных параболических уравнений с параболическим погранслоем // Успехи мат. наук. 1961. Т. 16 выпуск 1(97). С. 163-170.

50. Шишкин Г. И. Разностная схема для решения эллиптического уравнения с малым параметром в области с криволинейной границей // Журн. вычисл. матем. и матем. физики. 1978. Т.18. N 6. С.1466-1475.

51. Шишкин Г. И. Разностная схема на неравномерной сетке для дифференциального уравнения с малым параметром при старшей производной // Журн. вычисл. матем. и матем. физики. 1983. Т.23. N 3. С. 609-619.

52. Шишкин Г. И. Аппроксимация решений сингулярно возмущенных краевых задач с параболическим погранслоем // Журн. вычисл. матем. и матем. физики. 1989. - Т. - 29.- N 7. С. - 963-978.

53. Шишкин Г. И. Аппроксимация решений сингулярно возмущенных краевых с угловым пограничным слоем // Журн. вычисл. матем. и матем. физики. 1987. - Т. - 27. - N 9. - С.- 1360-1374.

54. Шишкин Г. И. Сеточная аппроксимация метода аддитивного выделения особенностей для сингулярно возмущенного уравнения параболического типа // Журн. вычисл. матем. и матем. физики. 1994. - Т. - 34. - N 5. - С. - 720-738.

55. Шишкин Г. И. Сеточные аппроксимации сингулярно возмущенных эллиптических и параболических уравнений. Екатеринбург, 1992.

56. Шубин М.А. Псевдоразностные операторы и их обращение // Докл. АН СССР. 1984. - Т. 276. - N 3. - С. 567-570.

57. Шубин М.А. Псевдоразностные операторы и их функция Грина // Изв. АН СССР. Сер. мат. - 1985. - Т. 49. - N 3. -С. 652-671.

58. Эстербю О., Златев 3. Прямые методы для разреженных матриц. М.: Мир, 1983.

59. Asher U.,Christiansen J.,Russel R. A collocation solver for mixed order system of boundary value problems // Math. Com-put. 1979. V.33. No.146. P.659-679.

60. Asher U., Weiss R. Collocation for singular perturbation problems I: first order system with constant coefficient // SIAM J. Numer. Anal.- June 1983. V.20. No.3. P.537-557.

61. Asher U., Weiss R. Collocation for singular perturbation problems II: linear first order system without turning point // Math. Comput.1984. V.43. No. 167. P.157-187.

62. Axelsson U. Iterative solution methods. Cambridge. University Press. - 1996.

63. Axelsson 0. Incomplete block matrix factorization methods. The ultimate answer? //J. Comput. and Appl. Math. 1985. -V. 12/13. - P. 3-18.

64. Axelsson 0.,Brinkemper S.,Il'in V.P. On some versions incomplete block matrix factorization iterative method. Nijmegen: Catholic Univ., 1983.

65. Axelsson 0. A general incomplete block matrix factorization methods. The ultimate answer? // Linear Algebra and its Applications 1986. - V. 74. - P. 179-190.

66. Beauwens R. Trois lemmes: Scientific Report. Univ. Libre de Bruxelles, 1990.

67. Beauwens R., WlmetR. Conditionig analusis of positive definite matrices approximate block factorization // Comput. Appl. Math. 1989. - V. 26. - P. 257-259.

68. Boor C.de. On local linear functionals wich vanish at all B-splines but one/ in "Theory of Approximation with Application", A.G.Law,B.N.Sahney eds.,Academic Press.New York,1976, P. 120-145.

69. Boor C.de. A bound on the Loo-norm of ¿^-approximation by splines in terms of a global mesh ratio // Math. Comput. 1976. - V. 30. - P. 687-694.

70. Chan T.F. Fourier analusis of related incomplete factorization preconditioners // SIAM J. Sci. Statist. 12 (1992).

71. Chan T.F., Vassilevski P.S. A framework for block ILU-Factorizations using block-size reduction // Math. Comput. -V. 64. n. 209. - P. 129-156.

72. Dernko S. Inverses of band matrices and local convergence of spline projection // SIAM J. Numer. Anal. 1977. 14. N 4. P. 616-619.

73. Demko S.,Moss W.,Smith P. Decay rates for inverses of band matrices // Math. Comput., 43 (1984), P. 491-499

74. Demko S. On bounding || A 1 Hoc for banded A // Math. Corn-put. -1979. Vol. 33. - N 148. - P. 1283-1288.

75. Douglas J.,Dupont T., Wahlbin L. The stability in Lq of the L2-projection into finite element function spaces // Numer. Math. 1975. V. 23. No. 3. P. 193-197

76. Eijkhout V., Polman B. Decay rates of banded M-matrices that are near Toeplitz matrices // Linear Algebra Appl. 109 (1988). - P. 247-277.

77. Flaherty J.E.,Mathon W. Collocation methods for singularly perturbed boundary value problems.- Boundary and Inter. Lauers Comput. and Asympt. Meth. Proc. BAIL. I. Conf. Dublin, 1980. P.77-92.

78. Flaherty J.E.,0'Malley R.E. Numerical methods for stiff systems of two-point boundary value problems // SIAM J. Sci. Stat. Comput. 5(1984). P. 865-886.

79. Flaherty J.E.,Aiffa M.,Adjerid S. High-order finite element methods for singular perturbed elliptic and parabolic problems // Rensselaer Polytechnic Institute. Troy. - New York. -121803590.

80. Gartland Jr. Uniform high-order difference schemes for a singularly perturbed two-point boundary value problem // Math. Comput. 1987. - V. 48. - P. 551-564.

81. Gartland Jr. Graded mesh difference schemes for a model singularly perturbed boundary value problem // Math. Comput. -1988. V. 51. - P. 631-657.

82. Gartland Jr. An analusis of a uniformly convergent finite-difference finite element scheme for a model singular perturbation boundary value problem // Math. Comput. 1988. - V. 51.- P. 111-123.

83. Groen P.P.N.de A finite element with a large mesh-width for a stiff two-point boundary value problem //J. Comput. and Appl. Math. 1981. - V. 7. - N 1. - P. 3-15.

84. Groen P.P.N, de, Hemker P. W. Error bound for exponentially fitted problems // Numer. Analys. Singular perturbation Problems. New York. - Acad. Press. - 1979. - P.217-249.

85. Herceg D. Numerical solution of some diskrete analogues of boundary value problemUniv. u Novom Sadu Zb. Rad. Prirod. Mat. Fak. Ser. Mat. 24.2 (1994) 187-196.

86. Kershaw D. Inequalites on the elements of the inverse of certain tridiagonal matricx // Math. Comput. 1970. - V. 24. P. 155158.

87. Kusnetsov Y. New alghorithms for approximate realization of implicit difference schemes // Sovjet. J. Numer. Anal. Math. Modelling. 3 (1988). - P. 99-114.

88. Manteuffel T.A. An incomplete factorization technique for positive definite linear systems // Math. Comput. 1980. - V. 34. -N 150. - P. 473-497.

89. Mejernic J.A., Van der Vorst H.A. An iterative mrthods of linear systems of which coefficients matrix is a symmetric M-matrix // Math. Comput. 1977. V. 31. - P. - 148-162.

90. Meurant G. A review on the inverse of symmetric tridiagonal and block tridiagonal matrices // SIAM J. Matrix Anal. Appl.- V. 13. N 3. - P. 707-728.

91. Concus P., Golub G., Meurant G. Block preconditioning for the conjugate gradient methods // SIAM J. Sci. Statist. Comput. -6 (1985). P. 220-252.

92. Natterer F. Uniform convergence of Galerkin method for splines on highly nonuniform mesh // Math. Comput. 1977. V. 31. P. 457-468.

93. Nitsche J.A. Loo-converence of finite element approximation. Proceedingsof the Symposium on the Mathematical aspects of the finite element methods, Rome, 1975, Lecture notes in Mathematics, 606 (1977). P.261-274.

94. Notay Y. Conditioning analysis of modified block incomplete factorizations //Lin. Alg. Appl. 154-156. P. 711-722.

95. Ringhover C. On collocation schemes for quasilinear singularly perturbed boundary value problems // SIAM J. Numer. Anal. 1984. V.21. No.5. P. 864-882.

96. Surla K.,Herceg D. Exponential spline difference scheme for singular perturbation problem // Spline Numer. Anal. Conf. Int. Semin. ISAM 89, Weisig, April 24-28.1989. Berlin. 1989. P. 171180.

97. Surla K. On numerical solving singularly perturbed boundary value problems by spline in tension // Univ. u Novom Sadu. Zb. Rad. Prir. Math. Fak. Ser. Math. -24. - 2(1994) P. 175-186

98. Schatz A.H.,Wahlbin L.B. On the finite element method for singularly wo and one dimensions // Math, comput. 1983. 40. No. 161. P. 47-89.

99. Schatz A.H.,Wahlbin L.B. Interior maximum norm estimates for finite element methods // Math, comput. 1977. 31. No. 138. P. 414-442.

100. Scymchak W.,Babushka I. Adaptivity and error estimates for the finite element method applied to convection-diffusion problems // SI AM. J. Numer Anal. 1984. - V.21. - N 5. - P. 910-954.

101. Scott R. Optimal L°° estimates for the finite element method on irregular meshes // Math. Comput. 1976. V. 30. N 136. P. 681-697.

102. Stynes M.,Riordan E. A finite element method for a singularly perturbed boundary value problem // Numer. Math. 1986. V. 50. P. 1-15.

103. Stynes M.,Riordan E. A uniformly accurace finite elements method for a singularly perturbed boundary value problem // Math. Comput. 1986. - V. 47. - P. 555-570.

104. Stynes M.,Riordan E. Ll and L°° uniform convergence of a difference scheme for a semilinear singular perturbation problem 11 Numer. Math. 1987. V. 80. No. 5. P. 519-531.

105. Stynes M.,Riordan E. Uniformly convergent difference schemes for singularly perturbed parabolic diffusion-convection problems without turning points// Numer. Math. 1989. V. 55. P. 521-544.

106. Stynes M.,Riordan E. An analusis of a superconvergence result for a singularly perturbed boundary value problem // Math. Comput. 1986. - V. 46. P. 81-92.

107. Sun G., Stynes M. An almost fourth order uniformly convergent diference scheme for a semilinear singularly perturbedreaction-diffusion problem // Numer. Math. 1995. V. 70. P. 487500.

108. Thomee V. Galerkin finite element methods for parabolic problems. Lect. Notes in Math. Vol. 1054. Berlin-New-York, 1984.

109. Vassilevski P.S. On some ways of approximating inverses of banded matrices in connection with deriving preconditioners based on incomplete block factorizations // 1990. Computing. 43. - P. 277-296.

110. Vassilevski P.S. Algorithms for construction of preconditioners based on incomplete block-factorizations // Internat. J. Numer. Methods. Engrg. 27 (1989). - 609-622.

111. Vulanovic R. On numerical sution of seilinear singular perturbation problems by using the Hermite scheme. Univ. u Novom Sadu. Zb. Rad. Prir. Math. Fak. Ser. Math. -23. - 2(1993) P. 363-379.

112. Zlatev Z. Computational methods for general sparse matrices. Dordrecht, Boston, London: Kluger Acad. Pub. 1991.

113. Блатов И.А.,Стрыгин В.В. Сходимость метода Галер-кина для нелинейной двухточечной сингулярно возмущенной краевой задачи в пространстве Са,Ь]Журн. вычисл. матем. и матем. физики. 1985. Т.25. N 7. С.1001-1008.

114. Блатов И.А. Сходимость в равномерной норме метода Га-леркина для нелинейной сингулярно возмущенной краевой задачи // Журн. вычисл. матем. и матем. физики. 1986. Т. 26. N 8. С. 1175-1188.

115. Блатов И. А.,Стрыгин B.B. Сходимость метода сплайн-коллокации на оптимальных сетках для сингулярно возмущенных краевых задач // Дифференциальные уравнения. 1988. Т.24. N 11. С. 1977-1987.

116. Блатов И.А., Стрыгин В.В. Метод сплайн-коллокации на адаптивных сетках для сингулярно возмущенных краевых задач // Докл. Акад. Наук СССР. 1989. Т.304. N 4. С. 785788.

117. Блатов И.А.,Стрыгин В.В. Сходимость метода сплайн-коллокации для сингулярно возмущенных краевых задач на локально равномерных сетках // Дифференциальные уравнения. 1990. Т.26. N 7. С.1191-1197.

118. Блатов И.А. О проекционном методе для сингулярно возмущенных краевых задач // Журн. вычисл. матем. и матем. физики. 1990. Т. 30. N 7. С. 1031-1044.

119. Блатов И.А. О методе конечных элементов Галеркина для эллиптических квазилинейных сингулярно возмущенных краевых задач.I // Дифференциальные уравнения. 1992. Т. 28. N 7. С. 1168-1177.

120. Блатов И.А. О методе конечных элементов Галеркина для эллиптических квазилинейных сингулярно возмущенных краевых задач.II // Дифференциальные уравнения. 1992. Т. 28. N 10. С. 1799-1810.

121. Блатов И.А. Об оценках элементов обратных матриц и о модификациях метода матричной прогонки // Сибирский мат. журнал. 1992. Т. 33. N 2. С. 10-21.

122. Блатов И.А.,Стрыгин B.B. Метод коллокации четвертого порядка точности для сингулярно возмущенных краевых задач // Сибирский мат. журнал. 1993. Т. 34. N 1. С. 16-31.

123. Блатов И.А.,Тертерян A.A. Об оценках элементов обратных матриц и методах неполной блочной факторизации на основе матричной прогонки // Журн. вычисл. матем и матем. физики. 1992. - Т. 32. - N 11. - С. 1683-1696.

124. Блатов И.А.,Стрыгин В.В. О неулучшаемых по порядку оценках в методе конечных элементов Галеркина для сингулярно возмущенных краевых задач // Доклады АН РАН. 1993. Т. 328. N 4. С.424-426.

125. Блатов И.А. О методах неполной факторизации для систем с разреженными матрицами // Журн. вычисл. матем. и матем. физики. 1993. Т. 33. N 7. С. 819-836.

126. Блатов И. А. О методе конечных элементов Галеркина для сингулярно возмущенных параболических начально-краевых задач. I // Дифференциальные уравнения. 1996. Т. 32, N 5. С. 661-669.

127. Блатов И. А. О методе конечных элементов Галеркина для сингулярно возмущенных параболических начально-краевых задач. II // Дифференциальные уравнения. 1996. Т. 32. N 7. С. 912-922.-332

128. Блатов И.А. Об алгебрах операторов с псевдоразреженными матрицами и их приложениях // Сибирский мат. журнал. 1996. Т. 37. N 1. С. 36-59.

129. Блатов И. А. Об оценках LfZ-разложений разреженных матриц и их приложениях к методам неполной факторизации // Журн. вычисл. матем. и матем. физики. 1997. Т. 37. - N 3. - С. 259-276.

130. Блатов И.А.,Стрыгин В.В. Элементы теории сплайнов и метод конечных элементов для задач с погранслоем. Воронеж. Изд-во ВГУ. - 1997. 406 С.

131. Блатов И.А. О методе неполной факторизации в сочетании с быстрым преобразованием Фурье для решения разностного уравнения Пуассона в области с криволинейной границей // Сиб. журн. вычисл. математики. 1998. - Т.1. -N 3. - С. 197-216.

132. Blatov I.A.,Blatova V.V., Rozhec Yu. В., Strygin V.V. Galerkin-petrov method for strongly nonlinear singularly perturbed boundary value problems on special meshes // Appl. Num. Math. 1997. V. 25. P. 321-332.

133. Blatov I.A., Strygin V.V. On best possible order of convergence estimates in collocation methods and Galerkin method for singularly perturbed boundary value problems // Math. Comput. 1999. V. 68. N 226. P. 683-715.