BSc: ComputationalLinearAlgebra

Вычислительная линейная алгебра

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а):

1. Краткая характеристика дисциплины

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

2. Перечень планируемых результатов обучения

Целью освоения дисциплины является освоение методов линейной алгебры, использующихся в анализе данных и естественных науках.

Задачами дисциплины являются

1. Освоение основных матричных разложений и алгоритмов их вычислений;

2. Применение матричных разложений для решения задач линейной алгебры, в частности линейных систем, задачи наименьших квадратов, задачи на собственные значения;

3. Освоение простейших итерационных алгоритмов;

4. Знакомство с библиотеками вычислительной линейной алгебры и их использование в прикладных задачах.

Общая характеристика результата обучения по дисциплине

Знания:

1. определений и свойств матриц различного вида: симметричные, ортогональные, ортопроекторы, псевдообратные, матрицы перестановок;

2. матричных разложений: LU, QR, собственное, скелетное, SVD;

3. формулировок алгоритмов вычисления матричных разложений;

4. метода наименьших квадратов;

5. итерационных методов: степенной метод, метод простой итерации; метод попеременных наименьших квадратов.

Умения: сформированы умения численно решать задачи линейной алгебры: системы линейных уравнений, задачу на собственные значения, задачу наименьших квадратов, построение наилучшего малорангового приближения матрицы.

Навыки (владения): сформировано владение навыками:

1. использовать инструменты линейной алгебры для математической постановки конкретной прикладной задачи;

2. применять освоенные инструменты для численного решения конкретной задачи.

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Линейные системы и LU разложение (3 лекции)	- (Повторение) Системы линейных уравнений, общий вид решения, метод Гаусса; - LU разложение, его существование и единственность, связь с методом Гаусса; - LU разложение ленточных матриц; - матрицы перестановок, проблема роста элементов, LU разложение с выбором ведущего элемента; - число арифметических операций при вычислении LU разложения. Неоптимальность Гауссовского исключения (Штрассен).
2.	Ортогонализация и QR разложение (2 лекции)	- (Повторение) Скалярное произведение, длина вектора. - Ортогональные матрицы и их свойства; - Популярные ортогональные базисы для сжатия данных; - Матрица Фурье, быстрое преобразование Фурье, дискретная теорема о свертке. - QR разложение и метод ортогонализации Грама-Шмидта. - Неустойчивость классического метода Грама-Шмидта, модифицированный алгоритм.
3.	Ортогональные проекции, метод наименьших квадратов (2 лекции)	- (Повторение) Подпространства, образ матрицы; - Проекции на подпространства, матрицы ортогональных проекций (ортопроекторы), формула ортопроектора на образ матрицы; - Метод наименьших квадратов, алгоритм решения с помощью QR разложения. - Метод регуляризации Тихонова, l1 регуляризация.
4.	Задача на собственные значения, собственное разложение (2-3 лекции)	- Собственные значения и собственные векторы, диагонализация матриц, подобные матрицы, собственное разложение; - Диагонализуемость симметричных матриц; - Матричная экспонента, ее приложения; - Параметризация ортогональных матриц с помощью матричной экспоненты; - QR алгоритм для симметричных матриц; - Степенной метод, PageRank.
5.	Сингулярное разложение (2 лекции)	- Скелетное разложение и определение ранга через разделение переменных (тензорный ранг); - Положительно определенные матрицы, матрица Грама; - Теорема о существовании сингулярного разложения, способы его вычисления; - Связь скелетного и сингулярного разложений, приведение одного разложения к другому; - Псевдообратные матрицы.
6.	Построение малоранговых приближений (1 лекция)	- Фробениусова норма, формула через след матрицы; - Теорема Эккарта-Янга; - Задача заполнения матрицы; - Метод попеременных наименьших квадратов (ALS).
7.	Итерационные методы для решения линейных систем (2 лекции)	- Операция матрично-векторного умножения для разреженных матриц; - Метод простой итерации; - Вариационные формулировки для линейных систем; - Понятие о методах решения линейных систем на Крыловских подпространствах (CG, GMRES); - Предобуславливание линейных систем.

Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1	Линейные системы и LU разложение	Домашние работы; Письменные тесты	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции. Вопросы для обсуждения: 1. Каким образом LU разложение используется для решения линейных систем уравнений и какова его роль в численных методах вычислительной линейной алгебры? Какие преимущества предоставляет LU разложение при решении систем уравнений в сравнении с прямыми методами? (ОПК-1.1) Какие алгоритмы и методы вычислительной линейной алгебры основаны на LU разложении матриц? Какие практические задачи и прикладные области могут быть решены с использованием LU разложения, и как данное разложение способствует оптимизации вычислительных процессов в рамках информатики, программирования и численных методов? (ОПК-1.1) Объясните, как LU разложение матриц используется для решения линейных систем уравнений и как это помогает выпускнику вычислительной линейной алгебры эффективно решать стандартные профессиональные задачи, требующие численных методов и математического моделирования. (ОПК-1.2) Почему понимание принципов LU разложения и его применение в численных методах вычислительной линейной алгебры являются ключевыми для успешного решения задач в области информатики, программирования и инженерных наук? Какие конкретные профессиональные навыки и компетенции развиваются у студентов благодаря изучению этого раздела дисциплины? (ОПК-1.2)
2	Ортогонализация и QR разложение; Ортогональные проекции, метод наименьших квадратов	Домашние работы; Письменные тесты	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. Дополнительно выдается практическая домашняя работа на языке Python с реконструкцией томографического снимка. На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции. Вопросы для обсуждения: Как метод наименьших квадратов может быть применен в экономике для аппроксимации данных и оценки параметров экономических моделей? Приведите примеры использования этого метода в различных областях экономической деятельности. (УК-9.1) Какие основные принципы лежат в основе метода наименьших квадратов и какие экономические концепции он отражает? Объясните, каким образом применение этого метода способствует улучшению прогнозирования экономических показателей и принятию обоснованных решений в различных сферах жизнедеятельности. (УК-9.1) Каким образом метод наименьших квадратов используется для аппроксимации данных и оценки параметров экономических моделей, и какие преимущества он предоставляет при принятии обоснованных решений в экономике? Приведите конкретные примеры применения этого метода в финансовой аналитике, маркетинге или других областях экономической деятельности. (УК-9.2) Как важно понимание ортогонализации, QR разложения и ортогональных проекций для успешного применения метода наименьших квадратов в экономике? Объясните, как эти концепции помогают улучшить точность аппроксимации данных, сделать более надежные прогнозы и принять обоснованные решения при анализе экономических показателей. (УК-9.2) Каким образом ортогонализация и QR разложение используются для улучшения аппроксимации данных и повышения точности прогнозов в экономическом анализе? Какие преимущества предоставляют эти методы при анализе экономических показателей и принятии обоснованных решений? (УК-9.3) Как ортогональные проекции и метод наименьших квадратов помогают оценивать параметры экономических моделей, аппроксимировать данные и снижать ошибку прогнозирования? Какие конкретные примеры использования этих методов можно привести в контексте финансового анализа или маркетинговых исследований для принятия обоснованных экономических решений? (УК-9.3)
3	Задача на собственные значения, собственное разложение	Домашние работы; Письменные тесты; Коллоквиум	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции. Коллоквиум – устный опрос по пройденным темам
4	Сингулярное разложение; Построение малоранговых приближений	Домашние работы; Письменный тест	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. Дополнительно выдается практическая домашняя работа на языке Python с построением рекомендательной системы на основе матричной факторизации (реализовать ALS, построить рекомендации с помощью ортопроектора). На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции.
5	Итерационные методы для решения линейных систем	Домашние работы; Письменные тесты	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции.

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Линейные системы и LU разложение	1. Найдите $LU$ разложение $A$ и решите линейную систему $Ax=b$ при $A={\begin{bmatrix}1&1&0\\2&4&-1\\-1&3&-1\end{bmatrix}},\quad b={\begin{bmatrix}1\\0\\1\end{bmatrix}}$. 2. Найдите $LU$ разложение матрицы $A={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}$. 3. Покажите, что в $LU$ разложении трехдиагональной матрицы матрицы $L$ и $U$ являются бидиагональными. 4. Найдите $LU$ разложение и $LUP$ разложение с частичным выбором ведущего элемента в матрице $A={\begin{bmatrix}\varepsilon &1\\1&1\end{bmatrix}}$ при $|\varepsilon |\ll 1$. Прокомментируйте на этом примере проблему роста элементов в $LU$ разложении. 5. Выразить детерминант матрицы через факторы ее $LU$ разложения.
2.	Ортогонализация и QR разложение	1. Найдите QR разложение нескольких заданных матриц. 2. Реализуйте на языке Python алгоритмы Грама-Шмидта и его модифированную версию. Протестируйте их на случайной матрице и на матрице Гильберта порядка $5$ и $100$. Прокомментируйте полученные результаты. 3. Ортогонализуйте систему мономов $\{1,x,x^{2}\}$ на интервале $(0,1)$ относительно скалярного произведения $(f,g)=\int _{0}^{1}f(x)g(x)\,dx$. 4. Покажите, что матрица вида $H(u)=I-2uu^{T}$ (матрица Хаусхолдера), $|u|=1$, является ортогональной. 5. Покажите ортогональность матрицы вращений Гивенса.
3.	Ортогональные проекции, метод наименьших квадратов	1. Решить на языке Python задачу наименьших квадратов для некоторого набора данных. Исследовать зависимость от параметра регуляризиации. 2. Постройте матрицу ортогональной проекции на образ некоторых заданных матриц. 3. Предложите алгоритм матрично-векторного умножения ортопроектора на подпространство $\mathrm {Im} (A)^{\perp }$, где $A\in \mathbb {R} ^{n\times r}$, $r\leq n$ с асимптотической сложностью ${\mathcal {O}}(nr^{2})$ и реализуйте его на языке Python. 4. Проверьте ортогональность матрицы дискретного косинус преобразования размера $4\times 4$.
4.	Задача на собственные значения, собственное разложение	1. Найти собственные значения, собственные векторы и собственное разложение нескольких заданных матриц размеров $2\times 2$ и $3\times 3$; 2. Найти собственные значения и собственные векторы матрицы Хаусхолдера, обсудить их геометрический смысл; 3. Найти собственные значения Жордановой клетки и обосновать невозможность построить ее собственное разложение; 4. Покажите, что собственные значения симметричной матрицы являются вещественными; 5. Вычислите матричную экспоненту несколько заданных матриц. 6. Реализуйте на языке Python QR алгоритм. 7. Реализуйте степенной метод и запустите его для задачи PageRank на нескольких заданных графов.
5.	Сингулярное разложение	1. Найти скелетное разложение с минимальным возможным значением ранга для матриц с элементами $a_{ij}=j$, $a_{ij}=2^{i+j}$ и $a_{ij}=i+j$. 2. Найти сингулярное разложение нескольких заданных матриц размера $2\times 2$. 3. Найти сингулярное разложение матрицы с элементами $a_{ij}=j$. 4. Показать неустойчивость алгоритма вычисления SVD через матрицу Грама на примере матрицы: $A={\begin{bmatrix}1&1\\0&{\sqrt {\varepsilon }}\end{bmatrix}}$ для достаточно малых $\varepsilon$. 5. Реализуйте на языке Python алгоритм приведения скелетного разложения к сингулярному. 6. Вычислить псевдообратную для нескольких заданных матриц.
6.	Построение малоранговых приближений	1. Покажите, что для любых ортогональных матриц $U$, $V$ выполняется $\|UAV\|_{F}=\|A\|_{F}.$ 2. Покажите, что $\|A\|_{F}={\sqrt {\sigma _{1}(A)^{2}+\ldots +\sigma _{r}(A)^{2}}}$, где $r=\mathrm {rank} (A)$. 3. Вывод формулы для ALS метода для построения наилучшего приближения матрицы во Фробениусовой норме. 4. Запустите ALS метод по формулам из предыдущей задачи и для заданной матрицы сравните по норме полученное приближение заданного ранга $r$ с наилучшим приближением ранга $r$.
7.	Итерационные методы для решения линейных систем	1. Реализовать на языке Python алгоритм быстрого матрично-векторного произведения матрицы из PageRank с ненулевым демпинг фактором. 2. На языке Python собрать разреженную матрицу в coo формате, соответствующую закону Кирхгофа некоторой простой электрической цепи. Решить линейную систему с этой матрицей с несколькими указанными итерационными методами и вариантами предобуславливателя.

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Линейные системы и LU разложение	LU разложение, его существование. Выбор ведущего элемента, LUP разложение. Число арифметических операций при вычислении LU разложения. Неоптимальность Гауссовского исключении.
2.	Ортогонализация и QR разложение	Ортогональные матрицы. QR разложение, его существование. Алгоритмы вычисления QR разложения.
3.	Ортогональные проекции, метод наименьших квадратов	Ортопроекторы. Метод наименьших квадратов (МНК). Алгоритмы решения МНК. l1 и l2 регуляризация.
4.	Задача на собственные значения, собственное разложение	Задача на собственные значения, собственное разложение. Диагонализуемость симметричных матриц. Матричная экспонента. QR алгоритм. Степенной метод.
5.	Сингулярное разложение	Скелетное разложение, его существование и единственность. Положительно определенные матрицы. Сингулярное разложение. Псевдообратные матрицы.
6.	Построение малоранговых приближений	Фробениусова норма, ее свойства. Теорема Эккарта-Янга. Метод попеременных наименьших квадратов.
7.	Итерационные методы для решения линейных систем	Метод простой итерации. Линейная система как решение задачи минимизации функционалов. Крыловские подпространства, понятие о методах CG, GMRES. Предобуславливатели.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Нижне- и вернетреугольные матрицы;
2. LU разложение;
3. Существование и единственность LU разложения;
4. Ленточные матрицы;
5. LU разложение ленточных матриц;
6. Проблема роста элементов;
7. Матрица перестановки;
8. Выбор ведущего элемента и LUP разложение;
9. Число арифметических операций при вычислении LU разложения;
10. Сложность матричного умножения и алгоритм Штрассена;
11. Ортогональная матрица;
12. Определение образа матрицы;
13. Базисы для сжатия и анализа данных: матрица дискретного косинус преобразования, матрица Фурье, матрица преобразования Хаара;
14. QR разложение;
15. Существование и единственность QR разложения;
16. Метод ортогонализации Грама-Шмидта как способ вычисления QR разложения;
17. Модифицированный алгоритм Грама-Шмидта;
18. Проекции на подпространства;
19. Ортопроектор;
20. Формула ортопроектора на образ матрицы;
21. Формулировка метода наименьших квадратов (МНК);
22. Алгоритм решения МНК с помощью QR разложения;
23. l1 и l2 регуляризации МНК;
24. Задача на собственные значения;
25. Характеристический полином;
26. Подобные матрицы;
27. Собственное разложение;
28. Диагонализуемость симметричных матриц;
29. Матричная экспонента;
30. Параметризация ортогональных матриц с помощью матричной экспоненты;
31. Формулировка QR алгоритма;
32. Степенной метод, его сходимость;
33. PageRank;
34. Скелетное разложение;
35. Определение ранга через разделение переменных’
36. Положительно определенные матрицы;
37. Матрица Грама;
38. Сингулярное разложение;
39. Алгоритм вычисления сингулярного разложения через матрицу Грама, его устойчивость;
40. Приведение скелетного разложения к виду сингулярного разложения;
41. Псевдообратные матрицы.
42. Запись решения МНК и ортопроекторов через псевдообратные матрицы;
43. Фробениусова норма, формула через след матрицы;
44. Теорема Эккарта-Янга;
45. Задача заполнения матрицы;
46. Метод попеременных наименьших квадратов (ALS);
47. CSR и COO форматы хранения разреженных матриц;
48. Метод простой итерации;
49. Линейная система как решение задачи минимизации функционала энергии для симметричных положительно определенных матриц;
50. Линейная система как решение задачи минимизации функционала нормы невязки в общем случае;
51. Понятие о методах решения линейных систем на Крыловских подпространствах (CG, GMRES);
52. Предобуславливание линейных систем: предобуславливатель Якоби, Гаусс-Зейделя, ILU.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

1. Гололобов, С. В. Вычислительные методы анализа и линейной алгебры. В 2 частях. Ч.1: учебно-методическое пособие / С. В. Гололобов, А. М. Мацокин. — Новосибирск: Новосибирский государственный университет, 2019. — 160 c. — Режим доступа: https://www.iprbookshop.ru/93807.html — ЭБС «IPRbooks».
2. Романников, А. Н. Линейная алгебра: учебное пособие / А. Н. Романников. — Москва: Евразийский открытый институт, Московский государственный университет экономики, статистики и информатики, 2007. — 124 c. — Режим доступа: https://www.iprbookshop.ru/10890.html — ЭБС «IPRbooks».

Список дополнительной литературы:

1. Алания, Л. А. Сборник задач по аналитической геометрии и линейной алгебре / Л. А. Алания, С. М. Гусейн-Заде, И. А. Дынников. — Москва: Логос, 2005. — 376 c. — Режим доступа: https://www.iprbookshop.ru/9121.html — ЭБС «IPRbooks».
2. Гусак, А. А. Аналитическая геометрия и линейная алгебра. Примеры и задачи: учебное пособие / А. А. Гусак. — Минск: ТетраСистемс, 2011. — 265 c. — Режим доступа: https://www.iprbookshop.ru/28035.html — ЭБС «IPRbooks».

Методические указания для обучающихся по освоению дисциплины

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Устный/письменный опрос	Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Подготовка к промежуточной аттестации	При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Практические (лабораторные) занятия	Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Тестирование (устное/письменное)	При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
Индивидуальная работа	При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов	Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции

Информационно – коммуникационная технология, Педагогика сотрудничества, Традиционные технологии, Модульная технология