Бакалавриат
2020/2021
Матричные вычисления
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
5
Контактные часы:
60
Программа дисциплины
Аннотация
Данный курс посвящен прикладным аспектам работы с матрицами и является естественным продолжением классического курса линейной алгебры, который читается на первом году обучения. В рамках курса рассматриваются как теоретические, так и практические стороны малорангового приближения матриц, решения систем линейных уравнений и задачи наименьших квадратов, а также решения задачи на собственные значения. Особое внимание уделяется использованию изученных алгоритмов в современных прикладных задачах. Часть домашних заданий предполагает программирование на языке Python.
Цель освоения дисциплины
- Знать основные матричные разложения и область их применения
- Знать основные пакеты программ линейной алгебры
- Получить навык реализации алгоритмов вычислительной линейной алгебры на языке Python
Планируемые результаты обучения
- Уметь эффективно решать линейные системы и задачу на собственные значения с большими разреженными и структурированными матрицами.
- Иметь представление о тензорных разложениях.
- Уметь оценивать сложность алгоритмов линейной алгебры.
- Знать основные алгоритмы решения задачи наименьших квадратов.
Содержание учебной дисциплины
- Некоторые понятия матричного анализаМатричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы. Матричные функции.
- Малоранговое приближение матрицСкелетное разложение матриц. Сингулярное разложение (SVD) и его основные свойства. Приближение матрицей меньшего ранга. CUR разложение. Приложения сингулярного разложения. Интерпретируемость CUR разложения и его приложения.
- Малоранговое приближение многомерных массивовКронекерово и тензорное произведения. Каноническое разложение многомерных массивов. Разложение Таккера. Higher-order SVD (HOSVD). Приложения.
- Вычислительные аспекты линейной алгебрыПредставление чисел в компьютере. Обусловленность и вычислительная устойчивость. Вычисление произведения матриц. Матрицы со специальной структурой: разреженные, тёплицевы матрицы, циркулянты, матрица Фурье. Быстрое преобразование Фурье. Пакеты программ для решения задач линейной алгебры.
- Метод наименьших квадратовQR разложение и способы его вычисления. Использование QR разложения для метода наименьших квадратов (МНК). Псевдообратная матрица. Использование SVD разложения для МНК. Линейная регрессия. L1- и L2-регуляризации.
- Прямые методы решения систем линейных уравненийТеория возмущений и число обусловленности матрицы. LU разложение, его связь с методом Гаусса. Ошибки округления и выбор ведущего элемента. Разложение Холецкого. Прямые методы решения больших разреженных систем линейных уравнений.
- Итерационные методы решения систем линейных уравненийМетод простой итерации. Метод наискорейшего спуска и его недостатки. Метод итераций Чебышева. Подпространства Крылова. Метод сопряженных градиентов. Метод обобщенных минимальных невязок (GMRES). Предобуславливание.
- Задача на собственные значенияСтепенной метод и обратная итерация. Их применения для анализа графов. Метод Ланцоша. QR алгоритм и его модификации. Методы вычисления сингулярного разложения.
Элементы контроля
- Домашние задания (x6)
- Бонусные задачи в ДЗ
- Самостоятельная работа
- Контрольная работа
- Экзамен
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э)), ДЗ –– средняя оценка за домашние задания Б –– средняя оценка за бонусные задачи в ДЗ ПР — средняя оценка за самостоятельные работы на семинарах КР –– оценка за контрольную работу (проводится в первой половине 2-го модуля) Э –– письменный экзамен
