Алговики - Вклад [ru]

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

2016-11-28T15:26:05Z

Jul305a: /* Схема реализации последовательного алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

<source>

начало;

ввод начальных параметров (x[0], t0, t1, m);

цикл по числу узлов сетки: i = 1..m-1

цикл по числу стадий: j = 1..4

цикл по числу компонент вектора x: k = 1..n

вычисление коэффициентов K[j,k,i];

конец цикла по k;

конец цикла по j;

цикл по числу компонент вектора x: k = 1..n

вычисление x[k,i+1];

конец цикла по k;

цикл по числу компонент вектора x: k = 1..n

сохранение x[k,i] = x[k,i+1];

конец цикла по k;

вывод x[i+1];

конец цикла по n;

конец;

</source>

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

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

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговым: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка <math>4h</math>. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требует вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

Число операций алгоритма равно <math>m (n - 1)</math>, общее число входных и выходных данных равно <math>mn + m + n + 3</math>. Следовательно, вычислительная мощность алгоритма
<math>\frac{mn-m}{mn + m + n + 3} \longrightarrow 1</math> при увеличении размерности задачи.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-11-28T15:20:32Z

Jul305a: /* Схема реализации последовательного алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

<source>

начало;

ввод начальных параметров (<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>;

конец;

</source>

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

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

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговым: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка <math>4h</math>. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требует вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

Число операций алгоритма равно <math>m (n - 1)</math>, общее число входных и выходных данных равно <math>mn + m + n + 3</math>. Следовательно, вычислительная мощность алгоритма
<math>\frac{mn-m}{mn + m + n + 3} \longrightarrow 1</math> при увеличении размерности задачи.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-11-28T15:14:42Z

Jul305a: /* Свойства алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговым: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка <math>4h</math>. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требует вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

Число операций алгоритма равно <math>m (n - 1)</math>, общее число входных и выходных данных равно <math>mn + m + n + 3</math>. Следовательно, вычислительная мощность алгоритма
<math>\frac{mn-m}{mn + m + n + 3} \longrightarrow 1</math> при увеличении размерности задачи.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T08:08:39Z

Jul305a:

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T08:05:57Z

Jul305a:

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T08:05:10Z

Jul305a:

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T08:03:58Z

Jul305a: /* Ресурс параллелизма алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

Алгоритм производит четыре обращения к функции <math>f</math>, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов. Сложность алгоритма по высоте составляет <math>m</math>, а сложность по ширине равна <math>q = \frac{n}{p}</math>.

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T07:58:12Z

Jul305a: /* Свойства алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод прост в реализации - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T07:23:48Z

Jul305a:

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-14T07:23:15Z

Jul305a:

{{Assignment}}

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T15:22:47Z

Jul305a:

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T15:22:36Z

Jul305a: /* Общее описание алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T15:20:58Z

Jul305a: /* Информационный граф */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png|500px|thumb|center|Информационный граф алгоритма]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T15:20:03Z

Jul305a: /* Информационный граф */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[File:Rkg.png]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T15:18:17Z

Jul305a: /* Информационный граф */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

[[Файл:rkg.png]]

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T14:33:33Z

Jul305a: /* Литература */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

[1] А. В. Старченко, Высокопроизводительные вычисления на кластерах, Издательство Томского университета, 2013, 127-130 с

[2] Л. П. Фельдман, И. А. Назарова, Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений
[http://masters.donntu.org/2008/fvti/zavalkin/library/feldman_nazarova2/default.htm]

[3] Е. Е. Тыртышников, Методы численного анализа, М, Академия, 2007

[4] Ващенко Г.В. Явные методы типа Рунге-Кутты и их параллельные аналоги // Численные методы, программные системы и комплексы программ.
[http://econf.rae.ru/article/5396]

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

2016-10-13T14:17:41Z

Jul305a: /* Свойства алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

Метод Рунге-Кутты 4-го порядка обладает следующими свойствами:

1. Эти метод (как и все семейство методов Рунге-Кутты) является одношаговыми: чтобы найти <math>x_{n+1}</math>, нужна информация об одной предыдущей точке <math>(t_i, x_i)</math>. (Это позволяет в любой момент изменить шаг интегрирования.)

2. Метод согласуются с рядом Тейлора вплоть до членов порядка 4h. (Используя большее количество вспомогательных точек, можно увеличить точность метода.)

3. Метод не требуют вычисления производных от функции <math>f(t,x)</math>, а только требуют вычисления самой функции.

Точность и устойчивость метода достаточна для широкого круга задач, метод легко программируется - эти достоинства определили популярность метода среди большого количества исследователей.

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

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

2016-10-13T14:06:34Z

Jul305a: /* Существующие реализации алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

Стандартная схема четвертого порядка реализована в различных математических пакетах: Maple (rkf45), MathCAD (rkfixed), Matlab (ode45).

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

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

2016-10-13T14:01:18Z

Jul305a: /* Последовательная сложность алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и шестнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T14:00:10Z

Jul305a: /* Ресурс параллелизма алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и четырнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T13:46:05Z

Jul305a: /* Ресурс параллелизма алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и четырнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[K_1]</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>[K_1]</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T13:40:04Z

Jul305a: /* Ресурс параллелизма алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и четырнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>K_1</math> по формуле <math>[K_1] = [f(t_i, x_i)]</math>. Проводится сборка вектора <math>K_1</math> целиком на каждом процессоре.

2-4. Аналогичным образом проводятся вычисления и сборка векторов <math>[K_2], [K_3], [K_4]</math>.

5. На каждом процессоре вычисляется q соответствующих компонент вектора <math>[x_{i+1}]</math> по формуле <math>[x_{i+1}] = [x_i] + \frac{h}{6} ([K_1] + 2 [K_2] + 2 [K_3] + [K_4])</math>. Проводится сборка вектора <math>[x_{i+1}]</math> целиком на каждом процессоре. Если вычисления не закончены, то сохраняется <math>[x_{i}] = [x_{i+1}]</math>, осуществляется переход на 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T13:30:47Z

Jul305a: /* Ресурс параллелизма алгоритма */

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

Основные авторы описания: [[Участник: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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и четырнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 n m</math>.

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

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

Последовательная схема алгоритма дает основание для организации параллельных вычислений с помощью декомпозиции. Пусть доступно <math>p</math> процессоров (для определенности будем считать, что размерность системы <math>n</math> кратна количество процессоров <math>p</math>: <math>n = qp</math>). На каждый из процессоров распределяется и вычисляется последовательно <math>q</math> компонент векторов коэффициентов. Далее расчеты проводятся следующим образом:

1. На каждом процессоре вычисляется q соответствующих компонент вектора <math>K_1</math> по формуле <math>K_1 = f(t_i, x_i)</math>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T13:08:16Z

Jul305a: /* Входные и выходные данные алгоритма */

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

2016-10-13T13:07:53Z

Jul305a:

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

2016-10-13T13:07:11Z

Jul305a: /* Последовательная сложность алгоритма */

{{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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>f</math> (порядка <math>n m</math> арифметических операций) и четырнадцать операций сложения векторов и умножения вектора на число (порядка <math>n</math> арифметических операций). Поскольку операция обращения к функции является более сложной, то сложность последовательного алгоритма можно считать равной <math>4 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>.

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T13:05:48Z

Jul305a: /* Макроструктура алгоритма */

{{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>f</math>, и основное внимание будет уделено распараллеливанию этой операции.

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

Приведем здесь псевдокод

начало;

ввод начальных параметров (<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>.

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T13:05:08Z

Jul305a: /* Вычислительное ядро алгоритма */

{{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>.

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T12:54:27Z

Jul305a:

{{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>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>.

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T12:53:56Z

Jul305a:

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

Основные авторы описания: [[Участник: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>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>.

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T12:53:00Z

Jul305a: /* Входные и выходные данные алгоритма */

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

Основные авторы описания: [[Участник: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>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>.

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T12:50:19Z

Jul305a: /* Входные и выходные данные алгоритма */

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

Основные авторы описания: [[Участник: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>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>.

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T12:43:46Z

Jul305a: /* Макроструктура алгоритма */

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

Основные авторы описания: [[Участник: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>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>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T12:42:45Z

Jul305a: /* Последовательная сложность алгоритма */

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

Основные авторы описания: [[Участник: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>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>.

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

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

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

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

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

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

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

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

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

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

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

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

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

Участник:Jul305a

2016-10-13T12:19:21Z

Jul305a: Новая страница: «Студентка 613 группы ВМК МГУ»

Студентка 613 группы ВМК МГУ

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

2016-10-13T12:18:00Z

Jul305a: /* Схема реализации последовательного алгоритма */

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

Основные авторы описания: [[Участник: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>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>;

конец;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-13T10:41:51Z

Jul305a: /* Макроструктура алгоритма */

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

2016-10-13T10:35:38Z

Jul305a: /* Макроструктура алгоритма */

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

2016-10-13T10:35:02Z

Jul305a: /* Макроструктура алгоритма */

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

2016-10-13T10:32:07Z

Jul305a: /* Вычислительное ядро алгоритма */

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

2016-10-13T10:25:53Z