Матричные вычисления 20/21

О курсе

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

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

Лекции проходят на Покровке по вторникам в ауд. D510 (09:30 - 10:50)

Семинарист: Высоцкий Лев Игоревич

Семинары проходят онлайн по пятницам (13:00 - 14:20)

Полезные ссылки

Телеграм-чат курса:

Anytask курса: https://anytask.org/course/706

План курса

Лекции

1. Некоторые понятия матричного анализа

Матричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы. Матричные функции.

2. Малоранговое приближение матриц 1

Скелетное разложение матриц. Сингулярное разложение (SVD) и его основные свойства. Приближение матрицей меньшего ранга. CUR разложение.

3. Малоранговое приближение матриц 2 (0.5 лекции)

Приложения сингулярного разложения. Интерпретируемость CUR разложения и его приложения.

Малоранговое приближение многомерных массивов (0.5 лекции)

Кронекерово и тензорное произведения. Каноническое разложение многомерных массивов.

4. Малоранговое приближение многомерных массивов (0.5 лекции)

Разложение Таккера. Higher-order SVD (HOSVD). Приложения.

Вычислительные аспекты линейной алгебры 1 (0.5 лекции)

Представление чисел в компьютере. Обусловленность и вычислительная устойчивость.

5. Вычислительные аспекты линейной алгебры 2

Вычисление произведения матриц. Матрицы со специальной структурой: разреженные, тёплицевы матрицы, циркулянты, матрица Фурье. Быстрое преобразование Фурье. Пакеты программ для решения задач линейной алгебры.

6. Метод наименьших квадратов 1

QR разложение и способы его вычисления. Использование QR разложения для метода наименьших квадратов (МНК).

7. Метод наименьших квадратов 2 (0.5 лекции)

Псевдообратная матрица. Использование SVD разложения для МНК. Линейная регрессия. L1- и L2-регуляризации.

Прямые методы решения систем линейных уравнений 1

Теория возмущений и число обусловленности матрицы.

8. Прямые методы решения систем линейных уравнений 2

LU разложение, его связь с методом Гаусса. Ошибки округления и выбор ведущего элемента. Разложение Холецкого

9. Прямые методы решения систем линейных уравнений 3

Прямые методы решения больших разреженных систем линейных уравнений.

10. Итерационные методы решения систем линейных уравнений 1

Метод простой итерации. Метод наискорейшего спуска и его недостатки. Метод итераций Чебышева.

11. Итерационные методы решения систем линейных уравнений 2

Подпространства Крылова. Метод сопряженных градиентов.

12. Итерационные методы решения систем линейных уравнений 3

Метод обобщенных минимальных невязок (GMRES). Предобуславливание.

13. Задача на собственные значения 1

Степенной метод и обратная итерация. Их применения для анализа графов. Метод Ланцоша.

14. Задача на собственные значения 2

QR алгоритм и его модификации. Методы вычисления сингулярного разложения.

Семинары

1. Повторение базовых понятий о матрицах. Разложение Шура.

2. CUR и SVD разложения.

3. Тензорные разложения.

4. Устойчивость вычислительных алгоритмов.

5. Структурированные матрицы.

6. QR разложение.

7. Псевдообратные матрицы. МНК.

8. LU разложение.

9. Графы разреженных матриц.

10. Метод простой итерации.

11. Подпространства Крылова.

12. Применение Крыловских итерационных методов.

13. Приложения степенного метода и обратной итерации.

14. QR алгоритм.

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

Домашнее задание 1 Основы матричного анализа и применение SVD

Выдается: 01.09.20 Дедлайн: 16.09.20 в 23:59

Домашнее задание 2 CUR разложение и HOSVD

Выдается: 16.09.20 Дедлайн: 30.09.20 в 23:59

Домашнее задание 3 Структурированные матрицы и QR разложение

Выдается: 30.09.20 Дедлайн: 14.10.20 в 23:59

Домашнее задание 4 МНК и LU разложение

Выдается: 14.10.20 Дедлайн: 11.11.20 в 23:59

Домашнее задание 5 Итерационные методы для решения линейных систем

Выдается: 11.11.20 Дедлайн: 25.11.20 в 23:59

Домашнее задание 6 Итерационные методы для решения задачи на собственные значения

Выдается: 25.11.20 Дедлайн: 16.12.20 в 23:59

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

Проведение: предварительно - вторая неделя 2-го модуля

Экзамен

Устный экзамен в аудитории, разрешается пользоваться рукописным листком А4 при подготовке.

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

Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э))

ДЗ –– средняя оценка за домашние задания Б –– средняя оценка за бонусные задачи в ДЗ ПР — средняя оценка за самостоятельные работы на семинарах КР –– оценка за контрольную работу (проводится в первой половине 2-го модуля) Э –– устный экзамен

Округление арифметическое

Автоматы не предусмотрены

Литература

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.