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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Лекции)
(→‎О курсе)
Строка 12: Строка 12:
 
! Группа !! Преподаватель !! Учебные ассистенты || Чат в телеграм
 
! Группа !! Преподаватель !! Учебные ассистенты || Чат в телеграм
 
|-
 
|-
−
| 1 || Рахуба Максим Владимирович || Максим Васильев, Каримжан Айтхаджаев || [https://t.me/+Hj_1QPjwC38xNTJi tg]
+
| 1 || Рахуба Максим Владимирович || Максим Васильев, Каримжан Айтхаджаев ||  
 
|-
 
|-
−
| 2 || Рахуба Максим Владимирович || Александра Сендерович || [https://t.me/+Ch8p3rht0YJhMTAy tg]
+
| 2 || Рахуба Максим Владимирович || Александра Сендерович ||  
 
|-
 
|-
−
| 3 || Тяпкин Даниил Николаевич || Николай Юдин || [https://t.me/+Nxz3yqh1w44zNzUy tg]
+
| 3 || Тяпкин Даниил Николаевич || Николай Юдин ||  
 
|-
 
|-
−
| 4 || Самсонов Сергей Владимирович || Кирилл Королев || [https://t.me/+rmLqljCEV8c0ZDcy tg]
+
| 4 || Самсонов Сергей Владимирович || Кирилл Королев ||  
 
|-
 
|-
−
| 5 || Медведь Никита Юрьевич  || Ян Максимов || [https://t.me/+BuVLj9Nb4P8xZjJi tg]
+
| 5 || Медведь Никита Юрьевич  || Ян Максимов ||  
 
|-
 
|-
−
| 6 || Зароднюк Алёна Владимировна || Тимофей Грицаев, Юрий Максюта || [https://t.me/+CzT7VrOuTGswYmQy tg]
+
| 6 || Зароднюк Алёна Владимировна || Тимофей Грицаев, Юрий Максюта ||  
 
|}
 
|}
−
 
−
=== Полезные ссылки ===
 
−
 
−
[https://docs.google.com/spreadsheets/d/1ULs3fdGXLDK7e14mqBU8QlQQdjPPI1p6NT_eDGdBytI Разбиение по группам]
 
−
 
−
[https://docs.google.com/forms/d/e/1FAIpQLSf2jlgN3xJMBJXknA-E_AOoFNsIq1iQVooCGxwAyBkSFm6o4g/viewform?usp=sf_link Форма для студентов из 5 группы (онлайн), которые хотят перевестись в очную группу]
 
−
 
−
[https://t.me/+IaUcrCPEVd9jNWVi Телеграм-канал курса]
 
−
 
−
[https://t.me/+P8SYuAIKP2kwM2Fi Телеграм-чат курса]
 
−
 
−
[https://disk.yandex.ru/d/LX1ljriMmEhGQQ Папка с материалами]
 
−
 
−
[https://docs.google.com/spreadsheets/d/19Mh9tJhvuZADXgoWVqjjOOhYByqKcx3OtrpHtN_AGgE Ведомость]
 
−
 
−
[https://yadi.sk/i/9yxtvKpGnAhC0g Неофициальный конспект лекций 2021-2022 от студента (могут быть ошибки)]
 
−
 
−
[https://www.overleaf.com/read/rnbdttwsnjvb Подготовленные билеты к коллоквиуму 2022-2023 от студентов (могут быть ошибки)]
 
  
 
== План курса ==
 
== План курса ==

Версия 12:53, 22 марта 2024

О курсе

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

Первая лекция состоится 13.01, первые семинары - начиная с 16.01.

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

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

Группа Преподаватель Учебные ассистенты Чат в телеграм
1 Рахуба Максим Владимирович Максим Васильев, Каримжан Айтхаджаев
2 Рахуба Максим Владимирович Александра Сендерович
3 Тяпкин Даниил Николаевич Николай Юдин
4 Самсонов Сергей Владимирович Кирилл Королев
5 Медведь Никита Юрьевич Ян Максимов
6 Зароднюк Алёна Владимировна Тимофей Грицаев, Юрий Максюта

План курса

Если какие-то лекции не выложены или найдены ошибки на вики-странице - пишите @tgritsaev

Лекции

  1. Основы матричного анализа (13.01.2023). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Слайды Конспект (TeX)
  2. Малоранговое приближение матриц – 1 (20.01.2023). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Слайды Конспект (TeX)
  3. Малоранговое приближение матриц – 2 (27.01.2023). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Слайды
  4. Малоранговое приближение матриц – 3 (03.02.2023). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Доска
  5. Малоранговое приближение матриц – 4 (11.02.2023). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Доска
  6. Малоранговое приближение многомерных массивов (17.02.2023). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Доска Конспект (TeX)
  7. Вычисление QR-разложения (03.03.2023). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Доска
  8. Метод наименьших квадратов и псевдообратные матрицы (10.03.2023). Полноранговый случай. Общий случай. Регуляризация. Доска
  9. FFT и структурированные матрицы (17.03.2023). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Доска
  10. FFT и структурированные матрицы – 2 (24.03.2023). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Доска
  11. Умножение матриц, вычислительная устойчивость, обусловленность (07.04.2023). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2F6nSlfat2nhylRJ6P593MRs4A%2BKnifZ9CUD2KI346u3uqBmvck2t8cWc%2Bsde8vpVoq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flecture_notes%2Flecture11_fmatcomp23.pdf&name=lecture11_fmatcomp23.pdf Презентация
  12. Матричные ряды (14.04.2023). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. Доска
  13. Прямые методы решения линейных систем с плотными матрицами (21.04.2023). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. Доска
  14. Прямые методы решения линейных систем с разреженными матрицами (28.04.2023). Формула Шермана-Моррисона, тождество Вудберри. Разреженные матрицы: заполнения в L и U. Алгоритмы поиска P (матрицы перестановки). Доска
  15. Итерационные методы решения линейных систем (12.05.2023). Одношаговые методы: метод простой итерации, градиентный спуск, метод Чебышёва. Презентация
  16. Итерационные методы решения линейных систем – 2 (19.05.2023). Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. Конспект
  17. Итерационные методы решения линейных систем – 3 (26.05.2023). Сходимость CG. GMRES. Предобуславливание. Презентация
  18. Методы решения частичной задачи на собственные значения (02.06.2023). Eigenvalue problem как задача оптимизации. Степенной метод. Метод Релея-Ритца. Методы Ланцоша и Арнольди. Конспект
  19. Методы решения частичной и полной задач на собственные значения (09.06.2023). Числа Ритца в методе Ланцоша. QR-алгоритм. Конспект
  20. Теория возмущений (16.06.2022). Алгоритм для SVD. 1-я и 2-я теоремы Гершгорина. Теорема Бауэра-Файка. Число обусловленности для отдельный собственных значений. Конспект

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

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

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

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

Каждый студент 2 раза за семестр может просрочить дедлайн ДЗ на 1 сутки. Чтобы использовать эту возможность, достаточно просто загрузить работу после дедлайна.

  • Теоретическое ДЗ-1. Дедлайн: 06.02.23 в 23:59. Условие TeX
  • Практическое ДЗ-1. Дедлайн: 15.02.23 в 23:59. Условие
  • Теоретическое ДЗ-2. Дедлайн: 01.03.23 в 23:59. Условие TeX
  • Практическое ДЗ-2. Дедлайн: 12.03.23 в 23:59. Условие
  • Теоретическое ДЗ-3. Дедлайн: 26.03.23 в 23:59. Условие TeX
  • Практическое ДЗ-3. Дедлайн: 09.04.23 в 23:59. Условие
  • Теоретическое ДЗ-4. Дедлайн: 30.04.23 в 23:59. Условие TeX
  • Практическое ДЗ-4. Дедлайн: 21.05.23 в 23:59. Условие
  • Теоретическое ДЗ-5. Дедлайн: 29.05.23 в 23:59. Условие TeX
  • Практическое ДЗ-5. Дедлайн: 18.06.23 в 23:59. Условие

Коллоквиум

Коллоквиум пройдет 25 апреля и будет включать в себя материалы по первым 12 лекциям и семинарам. Более детальная информация о времени и месте проведения коллоквиума будет ближе к дате проведения. Планируется следующий формат коллоквиума (максимальное число баллов: 2 за определения + 3 за теорему с доказательством + 3 за решение задачи + 2 за доп. вопрос):

Сначала выдается билет, включающий в сумме 4 определения/формулировки утверждений из следующего списка. На подготовку дается 10 минут. При правильном ответе хотя бы на 3 из 4 определений/формулировок коллоквиум продолжается дальше, и вы получаете x-2 баллов, где x – число верно отвеченных вопросов. В противном случае за коллоквиум выставляется 0 баллов.

При успешной сдаче определений вам выдается билет, содержащий теоретический вопрос на доказательство, а а также задачу. На подготовку к ответу дается 40 минут. Теоретический вопрос на доказательства будет по теоремам из следующего списка. Максимальное число баллов за ответ на этот вопрос равно 3. Для подготовки к задачам советуем повторить теоретические домашние задания, а также задачи с семинаров.

В процессе беседы по предыдущим пунктам экзаменатор может задавать уточняющие вопросы. После ответа на пункты 2) и 3) экзаменатор задает дополнительный вопрос, например, задачу или вопрос, связанный с теорией. Ответ на дополнительный вопрос оценивается в 2 балла.

P.S.: Список определений/формулировок, а также теорем с доказательствами будет дополнен материалами с 11 и 12 лекций и семинаров, которые пройдут в 4-м модуле.

Экзамен

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

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

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