Магистратура 2020/2021

Современные матричные вычисления

Статус: Курс по выбору (Науки о данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Кафедра технологий моделирования сложных систем

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Делицын Андрей Леонидович, Рыгаев Иван Петрович

Прогр. обучения: Науки о данных

Язык: русский

Кредиты: 6

Контактные часы: 48

Программа дисциплины

Аннотация

Методы вычислительной линейной алгебры и матричные вычисления являются базовым компонентом при решении различных задач статистического анализа, обработки изображений, предсказательного моделирования. Владение основными алгоритмами матричных вычислений необходимо в любой сфере математического моделирования. Изучение курса «Современные матричные вычисления» требует предварительных знаний в объеме первых курсов стандартной бакалаврской программы по направлению Прикладная математика и информатика или другой смежной программы.

Цель освоения дисциплины

• Овладение методами вычислительной линейной алгебры, технологией разреженных матриц, технологиями высокопроизводительных вычислений.

Планируемые результаты обучения

• Освоить техники приведения матрицы к каноническим формам и приложения канонических форм к оценкам собственных значений матриц.
• Знание основных алгоритмов упорядочения матриц и решения систем линейных уравнений с разреженными матрицами прямыми методами.
• Овладение основными современными итерационными методами решения сверхбольших систем линейных уравнений с разреженными матрицами (метод сопряженных градиентов и GMRES с предобусловливанием).
• Знание основных алгоритмов решения алгебраической проблемы собственных значений с плотными и разреженными матрицами (QR-алгоритм и методы Ланцоша).
• Знание основных технологий распараллеливания основных матричных операций.

Содержание учебной дисциплины

• Прямые методы решения систем линейных уравнений с разреженными матрицами
  Прямые методы решения систем линейных уравнений. Метод Гаусса и LR-разложение. Факторизация Холецкого симметричной положительно определенной матрицы. Уравнения с симметричной незнакоопределенной матрицей и методы их решения. Системы линейных уравнений с разреженными матрицами. Ленточный и профильный методы. Обратный алгоритм Катхил-Макки уменьшения профиля матрицы. Представление структуры разреженной матрицы в виде графа. Минимизация заполнения. Методы параллельных и вложенных сечений. Метод минимальной степени. Теплицевы матрицы.
• Канонические формы матриц
  Приведение матрицы к канонической форме. Теорема Шура. Жорданова форма матрицы. Принцип минимакса и некоторые его приложения. Сингулярные числа. SVD-разложение.
• Итерационные методы решения систем линейных уравнений с разреженными матрицами
  Метод сопряженных градиентов для систем уравнений с симметричной матрицей. Метод бисопряженных градиентов для несимметричных матриц. Сходимость метода. Системы разреженных линейных уравнений с несимметричной матрицей. GMRES. Методы предобусловливания.
• Матричные параллельные вычисления
  Биортогональный метод Ланцоша для несимметричной проблемы собственных значений. Метод Арнольди. Увеличение производительности алгоритмов линейной алгебры в блочных алгоритмах. Не-которые пакеты линейной алгебры и их оболочки (LAPACK, BLAS, IMSL, MKL). Анализ ошибок округления в прямых методах решения системы линейных уравнений.
• Алгебраическая проблема собственных значений
  Алгебраическая проблема собственных значений для симметричных плотных матриц. Приведение симметричной матрицы к трехдиагональному виду ортогональными преобразованиями. Методы Гивенса и Хаусхолдера. Теорема Штурма и метод бисекций. Алгебраическая проблема собственных значений для несимметричных плотных матриц. Приведение несимметричной матрицы к квазитреугольной форме. QR-алгоритм. Алгебраическая проблема собственных значений для разреженных матриц

Элементы контроля

• Контрольная работа
  письменная работа 60 минут
• Домашнее задание
  реализация матричных алгоритмов 360 минут
• Экзамен
  Оценка за дисциплину выставляется в соответствии с формулой оценивания от всех пройденных элементов контроля. Экзамен не проводится.

Промежуточная аттестация

• Промежуточная аттестация (4 модуль)
  0.25 * Домашнее задание + 0.25 * Контрольная работа + 0.5 * Экзамен

Список литературы

Рекомендуемая основная литература

• Квасов Б.И. - Численные методы анализа и линейной алгебры. Использование Matlab и Scilab - Издательство "Лань" - 2016 - 328с. - ISBN: 978-5-8114-2019-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/71713

Рекомендуемая дополнительная литература

• Тыртышников, Е. Е. Матричный анализ и линейная алгебра [Электронный ресурс] / Е. Е. Тыртышников. - М.: ФИЗМАТЛИТ, 2007. - 480 с. - ISBN 978-5-9221-0778-5.