Уровень алгоритма

Участник:Alexboboshko/Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 24: Строка 24:
 
Явный m-этапный метод Рунге-Кутта состоит в следующем. Пусть решение <math> y_n = y(t_n) </math> уже известно. Задаются числовые коэффициенты <math> a_i, \ b_{ij},\ i = 2, 3, \dots, m,\ j = 1, 2, \dots, m-1,\ \sigma_i,\ i = 1, 2, \dots, m, </math> и последовательно вычисляются функции
 
Явный m-этапный метод Рунге-Кутта состоит в следующем. Пусть решение <math> y_n = y(t_n) </math> уже известно. Задаются числовые коэффициенты <math> a_i, \ b_{ij},\ i = 2, 3, \dots, m,\ j = 1, 2, \dots, m-1,\ \sigma_i,\ i = 1, 2, \dots, m, </math> и последовательно вычисляются функции
 
:<math>
 
:<math>
\begin{align}
+
    \begin{array}{l}
k_1 = f(t_n, y_n), k_2 = f(t_n+a_2\tau,\ y_n+b_{21}\tau k_1) \\
+
        k_1 = f(t_n, y_n), \ k_2 = f(t_n+a_2\tau,\ y_n+b_{21}\tau k_1) \\
k_3 = f(t_n+a_3 \tau, \ y_n+b_{31}\tau k_1+b_{32}\tau k_2), \  \dots,\\
+
        k_3 = f(t_n+a_3 \tau, \ y_n+b_{31}\tau k_1+b_{32}\tau k_2), \  \dots, \\
k_m = f(t_n+a_m \tau, \ y_n+b_{m1}\tau k_1+b_{m2}\tau k_2+\dots+b_{m,m-1}\tau k_{m-1})
+
        k_m = f(t_n+a_m \tau, \ y_n+b_{m1}\tau k_1+b_{m2}\tau k_2+\dots+b_{m,m-1}\tau k_{m-1})
\end{align}
+
    \end{array}{l}
 
</math>
 
</math>
 +
Затем из формулы <math>\frac{y_{n+1}-y_n}{\tau} = \sum_{i = 1}^{m} \sigma_i k_i </math> находится новое значение  <math> y_{n+1} = y(t_{n+1}) </math>
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

Версия 14:52, 7 октября 2016


РК
Последовательный алгоритм
Последовательная сложность [math] 4mn [/math]
Объём входных данных [math] m + 3 [/math]
Объём выходных данных [math] (m+1)n [/math]
Параллельный алгоритм
Высота ярусно-параллельной формы ?
Ширина ярусно-параллельной формы ?


Основные авторы описания:

Содержание

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

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

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

Формально, методом Рунге — Кутты является модифицированный и исправленный метод Эйлера, они представляют собой схемы второго порядка точности. Существуют стандартные схемы третьего порядка, не получившие широкого распространения.

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

1.2.1 Общая формулировка методов

Рассматриваем задачу Коши

[math] \frac{du}{dt} = f(t,u), u(0)=u_0 [/math]

Явный m-этапный метод Рунге-Кутта состоит в следующем. Пусть решение [math] y_n = y(t_n) [/math] уже известно. Задаются числовые коэффициенты [math] a_i, \ b_{ij},\ i = 2, 3, \dots, m,\ j = 1, 2, \dots, m-1,\ \sigma_i,\ i = 1, 2, \dots, m, [/math] и последовательно вычисляются функции

[math] \begin{array}{l} k_1 = f(t_n, y_n), \ k_2 = f(t_n+a_2\tau,\ y_n+b_{21}\tau k_1) \\ k_3 = f(t_n+a_3 \tau, \ y_n+b_{31}\tau k_1+b_{32}\tau k_2), \ \dots, \\ k_m = f(t_n+a_m \tau, \ y_n+b_{m1}\tau k_1+b_{m2}\tau k_2+\dots+b_{m,m-1}\tau k_{m-1}) \end{array}{l} [/math]

Затем из формулы [math]\frac{y_{n+1}-y_n}{\tau} = \sum_{i = 1}^{m} \sigma_i k_i [/math] находится новое значение [math] y_{n+1} = y(t_{n+1}) [/math]

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

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

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

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

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

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

Поскольку в описанной выше вычислительной схеме наиболее трудоемкой является операция расчета правых частей ОДУ при вычислении [math]k_i ( i = 1, \dots, 4) [/math], то основное внимание следует уделить распараллеливанию этой операции. Здесь будет применяться подход декомпозиции уравнений системы ОДУ на подсистемы. Поэтому для инициализации рассмотрим следующую схему декомпозиции данных по имеющимся процессорным элементам с локальной памятью: на каждый [math]\mu[/math]- ПЭ (процессорный элемент) ([math]\mu = 0, \dots, p-1 [/math]) распределяется [math] m/p [/math] дифференциальных уравнений и вектор [math] \bar y_0 [/math]. Далее расчеты производятся по следующей схеме:

  1. на каждом ПЭ одновременно вычисляются [math] n/p [/math] соответствующих компонент вектора [math] \bar k_1 [/math] по формуле [math] [ \bar k_1 ]_{\mu} = h[ \bar f(x_i, \bar y_i) ]_{\mu} [/math]
  2. для обеспечения второго расчетного этапа необходимо провести сборку вектора [math] \bar k_1 [/math] целиком на каждом ПЭ. Затем независимо выполняется вычисление компонент вектора [math] \bar k_2 [/math] по формуле [math] [ \bar k_2 ]_{\mu} = h[ \bar f(x_i + h/2,\bar y_i + 1/2 \bar k_1)]_{\mu} [/math];
  3. проводится сборка вектора [math] \bar k_2 [/math] на каждом ПЭ, вычисляются компоненты вектора [math] \bar k_3:\ [ \bar k_3 ]_{\mu} = h [\bar f(x_i + h/2,\bar y_i + 1/2 \bar k_2)]_{\mu} [/math];
  4. проводится сборка вектора [math] \bar k_3 [/math] на каждом ПЭ, вычисляются компоненты вектора [math] \bar k_4:\ [ \bar k_4 ]_{\mu} = h [\bar f(x_i + h,\bar y_i + \bar k_3)]_{\mu} [/math];
  5. рассчитываются с идеальным параллелизмом компоненты вектора [math] \bar y_{i+1}:\ [\bar y_{i+1}]_{\mu} = [\bar y_{i}]_{\mu} + ([ \bar k_1 ]_{\mu} + 2[ \bar k_2 ]_{\mu} + 2[ \bar k_3 ]_{\mu} + [ \bar k_4 ]_{\mu})/6\ [/math] и производится сборка вектора [math] \bar y_{i+1} [/math] на каждом ПЭ. Если необходимо продолжить вычислительный процесс, то полагается [math] i = i + 1 [/math] и осуществляется переход на п. 1

Заметим, что в данном алгоритме производится четыре операции вычисления вектора правых частей ОДУ, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов.

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

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

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

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

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

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.2.1.3 Анализ на основе теста Apex-Map

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

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

2.4.1 Масштабируемость алгоритма

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

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

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

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

3 Литература

[1]

<references \>