Участник:Борис/Алгоритм Рунге-Кутты

Материал из Алговики
Перейти к навигации Перейти к поиску

1 ЧАСТЬ. Свойства и структура алгоритмов

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

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

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

[math] \begin{cases} \textbf{y}' = \textbf{f}(x, \textbf{y}),\\ \textbf{y}(x_0) = \textbf{y}_0. \end{cases} [/math]

При этом [math]\textbf{y}, \textbf{f}, x[/math] отвечают следующим свойствам: [math] \textbf{y}, \textbf{f} \in \mathbb{R}^m, x \in \mathbb{R}^1 [/math].

Пусть известно значение y(x) и требуется вычислить значение y(x+h). Это можно сделать при помощи формулы:

[math] y(x + h) = y(x) + \int_0^hy'(x + t)dt[/math]

Аппроксимируя интеграл в правой части, можно получить методы Рунге-Кутты разного порядка точности. В общем виде формулы методов Рунге-Кутты можно записать следующим образом:

[math]\textbf{y}_{n+1} = \textbf{y}_n + h\sum_{i=1}^s b_i \textbf{k}_i[/math]

[math] \begin{array}{ll} \textbf{k}_1 =& \textbf{f}(x_n, \textbf{y}_n),\\ \textbf{k}_2 =& \textbf{f}(x_n+c_2h, \textbf{y}_n+a_{21}h\textbf{k}_1),\\ \cdots&\\ \textbf{k}_s =& \textbf{f}(x_n+c_sh, \textbf{y}_n+a_{s1}h\textbf{k}_1+a_{s2}h\textbf{k}_2+\cdots+a_{s,s-1}h\textbf{k}_{s-1}) \end{array} [/math]

Увеличивая число s вспомогательных точек, можно построить методы Рунге-Кутты любого порядка точности p. Однако уже при p > 5 эти методы используются довольно редко. Это объясняется как чрезмерной громоздкостью получающихся вычислительных формул, так и тем, что преимущества методов высокого порядка точности над методами, в которых p = 4 или p = 5, проявляются либо в тех задачах, где нужна очень высокая точность и используются ЭВМ высокой разрядности, либо в тех задачах, где решение очень гладкое. Кроме того, методы Рунге-Кутты высокого порядка точности часто оказываются менее эффективными по сравнению с методами Адамса того же порядка точности. На этой странице представлен наиболее распространенный метод Рунге-Кутты 4 порядка с ошибкой на конечном интервале интегрирования [math]O(h^4)[/math].

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

Далее приняты следующие обозначения [math] \bold y, \bold f, \bold k_i \in \mathbb{R}^n[/math], а [math]x, h \in \mathbb{R}^1 [/math].


[math]\textbf{y}_{n+1} = \textbf{y}_n + {h \over 6}(\textbf{k}_1 + 2\textbf{k}_2 + 2\textbf{k}_3 + \textbf{k}_4)[/math]


[math] \textbf{k}_1 = \textbf{f} \left( x_n, \textbf{y}_n \right),[/math]

[math]\textbf{k}_2 = \textbf{f} \left( x_n + {h \over 2}, \textbf{y}_n + {h \over 2} \textbf{k}_1 \right),[/math]

[math]\textbf{k}_3 = \textbf{f} \left( x_n + {h \over 2}, \textbf{y}_n + {h \over 2} \textbf{k}_2 \right),[/math]

[math]\textbf{k}_4 = \textbf{f} \left( x_n + h, \textbf{y}_n + h\ \textbf{k}_3 \right).[/math]

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

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

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

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

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

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

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

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

2 ЧАСТЬ. Программная реализация алгоритма

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

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

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

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

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

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

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

3 Литература