Предобусловливание итерационных методов решения систем линейных алгебраических уравнений

Оглавление
Введение...................................................................5
1 Теория К-числа обусловленности 15
1.1 Основные свойства функционалов С и К......................... . . . 16
1.1.1 Определения и элементарные свойства........................... 16
1.1.2 Выпуклость и ортогональные преобразования..................... 17
1.1.3 Оценка сходимости метода сопряженных градиентов через К . . 21
1.1.4 Различия в свойствах функционалов С и К....................26
1.1.5 Применение функционалов С и К к неси м.метр изуемым матрицам 27
1.2 Свойства С и К как функций от спектра собственных значений .... 27
1.2.1 Выпуклость н экстремальные значения............................28
1.2.2 Верхняя оценка К через С...................................30
1.2.3 Связь между значениями К от разных аргументов..............32
1.3 Оценки собственных значений М через К(ІІ/)....................... 35
1.3.1 Оценки для наименьших собственных значений................... 36
1.3.2 Оценки для наибольших собственных значений................... 37
1.4 Выводы к главе 1.................................................... 39
2 Алгоритмы метода сопряженных градиентов 40
2.1 Определение и свойства пространств Крылова ..........................40
2.2 Оценка сходимости через чебышсвскис многочлены ......................41
2.3 Построение метода сопряженных градиентов (м.с.г.)................43
2.3.1 Определение итерационных параметров м.с.г......................45
2.3.2 Расчетные формулы м.с.г........................................46
2.3.3 Стандартный алгоритм метода................................49
2.1 Сходимость итераций м.с.г........................................51
2.4.1 Оценка убывания нормы невязки м.с.г. через С................. 51
2.4.2 Оценка числа итераций м.с.г. через С ........................ 52
2.4.3 Оценка числа итераций м.с.г. через К..........................53
2.5 Блочный метод сопряженных градиентов............................. 54
2.6 Построение предобусловленного м.с.г.............................. 56
2.7 Критерии качества предобусловливания.............................58
2.7.1 Обобщенная симметричная верхняя релаксация.................... 59
2.7.2 Блочная симметричная верхняя релаксация.................... 60
2
2.8 Параллельная реализация крыловских итераций............................................... 61
2.8.1 Ускорение и эффективность вычислений....................... 61
2.8.2 Масштабируемость алгоритмов................................63
2.8.3 Параллельные архитектуры и модели программирования .... 64
2.8.4 Параллельная реализация базовых процедур................... 65
2.9 Выводы к главе 2.......................................................................... 68
Приближенное и1 и-разложение , 69
3.1 Структура предобусловливапия и оценивание его качества*................................... 69
3.2 Предобусловливание м.с.г. при помощи приближенного 11т 11-разложения 70
3.3 Спектральная устойчивость приближенного ит11-разложения .................................. 71
3.4 Алгоритмы приближенною и ги-разложения.................................................... 72
3.5 Оценка заполнения треугольных множителей через параметр отсечения 73
3.5.1 Структурная устойчивость приближенного Пти-разложения . . 73
3.5.2 Оценка числа ненулевых элементов П......................... 74
3.5.3 Неулучшаемость оценки заполнения множителя и............... 75
3.6 Верхпие оценки обусловленности через параметр отсечения................................... 76
3.6.1 Простая оценка нижней границы спектра............................................... 76
3.6.2 Верхняя оценка общих затрат па итерации............................................. 77
3.7 Базовый алгоритм приближенного ити-разложевня ............................................ 78
3.$ Безотказные алгоритмы приближенного ит11-разложения....................................... 79
3.8.1 Приближенное итИ-разложение с пробными сдвигами......................................80
3.8.2 Приближенное П1 Б-разложение с пошаговой коррекцией..................................82
3.8.3 Приближенное ити-разложение с отложенным отсечением ... 82
3.18.4 Стабилизированный метод с отложенным отсечением............85
3.9 Общие затраты на итерации для методов 2-го порядка.........................................89
3.10 Оценка К-чпсла обусловленности для методов 2-го порядка................................... 89
3.11 Численный пример.......................................................................... 93
3.12 Выводы к главе 3.......................................................................... 95
Неполное обратное треугольное разложение 96
4.1 Общая ‘структура предобуслоплииании....................................................... 96
4.1.1 Предварительное масштабирование............................97
4.1.2 Предварительное переупорядочение........................... 97
4.1.3 Предобусловливание при помощи и.о.т.-факторизации.....................................98
4.2 Явное предобусловливание в алгоритме м.с.г................................................100
4.3 Выбор значений ненулевых элементов матрицы С..............................................101
4.3.1 Доказательство К-оптималыюсти нредобусловливателя..........102
4.3.2 Оценки достигаемого уменьшения К-числа обусловленности . . . 103
4.3.3 Многоуровневая структура н.о.т.-разложения...........................................105
4.4 Приближенное блочное н.о.т.-предобусловливание............................................107
4.4.1 Структура предобусловлпваннм...............................107
4.4.2 Рекурсивное описание прсдобусловливания ' . 108
3
4.4.3 Прпмер построения для трех блоков...........................109
4.4.4 Связь аддитивной формы с ы.о.т.-разложением.................111
4.4.5 Приближенное блочное н.о.т.-разложение......................115
4.5 Анализ блочного метода Якоби для модельных задач.....................118
4.6 Численные результаты для тестовой задачи.............................124
4.6.1 Тестовая матрица............................................125
4.6.2 Методика тестирования.......................................125
4.6.3 Исследование зависимости от числа блоков р .................126
4.6.4 Исследование зависимости от порога отсечения................129
4.6.5 Исследование зависимости от степени перекрытия..............132
4.7 Результаты для набора тестовых задач...............................136
4.8 Выводах к главе 4....................................................158
5 Полиномиальное предобусловливание 159
5.1 Анализ полиномиального предобусловливапия............................160
5.1.1 Структура полиномиального предобусловливапия................160
5.1.2 Построение многочленов Чебышева-наименьших квадратов . . . 162
5.1.3 Свойства многочленов Чебышева-наименьших квадратов .... 164
5.1.4 Вывод оценки для К(Л/р^-і(М)) ................................164
5.1.5 Оценка для многочленов Чебышева-напменыпих квадратов . . . 167
5.2 Оценка сходимости м.с.г. через верхнюю границу спектра и
изолированные наименьшие собственные значения........................167
5.3 Полиномиальное предобусловливание м.с.г..............................169
5.3.1 Предобусловливание, использующее полиномы Чебышева..........169
5.3.2 Алгоритм полиномиального предобусловливапия.................170
5.3.3 Сочетание полиномиального предобусловливапия с предварительным.....................................................170
5.4 Оценка погрешности м.с.г. для полиномиального предобусловливапия . 172
5.4.1 Полиномиальное предобусловливание и изолированные
наименьшие собственные значения ...............................172
5.4.2 Сравнение полиномиальных нредобусловливаний на модельной
задаче.......................................................175
5.4.3 Оценка евклидовой нормы погрешности через 11-норму невязки . 176
5.5 Численные результаты для тестовых задач .............................178
5.5.1 Набор тестовых матриц.......................................179
5.5.2 Методика тестирования....................................... 180
5.5.3 Результаты расчетов тестовых задач..........................181
5.6 Выводы к главе 5.................................................................188
6 Предобусловливание малоранговой модификацией 189
6.1 Структура предобусловливапия.........................................189
6.2 Анализ К-чпсла обусловленности.......................................190
6.2.1 Доказательство К-онтимальности..............................190
4
6.2.2 Случай <т = 1 и выбор матрицы С.............................192
6.3 Оценки спектральной обусловленности.................................193
6.3.1 Оценки границ спектра прсдобусловленной матрицы.............194
6.3.2 Оценки спектрального числа обусловленности..................196
6.4 Связь с мпошуровневыми и многосеточными методами ................197
6.5 Анализ предобусловливапия для модельных задач...............197
6.6 Расчеты тестовых задач..............................................199
6.7 Выводы к главе 6....................................................199
Заключение.............................................................200
Список сокращений.......................................................201
Литература..............................................................202
5
Введение
Исторический обзор. Преимущества итерационных методов при численном решении систем линейных уравнений с. разреженными матрицами специального вида были замечены достаточно давно, по крайнем мере с середины ’20-го века. Тогда же был отмечен единственный их недостаток: медленная сходимость итерационных приближений к искомому решению, причем как раз для тех задач, которые наиболее актуальны.
Двумя существенными шагами в развитии итерационных алгоритмов решения систем линейных уравнений Ах = Ь с симметричной положительно определенной матрицей А стали
(а) разработка Хестенсом и Штифелем в 1952 году [103) метода сопряженных градиентов, который, в свою очередь, тесно связан с алгоритмом тридиагопализации, опубликованным Ланцошем в 1950 году [136];
(б) разработка техники предобусловливалия для итерационных методов (эквивалентной предварительному линейному преобразованию матрицы системы, например, А —> А/, где М — НА, и преобразование задается симметричной положительно определенной матрицсй-предобусловлнвателем Я), сформулированной в связи с ускорением метода сопряженных градиентов в работах Даниэля 1967 года [69], Г. И. Марчука п 10. Л. Кузнецова 1968 года [26], О. Аксельсона [39] и др.
Как указывает, в частности, фундаментальная обзорная работа [94], теория прецобусловлепного метода сопряженных градиентов в основном развивалась вокруг ОЦСНОК 0171)10ШСНИЛ сряниц СПСКШрй Атлх (А/)/Ап»п(Л0 (т.иаз. спектрального числа обусловленности) нредобусловленной матрицы М, что порождало соответствующие критерии качества предобусловливания.
Это означало, что не только в теорию, но и в построение методов решения систем линейных уравнений в той или иной мере вовлекалась проблема, еще более сложная по сравнению с исходной, а именно, обобщенная задача на собственные значения Ао = ЛЯ-1 и. Причем эту задачу требуется решить не в прямой, а в обратной постановке, выбирая параметры предобусловливающей матрицы Н из условия минимума о тношения крайних собственных значений матрицы М = НА.
Естественно, что по мере усложнения актуальных прикладных задач, такая ситуация вылилась в несоответствие между реально применяемыми алгоритмами, доказавшими свою практическую эффективность (однако зачастую не имеющими достаточно строгого обоснования), и теми конструкциями, которые хотя и доиускали получение аналитических верхних границ числа итераций для некоторых модельных
6
проблем (г.е. имели теоретическое обоснование), однако, будучи реализованы в виде алгоритма, оказывались пригодны лишь для довольно ограниченного круга реальных задач.
Кроме того, укажем на целесообразность учета дополнительных свойств спектра предобу слов ленных матриц, характеризующих неравномерность распределения собственных значений внутри границ спектра. Такие свойства спектра, очевидно, не связаны непосредственно со спектральным числом обусловленности. Для метода сопряженных градиентов важной является не только малость отношения границ спектра, по и, в той же ме]>е, разреженность спектра собственных значений с левого конца и его уплотнение с правого конца. Наиболее ярким примером в этой связи является проблема оптимизации полиномиальных предобу словливанин, см., напр., [108], где обсуждался тот факт, что точное минимизация спектрального числа обусловленности может приводить к результату, весьма далекому от иаилучшего.
Таким образом, в идеале следовало бы найти некоторый матричный функционал, который
• характеризовал бы близость матрицы к единичной, при этом отдавая предпочтение тем случаям, когда дополнительно улучшается сходимость метода сопряженных градиентов;
• обладая достаточно простой структурой, допускал бы безусловную оптимизацию при параметризациях матрицы, типичных для иредобусловливаний (желательно, в виде аналитического решения);
• в качестве оптимального решения должен получаться ирсдобусловлмватель, обладающий разумными свойствами (такими. как симметрия, невырожденность, достаточно хорошее спектральное число обусловленности предобу словленной матрицы).
Отметим первые попытки разработки нестандартных подходов к
иредобусловливаишо метода сопряженных градиентов, см., напр., [4, б], а также более поздний обзор Т.Хукле [105], которые опирались на критерий качества предобусловливания, выбранный в виде евклидова расстояния || 1п — М\\г в от предобу слов леи ной матрицы М = НА до единичной /п* Однако, такому подходу присущи серьезные ограничения, делающие его непрактичным во многих важных ситуациях, см. напр., обсуждение в работе [122]. Прежде всего, если матрица А симметрична, а для матрицы И фиксирована структура разреженности и ищутся ее элементы, то в результате такой оптимизации получается несимметричная матрица //, невырожденность которой, как правило, ничем не гарантируется. Так, в [122] указывалось, что для того, чтобы быть уверенным хотя бы в невырожденности Л/, необходимо потребовать [|/и — Л7||р < 1, а это является чрезмерно жестким условием, непригодным для практического использования. Соответственно, не существует никакой содержательной оценки числа итераций, которая бы зависела только от величины ||/п — Л/Ц^. Следовательно, минимизация указанного евклидова расстояния (до значения, большего единицы) является не более чем эвристическим
7
приемом, за которым не стоит никаких теоретических гарантий. Заметим, что в работе [122] содержится законченная теория сходимости метода обобщенных минимальных невязок в терминах двух величии: во-первых, расстояния ||/п — М||^, и, во-вторых, дополнительного параметра, характеризующего отделение спектра М от нуля. Однако, в контексте разреженных матриц большого размера, не представляется реалистичной постановка задачи о минимизации ||/„ — M\\f при условии, например, ограниченности ||ЛУ_1||.
Таким образом, критерий малости евклидова расстояния )|/п — НА\\? сам по себе плохо приспособлен к случаю оптимизации предобусловлшзашш симметричных положительно определенных матриц. Поэтому в [132] (вслед за работами автора [11, 12, 110], см. также [17], где исследовалось улучшение спектрального числа обусловленности) был рассмотрен случай факторизованного предобусловливателя \ ' Н — GTG, где G - нижняя треугольная матрица. К настоящему времени этот
класс FSAI-предобусловливателей (от англ. Factorized Sparse Approximate Inverse) достаточно широко распространен в зарубежных работах; соответствующие методы используется, в основном, в высокопараллельных вычислениях. В отличие от оптимизации К-числа обусловленности, лежащей в основе работ автора, в [132, 16, 66] построение лредобусловливания снова использует минимизацию евклидова расстояния, но теперь уже в виде ||/n — GL\\p, где А — LL представляет собой точное симметрично-треугольное разложение исходной матрицы А (англ. Cholcsky factorization). Для точного вычисления такой матрицы G оказывается необходимым знать все диагональные элементы L, которые, естественно, на практике недоступны (в противном случае, можно было бы решить заданную систему быстро и точно, не прибегая к итерационным методам). Поэтому недостающая информация извлекается из естественного требования равенства единице всех диагональных элементов симметрично предобусловленной матрицы GAG1. Получаемое в итоге предобусловливание оказывается, таким образом, субоптимальиым с точки зрения минимума ||/„ — GL\\f, однако, как показано в [16], в точности совпадает с К-оптимальным выбором матрицы (7, выносимым на защиту в настоящей диссертации. Более того, в той же работе [16] построен пример параметризованной матрицы 2-го порядка, показывающий, что К-оптлмизация может давать сколь угодно лучшие результаты, чем безусловная оптимизация евклидовой нормы || 7n — GL\\f} (в смысле уменьшения спектрального числа обусловленности). В связи с этим, во вводной части упомянутой работы ее авторы справедливо указывают на “потенциальную опасность построения FSAI-предобусловливателей на основе безусловной минимизации фробениусовой нормы”.
Таким образом, практическая потребность в конструктивных методах построения эффективных иредобусловливаний закономерно приводит к необходимости разработки альтернативных подходов к оценке качества предобусловлнваний метода сопряженных градиентов.
11а этом же пути целесообразен поиск и разработка методов предобусловливапия, ориентированных на естественные достаточно широкие классы разреженных матриц независимо от частностей (например, связанных со спецификой значений ненулевых
S
элементов и структуры разреженности), отвечающих тем или иным свойствах! математических моделей и физических объектов, стоящих за этими матрицами. Таким образом, ставится важнейшая практическая задача о разработке не только эффективных, »о и достаточно универсальных алгоритмов решения больших разреженных систем линейных уравнений, приближающихся к способности работать в режиме ”черного ящика”.
Цель работы. В качестве целей работы можно указать решение следующих проблем:
1. Определение подходящего альтернативного числа обусловленности, способного учитывать не столько отношение крайних собственных значений, сколько интегральные свойства спектра, и не связанного, таким образом, с отдельно взятыми собственными значениями предобусловлспной матрицы.
2. Построение неулучшаемых оценок числа итераций метода сопряженных градиентов в терминах этого числа обусловленности.
3. Выявление известных н построение новых црсдобусловливаний, которые являются оптимальными (или близки к таковым) с точки зрения нового числа обусловленности. ,
4. Теоретическая проверка вновь построенных предобусловливаиий с точки зрения классической теории (основанной на уменьшении отношения границ спектра предобусловле 11ной матрицы).
о. Алгоритмизация новых предобусловливаиий (в том числе, перспективных в отношении эффективной реализации на высокопараллельных компьютерах) и практическая проверка их вычислительной пригодности на представительных тестовых задачах.
Актуальность темы. Решение линейных систем с разреженными (в том числе симметричными положительно определенными) матрицами большой размерности часто возникает как повторяющаяся (и при этом доминирующая по трудоемкости) подзадача в алгоритмах, реализующих самые разнообразные прикладные расчеты. Примером могут служить задачи математической физики, задачи построения сеток, задачи оптимизации и многие другие.
Довольно стандартной является ситуация, когда требуется решить серию линейных задач, соответствующих вычислению ньютоновских направлений для итерационного решения нелинейной задачи. При этом свойства возникающих матриц ' Якоби не всегда вполне предсказуемы, и требования к надежности алгоритмов решения линейных систем в этом случае возрастают.
С другой стороны, быстрое развитие вычислительной техники предъявляет особые требования к алгоритмам решения; так, под оптимизацией алгоритма, помимо привычного сокращения числа операций н объема памяти, может подразумеваться
9
и выявление или построение структуры вычислений, облегчающей эффективную работу компьютеров с иерархической системой памяти и/или параллельной организацией вычислений.
Таким образом, в условиях взаимообусловленного роста вычислительных мощностей и усложнения постановок прикладных задач, общая проблема построения ” паи лучшего77 метода решения больших разреженных систем линейных уравнений все еще остается далекой от окончательного решения (даже если ограничиться задачами с симметричной положительно определенной матрицей). Заметим, что с увеличением размеров задач для многих важных классов разреженных матриц (возникающих, например, при дискретизации пространственных объектов) методы “точной77 треугольной факторизации [82, 177} неизбежно начинают требовать нелинейно растущего объема памяти [139], что и является причиной постоянного интереса к усовершенствованию итерационных методов.
Кроме того, для итерационного решения сложных нелинейных задач могут представлять интерес методы предобусловливания (т.е., построения приближенных обратных матриц) как таковые. Например, эффективность применения методов нелинейной минимизации типа сопряженных градиентов (см., наир., [163]) к большим разреженным задачам на собственные значения [171, 192, 187, 81] или к нелинейным задачам наименьших квадратов [19, 112] сильно улучшается при использовании подходящих предобусловливателей (хотя сколько-нибудь точного решения какой-либо последовательности с.л.а.у. при этом не происходит).
Следует признать, что несмотря на усилия многочисленных исследователей на протяжении десятков лег, теоретические основы такого важного направления, как построение эффективных предобусловливаиий для естественных классов матриц, остаются недостаточными для практического решения ряда важных задач. Это и обусловило актуальность темы диссертации.
Научная новизна. В диссертации разработан новый критерий эффективности продобусловливапия для метода сопряженных градиентов. Критерий является конструктивным, что позволило получить новые варианты известных алгоритмов и разработать новые, еще более эффективные в определенных условиях. К основным новым результатам можно отнести следующие:
1. Предложен и исследован новый критерий эффективности предобусловливания, сформулированный в терминах минимизации матричного функционала К(Л/) = (п”1 trace М)п/del М, определенного для любой симметризуемой п х п-матрицы М и пропорционального отношению п-й степени следа матрицы к ее определителю. Этот функционал мы называем далее К-чнслом обусловленности (термин был введен О.Аксельсоном и использован в его известной монографии [41], где обширно цитированы некоторые результаты настоящей диссертации.)
2. В терминах К-числа обусловленности получена новая оценка числа итераций метода сопряженных градиентов, неул у читаемая в том же смысле, что н
10
известная оценка через спектральное число обусловленности. Кроме того, новая оценка сходимости устанавливает сверхлинеиную скорость сходимости, в отличие от известной оценки, которая указывает только на линейную сходимость итераций метода сопряженных градиентов.
3. С точки зрения оптимизации К-числа обусловленности проанализированы наиболее эффективные из известных приближенных треугольных разложений, выявлена их принадлежность к новому классу треугольных разложений 2-го порядка, а также осуществлен дополнительный анализ указанных предобусловливаннй с точки зрения спектрального числа обусловленности.
4. С точки зрения оптимизации. К-числа обусловленности проанализированы наиболее эффективные из известных явных предобусловливаннй, фактически являющихся приближенными обратными треугольными разложениями. Найдена блочно-неявная ([юрма представления таких предобусловливатслей, позволяющая избавиться от чрезмерных вычислительных затрат исходного разложения без потери параллелизуемости. Определен способ включения обычных приближенных треугольных разложений в блочную структуру метода, и доказана общая эффективность такого подхода. Анализ полученной конструкции с точки зрения стандартных подходов при том же уровне общности не представляется ВОЗМОЖНЫМ.
5. С точки зрения оптимизации К-числа обусловленности проаналнзироваиы полиномиальные предобусловливания метода сопряженных градиентов, получены теоретические объяснения того известного факта, что точная оптимизация таких предобусловливаннй по критерию минимума спектрального числа обусловленности, как правило, приводит к недостаточно эффективным вычислительным алгоритмам.
6. С точки зрения оптимизации К-числа обусловленности проанализированы наиболее эффективные из известных высокопараллельных ирсдобусловливаний, связанных с малоранговой коррекцией. Построены новые формулы таких предобусловливаннй, а также выполнен их дополнительный анализ с точки зрения спектрального числа обусловленности. Показана совместимость предобусловливания посредством малоранговой модификации с другими пр едобу словл и ва ни ям и, что позволяет существенно повышать эффективность
, известных методов.
Теоретическая и практическая ценность. Теоретическая ценность диссертации заключается в разработке повой теории сходимости метода сопряженных градиентов, а также непосредственно связанного с ней общего подхода к оптимизации предобусловливаннй. Кроме того, получен ряд важных частных теоретических результатов, отвечающих конкретным структурам п редобусловливающнх матриц.
11
Практическая ценность полученных результатов заключается в построении конкретных алгоритмов решения систем с разреженными положительно определенными матрицами общего вида, обладающих повышенной надежностью, высокой производительностью на последовательных компьютерах, а также хорошей параллелизуемостью.
В частности, разработаны эффективные параллелизусмые методы решения систем линейных .уравнений с симметричными положительно определенными ма I рицами, учитывающие разреженность и способные работать с плохо обусловленными матрицами, пригодные для использования во многих промышленных приложениях.
Положения, выносимые на защиту:
1. Новая теория сходимости метода сопряженных градиентов, основанная на использовании К-числа обусловленности (п. 1.1.3). и связанный с ней подход к построению предобусловллваций, основанный на минимизации К-числа обусловленное'! II (п. 2.6)
2. Теория предобусловливания симметричных положительно определенных матриц посредством приближенных треугольных разложений 2-го порядка, с обоснованием как через К-число обусловленности (п. 3.10), так и в терминах спектрального числа обусловленности (п. 3.8.4).
3. Теория предобусловливания симметричных положительно определенных
матриц посредством неполных обратных треугольных разложении (п. 4.3). с использованием блочности (п. 4.4.4), а также внутриблочнон аппроксимации, с обоснованием в терминах К-числа обусловленности (п. 4.4.5).
4. Теоретическое объяснение несоответствия точной оптимизации спектрального числа обусловленности и получаемого качества полиномиального
предобусловливания, полученное на основе анализа К-числа обусловленности; отыскание параметризации чебышевского многочлена, обеспечивающего близкое к оптимальному качество предобусловливания (глава 5).
5. Теория предобусловливания симметричных положительно определенных
матриц посредством К-оптималыюй малоранговой модификации, с обоснованием как через К-чпсло обусловленности (п. 6.2.1), так и в терминах спектрального числа обусловленности (п. 6.3.2).
Обоснованность и достоверность результатов. Представленные в диссертации результаты имеют строгое математическое обоснование. С другой стороны, достоверность эффективности построенных предобу слоили ваш ш
основывается на прямом сравнении результатов расчетов с результатами, полученными ири использовании других предобусловливаний: точечного метода Якоби, приближенного блочного метода Якоби. Кроме того, для ряда задач из
12
коллекции университета Флориды, использовавшихся другими авторами для проверки разработанных ими алгоритмов*, были получены, существенно лучшие результаты.
Апробация работы. Результаты работы докладывались и обсуждались на 7 всероссийских и 16 международных конференциях, в частности: международной-конференции “РаСТ99” (Санкт-Петербург, . Россия, 1999 г.), -всемирном 16-ом Конгрессе “IMACS 2000”. но научным вычислениям, прикладной математике и моделированию (Лозанна, Швейцария, 2000), Голландско-российском симпозиуме NWO (МГУ, Москва, июнь. 2000),. Симпозиуме N-VVO (Амстердам-Пиймеген, Голландия, ноябрь- 2000), Втором. Международном научно-практическом-; Семинаре и Всероссийской молодежной школе “Высокопроизводительные параллельные ' вычисления- на кластерных системах” (Нижний Новгород, Россия,. 2002), -международной конференции “Parallel CFD 2003” (Москва, 2003), Международной конференция “VIII Забабахинскпе научные чтения” (РФЯЦ-ВНИИТФ, Спсжииск, Россия, 2005), международной конференции по- вычислительной геометрии, генерации сеток и научным вычислениям “NUMGR1D2008:: (ВЦ РАН, Москва, 200$), международной конференции по-вычислительной геометрии, генерации сеток и высокопроизводительным вычислениям “NUMGR1D201CT (ВЦ РАН, Москва, 2010), международной конференции но прикладной математике и информатике, . посвященной 100-летию со дня рождения академика Л.А.Дородницына (ВЦ РАН, Москва, 2010), международной конференции по матричным методам в математике и приложениях “МММА-2011” (ИВМ РАН; Москва, 2011), научно-исследовательских семинарах Вычислительного центра РАИ и Института вычислительной математики РЛІІ (Москва, 2009-2011), рабочих семинарах ExxonMobil Upstrean: Research Co. (Хьюстон, США, 2006-2010).
Публикации.. ' г
По теме диссертации опубликовано 32 работы, из них 5 в отечественных ' рецензированных изданиях, рекомендованных ВАК, 9‘ в международных рецензируемых изданиях из рекомендованного■ ВАК списка “Web of Science: Science Citation Index Expanded” (база по естественным, наукам), 2 в других международных рецензируемых изданиях, 1 в российском рецензируемом издании,
4 в'трудах всероссийских конференций, 7 в трудах международных конференций, 4 публикации в других научных изданиях. 1
В совместных работах [115, 20, 119, 121, 22, 23, 2-1] И.Н.Конынину принадлежит разработка-и реализация параллельного алгоритма метода и описшше численных экспериментов, а автору диссертации - разработка и теоретическое исследование предобусловливання.
Благодарности. Автор выражает благодарность А. К). Еремину, привлекшему . автора к работе по теме диссертации, JI. Ю.. Колотилиной за внимание к работе и ценные обсуждения, профессору О. Аксельсону за интерес к работе и всестороннюю ее поддержку на протяжении многих лет, И. Н. Коньпшну за длительное сотрудничество в области численного тестирования и параллельной
13
реализации разработанных автором методов, В. А. Гар а иже за полезные обсуждения, замечания и поддержку работы. В. 10. Правильнпкову за сотрудничество в области практической реализации и внедрения разработок по теме диссертации, академику РАН 10. Г. Евтушенко и член-корреспонденту РАН Е. Е. Тыртышникову за внимание к работе и ее поддержку. Особенную ценность имели обсуждения материала главы 4 с О. К). Милюковой и Ю. В. Василевским, касающиеся оценок вычислительной эффективности предложенных автором методов.
Структура и объем работы. Диссертационная работа состоит из введения. 6 глав, заключения и списка литературы. Объем работы 216 страниц. Список литературы включает в себя 192 наименования.
14
Глава 1
Теория К-числа обусловленности
В этой главе для симметричной положительно определенной матрицы М вводится и изучается новое число обусловленности К(А/) = (п“1 traceA/)/det А/, далее называемое К-числом обусловленности. Также проводится его детальное сопоставление со стандартным спектральным числом обусловленности С(М) = Am»x(M)/Amin(jV/). Напоминаются или выводятся вновь важные свойства этих чисел обусловленности, прежде всего связанные с оценками сходимости метода сопряженных градиентов.
Как излагаемая в настоящей диссертации новая теория сходимости метода сопряженных градиентов, так и отвечающие ей методы предобусловливания [11, 12, 15, 110, 111) основаны на использовании матричного функционала
ЩМ) = (п-1 trace М)п/ det М (1.1)
= 1/,det (trace il-/'V/) ’ определяемого для любой симметризусмой п х n-матрицы М. (Под симмстрнзуемостью подразумевается подобие симметричной положительно определенной матрице.)
Отметим, что в самых ранних статьях [11, 12] использовалась величина/У — К1/”; впоследствии определение К в виде (1.1) было предложено О.Аксельеоном, также отметившим пригодность этого функционала в качестве числа обусловленности, в монографии [41].
Такой подход вполне правомерен, и ниже будет показано, что стандартное (спектральное) число обусловленности симметризуемой матрицы
С(М) = Атах
(A/)/Amin(iVf) (1.2)
действительно имеет много общего с К-числом обусловленности (хотя и скорее в качественном, чем в количественном смысле).
С практической точки зрения, паша основная задача сводится к следующему: требуется найти подходящую количественную меру близости произвольной
15
симметричной положительно определенной матрицы М к скалярной матрице а/, где а > 0. Подобная характеризация матрицы имеет первостепенную важность при анализе иредобусловленного метода сопряженных градиентов, применяемого к численному решению систем линейных алгебраических уравнений большою размера.
Можно также отметить, что в точности те же самые функционалы С(М) и К(М)^п используются в математической статистике для определения так называемых критериев сферичности Хартли и Бартлетта соответственно, где в качестве М фигурирует выборочная матрица ковариаций. В указанных статистических тестах, гипотеза о сферичности нормального многомерного распределения (эквивалентная .'V/ = т/) принимается или отвергается в зависимости от близости указанных критериев С(М) или К(Л/)^П к единице сверху. (Более детальное изложение можно найти в монографии [145], гл. 13, цц.А.1-Л.2.)
Функционал К(М) применялся также в исследовании методов квазпныотоновского типа для решения систем нелинейных алгебраических уравнений [72).
Некоторые результаты, относящиеся к сравнению функционалов С и К (а также функционала пйп„^0 х1 11 геометрической интерпретации можно
найти в статье [102], см. также [101].
1.1 Основные свойства функционалов С и К
Заметим, что поскольку спектр матрицы не изменяется при преобразовании подобия, для обоих чисел обусловленности безразлично, является ли матрица М симметричной и положительно определенной или всею лишь симметризусмой. Типичным случаем здесь является ситуация, когда
М = НА
где как Н. так п А являются симметричными положительно определенными матрицами (например, А - матрица решаемой системы уравнений, а Я -
приближенная обратная, используемая как нредобусловливающан матрица).
1.1.1 Определения и элементарные свойства
Ыижс будем предполагать, что матрица М симметрична и положительно определена. Из этого, в частности, следует, что
Ащ!п Ш) = 1ШП ПГЛ/н/пТи, ЛтлхШ) = ШйХ ЧГ Ми/уТп. (1.3)
и
Свойстбо 1.1.1 Как С, так к К являются однородными функционалами, то есть
С(оеМ) = С(Л/), (1.4)
К (аМ) = ЩМ), (1.5)
где а > 0.
16
Доказательство. Утверждение легко следует из определений (1.2) и (1.1). О
Свойство 1.1.2 Справедливы неравенства
С(М) > 1, (1.6)
К(М) > 1, (1.7)
причем равенства в них достигаются тогда и только тогда, когда М = ті, где г > 0.
Доказательство. Утверждение легко следует из результатов следующего параграфа (см. ниже Свойство 1.2.2; более общий случай, когда матрица Л/ только симметризуема, был рассмотрен в [110]). □
Свойство 1.1.2 можно дополнить следующими количественными результатами. Свойство 1.1.3 Справедливы оценки
$?H/-“-vll = üTT (1'8)
in || / — шМ\\ < \jl — (1.9)
Доказательство. Неравенство (1.8) представляет собой хорошо известный результат, относящийся к оптимальному выбору параметра в методе простой итерации (см., папр., [28], и.З глаиы VI), в то время как (1.9) следует из (1.8) и оценки (1.16), которая будет доказана ниже. П
1.1.2 Выпуклость и ортогональные преобразования
Свойство 1.1.4 Как С, таки К являются квазивыпуклыми функционалами, т. е. для любых симметричных положительно определенных матриц М и Аг и скаляра О < а < 1 справедливы неравенства
С(аМ + (1 - а)ЛГ) < шах(С(М), С(АГ)), (1.10)
К(огЛ/ + (1 - ог)Лг) < шах(К(М), К(Д')), (1.11)
17
Доказательство. Оценка (1.10) может быть легко получена из определения (1.2) и
соотношений (1.3):
ax(qjW +/9АГ) <Anax(-'W) + ) < Д/\ СГЛ'П
А («М-ГЖ) £ аА (M)+/3Alllin(.V) 2 ■”^С(Л/),С1Л)).
Оценка (1.11) следует из (1.1) и детерминантного неравенства (см., напр., [145],
H.16.F.2.C)
det(04 + (1 - 0)В) > (det 4)*(dct B)l~\ 0 < 9 < 1,
справедливого для любых симметричных положительно определенных матриц .4 н В. Действительно, используя (1.5), получаем (здесь используется обозначение р=\-а)
К(аМ + PN) = к(— гу^-г- -(«М + 0N))
\а trac<» М + р trace .V /
= К (о п .-М + (1 -й) .п- ы)
\ trace М trace N )
= 1 /del. (0 ^_Л/ + (1-0)—дЛ
! \ trace М trace N )
< l/(det (--------— AfV det (------^Ц-дЛ1"^
“ Vtrace Л/ / Vtrace N ) )
= K(JW)*K(/V)1_*,
где
^ _ a trace M
a trace M + (31race N ’ от куда следует (1.11). □
Свойство 1.1.5 ООа подмножества всех симметричных положительно определенных матриц с vuca<uiu обусловленности, ограниченными сверху как С(*) < СтЛх или К(') < А'швк, соответственно, являются выпуклыми.
Доказательство. Непосредственно следует из предыдущего свойства. □
Свойство 1.1.6 Пусть N является произвольной невырожденной квадратной матрицей. Тогда справедливы равенства
C(NrN) = C(NNT) (1.12)
К (NTN) = К (NNT). (1.13)
Доказательство. Оцепка (1.12) хорошо известна, тогда как (1.13) непосредственно следует из равенств trace А В = trace В А и det 4В = det В А. □
18
Свойство 1.1.7 Пусть V является п х к-матрицей с ортон ормнро ванными столбцами, то есть
причем если к — п (то есть V представляет, собой ортогональную матрицу) то (1.14) и (1.15) переходят в равенства.
Доказательство. Оценка (1.14) легко следует из определения (1.3), тогда как (1.15) цри к = п может быть непосредственно получена из определения (1.1), поскольку обе функции trace и det инвариантны относительно преобразования подобия. Докажем теперь общий случай для (1.15).
Пусть U является пх(п- Аг)-матрицей с ортонормироваппыми столбцами, образующими базис ортогонального дополнения к подпространству span (К). Таким образом, квадратная матрица
trace М = trace\VTMW = trace V1 MV + trace Ul MU, det M = det 1VTMW = det VTMV det UTMU det (I - BBT) < det Vх MV dct UrMU,
VTV = lki
тогда справедливы неравенства
С(VTMV) < С(М)
(1.14)
и
К(VхЛ/К) < К(М)
(1.15)
W = V : U
является ортогональной, то есть WTW = 1п. Рассматривая матрицу
получаем
где
В = (VTMV)-lf2VT MU{UT MU)~l/2. Используя (1.7) для матрицы UTMU получаем
1.9