BSc: ComputationalMathematics

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

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

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

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

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

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

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

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

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

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

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

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

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

Знания:

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

Умения:

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

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

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

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

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

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

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

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
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}$ будет предоставлен тестовой системой. Вы не должны пытаться проводить обратную инженерию "чёрного ящика" и/или взаимодействовать с ним каким-либо другим способом, кроме перечисленных выше четырёх функций. Задача проста: вам нужно подогнать набор точек под 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. Указатели ${\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 c}$ = 1): ${\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. Как выполнить численное решение УрЧП с использованием методов конечных разностей?

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

Список основной литературы: Gilbert Strang. Computational Science and Engineering. Wellesley, MA: Wellesley-Cambridge Press, 2007. 727 Pg. ISBN: 9780961408817. I.B. Petrov, A.I. Lobanov. Lectures in Computational Mathematics. M.: Internet University of Information Technology, 2006. 523 c. ISBN: 5-94774-542-9.

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

Вид учебных занятий/деятельности

Деятельность обучающегося

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

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