Просмотр исходного текста страницы Основы матричных вычислений 2020/2021

== О курсе ==

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

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



'''Семинаристы:''' 
{| class="wikitable"
|-
! Группа !! Преподаватель !! Учебный ассистент || Инвайт в anytask || Чат в телеграм || Консультации
|-
| 1 || Рахуба Максим Владимирович || Соколов Павел Павлович || hshcN22 || 
|| Вт 16:20 - 17:40, [https://zoom.us/j/91339444964 ссылка]
|-
| 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 января) [[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'''

[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 &mdash; справочный материал, скачивать не обязательно.

Дедлайн (строгий): 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'''.

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


=== Экзамен ===


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

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