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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 55: Строка 55:
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
 +
 +
Приведем здесь псевдокод
 +
 +
начало;
 +
 +
ввод начальных параметров (<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>;
 +
 +
конец;
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===

Версия 15:18, 13 октября 2016


Решение задачи Коши для системы ОДУ методом Рунге-Кутта
Последовательный алгоритм
Последовательная сложность ?
Объём входных данных n + 3
Объём выходных данных n m + m
Параллельный алгоритм
Высота ярусно-параллельной формы ?
Ширина ярусно-параллельной формы ?


Основные авторы описания: Филимонова Юлия

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]

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

В описанной выше вычислительной схеме наиболее трудоемкой является операция умножения матрицы на вектор при вычислении [math]K_i[/math], следовательно вычислительным ядром является их последовательное вычисление.

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

Макроструктура алгоритма представлена одним шагом итерационного процесса, описанного в пункте 1.2. Основной макрооперацией алгоритма является операция умножения вектора на число, и основное внимание будет уделено распараллеливанию этой операции.

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

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

начало;

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

конец;

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 Литература