Метод построения блочно-малоранговой аппроксимации матрицы по её элементам

• Автор: Михалев, Александр Юрьевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 105 с. : ил.

Содержание
Введение

ь 1 Исторический обзор

1.2 Содержание работ по главам

1 Предварительные сведения

1.1 Скелетное разложение

1.2 Доминантные подматрицы

1.3 Алгоритм тахуо

1.4 Мозаичное разбиение матрицы

1.5 "Д-матрицы

1.6 Д2-матрицы

1.6.1 Матрично-векторные операции в Д2-формате
1.7 Выводы по главе
2 Прямоугольная скелетная аппроксимация
2.1 Объём прямоугольных подматриц
2.1.1 Оценка 12 нормы строк матрицы коэффициентов
2.1.2 Алгоритм максимизации 2-объёма подматрицы
2.2 Прямоугольная псевдоскелетная аппроксимация
2.3 Модифицированная скелетная аппроксимация
2.4 Вложенное скелетное разложение
2.5 Оценка точности аппроксимации вложенными базисами
2.6 Выводы по главе
3 «Мультизарядовый» метод
3.1 «Мультизарядовое» представление Д2-матрицы

3.2 «Хорошие» строки и столбцы
3.2.1 «Хорошие» наборы и своя дальняя зона
3.2.2 Вычисление «хороших» наборов
3.3 Итерационный алгоритм
3.4 Проверка количества итераций и достигаемой точности
3.4.1 Программная реализация
3.4.2 Проверка на задаче многих тел
3.4.3 Проверка на граничном интегральном уравнении
3.5 Выводы по главе
4 Численные эксперименты
4.1 Континуальная модель растворителя
4.1.1 Уравнение РСМ и его дискретизация на молекулярной поверхности
4.1.2 Решение уравнения РСМ в программе DISOLV
4.1.3 Решение уравнения РСМ при помощи мультизарядового
метода в программе MCBHSOLV
4.1.4 Численное решение уравнения РСМ
4.1.5 Сравнение с мозаично-скелетным методом
4.1.6 Выводы по разделу «Континуальная модель растворителя» .
Заключение
Литература

Введение
Актуальность темы исследования. Ряд современных математических методов решения различных физических задач требуют решения систем линейных уравнений большой размерности. Этим методам посвящено множество работ [4,65, 72, 74-83, 87-91]. Для понижения вычислительной сложности работы с возникающими большими матрицами необходимо учитывать структуру этих матриц. Учёт этой структуры может сильно ускорить решение конкретного класса задач. Одним из самых распространённых и изученным является класс разреженных матриц [22,44,47, 54,69, 84,92]. Основным показателем разреженности является количество ненулевых элементов. Этот показатель определяет как память, необходимую для хранения матрицы в памяти компьютера, так и скорость вычисления матрично-векторных произведений, одного из основополагающих элементов линейной алгебры. Кроме этого, класс разреженных матриц довольно глубоко исследован на предмет построения предобуславливателей [7-9, 27,48-50]. Это позволяет успешно применять различные итерационные методы для быстрого решения систем линейных алгебраических уравнений. Однако, разреженная структура в матрицах — не единственная структура, представление которой требует малого количества параметров. В качестве примера структурированных матриц можно назвать семисепарабельные матрицы. Наддиагональная и поддиагональ-ная части таких матриц являются частями малоранговых матриц, из чего следует существование малопараметрических представлений.
Диссертация посвящена блочно-малоранговым матрицам, а именно 71-матрицам [28,30] и "^-матрицам [11,31]. Матрицы с данной структурой возникают, например, в задачах электростатики. За счёт того, что кулоновское взаимодействие на дальних расстояних обладает достаточной гладкостью, потенциал, создаваемый двумя геометрически разделёнными группами заряженных тел (частиц) друг на друга, может быть вычислен приближенно, например, на основе

Из алгоритма тахуо1, описанного в разделе 1.3, следует, что С-норма матрицы коэффициентов не превосходит 1. Из этого ограничения получаем оценки норм строк матрицы С:
ЦС^Цх < г, \Cih < у/г.
Эти оценки являются неулучшаемыми, например, для матриц Адамара.
Возникает вопрос: можно ли увеличить количество строк матрицы А так, что сохранится равенство
А ~ С А,
а норма матрицы С станет меньше. Очевидно, С-норма этой матрицы никогда не станет меньше 1, однако, это не касается других норм.
2.1.1. Оценка 12 нормы строк матрицы коэффициентов
Введём понятие прямоугольных доминантных подматриц по аналогии с квадратными доминантными подматрицами. Пусть дана матрица А £ СЛГхг, N > г, гапкА — г, из которой выбрана подматрица А £ СКхг, К > г. Обозначим за М (А) множество всех подматриц размера К х г матрицы А, отличающихся от А ровно в 1 строке. Прямоугольной доминантной подматрицей будем называть такую подматрицу А, что её 2-объём не меньше 2-объёма любой подматрицы из множества АЛ (А).
Напомним теорему Бине-Коши [21]:
Теорема 2.1.1 (Теорема Бине-Коши). Произведение двух матриц АиВ даёт квадратную матрицу порядка т, если матрица А имеет п столбцов и т строк, а матрица В имеет п строк и т столбцов. Миноры матриц АиВ одинакового порядка, равного наименьшему из чисел пит, называются соответствующими друг другу, если они стоят в столбцах (матрицы А) и строках (матрицы В) с одинаковыми номерами. Тогда определитель матрицы АВ равен нулю, если п < т, и равен сумме попарных произведений соответствующих друг другу миноров порядка т, если п > т.
д&(АВ) = ^ <ИЛ<) «ИД),

где с1е1:(Аг) и с1е1:(Д) - соответствующие миноры.