Методы Рунге – Кутты - Runge–Kutta methods

В числовой анализ, то Методы Рунге – Кутты семья неявный и явный итерационные методы, которые включают хорошо известную процедуру, называемую Метод Эйлера, используется в временная дискретизация для приближенных решений обыкновенные дифференциальные уравнения.^[1] Эти методы были разработаны около 1900 года немецкими математиками. Карл Рунге и Вильгельм Кутта.

Сравнение методов Рунге-Кутты для дифференциального уравнения y '= sin (t) ^ 2 * y (оранжевый - точное решение)

Метод Рунге – Кутты.

Склоны по классическому методу Рунге-Кутта

Наиболее широко известный член семейства Рунге-Кутта обычно упоминается как «RK4», «классический метод Рунге-Кутта» или просто как «метод Рунге-Кутта».

Пусть проблема начального значения указать следующее:

${ displaystyle { frac {dy} {dt}} = f (t, y), quad y (t_ {0}) = y_ {0}.}$

Здесь ${ displaystyle y}$ неизвестная функция (скаляр или вектор) времени ${ displaystyle t}$, которые мы хотели бы приблизить; нам говорят, что ${ displaystyle { frac {dy} {dt}}}$, скорость, с которой ${ displaystyle y}$ изменения, это функция ${ displaystyle t}$ и из ${ displaystyle y}$ сам. В начальное время ${ displaystyle t_ {0}}$ соответствующий ${ displaystyle y}$ ценность ${ displaystyle y_ {0}}$. Функция ${ displaystyle f}$ и первоначальные условия ${ displaystyle t_ {0}}$, ${ displaystyle y_ {0}}$ даны.

Теперь выберите размер шага час > 0 и определим

${ displaystyle { begin {align} y_ {n + 1} & = y_ {n} + { frac {1} {6}} h left (k_ {1} + 2k_ {2} + 2k_ {3} + k_ {4} right), t_ {n + 1} & = t_ {n} + h конец {выровнено}}}$

за п = 0, 1, 2, 3, ..., используя^[2]

${ displaystyle { begin {align} k_ {1} & = f (t_ {n}, y_ {n}), k_ {2} & = f left (t_ {n} + { frac {h} {2}}, y_ {n} + h { frac {k_ {1}} {2}} right), k_ {3} & = f left (t_ {n} + { frac {h} {2}}, y_ {n} + h { frac {k_ {2}} {2}} right), k_ {4} & = f left (t_ {n} + h, y_ {n} + hk_ {3} right). end {align}}}$

(Примечание: приведенные выше уравнения имеют разные, но эквивалентные определения в разных текстах).^[3]

Здесь ${ displaystyle y_ {n + 1}}$ является RK4-приближением ${ Displaystyle у (т_ {п + 1})}$, а следующее значение (${ displaystyle y_ {n + 1}}$) определяется текущей стоимостью (${ displaystyle y_ {n}}$) плюс средневзвешенное четырех приращений, где каждое приращение является произведением размера интервала, час, и предполагаемый наклон, заданный функцией ж в правой части дифференциального уравнения.

• ${ displaystyle k_ {1}}$ наклон в начале интервала, используя ${ displaystyle y}$ (Метод Эйлера );
• ${ displaystyle k_ {2}}$ - наклон в середине интервала, используя ${ displaystyle y}$ и ${ displaystyle k_ {1}}$;
• ${ displaystyle k_ {3}}$ снова наклон в средней точке, но теперь с использованием ${ displaystyle y}$ и ${ displaystyle k_ {2}}$;
• ${ displaystyle k_ {4}}$ наклон в конце интервала, используя ${ displaystyle y}$ и ${ displaystyle k_ {3}}$.

При усреднении четырех уклонов больший вес придается уклонам в средней точке. Если ${ displaystyle f}$ не зависит от ${ displaystyle y}$, так что дифференциальное уравнение эквивалентно простому интегралу, то RK4 есть Правило Симпсона.^[4]

Метод RK4 - это метод четвертого порядка, а это означает, что локальная ошибка усечения является в порядке ${ Displaystyle О (ч ^ {5})}$, в то время как общая накопленная ошибка находится в порядке ${ Displaystyle О (ч ^ {4})}$.

Во многих практических приложениях функция ${ displaystyle f}$ не зависит от ${ displaystyle t}$ (так называемые автономная система, или система, не зависящая от времени, особенно в физике), а их приращения вообще не вычисляются и не передаются в функцию ${ displaystyle f}$, с только окончательной формулой для ${ displaystyle t_ {n + 1}}$ использовал.

Явные методы Рунге – Кутты

Семья явный Методы Рунге – Кутты являются обобщением упомянутого выше метода RK4. Это дается

${ displaystyle y_ {n + 1} = y_ {n} + h sum _ {i = 1} ^ {s} b_ {i} k_ {i},}$

куда^[5]

${ displaystyle { begin {align} k_ {1} & = f (t_ {n}, y_ {n}), k_ {2} & = f (t_ {n} + c_ {2} h, y_ {n} + h (a_ {21} k_ {1})), k_ {3} & = f (t_ {n} + c_ {3} h, y_ {n} + h (a_ {31} k_ {1} + a_ {32} k_ {2})), & vdots k_ {s} & = f (t_ {n} + c_ {s} h, y_ {n} + h ( a_ {s1} k_ {1} + a_ {s2} k_ {2} + cdots + a_ {s, s-1} k_ {s-1})). end {выравнивается}}}$

(Примечание: приведенные выше уравнения могут иметь разные, но эквивалентные определения в некоторых текстах).^[3]

Чтобы указать конкретный метод, необходимо указать целое число s (количество ступеней), а коэффициенты а_ij (для 1 ≤ j < я ≤ s), б_я (за я = 1, 2, ..., s) и c_я (за я = 2, 3, ..., s). Матрица [а_ij] называется Матрица Рунге – Кутты, в то время как б_я и c_я известны как веса и узлы.^[6] Эти данные обычно хранятся в мнемоническом устройстве, известном как Таблица мясника (после Джон С. Батчер ):

${ displaystyle 0}$
${ displaystyle c_ {2}}$	${ displaystyle a_ {21}}$
${ displaystyle c_ {3}}$	${ displaystyle a_ {31}}$	${ displaystyle a_ {32}}$
${ displaystyle vdots}$	${ displaystyle vdots}$		${ displaystyle ddots}$
${ displaystyle c_ {s}}$	${ displaystyle a_ {s1}}$	${ displaystyle a_ {s2}}$	${ displaystyle cdots}$	${ displaystyle a_ {s, s-1}}$
	${ displaystyle b_ {1}}$	${ displaystyle b_ {2}}$	${ displaystyle cdots}$	${ displaystyle b_ {s-1}}$	${ displaystyle b_ {s}}$

А Серия Тейлор показывает, что метод Рунге – Кутты непротиворечив тогда и только тогда, когда

${ displaystyle sum _ {i = 1} ^ {s} b_ {i} = 1.}$

Также существуют сопутствующие требования, если требуется, чтобы метод имел определенный порядок. п, что означает, что локальная ошибка усечения равна O (час^п+1). Их можно получить из определения самой ошибки усечения. Например, двухэтапный метод имеет порядок 2, если б₁ + б₂ = 1, б₂c₂ = 1/2, и б₂а₂₁ = 1/2.^[7] Обратите внимание, что популярным условием определения коэффициентов является ^[8]

${ displaystyle sum _ {j = 1} ^ {i-1} a_ {ij} = c_ {i} { text {for}} i = 2, ldots, s.}$

Однако одно это условие не является ни достаточным, ни необходимым для согласованности.^[9]

В общем, если явный ${ displaystyle s}$-этапный метод Рунге – Кутта имеет порядок ${ displaystyle p}$, то можно доказать, что количество стадий должно удовлетворять ${ displaystyle s geq p}$, и если ${ displaystyle p geq 5}$, тогда ${ displaystyle s geq p + 1}$.^[10]Однако неизвестно, являются ли эти границы острый во всех случаях; например, все известные методы 8-го порядка имеют не менее 11 этапов, хотя возможно, что есть методы с меньшим числом этапов. (Приведенная выше граница предполагает, что может существовать метод с 9 этапами; но также может быть и то, что граница просто не точна.) Действительно, вопрос о том, какое точное минимальное количество этапов ${ displaystyle s}$ для явного метода Рунге – Кутты, чтобы иметь порядок ${ displaystyle p}$ в тех случаях, когда еще не обнаружены методы, удовлетворяющие приведенным выше оценкам с равенством. Вот некоторые известные значения:^[11]

${ displaystyle { begin {array} {c | cccccccc} p & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 hline min s & 1 & 2 & 3 & 4 & 6 & 7 & 9 & 11 end {array}}}$

Доказуемые оценки выше означают, что мы не можем найти методы заказов ${ Displaystyle р = 1,2, ldots, 6}$ которые требуют меньшего количества этапов, чем методы, которые мы уже знаем для этих заказов. Однако вполне возможно, что мы сможем найти способ упорядочения ${ displaystyle p = 7}$ в котором всего 8 стадий, тогда как в известных сегодня только 9 стадий, как показано в таблице.

Примеры

Метод RK4 подпадает под эти рамки. Его таблица^[12]

0
1/2	1/2
1/2	0	1/2
1	0	0	1
	1/6	1/3	1/3	1/6

Небольшая вариация «метода» Рунге – Кутты также принадлежит Кутте в 1901 году и называется правилом 3/8.^[13] Основное преимущество этого метода заключается в том, что почти все коэффициенты ошибок меньше, чем в популярном методе, но для этого требуется немного больше FLOP (операций с плавающей запятой) на временной шаг. Его таблица Мясника

0
1/3	1/3
2/3	-1/3	1
1	1	−1	1
	1/8	3/8	3/8	1/8

Однако самый простой метод Рунге – Кутты - это (вперед) Метод Эйлера, задаваемый формулой ${ displaystyle y_ {n + 1} = y_ {n} + hf (t_ {n}, y_ {n})}$. Это единственный последовательный явный метод Рунге – Кутты с одним этапом. Соответствующая таблица

0
	1

Методы второго порядка с двумя этапами

Пример метода второго порядка с двумя стадиями представлен метод средней точки:

${ displaystyle y_ {n + 1} = y_ {n} + hf left (t_ {n} + { frac {1} {2}} h, y_ {n} + { frac {1} {2}) } hf (t_ {n}, y_ {n}) right).}$

Соответствующая таблица

0
1/2	1/2
	0	1

Метод средней точки - не единственный метод Рунге – Кутты второго порядка, состоящий из двух этапов; существует семейство таких методов, параметризованных параметром α и задаваемых формулой^[14]

${ displaystyle y_ {n + 1} = y_ {n} + h { bigl (} (1 - { tfrac {1} {2 alpha}}) f (t_ {n}, y_ {n}) + { tfrac {1} {2 alpha}} f (t_ {n} + alpha h, y_ {n} + alpha hf (t_ {n}, y_ {n})) { bigr)}.}$

Его таблица Мясника

0
${ displaystyle alpha}$	${ displaystyle alpha}$
	${ displaystyle (1 - { tfrac {1} {2 alpha}})}$	${ displaystyle { tfrac {1} {2 alpha}}}$

В этой семье ${ Displaystyle альфа = { tfrac {1} {2}}}$ дает метод средней точки, а ${ Displaystyle альфа = 1}$ является Метод Хойна.^[4]

Использовать

В качестве примера рассмотрим двухэтапный метод Рунге – Кутты второго порядка с α = 2/3, также известный как Метод Ральстона. Это дано таблицей

с соответствующими уравнениями

${ displaystyle { begin {align} k_ {1} & = f (t_ {n}, y_ {n}), k_ {2} & = f (t_ {n} + { tfrac {2}) {3}} h, y_ {n} + { tfrac {2} {3}} hk_ {1}), y_ {n + 1} & = y_ {n} + h left ({ tfrac {1} {4}} k_ {1} + { tfrac {3} {4}} k_ {2} right). End {align}}}$

Этот метод используется для решения задачи начального значения

${ displaystyle { frac {dy} {dt}} = tan (y) +1, quad y_ {0} = 1, t in [1,1.1]}$

с размером шага час = 0,025, поэтому метод должен состоять из четырех шагов.

Метод работает следующим образом:

${ displaystyle t_ {0} = 1 двоеточие}$
	${ displaystyle y_ {0} = 1}$
${ displaystyle t_ {1} = 1,025 двоеточие}$
	${ displaystyle y_ {0} = 1}$	${ displaystyle k_ {1} = 2,557407725}$	${ displaystyle k_ {2} = f (t_ {0} + { tfrac {2} {3}} h, y_ {0} + { tfrac {2} {3}} hk_ {1}) = 2,7138981400 }$
	${ displaystyle y_ {1} = y_ {0} + h ({ tfrac {1} {4}} k_ {1} + { tfrac {3} {4}} k_ {2}) = { underline { 1.066869388}}}$
${ displaystyle t_ {2} = 1,05 двоеточие}$
	${ displaystyle y_ {1} = 1.066869388}$	${ displaystyle k_ {1} = 2,813524695}$	${ displaystyle k_ {2} = f (t_ {1} + { tfrac {2} {3}} h, y_ {1} + { tfrac {2} {3}} hk_ {1})}$
	${ displaystyle y_ {2} = y_ {1} + h ({ tfrac {1} {4}} k_ {1} + { tfrac {3} {4}} k_ {2}) = { underline { 1.141332181}}}$
${ displaystyle t_ {3} = 1,075 двоеточие}$
	${ displaystyle y_ {2} = 1,141332181}$	${ displaystyle k_ {1} = 3,183536647}$	${ displaystyle k_ {2} = f (t_ {2} + { tfrac {2} {3}} h, y_ {2} + { tfrac {2} {3}} hk_ {1})}$
	${ displaystyle y_ {3} = y_ {2} + h ({ tfrac {1} {4}} k_ {1} + { tfrac {3} {4}} k_ {2}) = { underline { 1.227417567}}}$
${ displaystyle t_ {4} = 1.1 двоеточие}$
	${ displaystyle y_ {3} = 1,227417567}$	${ displaystyle k_ {1} = 3,796866512}$	${ displaystyle k_ {2} = f (t_ {3} + { tfrac {2} {3}} h, y_ {3} + { tfrac {2} {3}} hk_ {1})}$
	${ displaystyle y_ {4} = y_ {3} + h ({ tfrac {1} {4}} k_ {1} + { tfrac {3} {4}} k_ {2}) = { underline { 1.335079087}}.}.$

Численные решения соответствуют подчеркнутым значениям.

Адаптивные методы Рунге – Кутты.

Адаптивные методы предназначены для оценки локальной ошибки усечения одного шага Рунге – Кутты. Это делается двумя способами, один с порядком ${ displaystyle p}$ и один с заказом ${ displaystyle p-1}$. Эти методы переплетены, т.е. имеют общие промежуточные этапы. Благодаря этому оценка ошибки требует небольших или пренебрежимо малых вычислительных затрат по сравнению с шагом с методом более высокого порядка.

Во время интегрирования размер шага адаптируется так, что оцененная ошибка остается ниже определенного пользователем порога: если ошибка слишком велика, шаг повторяется с меньшим размером шага; если ошибка намного меньше, размер шага увеличивается для экономии времени. Это приводит к (почти) оптимальному размеру шага, что экономит время вычислений. Более того, пользователю не нужно тратить время на поиск подходящего размера шага.

Шаг младшего порядка определяется выражением

${ displaystyle y_ {n + 1} ^ {*} = y_ {n} + h sum _ {i = 1} ^ {s} b_ {i} ^ {*} k_ {i},}$

куда ${ displaystyle k_ {i}}$ такие же, как и для метода высшего порядка. Тогда ошибка

${ displaystyle e_ {n + 1} = y_ {n + 1} -y_ {n + 1} ^ {*} = h sum _ {i = 1} ^ {s} (b_ {i} -b_ {i } ^ {*}) k_ {i},}$

который ${ Displaystyle О (ч ^ {р})}$. Таблица Бутчера для этого метода расширена, чтобы дать значения ${ displaystyle b_ {i} ^ {*}}$:

	0
	${ displaystyle c_ {2}}$	${ displaystyle a_ {21}}$
	${ displaystyle c_ {3}}$	${ displaystyle a_ {31}}$	${ displaystyle a_ {32}}$
	${ displaystyle vdots}$	${ displaystyle vdots}$		${ displaystyle ddots}$
	${ displaystyle c_ {s}}$	${ displaystyle a_ {s1}}$	${ displaystyle a_ {s2}}$	${ displaystyle cdots}$	${ displaystyle a_ {s, s-1}}$
		${ displaystyle b_ {1}}$	${ displaystyle b_ {2}}$	${ displaystyle cdots}$	${ displaystyle b_ {s-1}}$	${ displaystyle b_ {s}}$
		${ displaystyle b_ {1} ^ {*}}$	${ displaystyle b_ {2} ^ {*}}$	${ displaystyle cdots}$	${ displaystyle b_ {s-1} ^ {*}}$	${ displaystyle b_ {s} ^ {*}}$

В Метод Рунге – Кутты – Фельберга. имеет два метода порядков 5 и 4. Его расширенная таблица Мясника:

Однако простейший адаптивный метод Рунге – Кутты предполагает комбинирование Метод Хойна, который имеет порядок 2, с Метод Эйлера, который является порядком 1. Его расширенная таблица Мясника:

Другими адаптивными методами Рунге – Кутты являются Богацкий – Шампиновый метод (порядки 3 и 2), Кэш – метод Карпа и Метод Дорманда – Принса (оба с порядком 5 и 4).

Неконфлюэнтные методы Рунге – Кутты

Метод Рунге-Кутты называется несговорчивый ^[15] если все ${ Displaystyle c_ {я}, , я = 1,2, ldots, s}$ различны.

Методы Рунге – Кутта-Нистрома.

Методы Рунге-Кутта-Нюстрёма - это специализированные методы Рунге-Кутты, которые оптимизированы для дифференциальных уравнений второго порядка вида:^[16]

${ displaystyle { frac {d ^ {2} y} {dt ^ {2}}} = f (y, t)}$

С другой стороны, общий метод Рунге-Кутта-Нюстрёма оптимизирован для дифференциальных уравнений второго порядка вида:^[17]

${ displaystyle { frac {d ^ {2} y} {dt ^ {2}}} = f (y, { dot {y}}, t)}$

Неявные методы Рунге – Кутты

Все методы Рунге-Кутты, упомянутые до сих пор, являются явные методы. Явные методы Рунге – Кутты, как правило, не подходят для решения жесткие уравнения потому что их область абсолютной стабильности мала; в частности, он ограничен.^[18]Этот вопрос особенно важен при решении уравнения в частных производных.

Неустойчивость явных методов Рунге – Кутты мотивирует развитие неявных методов. Неявный метод Рунге – Кутты имеет вид

${ displaystyle y_ {n + 1} = y_ {n} + h sum _ {i = 1} ^ {s} b_ {i} k_ {i},}$

куда

${ Displaystyle к_ {я} = е влево (t_ {n} + c_ {i} h, y_ {n} + h sum _ {j = 1} ^ {s} a_ {ij} k_ {j} right), quad i = 1, ldots, s.}$ ^[19]

Разница с явным методом заключается в том, что в явном методе сумма более j только подходит к я - 1. Это также отображается в таблице Бутчера: матрица коэффициентов ${ displaystyle a_ {ij}}$ явного метода является нижнетреугольным. В неявном методе сумма более j подходит к s а матрица коэффициентов не является треугольной, давая таблицу Бутчера вида^[12]

${ displaystyle { begin {array} {c | cccc} c_ {1} & a_ {11} & a_ {12} & dots & a_ {1s} c_ {2} & a_ {21} & a_ {22} & dots & a_ {2s} vdots & vdots & vdots & ddots & vdots c_ {s} & a_ {s1} & a_ {s2} & dots & a_ {ss} hline & b_ {1} & b_ {2} & dots & b_ {s} & b_ {1} ^ {*} & b_ {2} ^ {*} & dots & b_ {s} ^ {*} end {array}} = { begin {array} {c | c} mathbf {c} & A hline & mathbf {b ^ {T}} end {array}}}$

Видеть Адаптивные методы Рунге-Кутты выше для объяснения ${ displaystyle b ^ {*}}$ ряд.

Следствием этого различия является то, что на каждом шаге необходимо решать систему алгебраических уравнений. Это значительно увеличивает вычислительные затраты. Если метод с s этапов используется для решения дифференциального уравнения с м компонентов, то система алгебраических уравнений имеет РС составные части. Это можно противопоставить неявному линейные многоступенчатые методы (другое большое семейство методов для ODE): неявный s-шаговый линейный многоступенчатый метод требует решения системы алгебраических уравнений с м компоненты, поэтому размер системы не увеличивается с увеличением количества шагов.^[20]

Примеры

Простейшим примером неявного метода Рунге – Кутты является метод обратный метод Эйлера:

${ displaystyle y_ {n + 1} = y_ {n} + hf (t_ {n} + h, y_ {n + 1}). ,}$

Таблица Мясника для этого проста:

${ displaystyle { begin {array} {c | c} 1 & 1 hline & 1 end {array}}}$

Эта таблица Бутчера соответствует формулам

${ displaystyle k_ {1} = f (t_ {n} + h, y_ {n} + hk_ {1}) quad { text {and}} quad y_ {n + 1} = y_ {n} + hk_ {1},}$

который можно перестроить, чтобы получить формулу обратного метода Эйлера, указанную выше.

Другой пример неявного метода Рунге – Кутты - это трапеция. Его таблица Мясника:

${ displaystyle { begin {array} {c | cc} 0 & 0 & 0 1 & { frac {1} {2}} & { frac {1} {2}} hline & { frac {1} {2}} & { frac {1} {2}} & 1 & 0 end {array}}}$

Правило трапеции - это метод коллокации (как описано в этой статье). Все методы коллокации являются неявными методами Рунге-Кутты, но не все неявные методы Рунге-Кутты являются методами коллокации.^[21]

В Методы Гаусса – Лежандра сформировать семейство методов коллокации на основе Квадратура Гаусса. Метод Гаусса – Лежандра с s этапов имеет порядок 2s (таким образом, могут быть построены методы сколь угодно высокого порядка).^[22] Метод с двумя этапами (и, следовательно, порядок четыре) имеет таблицу Мясника:

${ displaystyle { begin {array} {c | cc} { frac {1} {2}} - { frac {1} {6}} { sqrt {3}} & { frac {1} { 4}} & { frac {1} {4}} - { frac {1} {6}} { sqrt {3}} { frac {1} {2}} + { frac {1 } {6}} { sqrt {3}} & { frac {1} {4}} + { frac {1} {6}} { sqrt {3}} и { frac {1} {4 }} hline & { frac {1} {2}} & { frac {1} {2}} & { frac {1} {2}} + { frac {1} {2 }} { sqrt {3}} & { frac {1} {2}} - { frac {1} {2}} { sqrt {3}} end {array}}}$ ^[20]

Стабильность

Преимущество неявных методов Рунге – Кутты перед явными заключается в их большей устойчивости, особенно в применении к жесткие уравнения. Рассмотрим линейное тестовое уравнение y ' = λу. Примененный к этому уравнению метод Рунге – Кутты сводится к итерации ${ Displaystyle у_ {п + 1} = г (ч лямбда) , у_ {п}}$, с р данный

${ displaystyle r (z) = 1 + zb ^ {T} (I-zA) ^ {- 1} e = { frac { det (I-zA + zeb ^ {T})} { det (I -zA)}},}$ ^[23]

куда е обозначает вектор единиц. Функция р называется функция устойчивости.^[24] Из формулы следует, что р является фактором двух многочленов степени s если метод имеет s этапы.Явные методы имеют строго нижнетреугольную матрицу А, откуда следует, что det (я − zA) = 1 и что функция устойчивости является полиномом.^[25]

Численное решение линейного тестового уравнения обращается в ноль, если | р(z) | <1 с z = часλ. Набор таких z называется область абсолютной стабильности. В частности, метод называется абсолютная стабильность я упал z с Re (z) <0 находятся в области абсолютной устойчивости. Функция устойчивости явного метода Рунге – Кутты является полиномом, поэтому явные методы Рунге – Кутты никогда не могут быть A-стабильными.^[25]

Если метод имеет порядок п, то функция устойчивости удовлетворяет ${ displaystyle r (z) = { textrm {e}} ^ {z} + O (z ^ {p + 1})}$ в качестве ${ displaystyle z to 0}$. Таким образом, представляет интерес изучение частных многочленов заданных степеней, которые наилучшим образом аппроксимируют экспоненциальную функцию. Они известны как Аппроксимации Паде. Аппроксимация Паде с числителем степени м и знаменатель степени п A-стабильно тогда и только тогда, когда м ≤ п ≤ м + 2.^[26]

Метод Гаусса – Лежандра с s этапов имеет порядок 2s, поэтому его функция устойчивости является аппроксимацией Паде с м = п = s. Отсюда следует, что метод A-устойчив.^[27] Это показывает, что A-стабильный Рунге – Кутта может иметь сколь угодно высокий порядок. Напротив, порядок A-стабильной линейные многоступенчатые методы не может превышать двух.^[28]

B-стабильность

В А-стабильность Концепция решения дифференциальных уравнений связана с линейным автономным уравнением ${ displaystyle y '= lambda y}$. Дальквист предложил исследование устойчивости численных схем применительно к нелинейным системам, удовлетворяющим условию монотонности. Соответствующие концепции были определены как G-стабильность для многоступенчатых методов (и связанных с ними одноэтапных методов) и B-стабильность (Butcher, 1975) для методов Рунге – Кутты. Применение метода Рунге – Кутты к нелинейной системе ${ Displaystyle у '= е (у)}$, что подтверждает ${ Displaystyle langle f (y) -f (z), y-z rangle <0}$, называется B-стабильный, если из этого условия следует ${ displaystyle | y_ {n + 1} -z_ {n + 1} | leq | y_ {n} -z_ {n} |}$ для двух численных решений.

Позволять ${ displaystyle B}$, ${ displaystyle M}$ и ${ displaystyle Q}$ быть тремя ${ displaystyle s times s}$ матрицы, определяемые

${ displaystyle B = operatorname {diag} (b_ {1}, b_ {2}, ldots, b_ {s}), , M = BA + A ^ {T} B-bb ^ {T}, , Q = BA ^ {- 1} + A ^ {- T} BA ^ {- T} bb ^ {T} A ^ {- 1}.}$

Метод Рунге-Кутты называется алгебраически устойчивый ^[29] если матрицы ${ displaystyle B}$ и ${ displaystyle M}$ оба неотрицательно определены. Достаточное условие для B-стабильность ^[30] является: ${ displaystyle B}$ и ${ displaystyle Q}$ неотрицательно определенные.

Вывод метода четвертого порядка Рунге – Кутты.

В общем, метод порядка Рунге – Кутты ${ displaystyle s}$ можно записать как:

${ displaystyle y_ {t + h} = y_ {t} + h cdot sum _ {i = 1} ^ {s} a_ {i} k_ {i} + { mathcal {O}} (h ^ { s + 1}),}$

куда:

${ displaystyle k_ {i} = y_ {t} + h cdot sum _ {j = 1} ^ {s} beta _ {ij} f left (k_ {j}, t_ {n} + альфа _ {i} h right)}$

- приращения, полученные при оценке производных от ${ displaystyle y_ {t}}$ на ${ displaystyle i}$-й порядок.

Разрабатываем вывод^[31] для метода Рунге – Кутты четвертого порядка по общей формуле с ${ displaystyle s = 4}$ оценивается, как объяснялось выше, в начальной, средней и конечной точках любого интервала ${ Displaystyle (т, т + ч)}$; таким образом, выбираем:

${ displaystyle { begin {align} & alpha _ {i} && beta _ {ij} alpha _ {1} & = 0 & beta _ {21} & = { frac {1} {2 }} alpha _ {2} & = { frac {1} {2}} & beta _ {32} & = { frac {1} {2}} alpha _ {3} & = { frac {1} {2}} & beta _ {43} & = 1 alpha _ {4} & = 1 && конец {выровнено}}}$

и ${ displaystyle beta _ {ij} = 0}$ иначе. Начнем с определения следующих величин:

${ displaystyle { begin {align} y_ {t + h} ^ {1} & = y_ {t} + hf left (y_ {t}, t right) y_ {t + h} ^ { 2} & = y_ {t} + hf left (y_ {t + h / 2} ^ {1}, t + { frac {h} {2}} right) y_ {t + h} ^ {3} & = y_ {t} + hf left (y_ {t + h / 2} ^ {2}, t + { frac {h} {2}} right) end {выравнивается}}}$

куда ${ displaystyle y_ {t + h / 2} ^ {1} = { dfrac {y_ {t} + y_ {t + h} ^ {1}} {2}}}$ и ${ displaystyle y_ {t + h / 2} ^ {2} = { dfrac {y_ {t} + y_ {t + h} ^ {2}} {2}}}$.Если мы определим:

${ displaystyle { begin {align} k_ {1} & = f (y_ {t}, t) k_ {2} & = f left (y_ {t + h / 2} ^ {1}, t + { frac {h} {2}} right) = f left (y_ {t} + { frac {h} {2}} k_ {1}, t + { frac {h} {2 }} right) k_ {3} & = f left (y_ {t + h / 2} ^ {2}, t + { frac {h} {2}} right) = f left ( y_ {t} + { frac {h} {2}} k_ {2}, t + { frac {h} {2}} right) k_ {4} & = f left (y_ {t + h} ^ {3}, t + h right) = f left (y_ {t} + hk_ {3}, t + h right) end {выровнено}}}$

и для предыдущих соотношений мы можем показать, что следующие равенства справедливы до ${ Displaystyle { mathcal {O}} (ч ^ {2})}$:

${ displaystyle { begin {align} k_ {2} & = f left (y_ {t + h / 2} ^ {1}, t + { frac {h} {2}} right) = f left (y_ {t} + { frac {h} {2}} k_ {1}, t + { frac {h} {2}} right) & = f left (y_ {t}, t right) + { frac {h} {2}} { frac {d} {dt}} f left (y_ {t}, t right) k_ {3} & = f left (y_ {t + h / 2} ^ {2}, t + { frac {h} {2}} right) = f left (y_ {t} + { frac {h} {2}} f left (y_ {t} + { frac {h} {2}} k_ {1}, t + { frac {h} {2}} right), t + { frac {h} {2 }} right) & = f left (y_ {t}, t right) + { frac {h} {2}} { frac {d} {dt}} left [f left (y_ {t}, t right) + { frac {h} {2}} { frac {d} {dt}} f left (y_ {t}, t right) right] k_ {4} & = f left (y_ {t + h} ^ {3}, t + h right) = f left (y_ {t} + hf left (y_ {t} + { frac {h} {2}} k_ {2}, t + { frac {h} {2}} right), t + h right) & = f left (y_ {t} + hf left (y_ {t} + { frac {h} {2}} f left (y_ {t} + { frac {h} {2}} f left (y_ {t}, t right) ), t + { frac {h} {2}} right), t + { frac {h} {2}} right), t + h right) & = f left (y_ {t}, t right) + h { frac {d} {dt}} left [f left (y_ {t}, t right) + { frac {h} {2}} { frac {d} {dt}} left [f left (y_ {t}, t right) + { frac {h} {2}} { frac {d} {dt}} f left (y_ {t}, t right) right] right] end {выравнивается}}}$

куда:

${ displaystyle { frac {d} {dt}} f (y_ {t}, t) = { frac { partial} { partial y}} f (y_ {t}, t) { dot {y}} _ {t} + { frac { partial} { partial t}} f (y_ {t}, t) = f_ {y} (y_ {t}, t) { dot { y}} + f_ {t} (y_ {t}, t): = { ddot {y}} _ {t}}$

полная производная от ${ displaystyle f}$ относительно времени.

Если теперь выразить общую формулу, используя то, что мы только что вывели, мы получим:

${ displaystyle { begin {align} y_ {t + h} = {} & y_ {t} + h left lbrace a cdot f (y_ {t}, t) + b cdot left [f ( y_ {t}, t) + { frac {h} {2}} { frac {d} {dt}} f (y_ {t}, t) right] right. + & { } + c cdot left [f (y_ {t}, t) + { frac {h} {2}} { frac {d} {dt}} left [f left (y_ {t} , t right) + { frac {h} {2}} { frac {d} {dt}} f (y_ {t}, t) right] right] + & {} + d cdot left [f (y_ {t}, t) + h { frac {d} {dt}} left [f (y_ {t}, t) + { frac {h} {2 }} { frac {d} {dt}} left [f (y_ {t}, t) + left. { frac {h} {2}} { frac {d} {dt}} f (y_ {t}, t) right] right] right] right rbrace + { mathcal {O}} (h ^ {5}) = {} & y_ {t} + a cdot hf_ {t} + b cdot hf_ {t} + b cdot { frac {h ^ {2}} {2}} { frac {df_ {t}} {dt}} + c cdot hf_ {t } + c cdot { frac {h ^ {2}} {2}} { frac {df_ {t}} {dt}} + & {} + c cdot { frac {h ^ {3 }} {4}} { frac {d ^ {2} f_ {t}} {dt ^ {2}}} + d cdot hf_ {t} + d cdot h ^ {2} { frac {df_ {t}} {dt}} + d cdot { frac {h ^ {3}} {2}} { frac {d ^ {2} f_ {t}} {dt ^ {2}}} + d cdot { frac {h ^ {4}} {4}} { frac {d ^ {3} f_ {t}} {dt ^ {3}}} + { mathcal {O}} (h ^ { 5}) конец {выровнено}}}$

и сравнивая это с Серия Тейлор из ${ displaystyle y_ {t + h}}$ вокруг ${ displaystyle y_ {t}}$:

${ displaystyle { begin {align} y_ {t + h} & = y_ {t} + h { dot {y}} _ {t} + { frac {h ^ {2}} {2}} { ddot {y}} _ {t} + { frac {h ^ {3}} {6}} y_ {t} ^ {(3)} + { frac {h ^ {4}} {24}} y_ {t} ^ {(4)} + { mathcal {O}} (h ^ {5}) = & = y_ {t} + hf (y_ {t}, t) + { frac { h ^ {2}} {2}} { frac {d} {dt}} f (y_ {t}, t) + { frac {h ^ {3}} {6}} { frac {d) ^ {2}} {dt ^ {2}}} f (y_ {t}, t) + { frac {h ^ {4}} {24}} { frac {d ^ {3}} {dt ^ {3}}} f (y_ {t}, t) конец {выровнено}}}$

получаем систему ограничений на коэффициенты:

${ displaystyle { begin {cases} & a + b + c + d = 1 [6pt] & { frac {1} {2}} b + { frac {1} {2}} c + d = { frac {1} {2}} [6pt] & { frac {1} {4}} c + { frac {1} {2}} d = { frac {1} {6}} [6pt] & { frac {1} {4}} d = { frac {1} {24}} end {case}}}$

который при решении дает ${ displaystyle a = { frac {1} {6}}, b = { frac {1} {3}}, c = { frac {1} {3}}, d = { frac {1} {6}}}$ как указано выше.

Смотрите также

• Метод Эйлера
• Список методов Рунге – Кутты
• Численные методы решения обыкновенных дифференциальных уравнений
• Метод Рунге – Кутта (SDE)
• Общие линейные методы
• Интегратор групп Ли

Примечания

Рекомендации

• Рунге, Карл Давид Толме (1895), "Über die numerische Auflösung von Differentialgleichungen", Mathematische Annalen, Springer, 46 (2): 167–178, Дои:10.1007 / BF01446807.
• Кутта, Мартин (1901), Beitrag zur näherungweisen Integration totaler Differentialgleichungen.
• Ascher, Uri M .; Петцольд, Линда Р. (1998), Компьютерные методы решения обыкновенных дифференциальных и дифференциально-алгебраических уравнений, Филадельфия: Общество промышленной и прикладной математики, ISBN  978-0-89871-412-8.
• Аткинсон, Кендалл А. (1989), Введение в численный анализ (2-е изд.), Нью-Йорк: Джон Уайли и сыновья, ISBN  978-0-471-50023-0.
• Мясник, Джон С. (Май 1963 г.), «Коэффициенты для изучения интеграционных процессов Рунге-Кутта», Журнал Австралийского математического общества, 3 (2): 185–201, Дои:10.1017 / S1446788700027932.
• Мясник, Джон С. (1975), "Свойство устойчивости неявных методов Рунге-Кутта", КУСОЧЕК, 15 (4): 358–361, Дои:10.1007 / bf01931672.
• Мясник, Джон С. (2008), Численные методы решения обыкновенных дифференциальных уравнений., Нью-Йорк: Джон Уайли и сыновья, ISBN  978-0-470-72335-7.
• Cellier, F .; Кофман, Э. (2006), Непрерывное моделирование системы, Springer Verlag, ISBN  0-387-26102-8.
• Дальквист, Гермунд (1963), «Специальная задача устойчивости для линейных многоступенчатых методов», КУСОЧЕК, 3: 27–43, Дои:10.1007 / BF01963532, HDL:10338.dmlcz / 103497, ISSN  0006-3835.
• Форсайт, Джордж Э .; Малькольм, Майкл А .; Молер, Клив Б. (1977), Компьютерные методы математических вычислений, Prentice-Hall (см. главу 6).
• Хайрер, Эрнст; Норсетт, Сиверт Пол; Ваннер, Герхард (1993), Решение обыкновенных дифференциальных уравнений I: нежесткие задачи, Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-56670-0.
• Хайрер, Эрнст; Ваннер, Герхард (1996), Решение обыкновенных дифференциальных уравнений II: жесткие и дифференциально-алгебраические задачи (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-60452-5.
• Изерлес, Арье (1996), Первый курс численного анализа дифференциальных уравнений, Издательство Кембриджского университета, ISBN  978-0-521-55655-2.
• Ламберт, JD (1991), Численные методы для обыкновенных дифференциальных систем. Проблема начальной стоимости, Джон Уайли и сыновья, ISBN  0-471-92990-5
• Кау, Аутар; Калу, Эгву (2008), Численные методы с приложениями (1-е изд.), Autarkaw.com.
• Кутта, Мартин (1901), "Beitrag zur näherungsweisen Integration Totaler Differentialgleichungen", Zeitschrift für Mathematik und Physik, 46: 435–453.
• Press, William H .; Флэннери, Брайан П .; Теукольский, Саул А.; Веттерлинг, Уильям Т. (2007), «Раздел 17.1 Метод Рунге-Кутты», Числовые рецепты: искусство научных вычислений (3-е изд.), Издательство Кембриджского университета, ISBN  978-0-521-88068-8. Также, Раздел 17.2. Адаптивный контроль размера шага для Рунге-Кутты.
• Стоер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-0-387-95452-3.
• Сули, Эндре; Майерс, Дэвид (2003), Введение в численный анализ, Издательство Кембриджского университета, ISBN  0-521-00794-1.
• Тан, Делин; Чен, Чжэн (2012), "Об общей формуле метода Рунге-Кутты четвертого порядка" (PDF), Журнал математических наук и математического образования, 7 (2): 1–10.
• справочник по продвинутой дискретной математике игнорируется (код - mcs033)

внешняя ссылка

• «Метод Рунге-Кутта», Энциклопедия математики, EMS Press, 2001 [1994]
• Метод Рунге – Кутты 4-го порядка
• Реализация библиотеки компонентов трекера в Matlab - Реализует 32 встроенных алгоритма Рунге Кутта в РунгеКстеп, 24 встроенных алгоритма Рунге-Кутта-Нистрома в РунгеKNystroemSStep и 4 общих алгоритма Рунге-Кутта-Нистрома в РунгеKNystroemGStep.