Основы матричных вычислений 2023/24 — различия между версиями

Текущая версия на 11:02, 14 июня 2024

О курсе

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

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

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

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

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

Ведомость

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

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

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

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

Неофициальный конспект лекций 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). Разложение Холецкого. Доска Видео
14. Прямые методы решения линейных систем с разреженными матрицами (26.04.2024). Формула Шермана-Моррисона, тождество Вудберри. Разреженные матрицы: заполнения в L и U. Алгоритмы поиска P (матрицы перестановки). Доска Видео
15. Итерационные методы решения линейных систем (10.05.2024). Одношаговые методы: метод простой итерации, градиентный спуск, метод Чебышёва. Презентация Видео
16. Итерационные методы решения линейных систем – 2 (17.05.2024). Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. Конспект Видео
17. Итерационные методы решения линейных систем – 3 (24.05.2024). Сходимость CG. GMRES. Предобуславливание. Презентация Видео
18. Методы решения частичной задачи на собственные значения (31.05.2024). Eigenvalue problem как задача оптимизации. Степенной метод. Метод Релея-Ритца. Методы Ланцоша и Арнольди. Конспект Видео
19. Методы решения частичной и полной задач на собственные значения (07.06.2024). Числа Ритца в методе Ланцоша. QR-алгоритм. Конспект Видео

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

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

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

На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке 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

• Практическое ДЗ-4. Дедлайн: 16.05.24 в 23:59. Условие

• Теоретическое ДЗ-5. Дедлайн: 10.06.24 в 23:59. Условие TeX

• Практическое ДЗ-5. Дедлайн: 19.06.24 в 23:59. Условие

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

Итог = Округление(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.