BSc: ComputationalMathematics

Вычислительная математика

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

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

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

Программу разработали: Тыртышников Е.Е. и Холодов Я.А.

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

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

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

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

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

• Освоение основных численных алгоритмов и методов, применимых для решения математических задач.
• Изучение численной дифференциации и интеграции и их практическое применение.
• Разработка навыков решения систем нелинейных и линейных алгебраических уравнений численными методами различных типов.
• Овладение методами интерполяции и регрессии для анализа и предсказания данных.
• Получение практического опыта в численном решении систем нелинейных дифференциальных уравнений.

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

Знания:

• Основные принципы численного решения математических задач.
• Принципы численного дифференцирования и интегрирования.
• Различные методы численного решения систем нелинейных алгебраических уравнений.
• Методы интерполяции и регрессии.
• Основы численного решения систем нелинейных дифференциальных уравнений.

Умения:

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

Навыки (владения):

• Решение типичных математических задач с использованием численных методов.
• Проведение нелинейной регрессии и интерполяции.
• Выполнение численной дифференциации и интегрирования.
• Решение систем нелинейных алгебраических уравнений численными методами.
• Решение систем нелинейных дифференциальных уравнений численными методами.

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

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

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

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

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Численное дифференцирование и интегрирование, интерполяция функций, решение систем линейных алгебраических уравнений	Выполнить численное дифференцирование методом неопределенных коэффициентов. Выполнить интерполяцию функции, используя сплайны. Выполнить численное интегрирование, используя формулы квадратур. Решить систему линейных алгебраических уравнений, используя методы итерации. Решить систему линейных алгебраических уравнений, используя методы вариации.
2.	Решение нелинейных алгебраических уравнений и систем. Решение ОДУ и УПД. Дискретные ряды Фурье.	Выполнить численное решение нелинейных алгебраических уравнений и систем. Выполнить численное решение задачи с начальными условиями для обыкновенных дифференциальных уравнений (ОДУ). Выполнить численное решение задачи с краевыми условиями для ОДУ. Выполнить численное решение ОДУ и УПД с использованием дискретных рядов Фурье. Выполнить численное решение уравнений в частных производных (УПД) с помощью метода конечных разностей.

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

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1	Численное дифференцирование и интегрирование, интерполяция функций, решение систем линейных алгебраических уравнений	Разработка отдельных частей кода программного продукта Домашние задания и групповые проекты Промежуточная оценка Тестирование (письменное или компьютерное) Обсуждения	Как выполнить численное дифференцирование методом неопределенных коэффициентов? Как выполнить интерполяцию функции с помощью сплайнов? Как выполнить численное интегрирование с помощью квадратурных формул? Как решить систему линейных алгебраических уравнений итерационными методами? Как решить систему линейных алгебраических уравнений вариационными методами?
2	Решение нелинейных алгебраических уравнений и систем. Решение ОДУ и УЧП. Дискретный ряд Фурье.	Разработка отдельных частей кода программного продукта Домашние задания и групповые проекты Промежуточная оценка Тестирование (письменное или компьютерное) Обсуждения	Как выполнить численное решение нелинейных алгебраических уравнений и систем? Как выполнить численное решение начальной задачи для обыкновенных дифференциальных уравнений (ОДУ)? Как выполнить численное решение краевых задач для ОДУ? Как выполнить численное решение ОДУ и УЧП с помощью дискретных рядов Фурье? Как выполнить численное решение УЧП методами конечных разностей?

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

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Численное дифференцирование и интегрирование, интерполяция функций, решение систем линейных алгебраических уравнений	Вычислите интеграл функции из "чёрного ящика". Функция будет предоставлена вам во время компиляции в виде заголовочного файла ${\textstyle blackbox.h}$. В самом начале вашей программы вы должны считать одно целое число ${\textstyle n}$ из стандартного ввода и вызвать функцию ${\textstyle blackbox-init(n)}$. Функцию ${\textstyle blackbox-init}$ следует вызывать только один раз. Все остальные функции должны быть вызваны только после ${\textstyle blackbox-init}$. Вызов ${\textstyle blackbox_{i}nit}$ с аргументом, отличным от того, который был предоставлен через стандартный ввод, приводит к неопределённому поведению. Когда вам нужно получить значение функции в точке ${\textstyle x}$, вы должны вызвать ${\textstyle blackbox(x)}$. Гарантируется, что эта функция является потокобезопасной. ${\textstyle x}$ должен находиться в диапазоне [-1; 1]. Если вам нужно получить максимальное абсолютное значение ${\textstyle k}$-й производной функции из "чёрного ящика" на интервале интегрирования, вы должны вызвать ${\textstyle blackbox-df(k)}$. Значение ${\textstyle k}$ должно быть целым числом от 1 до 6. Для проверки, осциллирует ли функция из "чёрного ящика", вы должны вызвать ${\textstyle blackbox-period()}$. Возвращаемое значение будет длиной периода, если функция осциллирует, и 0 в противном случае. Требуемая абсолютная точность составляет ${\textstyle 10^{-}9}$. Усечённый файл ${\textstyle blackbox.h}$ (реализующий только одну из возможных функций "чёрного ящика") и пример (несовершенный) решения ${\textstyle solution.cpp}$ доступны вам на вкладке "Файлы" в PCMS. Вы должны отправить только свой файл ${\textstyle solution.c/solution.cpp}$. Соответствующий файл ${\textstyle blackbox.h}$ будет предоставлен тестовой системой. Вы не должны пытаться проводить reverse-engineering "чёрного ящика" и/или взаимодействовать с ним каким-либо другим способом, кроме перечисленных выше четырёх функций. Задача проста: вам нужно подогнать набор точек под полином 9-й степени ${\textstyle y=a_{9}x^{9}+a_{8}x^{8}+...+a_{1}x+a_{0}}$. Ваша программа получает следующий поток команд: ADD ${\textstyle x}$ ${\textstyle y}$ Считывает значения ${\textstyle x}$ и ${\textstyle y}$. FIT Выведите коэффициенты для полинома, подогнанного под все точки, считанные с начала программы. В каждом тесте у вас не будет более 13 команд FIT. END Выводит коэффициенты для полинома, подогнанного под все точки, считанные с начала программы, и завершает работу. Вы получите не более 107 команд до END. Решите систему линейных алгебраических уравнений (СЛАУ) ${\textstyle Ax=b}$ с остаточной ошибкой не более ${\textstyle 10^{-9}}$. И матрица ${\textstyle A}$ очень хороша: невырожденная, симметричная и строго диагонально доминирующая. Однако у вас нет явного представления о матрице ${\textstyle A}$. Вы можете только получить результат её умножения на вектор. У вас есть несколько функций черного ящика, через которые вы работаете с СЛАУ: void ${\textstyle blackbox-init()}$ – инициализирует внутренние структуры данных черного ящика. Эту функцию следует вызывать в самом начале программы! Ни одна другая функция черного ящика не должна быть вызвана до неё, и не должно быть чтения из ${\textstyle stdin}$. int ${\textstyle blackbox-size()}$ – возвращает количество уравнений (равное количеству неизвестных) системы. Количество уравнений находится между 10 и 10000 (включительно). void ${\textstyle blackbox-mult}$ (const double ${\textstyle *x}$, double ${\textstyle *out}$) – вычисляет произведение ${\textstyle A}$ и вектора ${\textstyle x}$, записывает результаты в out. Указатели Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x} и out должны указывать на разные участки памяти размером не менее ${\textstyle blackbox-size()*sizeof(double)}$ байт каждый. void ${\textstyle blackbox-rhs(double*b)}$ – записывает правую часть СЛАУ (т.е., вектор ${\textstyle b}$) в массив ${\textstyle b}$. Указатель ${\textstyle b}$ должен указывать на участок памяти размером не менее ${\textstyle blackbox-size()*sizeof(double)}$ байт. void ${\textstyle blackbox-submit(double*solution)}$ – записывает результат программы. Массив solution должен содержать решение СЛАУ: ${\textstyle blackbox-size()}$ значение типа double. Это должна быть последняя функция, вызываемая вашей программой (помимо return 0;).
2.	Решение нелинейных алгебраических уравнений и систем. Решение ОДУ и УПД. Дискретные ряды Фурье.	Создайте программное обеспечение для нового приёмника GPS/GLONASS. Навигация по спутникам работает следующим образом (конечно, это довольно упрощённое описание реальной ситуации). Существует ${\textstyle N}$ < 30 спутников. Каждый спутник передаёт своё положение (${\textstyle x_{i};y_{i};z_{i}}$) и синхронизированное высокоточное время ${\textstyle t_{i}}$. Эти сигналы занимают время на достижение приёмника (например, в вашем смартфоне). Если приёмник имеет положение ${\textstyle x}$; ${\textstyle y}$; ${\textstyle z}$ и получает сигнал в момент времени ${\textstyle t}$, справедливо следующее уравнение (называемое "Навигационным уравнением"): ${\textstyle (x-x_{i})^{2}+(y-y_{i})^{2}+(z-z_{i})^{2}=(t-t_{i})^{2}}$ Как видно, у нас четыре неизвестных (положение приёмника ${\textstyle x}$; ${\textstyle y}$; ${\textstyle z}$ и точное время ${\textstyle t}$, когда он получил сигнал). Таким образом, нам нужно как минимум ${\textstyle N}$ = 4 спутника для определения местоположения приёмника. Система из ровно четырёх навигационных уравнений в общем случае может иметь несколько решений. Но обычно видно более ${\textstyle N}$ > 4 спутников, и у нас имеется переопределённая система нелинейных уравнений (из-за шума уравнения не могут быть определены точно). В этом случае нашей целью является минимизация суммы квадратов остатков: ${\textstyle Sum_{i}((x-x_{i})^{2}+(y-y_{i})^{2}+(z-z_{i})^{2}-(t-t_{i})^{2})\xrightarrow {} min}$. Ваша программа должна непрерывно считывать данные с виртуального приёмника GPS и выводить положение в каждый момент времени до тех пор, пока сигнал не будет потерян. Количество спутников (и их порядок) может изменяться. Начальное положение неизвестно, но положение между последовательными чтениями не меняется слишком сильно. Требуемая точность задаётся выражением ${\textstyle Sum_{i}((x-x_{i})^{2}+(y-y_{i})^{2}+(z-z_{i})^{2}-(t-t_{i})^{2})<10^{-6}}$. Гарантируется, что такое решение существует. Координаты ${\textstyle x}$; ${\textstyle y}$; ${\textstyle z}$ находятся в диапазоне [-10; 10], время ${\textstyle t}$ находится в диапазоне [-1000; 1000]. Количество считываний гарантированно не превысит ${\textstyle 10^{5}}$. Создайте программное обеспечение для моделирования нового химического реактора. Ваша программа получает список химических реакций и начальные концентрации всех компонентов. Вы должны вывести концентрации после времени ${\textstyle t}$. В реакциях первого порядка для реакции достаточно только одной молекулы, и скорость реакции пропорциональна концентрации этого реагента: ${\textstyle A\xrightarrow {k_{1}} n_{1}B_{1}+n_{2}B_{2}+...+n_{I}B_{I}}$. Для этой реакции мы можем записать следующую систему дифференциальных уравнений: ${\textstyle d[A]/dt=-k_{1}[A]}$ ${\textstyle d[B_{i}]/dt=n_{i}k_{1}[A]}$, ${\textstyle i=1,...,I}$. Здесь ${\textstyle [A]}$ - концентрация молекулы ${\textstyle A}$, ${\textstyle [B_{i}]}$ - концентрация молекул ${\textstyle B_{i}}$, а ${\textstyle k_{1}}$ - постоянная скорости реакции. В реакциях второго порядка для продолжения реакции необходимы две молекулы: ${\textstyle A+C\xrightarrow {k_{2}} n_{1}B_{1}+n_{2}B_{2}+...+n_{I}B_{I}}$. ${\textstyle d[A]/dt=-k_{2}[A][C]}$ ${\textstyle d[B_{i}]/dt=n_{i}k_{2}[A][C]}$, ${\textstyle i=1,...,I}$. Простейшим примером колебательной химической системы является Oregonator [1], которая состоит из следующих реакций: ${\textstyle A+Y\xrightarrow {k_{1}} X+P}$. ${\textstyle X+Y\xrightarrow {k_{2}} 2P}$. ${\textstyle A+X\xrightarrow {k_{3}} 2X+2Z}$. ${\textstyle 2X\xrightarrow {k_{4}} A+P}$. ${\textstyle B+Z\xrightarrow {k_{5}} Y}$. Скорости реакций всегда будут в пределах порядка их соответствующих значений во входном файле с примерами. Ввод На первой строке содержится одно целое число ${\textstyle T}$ = 1...1000 – как долго мы будем запускать наш виртуальный реактор. Вторая строка содержит шесть вещественных чисел – начальные концентрации ${\textstyle X}$, ${\textstyle Y}$, ${\textstyle Z}$, ${\textstyle A}$, ${\textstyle B}$ и ${\textstyle P}$. Третья строка содержит пять вещественных чисел – константы скорости реакций ${\textstyle k_{1},...,k_{5}}$. Вывод На выходе должны быть шесть вещественных чисел – конечные концентрации ${\textstyle X}$, ${\textstyle Y}$, ${\textstyle Z}$, ${\textstyle A}$, ${\textstyle B}$ и ${\textstyle P}$. Требуемая точность - ${\textstyle 10^{-6}}$.

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

1. Как выполнить численное дифференцирование с помощью метода неопределенных коэффициентов?
2. Как выполнить интерполяцию функции с использованием сплайнов?
3. Как выполнить численное интегрирование с использованием квадратурных формул?
4. Как решить систему линейных алгебраических уравнений с использованием методов итерации?
5. Как решить систему линейных алгебраических уравнений с использованием методов вариации?
6. Как выполнить численное решение нелинейных алгебраических уравнений и систем?
7. Как выполнить численное решение задачи Коши для обыкновенных дифференциальных уравнений (ОДУ)?
8. Как выполнить численное решение краевых задач для ОДУ?
9. Как выполнить численное решение ОДУ и Уравнений в частных производных (УрЧП) с использованием Дискретного ряда Фурье?
10. Как выполнить численное решение УрЧП с использованием методов конечных разностей?

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

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

1. Gilbert Strang. Computational Science and Engineering. Wellesley, MA: Wellesley-Cambridge Press, 2007. 727 Pg. ISBN: 9780961408817.

2. I.B. Petrov, A.I. Lobanov. Lectures in Computational Mathematics. M.: Internet University of Information Technology, 2006. 523 c. ISBN: 5-94774-542-9.

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

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

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

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

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