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 разложение	Домашние работы; Письменные тесты	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции.
2	Ортогонализация и QR разложение; Ортогональные проекции, метод наименьших квадратов	Домашние работы; Письменные тесты	В домашние работы включаются задачи, аналогичные разобранным, а также нерешенные во время семинарских занятий. Дополнительно выдается практическая домашняя работа на языке Python с реконструкцией томографического снимка. На каждом семинаре проводится письменный тест из нескольких вопросов по темам предыдущей лекции.
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. Тыртышников, Е. Е. Матричный анализ и линейная алгебра. – М.: ФИЗМАТЛИТ, 2007. ISBN: 978-5-9221-0778-5
2. Gilbert Strang. Linear Algebra and Its Applications, 4th Edition, Brooks Cole, 2006. ISBN: 9780030105678

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

1. Golub, Gene Howard, and Charles F. Van Loan. Matrix Computations. Vol. 3. JHU Press, 2013.

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

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

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

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

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