Основы матричных вычислений 2020/2021 — различия между версиями
Rakhubam (обсуждение | вклад) (→О курсе) |
Rakhubam (обсуждение | вклад) (→О курсе) |
||
(не показано 75 промежуточных версии 4 участников) | |||
Строка 12: | Строка 12: | ||
! Группа !! Преподаватель !! Учебный ассистент || Инвайт в anytask || Чат в телеграм || Консультации | ! Группа !! Преподаватель !! Учебный ассистент || Инвайт в anytask || Чат в телеграм || Консультации | ||
|- | |- | ||
− | | 1 || Рахуба Максим Владимирович || Соколов Павел Павлович || | + | | 1 || Рахуба Максим Владимирович || Соколов Павел Павлович || hshcN22 || |
+ | || Вт 16:20 - 17:40, [https://zoom.us/j/91339444964 ссылка] | ||
|- | |- | ||
− | | 2 || Сушникова Дарья Алексеевна || | + | | 2 || Сушникова Дарья Алексеевна || Токкожин Аспандияр || ETq1F00 || || |
|- | |- | ||
− | | 3 || Высоцкий Лев Игоревич || || || | + | | 3 || Высоцкий Лев Игоревич || Мануйленко Никита Сергеевич || go4gqFC || || |
|- | |- | ||
− | | 4 || Высоцкий Лев Игоревич || | + | | 4 || Высоцкий Лев Игоревич || Кувшинова Ксения Алексеевна || dCQaAwe || |
|- | |- | ||
− | | 5 || Сушникова Дарья Алексеевна || | + | | 5 || Сушникова Дарья Алексеевна || Токкожин Аспандияр || m01wCso || |
|- | |- | ||
− | | 6 || Зароднюк Алёна Владимировна || || || | + | | 6 || Зароднюк Алёна Владимировна || Тяпкин Даниил Николаевич ||HX8MApN || |
|} | |} | ||
=== Полезные ссылки === | === Полезные ссылки === | ||
− | Телеграм-канал курса | + | Телеграм-канал курса |
− | Телеграм-чат курса: | + | Телеграм-чат курса: |
Anytask курса: https://anytask.org/course/771 | Anytask курса: https://anytask.org/course/771 | ||
+ | |||
+ | Папка с конспектами лекций: https://yadi.sk/d/zmEwUxsSmOW0xw | ||
+ | |||
+ | Плейлист с записями лекций: https://www.youtube.com/playlist?list=PLEwK9wdS5g0ouOxtCkrw9_niJ5IW9zm0G | ||
+ | |||
+ | Ещё одна папка с записями: https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/ErwdF_hjiM1FmbSWp56u574BK5wHfU1Nk8qwVTxsvesZ6g?e=QoBm6H | ||
== План курса == | == План курса == | ||
− | === | + | === Еженедельные тесты === |
+ | В начале каждого семинаре будет проходить короткий тест по теме лекции с предыдущей недели. | ||
+ | На первом семинаре (19.01.21) пройдет пробный тест, за который не будет выставляться баллов. | ||
+ | Подробнее о правилах проведения будет рассказано на первом семинаре. | ||
+ | |||
+ | === Лекции === | ||
+ | * '''Основы матричного анализа''' (18 января) [[https://yadi.sk/i/6YShCOT_Xt6miQ Конспект], [https://youtu.be/N7kRa4ipX7c Видео]]: Векторные и матричные нормы. Унитарные матрицы. Разложение Шура. | ||
+ | * '''Малоранговое приближение матриц — 1''' (25 января) [[https://yadi.sk/i/xYj8SurHqtwAZQ Конспект], [https://youtu.be/aONYZFrEXwg Видео]]: Разделение переменных и ранг матриц. SVD. | ||
+ | * '''Малоранговое приближение матриц — 2''' (1 февраля) [[https://yadi.sk/i/EEEyMy9utOjFFg Конспект], [https://youtu.be/nEZS13D0Q2M Видео]]: QR-разложение. Операции с малоранговыми матрицами. Ортопроектор. Простейший рандомизированный алгоритм SVD. | ||
+ | * '''Малоранговое приближение матриц — 3''' (8 февраля) [[https://yadi.sk/i/DFWThAhExmFOGA Конспект], [https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/ErwdF_hjiM1FmbSWp56u574BK5wHfU1Nk8qwVTxsvesZ6g?e=QoBm6H Видео]]: ALS-алгоритм. Кронекерово произведение. | ||
+ | * '''Малоранговая аппроксимация многомерных массивов (тензоров)''' (15 февраля) [[https://yadi.sk/i/qApkcNMbL8Gaxw Конспект], [https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/ErwdF_hjiM1FmbSWp56u574BK5wHfU1Nk8qwVTxsvesZ6g?e=QoBm6H Видео]]: Каноническое разложение. Разложение Таккера. HOSVD-алгоритм. Тензорные сети*. | ||
+ | * '''Вычисление QR-разложения''' (22 февраля) [[https://yadi.sk/i/74eD9NfYaACvIw Конспект], [https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/ErwdF_hjiM1FmbSWp56u574BK5wHfU1Nk8qwVTxsvesZ6g?e=QoBm6H Видео]]: Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR. | ||
+ | * '''Псевдообратные матрицы и метод наименьших квадратов''' (29 февраля) (1 марта) [[https://yadi.sk/i/EBKCbSO-UGHEUQ Конспект], [https://youtu.be/fwOF70yBDaU Видео]]: Полноранговый случай. Общий случай. Регуляризация. | ||
+ | * '''FFT и структурированные матрицы''' (9 марта) [[https://yadi.sk/i/jNbPtGFDoQGsQQ Конспект], [https://youtu.be/toetw2UlHwo Видео]]: Быстрое преобразование Фурье. Циркулянты. Тёплицевы матрицы. | ||
+ | * '''FFT и структурированные матрицы — 2''' (22 марта) [[https://yadi.sk/i/PpuJYikN-hRTjQ Конспект], [https://youtu.be/FC30e3fboiU Видео]]: FFT для произвольных n. Двумерное FFT. Двумерные циклические свёртки. Дискретная свёртка. Дискретное косинус-преобразование. | ||
+ | * '''Умножение матриц и вычислительная устойчивость''' (5 апреля) [[https://yadi.sk/i/eWB0PPGRJuLhdw Конспект], [https://youtu.be/8p_2wXj09ww Видео]]: Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. | ||
+ | * '''Лекция 11''' (12 апреля) [[https://yadi.sk/i/qtqjwVYWiT1T_g Конспект], [https://youtu.be/eOcKu-dJuxg Видео]]: Матричные ряды. Теория возмущений для линейных систем. Матричная экспонента. | ||
+ | * '''Прямые методы решения линейных систем с плотными матрицами''' (19 апреля) [[https://yadi.sk/i/5KeAH1gLuGgc2w Конспект], [https://youtu.be/LI_HqDWAPBU Видео]]: LU-разложение. Связь LU-разложения и метода исключения Гаусса. Выбор ведущего элемента. Разложение Холецкого. | ||
+ | * '''Прямые методы для решения линейных систем с большими разреженными матрицами''' (26 апреля) [[https://yadi.sk/i/tCtJ7rmNynMuXA Конспект], [https://youtu.be/55MtLd4vfMY Видео]]: Формула Шермана-Моррисона. Разреженные матрицы. Алгоритмы поиска P. МНК для разреженных матриц. | ||
+ | * '''Итерационные методы для решения систем линейных уравнений''' (11 мая) [[https://yadi.sk/i/Qys5n5whTUMgaQ Презентация], [https://youtu.be/lFv4IKzyFS4 Видео]]: Метод простой итерации. Градиентный спуск. Итерационный метод Чёбышева. | ||
+ | * '''Итерационные методы для решения линейных систем — 2''' (17 мая) [[https://yadi.sk/i/HMLDY9QLW97sqA Конспект], [https://youtu.be/gTeniSq3sQA Видео]]: Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. | ||
+ | * '''Итерационные методы для решения линейных систем — 3''' (24 мая) [[https://disk.yandex.ru/i/LPo02NjN72t-Zw Презентация], [https://youtu.be/ejNjWukiiCk Видео]]: Сходимость CG. GMRES. Предобуславливание. | ||
+ | * '''Методы решения частичной задачи на собственные значения''' (31 мая) [[https://yadi.sk/i/JG0o7vdqwpmXJA Конспект], [https://youtu.be/RTArMt74BpE Видео]]: EigenValue Problem как задача оптимизации. Степенной метод (power iteration). Метод Релея-Ритца. Методы Ланцоша и Арнольди. | ||
+ | * '''Лекция 18''' (7 июня) [[https://yadi.sk/i/TQ1X7PwdU3EkCA Конспект], [https://youtu.be/iP8tJCk8bPc Видео]]: QR-алгоритм. Алгоритм для SVD. Теория возмущений. | ||
+ | * '''Лекция 19''' (14 июня) [[https://yadi.sk/i/U1lfxkuGMx9J9A Конспект], [https://youtu.be/QYcxRdx-FlA Видео]]: Теория возмущений (окончание). Крыловские пространства для матричных функций. Оценка вычисления следа | ||
=== Домашние задания === | === Домашние задания === | ||
+ | |||
+ | Выдаются каждые 2 или 3 недели. | ||
'''Домашнее задание 1''' | '''Домашнее задание 1''' | ||
− | + | [https://yadi.sk/d/U3b8DPy_Kb3NDQ Папка с заданием] | |
− | + | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать видеофайлы из папки). | |
+ | Выдается: 18.01.21. | ||
+ | |||
+ | Дедлайн (строгий): 08.02.21 в 21:59. | ||
+ | |||
+ | '''Домашнее задание 2''' | ||
+ | |||
+ | [https://yadi.sk/d/eS8HdnPRbMZPMw Папка с заданием] | ||
+ | |||
+ | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. | ||
+ | |||
+ | Выдается: 09.02.21. | ||
+ | |||
+ | Дедлайн (строгий): 24.02.21 в 23:59. | ||
+ | |||
+ | '''Домашнее задание 3''' | ||
+ | |||
+ | [https://yadi.sk/d/-BkHWeMWbMIhxQ Папка с заданием] | ||
+ | |||
+ | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать папку data). | ||
+ | |||
+ | Дедлайн (строгий): 24.03.21 в 23:59. | ||
+ | |||
+ | '''Домашнее задание 4''' | ||
+ | |||
+ | [https://yadi.sk/d/PGy5uyK__-QnqA Папка с заданием] | ||
+ | |||
+ | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать файл cameraman.tif). | ||
+ | |||
+ | Дедлайн (строгий): 29.04.21 в 23:59. | ||
+ | |||
+ | '''Домашнее задание 5''' | ||
+ | |||
+ | [https://yadi.sk/d/INM5Vaay-0jZ5w Папка с заданием] | ||
+ | |||
+ | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. resistors.svg — справочный материал, скачивать не обязательно. | ||
+ | |||
+ | Дедлайн (строгий): 16 мая 2021 в 23:59. | ||
+ | |||
+ | '''Домашнее задание 6''' | ||
+ | |||
+ | [https://disk.yandex.ru/d/KMMdZeKvyD_HMA Папка с заданием] | ||
+ | |||
+ | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. | ||
+ | |||
+ | Дедлайн (строгий): 31 мая 2021 в 23:59. | ||
+ | |||
+ | '''Домашнее задание 7''' | ||
+ | |||
+ | [https://yadi.sk/d/71sTEAGNGWiPWA Папка с заданием] | ||
+ | |||
+ | Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. | ||
+ | |||
+ | Дедлайн (строгий): '''15 июня 2021''' в '''23:59'''. | ||
=== Контрольная работа === | === Контрольная работа === | ||
Строка 55: | Строка 141: | ||
=== Итоговая оценка за курс === | === Итоговая оценка за курс === | ||
+ | |||
+ | Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.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. |
Текущая версия на 19:17, 6 августа 2021
Содержание
О курсе
Курс для студентов 2 курса в 3-4 модулях.
Лектор: Рахуба Максим Владимирович
Семинаристы:
Группа | Преподаватель | Учебный ассистент | Инвайт в anytask | Чат в телеграм | Консультации |
---|---|---|---|---|---|
1 | Рахуба Максим Владимирович | Соколов Павел Павлович | hshcN22 | Вт 16:20 - 17:40, ссылка | |
2 | Сушникова Дарья Алексеевна | Токкожин Аспандияр | ETq1F00 | ||
3 | Высоцкий Лев Игоревич | Мануйленко Никита Сергеевич | go4gqFC | ||
4 | Высоцкий Лев Игоревич | Кувшинова Ксения Алексеевна | dCQaAwe | ||
5 | Сушникова Дарья Алексеевна | Токкожин Аспандияр | m01wCso | ||
6 | Зароднюк Алёна Владимировна | Тяпкин Даниил Николаевич | HX8MApN |
Полезные ссылки
Телеграм-канал курса
Телеграм-чат курса:
Anytask курса: https://anytask.org/course/771
Папка с конспектами лекций: https://yadi.sk/d/zmEwUxsSmOW0xw
Плейлист с записями лекций: https://www.youtube.com/playlist?list=PLEwK9wdS5g0ouOxtCkrw9_niJ5IW9zm0G
Ещё одна папка с записями: https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/ErwdF_hjiM1FmbSWp56u574BK5wHfU1Nk8qwVTxsvesZ6g?e=QoBm6H
План курса
Еженедельные тесты
В начале каждого семинаре будет проходить короткий тест по теме лекции с предыдущей недели. На первом семинаре (19.01.21) пройдет пробный тест, за который не будет выставляться баллов. Подробнее о правилах проведения будет рассказано на первом семинаре.
Лекции
- Основы матричного анализа (18 января) [Конспект, Видео]: Векторные и матричные нормы. Унитарные матрицы. Разложение Шура.
- Малоранговое приближение матриц — 1 (25 января) [Конспект, Видео]: Разделение переменных и ранг матриц. SVD.
- Малоранговое приближение матриц — 2 (1 февраля) [Конспект, Видео]: QR-разложение. Операции с малоранговыми матрицами. Ортопроектор. Простейший рандомизированный алгоритм SVD.
- Малоранговое приближение матриц — 3 (8 февраля) [Конспект, Видео]: ALS-алгоритм. Кронекерово произведение.
- Малоранговая аппроксимация многомерных массивов (тензоров) (15 февраля) [Конспект, Видео]: Каноническое разложение. Разложение Таккера. HOSVD-алгоритм. Тензорные сети*.
- Вычисление QR-разложения (22 февраля) [Конспект, Видео]: Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR.
- Псевдообратные матрицы и метод наименьших квадратов (29 февраля) (1 марта) [Конспект, Видео]: Полноранговый случай. Общий случай. Регуляризация.
- FFT и структурированные матрицы (9 марта) [Конспект, Видео]: Быстрое преобразование Фурье. Циркулянты. Тёплицевы матрицы.
- FFT и структурированные матрицы — 2 (22 марта) [Конспект, Видео]: FFT для произвольных n. Двумерное FFT. Двумерные циклические свёртки. Дискретная свёртка. Дискретное косинус-преобразование.
- Умножение матриц и вычислительная устойчивость (5 апреля) [Конспект, Видео]: Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность.
- Лекция 11 (12 апреля) [Конспект, Видео]: Матричные ряды. Теория возмущений для линейных систем. Матричная экспонента.
- Прямые методы решения линейных систем с плотными матрицами (19 апреля) [Конспект, Видео]: LU-разложение. Связь LU-разложения и метода исключения Гаусса. Выбор ведущего элемента. Разложение Холецкого.
- Прямые методы для решения линейных систем с большими разреженными матрицами (26 апреля) [Конспект, Видео]: Формула Шермана-Моррисона. Разреженные матрицы. Алгоритмы поиска P. МНК для разреженных матриц.
- Итерационные методы для решения систем линейных уравнений (11 мая) [Презентация, Видео]: Метод простой итерации. Градиентный спуск. Итерационный метод Чёбышева.
- Итерационные методы для решения линейных систем — 2 (17 мая) [Конспект, Видео]: Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов.
- Итерационные методы для решения линейных систем — 3 (24 мая) [Презентация, Видео]: Сходимость CG. GMRES. Предобуславливание.
- Методы решения частичной задачи на собственные значения (31 мая) [Конспект, Видео]: EigenValue Problem как задача оптимизации. Степенной метод (power iteration). Метод Релея-Ритца. Методы Ланцоша и Арнольди.
- Лекция 18 (7 июня) [Конспект, Видео]: QR-алгоритм. Алгоритм для SVD. Теория возмущений.
- Лекция 19 (14 июня) [Конспект, Видео]: Теория возмущений (окончание). Крыловские пространства для матричных функций. Оценка вычисления следа
Домашние задания
Выдаются каждые 2 или 3 недели.
Домашнее задание 1
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать видеофайлы из папки).
Выдается: 18.01.21.
Дедлайн (строгий): 08.02.21 в 21:59.
Домашнее задание 2
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook.
Выдается: 09.02.21.
Дедлайн (строгий): 24.02.21 в 23:59.
Домашнее задание 3
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать папку data).
Дедлайн (строгий): 24.03.21 в 23:59.
Домашнее задание 4
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать файл cameraman.tif).
Дедлайн (строгий): 29.04.21 в 23:59.
Домашнее задание 5
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. resistors.svg — справочный материал, скачивать не обязательно.
Дедлайн (строгий): 16 мая 2021 в 23:59.
Домашнее задание 6
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook.
Дедлайн (строгий): 31 мая 2021 в 23:59.
Домашнее задание 7
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook.
Дедлайн (строгий): 15 июня 2021 в 23:59.
Контрольная работа
Экзамен
Итоговая оценка за курс
Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.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.