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

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

О курсе

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

Первые лекция и семинары состоятся 19.01

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

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

Группа Преподаватель Учебные ассистенты Чат в телеграм
1 Рахуба Максим Владимирович Максим Васильев, Андрей Аржанцев tg
2 Самсонов Сергей Владимирович Никита Козлов, Артем Малько tg
3 Ваня Пешехонов Иван Сидоренко, Тимофей Сенин tg
4 Кухарчук Иван Андреевич Егор Бугаев, Тимофей Сенин  ?
5 Сендерович Александра Леонидовна Алмасбек Стамбеков, Максим Захарченко tg
6 Медведь Никита Юрьевич Илья Дробышевский, Виктория Шварева, Максим Захарченко tg
7 Левин Илья Валерьевич Александр Гапонов, Артем Малько  ?

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

Ведомость

Разбиение по группам

Телеграм-канал курса

Телеграм-чат курса

Папка с материалами

Неофициальный конспект лекций 2021-2022 от студента (могут быть ошибки)

Подготовленные билеты к коллоквиуму 2022-2023 от студентов (могут быть ошибки)

План курса

Если какие-то лекции не выложены или найдены ошибки на вики-странице - пишите @strange_guest.

  1. Основы матричного анализа (19.01.2024). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Слайды Запись Конспект (TeX)
  2. Малоранговое приближение матриц – 1 (26.01.2024). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Слайды Запись Конспект (TeX)
  3. Малоранговое приближение матриц – 2 (02.02.2024). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Слайды Видео
  4. Малоранговое приближение матриц – 3 (09.02.2024). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Доска Видео
  5. Малоранговое приближение матриц – 4 (16.02.2024). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Доска Видео
  6. Малоранговое приближение многомерных массивов (26.02.2024). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Доска Видео Конспект (TeX)
  7. Вычисление QR-разложения (01.03.2024). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Доска Видео
  8. Метод наименьших квадратов и псевдообратные матрицы (11.03.2024). Полноранговый случай. Общий случай. Регуляризация. Доска Видео
  9. FFT и структурированные матрицы (15.03.2024). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Доска Видео
  10. FFT и структурированные матрицы – 2 (22.03.2024). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Доска Видео
  11. Умножение матриц, вычислительная устойчивость, обусловленность (05.04.2023). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. Презентация Видео
  12. Матричные ряды (12.04.2024). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. Доска Видео
  13. Прямые методы решения линейных систем с плотными матрицами (15.04.2024). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. Доска Видео


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

На семинарах будут проходить короткие тесты (проверочные работы) по теме лекции и семинара с предыдущей недели.

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

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

Каждый студент 2 раза за семестр может просрочить дедлайн ДЗ на 1 сутки. Чтобы использовать эту возможность, достаточно просто загрузить работу после дедлайна.

  • Теоретическое ДЗ-1. Дедлайн: 10.02.24 в 23:59. Условие TeX
  • Практическое ДЗ-1. Дедлайн: 24.02.24 в 23:59. Условие
  • Теоретическое ДЗ-2. Дедлайн: 07.03.24 в 23:59. Условие TeX
  • Практическое ДЗ-2. Дедлайн: 18.03.24 в 23:59. Условие
  • Теоретическое ДЗ-3. Дедлайн: 03.04.24 в 23:59. Условие
  • Практическое ДЗ-3. Дедлайн: 10.04.24 в 23:59. Условие
  • Теоретическое ДЗ-4. Дедлайн: 29.04.24 в 23:59. Условие TeX

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

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

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

  • ТДЗ – средняя оценка за теоретические домашние задания.
  • ПДЗ – средняя оценка за практические домашние задания в Python.
  • БДЗ – средняя оценка за бонусные задачи.
  • ПР – средняя оценка за проверочные работы на семинарах.
  • К – оценка за коллоквиум.
  • Э – оценка за письменный экзамен, проводимый в конце 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.

Источник — «http://wiki.cs.hse.ru/index.php?title=Основы_матричных_вычислений_2023/24&oldid=84845»