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

Материалы лекций

Номер лекции Название Материал Презентация Ссылки
1 Примеры краевых задач, приводящих к системам уравнений PDF PDF Varga Ikramov
2 Метод сопряженных градиентов (CG) PDF PDF Капорин,Kaporin
3 Метод неполной факторизации (ILU) PDF - Saad
4 Введение в многосеточный (MG) и многоуровневый (ML) методы - - Kostler
5-6 Алгебраический многосеточный метод (AMG) PDF PDF Ruge-Stuben, Stuben, Kuznetsov
7-8 Многоуровневый метод (ML) - - Bollhoefer
9 Переупорядочивание и масштабирование систем (MPT) PDF - Sinkhorn, Kaporin, Olschowka-Neumaier
10 Метод вложенных рассечений (ND) - - Karypis, Jian-ping
11 Методы решения седловых задач (BP) PDF - Golub, Bramble-Pasciak
12 Методы решения блочных задач (CPR) PDF - Wallis
13 Методы решения нелинейных систем PDF - Armijo, Anderson, Sorensen, Martinez
14 Метод дефляций для отыскания нескольких решений нелинейной системы - - Farrell
Инструкции по практической части: PDF

Вопросы к экзамену

1. Необходимые шаги для построения дискретизации и решения задачи математической физики с начальными или краевыми условиями и особенности формируемых разреженных систем.
2. Что такое пространство Крылова? На чем основаны методы Крылова и как можно повысить скорость их сходимости.
3. Возможные проблемы в методе неполной факторизации и подходы к их решению.
4. Какие операторы требуется определить для алгебраического многосеточного метода? Какие системы позволяет решать метод? Зависимость сложности решения задачи от числа неизвестных.
5. Что такое дополнение по Шуру? Как работает многоуровневый метод неполной факторизации и его достоинства и недостатки.
6. Какие приемы можно применить для эффективного решения седловых и блочно-структурированных задач (Стокс, Био, двухфазная фильтрация).
7. Основные методы решения нелинейных задач и способы улучшения их сходимости. Возможные проблемы при решении нелинейных задач.

Примеры систем для тестов

Происхождение Свойства Матрица Правая часть Решение
Уравнение Пуассона на регулярной сетке 10x10x10 Симметричная положительно определенная A.mtx b.mtx x.mtx
Задача однофазной фильтрации с двумя скважинами, двухточечная аппроксимация потока (TPFA) Симметричная положительно определенная A.mtx b.mtx x.mtx
Задача однофазной фильтрации с двумя скважинами, дискретизация уравнений Дарси в смешанной форме с седловой точкой Симметричная квази-определенная A.mtx b.mtx x.mtx
Задача однофазной фильтрации с двумя скважинами, дискретизации меметичными конечными разностями (MFD) Симметричная A.mtx b.mtx x.mtx
Генераторы линейных систем для задачи Пуассона, Бигармонического уравнения и системы Стокса Симметричная, Симметричная, Седловая generators.zip

Отправка выполненного задания на проверку

Подача исходного файла на тестирование: пароль:

Примеры программ

Метод простой итерации (пример считывания матрицы в формате mtx):simple_iteration.cpp
Метод Гаусса-Зейделя (пример считывания матрицы в формате mtx):gauss_seidel.cpp
Пример очереди с приоритетом:priority_queue.cpp
Пример связного списка для сложения разреженных векторов:linked_list.cpp
Сложение разреженных матриц:matrix_sum.cpp
Умножение прямоугольных разреженных матриц:matrix_mult.cpp
Вычисление невязки для решения системы:resid.cpp
Проверка матрицы на симметрию, включает транспонирование матрицы:symm.cpp
Репозиторий примеров https://github.com/kirill-terekhov/mipt-solvers