Прикладная линейная алгебра и численные методы

2020/2021

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Майнор

Кто читает: Департамент математики

Где читается: Факультет экономических наук

Когда читается: 3, 4 модуль

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Пионтковский Дмитрий Игоревич

Язык: русский

Кредиты: 5

Контактные часы: 120

Полная версия программы учебной дисциплины

Аннотация

В курсе будут рассмотрены вопросы линейной алгебры и близких областей, важные для приложений и вычислительных методов, но обычно не затрагиваемые в стандартных курсах. В их числе понятие псевдообратной матрицы, интерполяция и аппроксимация функций, основы теории нормированных пространств, теория многочленов Чебышева, элементы теории возмущений, оценки на погрешности решений систем линейных уравнений и матричных вычислений, матричные итеративные методы, символьные решения систем алгебраических уравнений и др. Они служат основой работы с данными не только в естественно-научных расчетах, но и в экономических, технических и социальных задачах.

Цель освоения дисциплины

Огромные массивы данных ежедневно превращаются в прогнозы, модели, в устройства и приложения, окружающие нас. Превращение может начаться с физических или статистических моделей, с задач оптимизации или с дифференциальных уравнений, но как только мы из двух-трехмерного мира элементарных моделей переходим в мультиразмерный мир реальных данных, в итоге задача решается методами линейной алгебры. Суть линейной алгебры проста: это матричные и векторные вычисления. Как их применить для описания сложных явлений? Об этом наш курс. Мы начнем с методов обращения необратимых матриц, поговорим про приближенные и точные решения систем линейных уравнений, разобрав модель линейной регрессии. Обсудим связи линейной алгебры с задачами интерполяции и аппроксимации функций. Самая теоретическая часть курса – теория нормированных пространств, обобщающая естественные способы измерения векторов, матриц и функций. А самая практическая – наверное, теория неотрицательных матриц и способы нахождения их положительных собственных векторов, включая тот собственные вектор, который принес первые миллиарды долларов создателям поисковика Google. Мы коснемся популярного у дизайнеров метода приближения ломаных гладкими кривыми, обсудим классические линейные производственные модели, упомянем один из методов сжатия изображений, встретимся с индексами влияния в социальных сетях, изучим основы символьных алгебраических вычислений. Все темы курса будут сопровождаться компьютерной практикой. Слушатели курса также приглашаются сделать доклад по приложениям линейной алгебры в близким им областям.

Планируемые результаты обучения

Студент будет владеть понятием псевдообратной матрицы, знать ее определение, основные свойства и способы вычисления. Будет владеть основами метода наименьших квадратов, уметь решать линейные задачи на метод наименьших квадратов с помощью псевдообратной матрицы. Получит понятие о линейной регрессии, применит его на примерах решения практических задач.
Студент овладеет следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: 1) Задача полиномиальной интерполяции. 2) Многочлен Лагранжа. 3) Интерполяция с кратными узлами, многочлен Эрмита (Лагранжа-Сильвестра). 4) Полиномиальные сплайны. 5) Кривые Безье, сплайны Безье.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Матричные разложения и их приложения. Метод Гаусса и LU разложение, применение LU разложения к решению систем. Матричные разложения и их приложения к обработке изображений и к машинному обучению. Разложения полного ранга. QR разложение и сингулярное (SVD) разложение. Применение разложений полного ранга и SVD к вычислению псевдообратной матрицы.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Метрические и нормированные пространства. Эквивалентность норм в конечномерном пространстве. Теорема Минковского о единичном шаре в n-мерном пространстве. Матричные нормы, их связь с векторными нормами. Нормы Гельдера и Фробениуса. Спектральный радиус, связь с нормами.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Многочлены Чебышева, их построение, основные свойства. Основные нормы и скалярные произведения в пространствах функций. Многочлены, наименее уклоняющиеся от нуля. Ортогональные системы полиномов. Аппроксимация функций многочленами.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Число обусловленности матрицы. Связь с обусловленностью систем линейных уравнений. Оценки на погрешность решения линейных систем и вычисления обратной матрицы. Примеры приближенного решения систем линейных уравнений.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Связь задачи приближения матрицы матрицей малого ранга с сингулярным разложением. Основы анализа главных компонент. Регуляризация.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Метод простой итерации. Приведение системы к виду, пригодному для итерации. Метод Зейделя и метод Якоби.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Теорема Перрона-Фробениуса. Итеративный метод нахождения собственного вектора. Линейная производственная модель и продуктивные матрицы. Алгоритм PageRank и индексы влияния в социальных сетях.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Оценки собственных значений, теоремы Гершгорина. Методы нахождения характеристического многочлена (Крылова и Данилевского). Циклические клетки и фробениусова нормальная форма матрицы. Итеративные методы нахождения собственных значений. Методы нахождения сингулярных значений.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: Достаточные признаки сходимости матричных рядов. Жорданова форма, ее применение для вычисления функция от матриц. Многочлены Лагранжа-Сильвестра.
Студенты овладеют следующими понятиями, будет уметь решать связанные с ними прикладные и теоретические задачи: упорядоченная полугруппа, базис Гребнера, алгоритмическая теория исключения, нульмерный полиномиальный идеал.

Содержание учебной дисциплины

Псевдообратная матрица и метод наименьших квадратов
Псевдообратная матрица, ее определения, основные свойства и способы вычисления. Основы метода наименьших квадратов, решение линейной задачи на метод наименьших квадратов с помощью псевдообратной матрицы. Понятие о линейной регрессии, примеры решения практических задач.
Полиномиальная интерполяция
Матричные разложения.
Метрики и нормы. Матричные нормы.
Аппроксимация функций многочленами.
Элементы теории возмущений.
Приближение матрицы матрицей малого ранга и идея анализа главных компонент.
Итеративные методы.
Неотрицательные матрицы.
Проблема собственных значений.
Функции от матриц.
Алгебраические уравнения и символьные вычисления.

Элементы контроля

Контрольная работа (очная или заочная с индивидуальными вариантами задач)
Контрольная работа после 3 модуля (очная или заочная с индивидуальным набором заданий)

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
Итоговая оценка вычисляется по формуле Min(10, 0.5 * (Контрольная работа после 3 модуля)+ 0.5 * (Экзаменационнная работа) + 0.5 * (Выступление с докладом по индивидуальному проекту)

Программа дисциплины