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. Указатели ${\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. Как выполнить численное решение УрЧП с использованием методов конечных разностей?

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

Список основной литературы: 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.

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

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

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

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

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