Участник:Anlesnichiy/Решение задачи Коши для системы ОДУ методом Рунге-Кутты 4 порядка: различия между версиями
(Добавлен раздел "Ресурс параллелизма алгоритма") |
|||
Строка 8: | Строка 8: | ||
}} | }} | ||
− | Основные авторы описания: [[Участник:Anlesnichiy|А.А. Лесничий]] (разделы [[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]]), [[Участник:Алимов Дамир Алиевич|Д.А. Алимов]] | + | Основные авторы описания: [[Участник:Anlesnichiy|А.А. Лесничий]] (разделы [[#Общее описание алгоритма|1.1]], [[#Математическое описание алгоритма|1.2]], [[#Ресурс параллелизма алгоритма|1.3]]), [[Участник:Алимов Дамир Алиевич|Д.А. Алимов]] |
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
Строка 60: | Строка 60: | ||
:<math> | :<math> | ||
\begin{cases} | \begin{cases} | ||
− | \bar k_1 = h | + | \bar k_1 = h\bar f(x_i,\bar y_i)\\ |
− | \bar k_2 = h | + | \bar k_2 = h\bar f(x_i + h/2,\bar y_i + 1/2 \bar k_1)\\ |
− | \bar k_3 = h | + | \bar k_3 = h\bar f(x_i + h/2,\bar y_i + 1/2 \bar k_2)\\ |
− | \bar k_4 = h | + | \bar k_4 = h\bar f(x_i + h,\bar y_i + \bar k_3)\\ |
− | \bar y_i+1 = \bar y_i + 1/6 | + | \bar y_i+1 = \bar y_i + 1/6 [ \bar k_1 + 2\bar k_2 + 2\bar k_3 + \bar k_4 ] \\ |
\end{cases} | \end{cases} | ||
</math> | </math> | ||
+ | |||
+ | === Ресурс параллелизма алгоритма === | ||
+ | Поскольку в описанной выше вычислительной схеме наиболее трудоемкой является операция расчета правых частей ОДУ при вычислении <math>k_i ( i = 1, \dots, 4) </math>, то основное внимание следует уделить распараллеливанию этой операции. | ||
+ | Здесь будет применяться подход декомпозиции уравнений системы ОДУ на подсистемы. | ||
+ | Поэтому для инициализации рассмотрим следующую схему декомпозиции данных по имеющимся процессорным элементам с локальной памятью: на каждый <math>\mu</math>- ПЭ (процессорный элемент) (<math>\mu = 0, \dots, p-1 </math>) распределяется <math> n/p </math> дифференциальных уравнений и вектор <math> \bar y_0 </math>. Далее расчеты производятся по следующей схеме: | ||
+ | # на каждом ПЭ одновременно вычисляются <math> n/p </math> соответствующих компонент вектора <math> \bar k_1 </math> по формуле <math> [ \bar k_1 ]_{\mu} = h[ \bar f(x_i, \bar y_i) ]_{\mu} </math> | ||
+ | # для обеспечения второго расчетного этапа необходимо провести сборку вектора <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>; | ||
+ | # проводится сборка вектора <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>; | ||
+ | # проводится сборка вектора <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>; | ||
+ | # рассчитываются с идеальным параллелизмом компоненты вектора <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] А. В. Старченко, В. Н. Берцун. Методы параллельных вычислений - Издательство Томского университета, 2013 - 173 с. | ||
<references \> | <references \> |
Версия 23:12, 1 октября 2016
Решение задачи Коши для системы ОДУ методом Рунге-Кутты 4 порядка | |
Последовательный алгоритм | |
Последовательная сложность | ? |
Объём входных данных | ? |
Объём выходных данных | ? |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | ? |
Ширина ярусно-параллельной формы | ? |
Основные авторы описания: А.А. Лесничий (разделы 1.1, 1.2, 1.3), Д.А. Алимов
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод Рунге-Кутты четвертого порядка — наиболее распространенный метод из семейства методов Метод Рунге-Кутты численных алгоритмов решения обыкновенных дифференциальных уравнений и их систем. Данные итеративные методы явного и неявного приближённого вычисления были разработаны около 1900 года немецкими математиками К. Рунге и М. В. Куттой.
Формально, методом Рунге-Кутты является модифицированный и исправленный метод Эйлера, они представляют собой схемы второго порядка точности. Существуют стандартные схемы третьего порядка, не получившие широкого распространения.
1.2 Математическое описание алгоритма
1.2.1 Метод Рунге-Кутты для задачи Коши для ДУ первого порядка
Рассмотрим задачу Коши
- [math] y' = f(x,y),\ a \leq x \leq b;\ y(a) = y^0 [/math]
Зададим равномерную сетку
- [math] x_i = a + i*h,\ i = 1,\dots, n,\ h = \frac{b-a}{n} [/math]
Введём обозначения [math]y(x_i) = y_i[/math]. Получим вычислительную формулу:
- [math] \begin{cases} k_1 = h*f(x_i,y_i)\\ k_2 = h*f(x_i + h/2,y_i + 1/2 k_1)\\ k_3 = h*f(x_i + h/2,y_i + 1/2 k_2)\\ k_4 = h*f(x_i + h,y_i + k_3)\\ y_i+1 = y_i + 1/6 \lbrace k_1 + 2k_2 + 2k_3 + k_4 \rbrace \\ \end{cases} [/math]
1.2.2 Метод Рунге-Кутты для задачи Коши для системы ДУ первого порядка
Численное решение задачи Коши для систем ОДУ 1-го порядка методами Рунге-Кутты ищется по тем же формулам, что и для ОДУ первого порядка. Например, решение методом Рунге-Кутты 4 го порядка можно найти, если положить:
- [math] \begin{align} y_i \rightarrow \bar y_i\\ f(x_i,y_i) \rightarrow \bar f(x_i,\bar y_i)\\ k_l \rightarrow \bar k_l,\ l = 1, \dots, 4\\ \bar k_l = \begin{pmatrix} k^i_{l,1}\\ \vdots\\ k^i_{l,m}\\ \end{pmatrix} \end{align} [/math]
где m -- размерность системы. В результате получим
- [math] \begin{cases} \bar k_1 = h\bar f(x_i,\bar y_i)\\ \bar k_2 = h\bar f(x_i + h/2,\bar y_i + 1/2 \bar k_1)\\ \bar k_3 = h\bar f(x_i + h/2,\bar y_i + 1/2 \bar k_2)\\ \bar k_4 = h\bar f(x_i + h,\bar y_i + \bar k_3)\\ \bar y_i+1 = \bar y_i + 1/6 [ \bar k_1 + 2\bar k_2 + 2\bar k_3 + \bar k_4 ] \\ \end{cases} [/math]
1.3 Ресурс параллелизма алгоритма
Поскольку в описанной выше вычислительной схеме наиболее трудоемкой является операция расчета правых частей ОДУ при вычислении [math]k_i ( i = 1, \dots, 4) [/math], то основное внимание следует уделить распараллеливанию этой операции. Здесь будет применяться подход декомпозиции уравнений системы ОДУ на подсистемы. Поэтому для инициализации рассмотрим следующую схему декомпозиции данных по имеющимся процессорным элементам с локальной памятью: на каждый [math]\mu[/math]- ПЭ (процессорный элемент) ([math]\mu = 0, \dots, p-1 [/math]) распределяется [math] n/p [/math] дифференциальных уравнений и вектор [math] \bar y_0 [/math]. Далее расчеты производятся по следующей схеме:
- на каждом ПЭ одновременно вычисляются [math] n/p [/math] соответствующих компонент вектора [math] \bar k_1 [/math] по формуле [math] [ \bar k_1 ]_{\mu} = h[ \bar f(x_i, \bar y_i) ]_{\mu} [/math]
- для обеспечения второго расчетного этапа необходимо провести сборку вектора [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];
- проводится сборка вектора [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];
- проводится сборка вектора [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];
- рассчитываются с идеальным параллелизмом компоненты вектора [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
Заметим, что в данном алгоритме производится четыре операции вычисления вектора правых частей ОДУ , шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов.
2 Литература
[1] А. В. Старченко, В. Н. Берцун. Методы параллельных вычислений - Издательство Томского университета, 2013 - 173 с.
<references \>