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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

О курсе

Курс для студентов 2 курса в 3-4 модулях.

Лектор: Рахуба Максим Владимирович


Семинаристы:

Группа Преподаватель Учебный ассистент Время начала семинара Инвайт в anytask Чат в телеграм Консультации
1 Высоцкий Лев Игоревич Иоанн Довгополый Пт, 11:10 ecpmalC tg
2 Рахуба Максим Владимирович Михаил Петров Пт, 09:30 WaheRR2 tg
3 Сушникова Дарья Алексеевна Александр Демин Пт, 11:10 ZIeqosn tg
4 Сушникова Дарья Алексеевна Влад Княжевский Пт, 09:30 yYBADOt tg
5 Медведь Никита Юрьевич Дмитрий Лишуди Вт, 11:10 6T48c6J tg  ?
6 Зароднюк Алёна Владимировна Ира Голобородько Вт, 11:10 BjKRP6u tg

Полезные ссылки

Телеграм-канал курса: t.me

Телеграм-чат курса: t.me

Таблица с оценками: docs.google.com

Материалы курса: disk.yandex.ru

Плейлист с видеозаписями: youtube.com

План курса

Лекции

  1. Основы матричного анализа (14.01.2022). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Конспект Видео (youtube) Конспект (TeX)
  2. Малоранговое приближение матриц – 1 (21.01.2022). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Конспект Видео (youtube) Конспект (TeX)
  3. Малоранговое приближение матриц – 2 (28.01.2022). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Конспект Видео (zoom.us) Видео (youtube)
  4. Малоранговое приближение матриц – 3 (04.02.2022). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Конспект Видео (zoom.us) Видео (youtube)
  5. Малоранговое приближение матриц – 4 (11.02.2022). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Конспект Видео (zoom.us) Видео (youtube)
  6. Малоранговое приближение многомерных массивов (18.02.2022). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Конспект Видео (zoom.us) Видео (youtube)
  7. Вычисление QR-разложения (25.02.2022). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Конспект Видео (zoom.us) Видео (youtube)
  8. Метод наименьших квадратов и псевдообратные матрицы (04.03.2022). Полноранговый случай. Общий случай. Регуляризация. Конспект Видео (zoom.us) Видео (youtube)
  9. FFT и структурированные матрицы (11.03.2022). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Конспект Видео (youtube)
  10. FFT и структурированные матрицы – 2 (18.03.2022). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Конспект Видео (zoom.us) Видео (youtube)
  11. 25.03.2022 лекции не было, была финальная проверочная работа.

Проверочные работы на семинарах

Каждые 1-2 недели на семинарах будет проходить короткие тесты по теме лекции и семинара с предыдущей недели. На первом семинаре пройдет пробный тест, за который не будет выставляться баллов. Подробнее о правилах проведения будет рассказано на первом семинаре.

Домашние задания

На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели.

У каждого студента есть трое суток суммарно, на которые можно продлить срок сдачи любых заданий. Чтобы использовать эту возможность, достаточно просто загрузить работу в anytask после дедлайна.

  • Теоретическое ДЗ-1. Дедлайн: 06.02.22 в 23:59. Условие TeX
  • Практическое ДЗ-1. Дедлайн: 17.02.22 в 23:59. Условие
  • Теоретическое ДЗ-2. Дедлайн: 28.02.22 в 23:59. Условие TeX
  • Практическое ДЗ-2. Дедлайн: 13.03.22 в 23:59. Условие
  • Теоретическое ДЗ-3. Дедлайн: 21.03.22 в 23:59. Условие TeX

Контрольная работа

Экзамен

По завершению 4-го модуля предусмотрен письменный экзамен

Итоговая оценка за курс

3 модуль: Итог = Округление(min(10, 0.4 * ТДЗ + 0.3 * ПДЗ + 0.2 * ПР + 0.1 * ФПР + 0.1 * БДЗ))

4 модуль: Итог = Округление(min(10, 0.2 * ТДЗ + 0.15 * ПДЗ + 0.1 * ПР + 0.05 * ФПР + 0.2 * КР + 0.3 * Э + 0.1 * БДЗ))

Обратите внимание, что в 4-м модуле ТДЗ, ПДЗ, ПР являются средними оценками за оба модуля.

  • ТДЗ – средняя оценка за теоретические домашние задания
  • ПДЗ – средняя оценка за практические домашние задания в Python
  • БДЗ – средняя оценка за бонусные задачи
  • ПР – средняя оценка за проверочные работы (до 10 минут), проводимые каждые 1-2 недели на семинарах
  • ФПР – оценка за финальную проверочную работу, которая проводится в конце 3-го модуля
  • КР – оценка за письменную контрольную работу, включающую теоретические вопросы и задачи
  • Э – оценка за письменный экзамен, проводимый в конце 4-го модуля

Округление арифметическое.

Автоматов не предусмотрено.

Литература

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.

4) Demmel, James W. Applied numerical linear algebra. Society for Industrial and Applied Mathematics, 1997.