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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Полезные ссылки)
 
(не показана одна промежуточная версия 9 участников)
Строка 4: Строка 4:
  
 
'''Лектор:''' Рахуба Максим Владимирович
 
'''Лектор:''' Рахуба Максим Владимирович
−
 
−
 
  
 
'''Семинаристы:'''  
 
'''Семинаристы:'''  
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! Группа !! Преподаватель !! Учебный ассистент || Инвайт в anytask || Чат в телеграм || Консультации
+
! Группа !! Преподаватель !! Учебный ассистент || Время начала семинара || Инвайт в anytask || Чат в телеграм || Консультации
 
|-
 
|-
−
| 1 || Рахуба Максим Владимирович || || ||  
+
| 1 || Высоцкий Лев Игоревич || Илья Анищенко || Пт, 11:10 || ecpmalC || [https://t.me/+G-elYeMh-q5iNjYy tg] ||  
−
||  
+
 
|-
 
|-
−
| 2 || Сушникова Дарья Алексеевна || || || ||  
+
| 2 || Рахуба Максим Владимирович || Михаил Петров || Пт, 09:30 || WaheRR2 || [https://t.me/+3c6szNe8E9E4NmQy tg] ||
 
|-
 
|-
−
| 3 || Высоцкий Лев Игоревич || || || ||  
+
| 3 || Сушникова Дарья Алексеевна || Александр Демин || Пт, 11:10 || ZIeqosn || [https://t.me/+9bx9m8279vAyYWYy tg] ||  
 
|-
 
|-
−
| 4 || Высоцкий Лев Игоревич || ||  ||
+
| 4 || Сушникова Дарья Алексеевна || Влад Княжевский || Пт, 09:30 || yYBADOt || [https://t.me/+4fUPIKLCPlVmMTky tg] ||
 
|-
 
|-
−
| 5 ||  Сушникова Дарья Алексеевна ||   || ||
+
| 5 || Медведь Никита Юрьевич || Дмитрий Лишуди  || Вт, 11:10 || 6T48c6J || [https://t.me/+xjDuK64sj_s5ODcy tg] || ?
 
|-
 
|-
−
| 6 || Зароднюк Алёна Владимировна || || ||
+
| 6 || Зароднюк Алёна Владимировна || Ира Голобородько || Вт, 11:10 || BjKRP6u || [https://t.me/+TEbCCgNqktU3ZjRi tg] ||
 
|}
 
|}
  
 
=== Полезные ссылки ===
 
=== Полезные ссылки ===
  
−
Телеграм-канал курса: https://t.me/+u0U2pqXT4WE0NGEy
+
Телеграм-канал курса: [https://t.me/+u0U2pqXT4WE0NGEy t.me]
  
−
Телеграм-чат курса: https://t.me/+eCqsF6E-UzI5MjVi
+
Телеграм-чат курса: [https://t.me/+eCqsF6E-UzI5MjVi t.me]
  
−
== План курса ==
+
Таблица с оценками: [https://docs.google.com/spreadsheets/d/1zuBkOv1TLd5FK9LfyfnuirwON9Js4AoW2gn0grrvdcc/edit#gid=833242058 docs.google.com]
  
 +
Материалы курса: [https://disk.yandex.ru/d/rylf3xk13J4ztA disk.yandex.ru]
  
−
=== Еженедельные тесты ===
+
Плейлист с лекциями: [https://www.youtube.com/playlist?list=PLEwK9wdS5g0rSn5GRkyUBLw5FurjVy0yp youtube.com]
  
−
В начале каждого семинаре будет проходить короткий тест по теме лекции с предыдущей недели.  
+
Плейлист с семинарами 2-й группы: [https://www.youtube.com/playlist?list=PLEwK9wdS5g0ooOooUYyzbhTu_6N7ycXvF youtube.com]
−
На первом семинаре  (19.01.21) пройдет пробный тест, за который не будет выставляться баллов.
+
−
Подробнее о правилах проведения будет рассказано на первом семинаре.
+
  
−
=== Лекции ===
+
Неофициальный конспект лекций от Артёма: [https://nextcloud.codereptile.ru/index.php/s/Tn7DxZFDzwRQPDm nextcloud.codereptile.ru]
−
* '''Основы матричного анализа''' (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'''
+
# '''Основы матричного анализа''' (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)]
 +
# '''Умножение матриц и вычислительная устойчивость''' (06.04.2022). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. [https://disk.yandex.ru/i/e3OE5EEhi7gbyw Презентация] [https://us06web.zoom.us/rec/share/LiIqMsR0llK1Eg_l9G6J2wJ4-va-IzOClY8G-Jz-_UrDd5HYnsLuW9UX5rAqno1z.PkknvV_pR3eLOQq0 Видео (zoom.us)] [https://youtu.be/4BnDSccgc8U Видео (youtube)]
 +
# '''Матричные ряды''' (08.04.2022). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. [https://disk.yandex.ru/i/6T_-bxlyGRU7Vg Конспект] [https://us06web.zoom.us/rec/share/i-3aGrTq1ZlJI86Qov1yc7uhtx29pLs2mhdW37IfKPCvTZ-TPeNMElZblHrIJ7Z3.7lotWfgDT3axI4zi?startTime=1649411827000 Видео (zoom.us)] [https://youtu.be/8zPPowwCRuw Видео (youtube)]
 +
# '''Прямые методы решения линейных систем с плотными матрицами''' (15.04.2022). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. [https://disk.yandex.ru/i/cURgrFOjTndTNA Конспект] [https://us06web.zoom.us/rec/share/YNY0UQw-AFYLJ6wVJ1cRU7HpL83QmMS6R56jT-9kdXMzIublTngoHm8HOMYmst9X.MUMLDmpyumpcyhBp?startTime=1650016192000 Видео (zoom.us)] [https://youtu.be/FMtci0ypU60 Видео (youtube)]
 +
# '''Прямые методы решения линейных систем с разреженными матрицами''' (22.04.2022). Формула Шермана-Моррисона, тождество Вудберри. Разреженные матрицы: заполнения в L и U. Алгоритмы поиска P (матрицы перестановки). [https://disk.yandex.ru/i/c1OqWHy6bA18yw Конспект] [https://us06web.zoom.us/rec/play/1iUsmRSIo5pPTzrxDB4iB9lFOJ01YShamrJdKnDFFL0BdXApechwwcGbjfCPx-outLjhXX3OFpSfNhSn.u3fDzyujeCrSdqiz?startTime=1650620725000 Видео (zoom.us)] [https://youtu.be/Y0Cwm4Vgdi4 Видео (youtube)]
 +
# '''Итерационные методы решения линейных систем''' (29.04.2022). Одношаговые методы: метод простой итерации, градиентный спуск, метод Чебышёва. [https://disk.yandex.ru/i/EGC5Fj5H8WYucg Презентация] [https://us06web.zoom.us/rec/play/iDEj9La4JYiz0vdyom11cn3rcdGixY3CnlVSdKT2bJR6fROwqPZXo-_oQmDMTJln3lUuk1wuJFOWf3zp.rsJLYIL1mb52wIDE?startTime=1651226019000 Видео (zoom.us)] [https://youtu.be/Okssj7JBXlI Видео (youtube)]
 +
# '''Итерационные методы решения линейных систем – 2''' (13.05.2022). Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. [https://disk.yandex.ru/i/Pz1HtTqA8L3SMg Конспект] [https://us06web.zoom.us/rec/share/bpi0bue_WXpSB25dGGqRKJ6Q4vdedPHiz3RcyB9yGAqup_1Brz__GyTIbL-6JyIJ.TpJAYyxf543IYaq3?startTime=1652435713000 Видео (zoom.us, часть 1)] [https://us06web.zoom.us/rec/share/bpi0bue_WXpSB25dGGqRKJ6Q4vdedPHiz3RcyB9yGAqup_1Brz__GyTIbL-6JyIJ.TpJAYyxf543IYaq3?startTime=1652441204000 Видео (zoom.us, часть 2)] [https://youtu.be/-Wok-D7rtUU Видео (youtube)]
 +
# '''Итерационные методы решения линейных систем – 3''' (20.05.2022). Сходимость CG. GMRES. Предобуславливание. [https://disk.yandex.ru/i/ik0sVFqiLAYtyQ Презентация] [https://us06web.zoom.us/rec/share/xMb0jzGdAHPSPYEfsoTtSK9D5z39M4sC-9g-CYdkXKggLj_4jQMDZwYiicQhZA2B.DOo-SWkw3c0kqHQW?startTime=1653040598000 Видео (zoom.us)] [https://youtu.be/aC6z_gfX0j0 Видео (youtube)]
 +
# '''Методы решения частичной задачи на собственные значения''' (27.05.2022). Eigenvalue problem как задача оптимизации. Степенной метод. Метод Релея-Ритца. Методы Ланцоша и Арнольди. [https://disk.yandex.ru/d/RlNCY-fZMHDqHw Конспект] [https://us06web.zoom.us/rec/share/g5anJURAqh1jgSZUmUfhr0YUo7NLbug4Yd1dpUmqVa-QvLe1H1YwTeiWzjqRII1r.b0e8fd0dBykxh20z?startTime=1653644726000 Видео (zoom.us)] [https://youtu.be/bqezn9wzA7I Видео (youtube)]
 +
# '''Методы решения частичной и полной задач на собственные значения''' (03.06.2022). Числа Ритца в методе Ланцоша. QR-алгоритм. [https://disk.yandex.ru/i/0l4uzDHVatjxdA Конспект] [https://us06web.zoom.us/rec/share/SakkSQ6kB6vJ7nTd4kG98_gTHKRH8U7RKxCJ0CXO-P9Y6YlAlribNedH35MFHPj4.Uqzlpx048JLSCiL6?startTime=1654250018000 Видео (zoom.us)] [https://youtu.be/_-hhhxmaKmo Видео (youtube)]
 +
# '''Теория возмущений''' (10.06.2022). Алгоритм для SVD. 1-я и 2-я теоремы Гершгорина. Теорема Бауэра-Файка. Число обусловленности для отдельный собственных значений. [https://disk.yandex.ru/i/MQO2hoeNUyEV0A Конспект] [https://us06web.zoom.us/rec/share/bU3q29d6lZXhGl0lky9OWMeOERO2kIJV34vSigUHlbVvegSMhfILboGk06UdlI88.w6P2QX1nnBB4QHeB?startTime=1654854320000 Видео (zoom.us)] [https://youtu.be/tiLPidM4bME Видео (youtube)]
 +
# '''Сингулярные числа свёрточных слоёв''' (доп. лекция, 17.06.2022). Константа Липшица для нейронных сетей. Неточные методы поиска. Точные методы и оценки. [https://disk.yandex.ru/i/AcRDCPT6Bc_3xg Конспект] [https://us06web.zoom.us/rec/share/VLB43uFMZu-o8dYzdltddhAMrA5otPOe23m5HpmvPGlINm6Re_oX2VqwmSmMxnji.lCAJKjhjBkST_XUf Видео (zoom.us)]
  
−
[https://yadi.sk/d/U3b8DPy_Kb3NDQ Папка с заданием]
+
=== Проверочные работы на семинарах ===
  
−
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать видеофайлы из папки).
+
Каждые 1-2 недели на семинарах будут проходить короткие тесты по теме лекции и семинара с предыдущей недели.
 +
На первом семинаре пройдет пробный тест, за который не будет выставляться баллов.
 +
Подробнее о правилах проведения будет рассказано на первом семинаре.
  
−
Выдается: 18.01.21.
+
=== Домашние задания ===
  
−
Дедлайн (строгий): 08.02.21 в 21:59.
+
На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели.
  
−
'''Домашнее задание 2'''
+
У каждого студента есть трое суток суммарно, на которые можно продлить срок сдачи любых заданий. Чтобы использовать эту возможность, достаточно просто загрузить работу в anytask после дедлайна.
  
−
[https://yadi.sk/d/eS8HdnPRbMZPMw Папка с заданием]
+
* '''Теоретическое ДЗ-1'''. Дедлайн: 06.02.22 в 23:59. [https://disk.yandex.ru/i/maDXz7-lSb1zYw Условие] [https://disk.yandex.ru/d/pdhDZE2SHTxKGQ TeX]
  
−
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook.
+
* '''Практическое ДЗ-1'''. Дедлайн: 17.02.22 в 23:59. [https://disk.yandex.ru/d/V0gba6JQ7DpxSQ Условие]
  
−
Выдается: 09.02.21.
+
* '''Теоретическое ДЗ-2'''. Дедлайн: 28.02.22 в 23:59. [https://disk.yandex.ru/i/PoaniM3ijMrH6w Условие] [https://disk.yandex.ru/d/tvC0Onp2HVv2RA TeX]
  
−
Дедлайн (строгий): 24.02.21 в 23:59.
+
* '''Практическое ДЗ-2'''. Дедлайн: 13.03.22 в 23:59. [https://disk.yandex.ru/d/Wu7xqOagVGGwMg Условие]
  
−
'''Домашнее задание 3'''
+
* '''Теоретическое ДЗ-3'''. Дедлайн: 21.03.22 в 23:59. [https://disk.yandex.ru/i/9YNdA48go0CXAw Условие] [https://disk.yandex.ru/d/b3UiChRvQWUTWA TeX]
  
−
[https://yadi.sk/d/-BkHWeMWbMIhxQ Папка с заданием]
+
* '''Практическое ДЗ-3'''. Дедлайн: 13.04.22 в 23:59. [https://disk.yandex.ru/d/yashQooHlZeO4A Условие] [https://disk.yandex.ru/d/VDSLkN3aMt2GmQ Папка с данными]
  
−
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать папку data).
+
* '''Теоретическое ДЗ-4'''. Дедлайн: 30.04.22 в 23:59. [https://disk.yandex.ru/i/FulZ-y_WG1bc_Q Условие] [https://disk.yandex.ru/d/mz0ozvPNf-3_iA TeX]
  
−
Дедлайн (строгий): 24.03.21 в 23:59.
+
* '''Практическое ДЗ-4'''. Дедлайн: 18.05.22 в 23:59. [https://disk.yandex.ru/d/1v-Rzg7MQn8mWQ Условие] [https://disk.yandex.ru/d/gpCqVZeZh5q_lg Папка с данными]
  
−
'''Домашнее задание 4'''
+
* '''Теоретическое ДЗ-5'''. Дедлайн: 26.05.22 в 23:59. [https://disk.yandex.ru/i/4preghNbmnWaPQ Условие] [https://disk.yandex.ru/d/n-aRnL4uViN_Gw TeX]
  
−
[https://yadi.sk/d/PGy5uyK__-QnqA Папка с заданием]
+
* '''Практическое ДЗ-5'''. Дедлайн: 09.06.22 в 23:59. [https://disk.yandex.ru/d/ZF31ISNhCqYq2w Условие]
  
−
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать файл cameraman.tif).
+
* '''Теоретическое ДЗ-6'''. Дедлайн: 18.06.22 в 23:59. [https://disk.yandex.ru/i/ybpwV_2aR4-WNw Условие] [https://disk.yandex.ru/d/Dm9-smgcWbkfFg TeX]
−
 
+
−
Дедлайн (строгий): 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'''.
+
  
 
=== Контрольная работа ===
 
=== Контрольная работа ===
  
 +
Контрольная работа пройдет очно 25 апреля, начало: 18:10, время написания: 120 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на дистанте мы предусмотрим написание в онлайн формате. [https://t.me/c/1668317399/53 Подробности]
  
 
=== Экзамен ===
 
=== Экзамен ===
  
 +
Экзамен пройдет очно 28 июня (вторник), начало: 11:00, время написания: 150 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на официальном дистанте мы предусмотрим написание в онлайн формате. [https://t.me/c/1668317399/81 Подробности]
  
 
=== Итоговая оценка за курс ===
 
=== Итоговая оценка за курс ===
  
−
Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э))
+
'''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
−
КР –– оценка за контрольную работу (проводится в первой половине 4-го модуля),
+
* БДЗ – средняя оценка за бонусные задачи
−
Э –– письменный экзамен.
+
* ПР – средняя оценка за проверочные работы (до 10 минут), проводимые каждые 1-2 недели на семинарах
 +
* ФПР – оценка за финальную проверочную работу, которая проводится в конце 3-го модуля
 +
* КР – оценка за письменную контрольную работу, включающую теоретические вопросы и задачи
 +
* Э – оценка за письменный экзамен, проводимый в конце 4-го модуля
  
 
Округление арифметическое.
 
Округление арифметическое.
  
−
Автоматы не предусмотрены.
+
'''Автоматов не предусмотрено'''.
  
 
== Литература ==
 
== Литература ==

Текущая версия на 11:45, 25 июня 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

Плейлист с семинарами 2-й группы: youtube.com

Неофициальный конспект лекций от Артёма: nextcloud.codereptile.ru

План курса

Лекции

  1. Основы матричного анализа (14.01.2022). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Конспект Видео (youtube) Конспект (TeX)
  2. Малоранговое приближение матриц – 1 (21.01.2022). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Конспект Видео (youtube) Конспект (TeX)
  3. Малоранговое приближение матриц – 2 (28.01.2022). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Конспект Видео (zoom.us) Видео (youtube)
  4. Малоранговое приближение матриц – 3 (04.02.2022). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Конспект Видео (zoom.us) Видео (youtube)
  5. Малоранговое приближение матриц – 4 (11.02.2022). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Конспект Видео (zoom.us) Видео (youtube)
  6. Малоранговое приближение многомерных массивов (18.02.2022). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Конспект Видео (zoom.us) Видео (youtube)
  7. Вычисление QR-разложения (25.02.2022). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Конспект Видео (zoom.us) Видео (youtube)
  8. Метод наименьших квадратов и псевдообратные матрицы (04.03.2022). Полноранговый случай. Общий случай. Регуляризация. Конспект Видео (zoom.us) Видео (youtube)
  9. FFT и структурированные матрицы (11.03.2022). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Конспект Видео (youtube)
  10. FFT и структурированные матрицы – 2 (18.03.2022). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Конспект Видео (zoom.us) Видео (youtube)
  11. Умножение матриц и вычислительная устойчивость (06.04.2022). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. Презентация Видео (zoom.us) Видео (youtube)
  12. Матричные ряды (08.04.2022). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. Конспект Видео (zoom.us) Видео (youtube)
  13. Прямые методы решения линейных систем с плотными матрицами (15.04.2022). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. Конспект Видео (zoom.us) Видео (youtube)
  14. Прямые методы решения линейных систем с разреженными матрицами (22.04.2022). Формула Шермана-Моррисона, тождество Вудберри. Разреженные матрицы: заполнения в L и U. Алгоритмы поиска P (матрицы перестановки). Конспект Видео (zoom.us) Видео (youtube)
  15. Итерационные методы решения линейных систем (29.04.2022). Одношаговые методы: метод простой итерации, градиентный спуск, метод Чебышёва. Презентация Видео (zoom.us) Видео (youtube)
  16. Итерационные методы решения линейных систем – 2 (13.05.2022). Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. Конспект Видео (zoom.us, часть 1) Видео (zoom.us, часть 2) Видео (youtube)
  17. Итерационные методы решения линейных систем – 3 (20.05.2022). Сходимость CG. GMRES. Предобуславливание. Презентация Видео (zoom.us) Видео (youtube)
  18. Методы решения частичной задачи на собственные значения (27.05.2022). Eigenvalue problem как задача оптимизации. Степенной метод. Метод Релея-Ритца. Методы Ланцоша и Арнольди. Конспект Видео (zoom.us) Видео (youtube)
  19. Методы решения частичной и полной задач на собственные значения (03.06.2022). Числа Ритца в методе Ланцоша. QR-алгоритм. Конспект Видео (zoom.us) Видео (youtube)
  20. Теория возмущений (10.06.2022). Алгоритм для SVD. 1-я и 2-я теоремы Гершгорина. Теорема Бауэра-Файка. Число обусловленности для отдельный собственных значений. Конспект Видео (zoom.us) Видео (youtube)
  21. Сингулярные числа свёрточных слоёв (доп. лекция, 17.06.2022). Константа Липшица для нейронных сетей. Неточные методы поиска. Точные методы и оценки. Конспект Видео (zoom.us)

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

Каждые 1-2 недели на семинарах будут проходить короткие тесты по теме лекции и семинара с предыдущей недели. На первом семинаре пройдет пробный тест, за который не будет выставляться баллов. Подробнее о правилах проведения будет рассказано на первом семинаре.

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

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

У каждого студента есть трое суток суммарно, на которые можно продлить срок сдачи любых заданий. Чтобы использовать эту возможность, достаточно просто загрузить работу в anytask после дедлайна.

  • Теоретическое ДЗ-1. Дедлайн: 06.02.22 в 23:59. Условие TeX
  • Практическое ДЗ-1. Дедлайн: 17.02.22 в 23:59. Условие
  • Теоретическое ДЗ-2. Дедлайн: 28.02.22 в 23:59. Условие TeX
  • Практическое ДЗ-2. Дедлайн: 13.03.22 в 23:59. Условие
  • Теоретическое ДЗ-3. Дедлайн: 21.03.22 в 23:59. Условие TeX
  • Теоретическое ДЗ-4. Дедлайн: 30.04.22 в 23:59. Условие TeX
  • Теоретическое ДЗ-5. Дедлайн: 26.05.22 в 23:59. Условие TeX
  • Практическое ДЗ-5. Дедлайн: 09.06.22 в 23:59. Условие
  • Теоретическое ДЗ-6. Дедлайн: 18.06.22 в 23:59. Условие TeX

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

Контрольная работа пройдет очно 25 апреля, начало: 18:10, время написания: 120 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на дистанте мы предусмотрим написание в онлайн формате. Подробности

Экзамен

Экзамен пройдет очно 28 июня (вторник), начало: 11:00, время написания: 150 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на официальном дистанте мы предусмотрим написание в онлайн формате. Подробности

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

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.

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