Бакалавриат 2020/2021

Основы матричных вычислений

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Прикладная математика и информатика)

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

Кто читает: Департамент больших данных и информационного поиска

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

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Высоцкий Лев Игоревич, Зароднюк Алёна Владимировна, Рахуба Максим Владимирович, Сушникова Дарья Алексеевна

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

Кредиты: 5

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

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

Аннотация

Данный курс посвящен прикладным аспектам работы с матрицами и является естественным продолжением классического курса линейной алгебры, который читается на первом году обучения. В рамках курса рассматриваются как теоретические, так и практические стороны малорангового приближения матриц, решения систем линейных уравнений и задачи наименьших квадратов, а также решения задачи на собственные значения. Особое внимание уделяется использованию изученных алгоритмов в современных прикладных задачах. Часть домашних заданий предполагает программирование на языке Python.

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

• Дать теоретические и практические основы матричных вычислений, познакомить с областью их применения в задачах анализа данных и научных вычислениях

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

• Знать основные матричные разложения и область их применения
• Знать основные пакеты программ линейной алгебры
• Получить навык реализации алгоритмов вычислительной линейной алгебры на языке Python
• Уметь эффективно решать линейные системы и задачи на собственные значения с большими разреженными и структурированными матрицами.

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

• Некоторые понятия матричного анализа
  Матричные нормы. Спектральный радиус. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы. Матричные функции. Ряд Неймана. Матрично-векторное дифференцирование.
• Малоранговое приближение матриц и многомерных массивов
  Скелетное разложение матриц. Сингулярное разложение (SVD) и его основные свойства. Приближение матрицей меньшего ранга. ALS (alternating least squares) и рандомизированный алгоритмы поиска малорангового приближения. CUR разложение. Приложения сингулярного разложения. Интерпретируемость CUR разложения и его приложения. Кронекерово и тензорное произведения, их свойства. Каноническое разложение многомерных массивов. Разложение Таккера. Higher-order SVD (HOSVD).
• Вычислительные аспекты линейной алгебры
  Представление чисел в компьютере. Обусловленность и вычислительная устойчивость. Вычисление произведения матриц. Матрицы со специальной структурой: разреженные, тёплицевы матрицы, циркулянты, матрица Фурье. Быстрое преобразование Фурье. Дискретная свертка и ее приложения. Пакеты программ для решения задач линейной алгебры.
• Метод наименьших квадратов
  QR разложение и способы его вычисления. Использование QR разложения для метода наименьших квадратов (МНК). Псевдообратная матрица. Использование SVD разложения для МНК. Линейная регрессия. L1- и L2-регуляризации.
• Прямые методы решения систем линейных уравнений
  Теория возмущений и число обусловленности матрицы. LU разложение, его связь с методом Гаусса. Ошибки округления и выбор ведущего элемента. Разложение Холецкого. Прямые методы решения больших разреженных систем линейных уравнений: обратный алгоритм Катхилл-Макки, вложенное рассечение, алгоритм минимальной степени.
• Итерационные методы решения систем линейных уравнений
  Метод простой итерации. Метод наискорейшего спуска и его недостатки. Метод итераций Чебышева. Подпространства Крылова. Соотношение Арнольди. Метод сопряженных градиентов, его сходимость. Метод обобщенных минимальных невязок (GMRES). Предобуславливание.
• Задача на собственные значения
  Основы теории возмущений для задачи на собственные значения. Степенной метод и обратная итерация. Их применения для анализа графов. Метод Релея-Ритца. Методы Ланцоша и Арнольди. QR алгоритм и его модификации. Методы вычисления сингулярного разложения.

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

• Домашние задания
• Письменная контрольная работа
• Письменный экзамен
  Экзамен проводится в Zoom с синхронным прокторингом.

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

• Промежуточная аттестация (3 модуль)
  Контрольная работа по темам третьего модуля. Вес указан в итоговой формуле оценивания.
• Промежуточная аттестация (4 модуль)
  Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э)), ДЗ –– средняя оценка за домашние задания Б –– средняя оценка за бонусные задачи в ДЗ ПР — средняя оценка за самостоятельные работы на семинарах КР –– оценка за контрольную работу (проводится в первой половине 4-го модуля) Э –– письменный экзамен

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

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

• Методы численного анализа : учеб. пособие для вузов, Тыртышников, Е. Е., 2007

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

• Вычислительная линейная алгебра : теория и приложения, Деммель, Дж., 2001