Матричные вычисления 20/21
Содержание
О курсе
Курс по выбору для студентов для студентов 3 и 4 курса в 1-2 модулях.
Лектор: Рахуба Максим Владимирович
Лекции проходят на Покровке по вторникам в ауд. D510 (09:30 - 10:50)
Семинарист: Высоцкий Лев Игоревич
Семинары проходят онлайн по пятницам (13:00 - 14:20) Ссылка на регулярную Zoom-конференцию: https://zoom.us/j/91934043735
Ассистент курса: Фёдоров Андрей Александрович
Домашние задания необходимо присылать на почту aafedorov_2@edu.hse.ru
Полезные ссылки
Телеграм-канал курса: https://t.me/joinchat/AAAAAFkvC-gUnDmoK-YY2w
Телеграм-чат курса: https://t.me/joinchat/AiDEvBgUTMjcfkWpD8NMWA
Anytask курса: https://anytask.org/course/706
План курса
Еженедельные тесты
На каждом семинаре (начиная с первого) будет проходить короткий тест по теме последней лекции.
Лекции
1. Основы матричного анализа Записи с лекции
Матричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы.
2. Малоранговая аппроксимация матриц Записи с лекции
Разделение переменных и скелетное разложение. Сингулярное разложение матриц. Теорема Эккарта-Янга-Мирского. Ортопроекторы. Простейший рандомизированный алгоритм поиска малорангового приближения матриц.
3. Малоранговая аппроксимация матриц 2 Записи с лекции, Слайды (метод крестовой аппроксимации)
CUR разложение матриц. Метод крестовой аппроксимации матриц. ALS (Alternating Least Square) алгоритм для матричной факторизации.
4. Малоранговая аппроксимация тензоров Записи с лекции
Кронекерово и внешнее (тензорное) произведения. Каноническое разложение и разложение Таккера. Теорема о мультилинейном ранге тензора. HOSVD алгоритм.
5. QR разложение и метод наименьших квадратов Записи с лекции
QR разложением матриц с помощью отражений Хаусхолдера и вращений Гивенса. Метод наименьших квадратов. Решение системы нормальных уравнений с помощью QR и SVD разложений. Псевдообратная матрица Мура-Пенроуза.
6. Быстрое преобразование Фурье и структурированные матрицы Записи с лекции
Матрица Фурье и быстрое преобразование Фурье. Циркулянты и дискретная теорема свертки. Теплицевы матрицы.
7. Умножение матриц. Вычислительная устойчивость. ' Записи с лекции
Сложность умножения матриц. Метод Штрассена и его связь с каноническим разложением тензоров. BLAS и связанные с ним пакеты программ. Представление чисел в памяти компьютера. Вычислительная устойчивость алгоритмов. Основные аксимомы машинной арифметики. Обусловленность задач.
8. Прямые методы решения систем линейных уравнений с плотными матрицами. ' Записи с лекции
LU разложения, его существование и единственность. Стратегии выбора ведущего элемента: частичный и полный выборы. Разложение Холецкого.
Домашние задания
Домашнее задание 1 Папка с заданием
Задание состоит из теоретических задач в pdf файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать файл с видео из папки).
Выдается: 02.09.20
Дедлайн (строгий): 17.09.20 в 21:59
Домашнее задание 2 Папка с заданием
Задание состоит из теоретических задач в pdf файле и практической задачи в Jupyter Notebook.
Выдается: 18.09.20
Дедлайн (строгий): 01.10.20 в 21:59
Домашнее задание 3 Папка с заданием
Задание состоит из теоретических задач в pdf файле и практической задачи в Jupyter Notebook.
Выдается: 02.10.20
Дедлайн (строгий): 15.10.20 в 21:59
Контрольная работа
Проведение: предварительно - вторая неделя 2-го модуля.
Экзамен
Устный экзамен в аудитории, разрешается пользоваться рукописным листком А4 при подготовке.
Итоговая оценка за курс
Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э))
ДЗ –– средняя оценка за домашние задания Б –– средняя оценка за бонусные задачи в ДЗ ПР — средняя оценка за самостоятельные работы на семинарах КР –– оценка за контрольную работу (проводится в первой половине 2-го модуля) Э –– устный экзамен
Округление арифметическое
Автоматы не предусмотрены
Литература
1) Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations 4th Edition. The Johns Hopkins University Press. Baltimore.
2) Тыртышников, Е. Е. (2007). Методы численного анализа. Академия, Москва.
3) Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra. (Vol. 50). Siam. Philadelphia.
