Просмотр кода страницы Участник:Филимонова Юлия/Решение начальной задачи Коши для системы обыкновенных дифференциальных уравнений методом Рунге-Кутта 4-го порядка

{{algorithm
| name              = Решение задачи Коши для системы ОДУ методом Рунге-Кутта
| serial_complexity = 8mn
| pf_height         = ?
| pf_width          = ?
| input_data        = n + 3
| output_data       = m(n + 1)
}}

Основные авторы описания: [[Участник:jul305a|Филимонова Юлия]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Методы Рунге-Кутты (распространено неправильное название Методы Рунге-Кутта) — важное семейство численных алгоритмов решения обыкновенных дифференциальных уравнений и их систем. Данные итеративные методы явного и неявного приближённого вычисления были разработаны около 1900 года немецкими математиками К. Рунге и М. В. Куттой.

Формально, методом Рунге-Кутты является модифицированный и исправленный метод Эйлера, они представляют собой схемы второго порядка точности. Существуют стандартные схемы третьего порядка, не получившие широкого распространения. Наиболее часто используется и реализована в различных математических пакетах (Maple, MathCAD, Maxima) стандартная схема четвёртого порядка. Классический метод Рунге-Кутты четвёртого порядка столь широко распространён, что его часто называют просто методом Рунге-Кутты, опуская порядок.

=== Математическое описание алгоритма ===

Рассмотрим задачу Коши для системы обыкновенных дифференциальных уравнений размерности <math>n</math>

<math>\dot{x} = f(t, x),\ t_0 \leqslant t \leqslant t_1,\ x(t_0) = x_0.</math>

Здесь <math>x(t), x_0 \in \mathbb{R}^n,\ t, t_0, t_1 \in \mathbb{R}, f: \mathbb{R} \rightarrow \mathbb{R}^n</math>.

Введем равномерную сетку

<math>t_i = t_0 + ih,\ i = \overline{1, n},\ h = \frac{t_1 - t_0}{m},</math>

<math>x(t_i) = x_i.</math>

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

<math>x_{i+1} = x_i + \frac{h}{6} (K_1 + 2 K_2 + 2 K_3 + K_4).</math>

Вычисление нового значения происходит в четыре стадии:

<math>K_1 = f (t_i, x_i),</math>

<math>K_2 = f (t_i + \frac{h}{2}, x_i + \frac{h}{2} K_1),</math>

<math>K_3 = f (t_i + \frac{h}{2}, x_i + \frac{h}{2} K_2),</math>

<math>K_4 = f (t_i + h, x_i + h K_3).</math>

=== Вычислительное ядро алгоритма ===

В описанной выше вычислительной схеме наиболее трудоемкой является операция обращения к функции <math>f</math> при вычислении коэффициентов <math>K_i</math>, эта операция является вычислительным ядром.

=== Макроструктура алгоритма ===

Макроструктура алгоритма представлена одним шагом итерационного процесса, описанного в пункте 1.2. Основной макрооперацией алгоритма является операция умножения матрицы на вектор, и основное внимание будет уделено распараллеливанию этой операции.

=== Схема реализации последовательного алгоритма ===
 
Приведем здесь псевдокод

начало;

ввод начальных параметров (<math>x_0, t_0, t_1, m</math>);

цикл по числу узлов сетки: <math>i = \overline{1,m-1}</math> 

цикл по числу стадий: <math>j = \overline{1,4}</math>

цикл по числу компонент вектора <math>x:\ k = \overline{1,n}</math>

вычисление коэффициентов <math>K_{j, k}^{i}</math>;

конец цикла по <math>k</math>;

конец цикла по <math>j</math>;

цикл по числу компонент вектора <math>x:\ k = \overline{1,n}</math>

вычисление <math>y_{j}^{i+1}</math>;

конец цикла по <math>k</math>;

цикл по числу компонент вектора <math>x:\ k = \overline{1,n}</math>

сохранение <math>y_{j}^{i} = y_{j}^{i+1}</math>;

конец цикла по <math>k</math>;

вывод <math>y^{i+1}</math>;

конец цикла по <math>n</math>;

конец;

=== Последовательная сложность алгоритма ===

В данном алгоритме производится четыре операции умножения матрицы на вектор (порядка <math>2 n m</math> арифметических операций) и четырнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция умножения матрицы на вектор является более сложной, то сложность последовательного алгоритма можно считать равной <math>8 n m</math>.

=== Информационный граф ===

=== Ресурс параллелизма алгоритма ===

=== Входные и выходные данные алгоритма ===

На вход алгоритма подаются следующие данные:

# вектор начальных значений <math>x_0</math> размерности <math>n</math>;
# границы временного интервала <math>t_0, t_1</math>;
# частота дискретизации <math>n</math>.

Общий размер входных данных <math>n + 3</math>.

На выходе получаются следующие данные:

# вектор времени <math>t</math> размерности <math>m</math>;
# матрица значений <math>x</math> (<math>m</math> векторов длины <math>n</math>) размерности <math>m n</math>.

Общий размер выходных данных <math>m + m n</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==