Матричные вычисления 20/21 — различия между версиями
Kris ros (обсуждение | вклад) (Новая страница: «== О курсе == Курс по выбору для студентов для студентов 3 и 4 курса в 1-2 модулях. === Полезные…») |
Kris ros (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
Курс по выбору для студентов для студентов 3 и 4 курса в 1-2 модулях. | Курс по выбору для студентов для студентов 3 и 4 курса в 1-2 модулях. | ||
| + | |||
| + | '''Лектор:''' Рахуба Максим Владимирович | ||
| + | |||
| + | Лекции проходят на Покровке по вторникам в ауд. D510 (09:30 - 10:50) | ||
| + | |||
| + | '''Семинарист:''' Высоцкий Лев Игоревич | ||
| + | |||
| + | Семинары проходят онлайн по пятницам (13:00 - 14:20) | ||
=== Полезные ссылки === | === Полезные ссылки === | ||
| Строка 17: | Строка 25: | ||
Матричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы. Матричные функции. | Матричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы. Матричные функции. | ||
| − | '''2.Малоранговое приближение матриц 1''' | + | '''2. Малоранговое приближение матриц 1''' |
Скелетное разложение матриц. Сингулярное разложение (SVD) и его основные свойства. Приближение матрицей меньшего ранга. CUR разложение. | Скелетное разложение матриц. Сингулярное разложение (SVD) и его основные свойства. Приближение матрицей меньшего ранга. CUR разложение. | ||
| Строка 59: | Строка 67: | ||
Прямые методы решения больших разреженных систем линейных уравнений. | Прямые методы решения больших разреженных систем линейных уравнений. | ||
| − | |||
'''10. Итерационные методы решения систем линейных уравнений 1''' | '''10. Итерационные методы решения систем линейных уравнений 1''' | ||
| Строка 80: | Строка 87: | ||
QR алгоритм и его модификации. Методы вычисления сингулярного разложения. | QR алгоритм и его модификации. Методы вычисления сингулярного разложения. | ||
| − | |||
=== Семинары === | === Семинары === | ||
| Строка 98: | Строка 104: | ||
7. Псевдообратные матрицы. МНК. | 7. Псевдообратные матрицы. МНК. | ||
| − | 8. LU | + | 8. LU разложение. |
9. Графы разреженных матриц. | 9. Графы разреженных матриц. | ||
| Строка 115: | Строка 121: | ||
'''Домашнее задание 1''' | '''Домашнее задание 1''' | ||
| − | + | Основы матричного анализа и применение SVD | |
| − | Дедлайн: | + | |
| + | Выдается: 01.09.20 | ||
| + | Дедлайн: 16.09.20 в 23:59 | ||
'''Домашнее задание 2''' | '''Домашнее задание 2''' | ||
| − | + | CUR разложение и HOSVD | |
| − | Дедлайн: | + | |
| + | Выдается: 16.09.20 | ||
| + | Дедлайн: 30.09.20 в 23:59 | ||
'''Домашнее задание 3''' | '''Домашнее задание 3''' | ||
| − | + | Структурированные матрицы и QR разложение | |
| − | Дедлайн: | + | |
| + | Выдается: 30.09.20 | ||
| + | Дедлайн: 14.10.20 в 23:59 | ||
'''Домашнее задание 4''' | '''Домашнее задание 4''' | ||
| − | + | МНК и LU разложение | |
| − | Дедлайн: | + | |
| + | Выдается: 14.10.20 | ||
| + | Дедлайн: 11.11.20 в 23:59 | ||
'''Домашнее задание 5''' | '''Домашнее задание 5''' | ||
| − | + | Итерационные методы для решения линейных систем | |
| − | Дедлайн: | + | |
| + | Выдается: 11.11.20 | ||
| + | Дедлайн: 25.11.20 в 23:59 | ||
'''Домашнее задание 6''' | '''Домашнее задание 6''' | ||
| − | + | Итерационные методы для решения задачи на собственные значения | |
| − | + | ||
| − | + | Выдается: 25.11.20 | |
| − | + | Дедлайн: 16.12.20 в 23:59 | |
| − | Дедлайн: | + | |
| − | + | === Контрольная работа === | |
| − | + | ||
| − | + | ||
| − | + | Проведение: предварительно - вторая неделя 2-го модуля | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Экзамен === | === Экзамен === | ||
| − | + | Устный экзамен в аудитории, разрешается пользоваться рукописным листком А4 при подготовке. | |
| − | + | ||
| − | + | ||
=== Итоговая оценка за курс === | === Итоговая оценка за курс === | ||
| − | Итог = Округление(0. | + | Итог = Округление(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. | |
Версия 20:38, 31 августа 2020
Содержание
О курсе
Курс по выбору для студентов для студентов 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.
