Участник:Максим
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Ме́тод Ру́нге — Ку́тты 4-го порядка — важный итерационный метод численного решения систем обыкновенных дифференциальных уравнений. Он был разработан около 1900 года немецкими математиками К. Рунге и М. В. Куттой. Для численного решения системы на отрезке, на котором определена независимая переменная, задается сетка с некоторым маленьким шагом. Последовательно, на каждом шаге, вычисляем значения зависимых переменных через значения зависимых переменных на предыдущем шаге по формулам Рунге-Кутты.
1.2 Математическое описание алгоритма
Рассматривается следующая система ОДУ:
[math] \begin{align} X^'=f(t,X,Y,...)\\ Y^'=g(t,X,Y,...),... \end{align} [/math]
и т.д.
с начальным условием [math] X(t_0)=X_0,Y(t_0)=Y_0,... [/math]
Пусть h-шаг сетки, тогда имеем следующие формулы Рунге-Кутты численного решения системы:
[math] \begin{align} t_{k+1}=t_{k}+h\\ X_{k+1}=\frac{1}{6}(k_1+2k_2+2k_3+k_4),\\ Y_{k+1}=\frac{1}{6}(m_1+2m_2+2m_3+m_4),...,\\ k_1=f(t_k,X_k,Y_k,...)h,\\ m_1=g(t_k,X_k,Y_k,...)h,...,\\ k_2=f(t_k+\frac{h}{2},X_k+\frac{k_1}{2},Y_k+\frac{m_1}{2},...)h,\\ m_2=g(t_k+\frac{h}{2},X_k+\frac{k_1}{2},Y_k+\frac{m_1}{2},...)h,...,\\ k_3=f(t_k+\frac{h}{2},X_k+\frac{k_2}{2},Y_k+\frac{m_2}{2},...)h,\\ m_3=g(t_k+\frac{h}{2},X_k+\frac{k_2}{2},Y_k+\frac{m_2}{2},...)h,...,\\ k_4=f(t_k+h,X_k+k_3,Y_k+m_3,...)h,\\ m_4=g(t_k+h,X_k+k_3,Y_k+m_3,...)h,...\\ \end{align} [/math]
1.3 Вычислительное ядро алгоритма
Вычислительное ядро метода Рунге-Кутты можно составить из множественных вычислений функций f,g,... и т.д.
1.4 Макроструктура алгоритма
Как и записано в предыдущем пункте основную часть метода составляют множественные вычисления значений функций от нескольких переменных f,g,... и т.д.
1.5 Схема реализации последовательного алгоритма
Последовательность исполнения метода следующая:
[math] 1. t_{k+1}=t_{k}+h [/math]
[math] 2. k_1=f(t_k,X_k,Y_k,...)h,[/math]
[math] m_1=g(t_k,X_k,Y_k,...)h,...,[/math]
[math] k_2=f(t_k+\frac{h}{2},X_k+\frac{k_1}{2},Y_k+\frac{m_1}{2},...)h,[/math]
[math] m_2=g(t_k+\frac{h}{2},X_k+\frac{k_1}{2},Y_k+\frac{m_1}{2},...)h,...,[/math]
[math] k_3=f(t_k+\frac{h}{2},X_k+\frac{k_2}{2},Y_k+\frac{m_2}{2},...)h,[/math]
[math] m_3=g(t_k+\frac{h}{2},X_k+\frac{k_2}{2},Y_k+\frac{m_2}{2},...)h,...,[/math]
[math] k_4=f(t_k+h,X_k+k_3,Y_k+m_3,...)h,[/math]
[math] m_4=g(t_k+h,X_k+k_3,Y_k+m_3,...)h,...[/math]
[math] 3. X_{k+1}=\frac{1}{6}(k_1+2k_2+2k_3+k_4),[/math]
[math] Y_{k+1}=\frac{1}{6}(m_1+2m_2+2m_3+m_4),...[/math]
1.6 Последовательная сложность алгоритма
Пусть m-число узлов сетки, n-размерность системы ОДУ. Тогда найдем количество операций, требуемое для решения задачи.
1. Сложений
[math] (7n+2)m [/math]
2. Умножений
[math] 4nm [/math]
3. Делений
[math] (4n+1)m [/math]
4. Вычислений значения многомерной функции
[math] 4nm [/math]
1.7 Информационный граф
По оси OX происходит вычисление функций [math] f,g [/math] и т.д. По оси OY происходит вычисление коэффициентов [math] k_1,k_2,k_3,k_4;m_1,m_2,m_3,m_4 [/math] и т.д. По оси OZ вычисление вектора функций [math] Y_{k+1} [/math] на очередном шаге. Вообще говоря, информационный граф четырехмерен, так как на четвертой оси будут располагаться последовательные итерации [math] Y_{k+1},Y_{k+2} [/math] и т.д.
1.8 Входные и выходные данные алгоритма
Входные данные: вектор начальных данных размером n, вектор функций размером n
Выходные данные: вектор значений функций в конечный момент времени размером n.
