Участник:Филимонова Юлия/Решение начальной задачи Коши для системы обыкновенных дифференциальных уравнений методом Рунге-Кутта 4-го порядка: различия между версиями
Jul305a (обсуждение | вклад) |
Jul305a (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| − | Рассмотрим задачу Коши для системы обыкновенных дифференциальных уравнений | + | Рассмотрим задачу Коши для системы обыкновенных дифференциальных уравнений размерности <math>n</math> |
| − | <math>\dot{x} = f(t, x),\ x(t_0) = x_0,\ t \ | + | <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> | |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Версия 13:25, 13 октября 2016
| Решение задачи Коши для системы ОДУ методом Рунге-Кутта | |
| Последовательный алгоритм | |
| Последовательная сложность | ? |
| Объём входных данных | n + 3 |
| Объём выходных данных | n m + m |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | ? |
| Ширина ярусно-параллельной формы | ? |
Основные авторы описания: Филимонова Юлия
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 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 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Методы Рунге-Кутты (распространено неправильное название Методы Рунге-Кутта) — важное семейство численных алгоритмов решения обыкновенных дифференциальных уравнений и их систем. Данные итеративные методы явного и неявного приближённого вычисления были разработаны около 1900 года немецкими математиками К. Рунге и М. В. Куттой.
Формально, методом Рунге-Кутты является модифицированный и исправленный метод Эйлера, они представляют собой схемы второго порядка точности. Существуют стандартные схемы третьего порядка, не получившие широкого распространения. Наиболее часто используется и реализована в различных математических пакетах (Maple, MathCAD, Maxima) стандартная схема четвёртого порядка. Классический метод Рунге-Кутты четвёртого порядка столь широко распространён, что его часто называют просто методом Рунге-Кутты, опуская порядок.
1.2 Математическое описание алгоритма
Рассмотрим задачу Коши для системы обыкновенных дифференциальных уравнений размерности [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]
