Основы матричных вычислений 2021/2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Esquerte (обсуждение | вклад) |
Mednik (обсуждение | вклад) (→Лекции) |
||
| Строка 41: | Строка 41: | ||
=== Лекции === | === Лекции === | ||
| − | + | # '''Основы матричного анализа''' (14.01.2022). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. [https://disk.yandex.ru/i/IIvxT83Zl6ntpw Конспект] [https://youtu.be/Ko6r7Q4Jnz8 Видео (youtube)] [https://disk.yandex.ru/i/90mmYWp4Sy4JcQ Конспект (TeX)] | |
| − | + | # '''Малоранговое приближение матриц – 1''' (21.01.2022). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. [https://disk.yandex.ru/i/9VWiLWGimcQbzg Конспект] [https://www.youtube.com/watch?v=vXxADPKz_b0 Видео (youtube)] [https://disk.yandex.ru/i/tiW02SnyGxH__A Конспект (TeX)] | |
| − | + | # '''Малоранговое приближение матриц – 2''' (28.01.2022). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. [https://disk.yandex.ru/i/orYYoneNleFQLQ Конспект] [https://zoom.us/rec/share/l6q8M4L682rKx5aVcidQEQAq3JMEv67yYK320PlNBBWFK_IUPZri05La0nPLxDlF.5k5bznR6401JqaSW Видео (zoom.us)] [https://youtu.be/UfTXNY7i8Ek Видео (youtube)] | |
| − | + | # '''Малоранговое приближение матриц – 3''' (04.02.2022). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. [https://disk.yandex.ru/i/5C2N3FXvMMZExQ Конспект] [https://zoom.us/rec/share/ZfW8cMQbLzqHt0NkEEMF95HtS3tcKO2FnJn4psz6tq5WI_e-eeVobyuR_S5jN4v8.2MfNKPJA2oJB1E0v?startTime=1643967927000 Видео (zoom.us)] [https://youtu.be/G-EGHRZXImI Видео (youtube)] | |
| − | + | # '''Малоранговое приближение матриц – 4''' (11.02.2022). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. [https://disk.yandex.ru/i/SO5hvmLd-AID-A Конспект] [https://zoom.us/rec/play/hBNoyzwFwD_cY7lnDQ95XqDulDoVXnzkGeyLl5GDLBJIxe90Wubix8Dk5wP-V4cOkHBYzeAZFYcRMN-I.QT_JGe_6sKYizBe6?startTime=1644572731000 Видео (zoom.us)] [https://youtu.be/gYQp_xuLppk Видео (youtube)] | |
| − | + | # '''Малоранговое приближение многомерных массивов''' (18.02.2022). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. [https://disk.yandex.ru/i/mh9PyT_QEqn7sg Конспект] [https://zoom.us/rec/play/gLtwlrvbPIcZ_ykNJe_Ehmx6ubIo4of_x2kBchDuPRVLAGYFIsQ20f_yABwi8iqfHfpzhEZy495s-JT5.6TDQuJvrLjcusUTP Видео (zoom.us)] [https://youtu.be/nnqVzdUopko Видео (youtube)] | |
| − | + | # '''Вычисление QR-разложения''' (25.02.2022). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). [https://disk.yandex.ru/i/VGGPHM8Gs7QnQg Конспект] [https://zoom.us/rec/play/ePZWHHNY9WeKV09YTNg6OeojRlYDU3fe7nsKz92texsTighD2es7d7ZCPy6RFizQ6fRTLlcBmjCuk9uh.aSw0CzKfOnwQD9fs Видео (zoom.us)] [https://youtu.be/gG5D0ZkLCTk Видео (youtube)] | |
| − | + | # '''Метод наименьших квадратов и псевдообратные матрицы''' (04.03.2022). Полноранговый случай. Общий случай. Регуляризация. [https://disk.yandex.ru/i/7WnRgjPjDb3nrQ Конспект] [https://zoom.us/rec/share/jpqczk61nIXYdqXbDvblwQRW_oI8Nra6WLVWcuXzcYGgTtReInr1fBAX_T2inpia.QOImTcwLuWi86lfo?startTime=1646387105000 Видео (zoom.us)] [https://youtu.be/T11F_C8wGkQ Видео (youtube)] | |
| − | + | # '''FFT и структурированные матрицы''' (11.03.2022). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. [https://disk.yandex.ru/i/mowg4aJpB2H4Bw Конспект] [https://youtu.be/906JLb3aAkQ Видео (youtube)] | |
| − | + | # '''FFT и структурированные матрицы – 2''' (18.03.2022). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). [https://disk.yandex.ru/i/mmX6VFAqFcOGAA Конспект] [https://zoom.us/rec/share/Hv4RBdR46AeWmZi2WsDCWsnykosEWeTzttI9jFF8-a1YEVx8_YMODSiCqZMuMxE.pZ2W9hph7dIIs2Xp?startTime=1647596739000 Виде (zoom.us)] [https://youtu.be/b2JFHqCbm74 Видео (youtube)] | |
=== Проверочные работы на семинарах === | === Проверочные работы на семинарах === | ||
Версия 20:25, 22 марта 2022
Содержание
О курсе
Курс для студентов 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
План курса
Лекции
- Основы матричного анализа (14.01.2022). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Конспект Видео (youtube) Конспект (TeX)
- Малоранговое приближение матриц – 1 (21.01.2022). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Конспект Видео (youtube) Конспект (TeX)
- Малоранговое приближение матриц – 2 (28.01.2022). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Конспект Видео (zoom.us) Видео (youtube)
- Малоранговое приближение матриц – 3 (04.02.2022). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Конспект Видео (zoom.us) Видео (youtube)
- Малоранговое приближение матриц – 4 (11.02.2022). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Конспект Видео (zoom.us) Видео (youtube)
- Малоранговое приближение многомерных массивов (18.02.2022). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Конспект Видео (zoom.us) Видео (youtube)
- Вычисление QR-разложения (25.02.2022). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Конспект Видео (zoom.us) Видео (youtube)
- Метод наименьших квадратов и псевдообратные матрицы (04.03.2022). Полноранговый случай. Общий случай. Регуляризация. Конспект Видео (zoom.us) Видео (youtube)
- FFT и структурированные матрицы (11.03.2022). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Конспект Видео (youtube)
- FFT и структурированные матрицы – 2 (18.03.2022). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Конспект Виде (zoom.us) Видео (youtube)
Проверочные работы на семинарах
Каждые 1-2 недели на семинарах будет проходить короткие тесты по теме лекции и семинара с предыдущей недели. На первом семинаре пройдет пробный тест, за который не будет выставляться баллов. Подробнее о правилах проведения будет рассказано на первом семинаре.
Домашние задания
На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели.
У каждого студента есть трое суток суммарно, на которые можно продлить срок сдачи любых заданий. Чтобы использовать эту возможность, достаточно просто загрузить работу в anytask после дедлайна.
- Практическое ДЗ-1. Дедлайн: 17.02.22 в 23:59. Условие
- Практическое ДЗ-2. Дедлайн: 13.03.22 в 23:59. Условие
Контрольная работа
Экзамен
По завершению 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.
