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

• Автор: Капорин, Игорь Евгеньевич
• Шифр специальности: 01.01.07
• Научная степень: Докторская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 216 с. : ил.

Оглавление
Введение

1 Теория К-числа обусловленности

1.1 Основные свойства функционалов С и К

1.1.1 Определения и элементарные свойства

1.1.2 Выпуклость и ортогональные преобразования

1.1.3 Оценка сходимости метода сопряженных градиентов через К

1.1.4 Различия в свойствах функционалов С и К

1.1.5 Применение функционалов С и К к несимметризуемым матрицам

1.2 Свойства С и К как функций от спектра собственных значений

1.2.1 Выпуклость п экстремальные значения

1.2.2 Верхняя оценка К через С
1.2.3 Связь между значениями К от разных аргументов
1.3 Оценки собственных значений М через К(Л7)
1.3.1 Оценки для наименьших собственных значений
1.3.2 Оценки для наибольших собственных значений
1.4 Выводы к главе 1
2 Алгоритмы метода сопряженных градиентов
2.1 Определение и свойства пространств Крылова
2.2 Оценка сходимости через чебышевские многочлены
2.3 Построение метода сопряженных градиентов (м.с.г.)
2.3.1 Определение итерационных параметров м.с.г
2.3.2 Расчетные формулы м.с.г
2.3.3 Стандартный алгоритм метода
2.4 Сходимость итераций м.с.г
2.4.1 Оценка убывания нормы невязки м.с.г. через С
2.4.2 Оценка числа итераций м.с.г. через С
2.4.3 Оценка числа итераций м.с.г. через К
2.5 Блочный метод сопряженных градиентов
2.6 Построение предобусловленного м.с.г
2.7 Критерии качества предобусловливания
2.7.1 Обобщенная симметричная верхняя релаксация
2.7.2 Блочная симметричная верхняя релаксация

2.8 Параллельная реализация крыловских итераций
2.8.1 Ускорение и эффективность вычислений
2.8.2 Масштабируемость алгоритмов
2.8.3 Параллельные архитектуры и модели программирования
2.8.4 Параллельная реализация базовых процедур
2.9 Выводы к главе
3 Приближенное ити-разложение ,
3.1 Структура предобусловливадия и оценивание его качества'
3.2 Предобусловливание м.с.г. при помощи приближенного ит11-разложения
3.3 Спектральная устойчивость приближенного итІПразложения
3.4 Алгоритмы приближенного ити-разложения
3.5 Оценка заполнения треугольных множителей через параметр отсечения
3.5.1 Структурная устойчивость приближенного ІТтІУразложешія . .
3.5.2 Оценка числа ненулевых элементов II
3.5.3 Неулучшаемость оценки заполнения множителя £/
3.6 Верхпие оценки обусловленности через параметр отсечения
3.6.1 Простая оценка нпжней границы спектра
3.6.2 Верхняя оценка общих затрат па итерации
3.7 Базовый алгоритм приближенного ити-разложения
3.8 Безотказные алгоритмы приближенного ити-разложения
3.8.1 Приближенное ити-разложение с пробными сдвигами
З.Б.2 Приближенное 11ти-разложение с пошаговой коррекцией
3.8.3 Приближенное ити-разложение с отложенным отсечением
3.8.4 Стабилизированный метод с отложенным отсечением
3.9 Общие затраты на итерации для методов 2-го порядка
3.10 Оценка К-чпсла обусловленности для методов 2-го порядка
3.11 Численный пример
3.12 Выводы к главе
4 Неполное обратное треугольное разложение
4.1 Общая' структура предобусловливания
4.1.1 Предварительное масштабирование
4.1.2 Предварительное переупорядочение
4.1.3 Предобусловливание при помощи и.о.т.-факторизации
4.2 Явное предобусловливание в алгоритме м.с.г
4.3 Выбор значений ненулевых элементов матрицы (3
4.3.1 Доказательство К-оптимальпости предобусловливателя
4.3.2 Оценки достигаемого уменьшения К-числа обусловленности . . .
4.3.3 Многоуровневая структура н.о.т.-разложения
4.4 Приближенное блочное н.о.т.-предобусловливание
4.4.1 Структура предобусловливания
4.4.2 Рекурсивное описание предобусловливания

4.4.3 Пример построения для трех блоков
4.4.4 Связь аддитивной формы с н.о.т.-разложением
4.4.5 Приближенное блочное н.о.т.-разложение
4.5 Анализ блочного метода Якоби для модельных задач
4.6 Численные результаты для тестовой задачи
4.6.1 Тестовая матрица
4.6.2 Методика тестирования
4.6.3 Исследование зависимости от числа блоков р
4.6.4 Исследование зависимости от порога отсечения
4.6.5 Исследование зависимости от степени перекрытия
4.7 Результаты для набора тестовых задач
4.8 Выводы к главе
5 Полиномиальное предобусловливание
5.1 Анализ полиномиального предобусловливания
5.1.1 Структура полиномиального предобусловливания
5.1.2 Построение многочленов Чебышева-паимсныних квадратов . . .
5.1.3 Свойства многочленов Чебышева-наимсныних квадратов
5.1.4 Вывод оценки для K(Mp,j_i(M))
5.1.5 Оценка для многочленов Чебышева-напменьших квадратов . . .
5.2 Оценка сходимости м.с.г. через верхнюю границу спектра и
изолированные наименьшие собственные значения
5.3 Полиномиальное предобусловливание м.с.г
5.3.1 Предобусловливание, использующее полиномы Чебышева
5.3.2 Алгоритм полиномиального предобусловливания
5.3.3 Сочетание полиномиального предобусловливания с предварительным
5.4 Оценка погрешности м.с.г. для полиномиального предобусловливания .
5.4.1 Полиномиальное предобусловливание и изолированные
наименьшие собственные значения
5.4.2 Сравнение полиномиальных предобусловливаний на модельной
задаче
5.4.3 Оценка евклидовой нормы погрешности через Н-норму невязки .
5.5 Численные результаты для тестовых задач
5.5.1 Набор тестовых матриц
5.5.2 Методика тестирования
5.5.3 Результаты расчетов тестовых задач
5.6 Выводы к главе
6 Предобусловливание малоранговой модификацией
6.1 Структура предобусловливания
6.2 Анализ К-чнсла обусловленности
6.2.1 Доказательство К-оптимальности

Доказательство. Обозначая р, = ф(А;), нетрудно убедиться в том, что выполнены все предположения утверждения 3.2. В самом деле, из условия (1.41), легко следует неравенство (рк+1 — pi) + . • • + {pk+i — Рк) > 0, эквивгшентное (1.36). Далее, учитывая i/>(0) = 0, имеем
ф() = А [ ф'(Хт)<1т,

откуда, при А = А*,+1 и А = k, с учетом невозрастания ф'(-) в силу (1.42), получаем (1.37):
f^±L - [ ф'(Хк+1т)с1т < [ ф'(Хкт)<1т =
^Ч-+1 Jo Jo К

Следствие 1.2.5 Пусть функция ф удовлетворяет условиям следствия 3-4■ Тогда для любой симметричной положительно определенной матрицы М справедлива оценка
Щф(М)) < К(М). (1.44)
Доказательство. Достаточно подставить в (1-44) спектральное разложение матрицы М — VA.V1 и убедиться в том, что утверждение эквивалентно доказанному выше неравенству (1.43). □
1.3 Оценки собственных значений М через К(М)
Очевидно, задание только спектрального числа обусловленности С{М) не дает много информации о локализации остальных собственных значений А2, •. ■, A„_i матрицы М, см. ниже замечание 1.3.1.
Напротив, если известно, что К(М) не слишком велико, то задается построить достаточно нетривиальные оценки наибольших и наименьших собственных значений симметричной положительно определенной матрицы М.
Здесь и далее будем предполагать, что собственные значения матрицы М пронумерованы в неубывающем порядке,
О < Aj < ■ • • < А„,
в то время как сама матрица М нормализована условием
trace М = п. (1-45)