Основы матричных вычислений 2022/2023

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

О курсе

Курс для студентов 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. Машинные числа. Вычислительная устойчивость. Обусловленность. Презентация
  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=84846»