Сравнение методов Рунге-Кутты для дифференциального уравнения y '= sin (t) ^ 2 * y (красный - точное решение)
Метод Рунге – Кутты.
Склоны по классическому методу Рунге-Кутта
Наиболее широко известный член семейства Рунге-Кутта обычно упоминается как «RK4», «классический метод Рунге-Кутта» или просто как «метод Рунге-Кутта».
Здесь неизвестная функция (скаляр или вектор) времени , которые мы хотели бы приблизить; нам говорят, что, скорость, с которой изменения, это функция и из сам. В начальное время соответствующий ценность . Функцияи начальные условия, дано.
(Примечание: приведенные выше уравнения имеют разные, но эквивалентные определения в разных текстах). [4]
Здесь является RK4-приближением , а следующее значение () определяется текущей стоимостью () плюс средневзвешенное значение четырех приращений, где каждое приращение является произведением размера интервала h и предполагаемого наклона, заданного функцией f в правой части дифференциального уравнения.
- наклон в начале интервала, используя ( Метод Эйлера );
- наклон в середине интервала, используя а также ;
это снова наклон в средней точке, но теперь с использованием а также ;
- наклон в конце интервала, используя а также .
При усреднении четырех уклонов больший вес придается уклонам в средней точке. Если не зависит от , так что дифференциальное уравнение эквивалентно простому интегралу, то RK4 - это правило Симпсона . [5]
Во многих практических приложениях функция не зависит от (так называемая автономная система , или инвариантная во времени система, особенно в физике), и их приращения вообще не вычисляются и не передаются в функцию, с только окончательной формулой для использовал.
Явные методы Рунге – Кутты
Семейство явных методов Рунге – Кутты является обобщением упомянутого выше метода RK4. Это дается
(Примечание: приведенные выше уравнения могут иметь разные, но эквивалентные определения в некоторых текстах). [4]
Чтобы указать конкретный метод, необходимо указать целое число s (количество этапов) и коэффициенты a ij (для 1 ≤ j < i ≤ s ), b i (для i = 1, 2, ..., s ) и c i (для i = 2, 3, ..., s ). Матрица [ a ij ] называется матрицей Рунге – Кутты , а b i и c i называются весами и узлами . [7] Эти данные обычно располагаются в виде мнемонического устройства, известного как таблица Мясника (в честь Джона К. Батчера ):
Ряд Тейлора разложение показывает , что метод Рунге-Кутта совместна тогда и только тогда ,
Существуют также сопутствующие требования, если требуется, чтобы метод имел определенный порядок p , что означает, что локальная ошибка усечения равна O ( h p +1 ). Их можно вывести из определения самой ошибки усечения. Например, двухэтапный метод имеет порядок 2, если b 1 + b 2 = 1, b 2 c 2 = 1/2 и b 2 a 21 = 1/2. [8] Обратите внимание, что популярным условием определения коэффициентов является [9]
Однако одно это условие не является ни достаточным, ни необходимым для согласованности. [10]
В общем, если явный -этапный метод Рунге – Кутта имеет порядок , то можно доказать, что количество стадий должно удовлетворять , и если , тогда . [11] Однако неизвестно, являются ли эти границы точными во всех случаях; например, все известные методы 8-го порядка имеют не менее 11 этапов, хотя возможно, что существуют методы с меньшим числом этапов. (Приведенная выше граница предполагает, что может существовать метод с 9 этапами; но также может быть и то, что граница просто не точна.) Действительно, это открытый вопрос, какое точное минимальное количество этапов для явного метода Рунге – Кутты, чтобы иметь порядок в тех случаях, когда еще не обнаружены методы, удовлетворяющие приведенным выше оценкам с равенством. Вот некоторые известные значения: [12]
Доказуемые оценки выше означают, что мы не можем найти методы порядков которые требуют меньшего количества этапов, чем методы, которые мы уже знаем для этих заказов. Однако вполне возможно, что мы найдем способ упорядочения в котором всего 8 стадий, тогда как в единственных, известных сегодня, есть не менее 9 стадий, как показано в таблице.
Примеры
Метод RK4 подпадает под эти рамки. Его таблица [13]
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. [14] Основным преимуществом этого метода является то, что почти все коэффициенты ошибок меньше, чем в популярном методе, но для этого требуется немного больше FLOP (операций с плавающей запятой) на временной шаг. Его таблица Мясника
0
1/3
1/3
2/3
-1/3
1
1
1
−1
1
1/8
3/8
3/8
1/8
Однако простейший метод Рунге – Кутты - это (прямой) метод Эйлера , задаваемый формулой. Это единственный непротиворечивый явный метод Рунге – Кутты с одним этапом. Соответствующая таблица
0
1
Методы второго порядка с двумя этапами
Пример метода второго порядка с двумя этапами предоставляется методом средней точки :
Соответствующая таблица
0
1/2
1/2
0
1
Метод средней точки - не единственный метод Рунге – Кутты второго порядка, состоящий из двух этапов; существует семейство таких методов, параметризованных параметром α и задаваемых формулой [15]
Его таблица Мясника
0
В этой семье дает метод средней точки, а это метод Хойна . [5]
Использовать
В качестве примера рассмотрим двухэтапный метод Рунге – Кутты второго порядка с α = 2/3, также известный как метод Ральстона . Это дано таблицей
0
2/3
2/3
1/4
3/4
с соответствующими уравнениями
Этот метод используется для решения задачи начального значения
с размером шага h = 0,025, поэтому метод должен состоять из четырех шагов.
Метод работает следующим образом:
Численные решения соответствуют подчеркнутым значениям.
Адаптивные методы Рунге – Кутты.
Адаптивные методы предназначены для оценки локальной ошибки усечения одного шага Рунге – Кутты. Это делается двумя способами, один с порядком и один с порядком . Эти методы переплетены, т. Е. Имеют общие промежуточные этапы. Благодаря этому оценка ошибки требует небольших или пренебрежимо малых вычислительных затрат по сравнению с шагом с помощью метода более высокого порядка.
Во время интегрирования размер шага адаптируется так, чтобы оцененная ошибка оставалась ниже определенного пользователем порога: если ошибка слишком велика, шаг повторяется с меньшим размером шага; если ошибка намного меньше, размер шага увеличивается для экономии времени. Это приводит к (почти) оптимальному размеру шага, что экономит время вычислений. Более того, пользователю не нужно тратить время на поиск подходящего размера шага.
Шаг более низкого порядка определяется выражением
где такие же, как и для метода высшего порядка. Тогда ошибка
который . Таблица Бутчера для этого метода расширена, чтобы дать значения:
Однако простейший адаптивный метод Рунге – Кутты включает в себя сочетание метода Хойна , который имеет порядок 2, с методом Эйлера , который является порядком 1. Его расширенная таблица Бутчера имеет следующий вид:
Метод Рунге – Кутты называется неконфлюэнтным [16], если все различны.
Методы Рунге – Кутты – Нистрома.
Методы Рунге – Кутты – Нистрома - это специализированные методы Рунге-Кутты, которые оптимизированы для дифференциальных уравнений второго порядка следующего вида: [17] [18]
Неявные методы Рунге – Кутты
Все упомянутые до сих пор методы Рунге – Кутты являются явными . Явные методы Рунге – Кутты обычно не подходят для решения жестких уравнений, поскольку их область абсолютной устойчивости мала; в частности, он ограничен. [19] Этот вопрос особенно важен при решении уравнений в частных производных .
Неустойчивость явных методов Рунге – Кутты мотивирует развитие неявных методов. Неявный метод Рунге – Кутты имеет вид
где
[20]
Разница с явным методом заключается в том, что в явном методе сумма по j возрастает только до i - 1. Это также отображается в таблице Бутчера: матрица коэффициентовявного метода является нижнетреугольным. В неявном методе сумма по j увеличивается до s, а матрица коэффициентов не является треугольной, давая таблицу Бутчера вида [13]
См. Выше адаптивные методы Рунге-Кутты для объяснения строка.
Следствием этого различия является то, что на каждом шаге необходимо решать систему алгебраических уравнений. Это значительно увеличивает вычислительные затраты. Если для решения дифференциального уравнения с m компонентами используется метод с s этапами , то система алгебраических уравнений имеет ms компоненты. Этому можно противопоставить неявные линейные многоступенчатые методы (другое большое семейство методов для ОДУ): неявный s- ступенчатый линейный многоступенчатый метод должен решать систему алгебраических уравнений только с m компонентами, поэтому размер системы не увеличивается. по мере увеличения количества шагов. [21]
Примеры
Простейшим примером неявного метода Рунге – Кутты является обратный метод Эйлера :
Таблица Мясника для этого проста:
Эта таблица Бутчера соответствует формулам
который можно перестроить, чтобы получить формулу обратного метода Эйлера, указанную выше.
Другой пример неявного метода Рунге – Кутты - правило трапеций . Его таблица Мясника:
Правило трапеции - это метод коллокации (как описано в этой статье). Все методы коллокации являются неявными методами Рунге-Кутты, но не все неявные методы Рунге-Кутты являются методами коллокации. [22]
Эти методы Гаусса-Лежандра образуют семейство методов коллокации на основе гауссовой квадратуре . Метод Гаусса – Лежандра с s этапами имеет порядок 2 s (таким образом, могут быть построены методы с произвольно высоким порядком). [23] Метод с двумя этапами (и, следовательно, порядок четыре) имеет таблицу Мясника:
[21]
Стабильность
Преимущество неявных методов Рунге – Кутты перед явными заключается в их большей устойчивости, особенно в применении к жестким уравнениям . Рассмотрим линейное тестовое уравнение y ' = λ y . Метод Рунге – Кутты, примененный к этому уравнению, сводится к итерации, с r, заданным как
[24]
где e обозначает вектор единиц. Функция r называется функцией устойчивости . [25] Из формулы следует, что r является частным двух многочленов степени s, если метод имеет s этапов. Явные методы имеют строго нижнюю треугольную матрицу A , из чего следует, что det ( I - zA ) = 1 и что функция устойчивости является полиномом. [26]
Численное решение линейного тестового уравнения обращается в ноль, если | г ( г ) | <1 при z = h λ. Множество таких z называется областью абсолютной устойчивости . В частности, метод называется абсолютно устойчивым, если все z с Re ( z ) <0 находятся в области абсолютной устойчивости. Функция устойчивости явного метода Рунге – Кутты является полиномом, поэтому явные методы Рунге – Кутта никогда не могут быть A-стабильными. [26]
Если метод имеет порядок p , то функция устойчивости удовлетворяет в виде . Таким образом, представляет интерес изучение частных многочленов заданных степеней, которые наилучшим образом аппроксимируют экспоненциальную функцию. Они известны как аппроксимации Паде . Аппроксимация Паде с числителем степени m и знаменателем степени n A-устойчива тогда и только тогда, когда m ≤ n ≤ m + 2. [27]
Метод Гаусса – Лежандра с s этапами имеет порядок 2 s , поэтому его функция устойчивости является аппроксимацией Паде с m = n = s . Следовательно, метод является A-устойчивым. [28] Это показывает, что A-стабильный Рунге – Кутта может иметь сколь угодно высокий порядок. Напротив, порядок A-устойчивых линейных многоступенчатых методов не может превышать двух. [29]
B-стабильность
Концепция A-устойчивости решения дифференциальных уравнений связана с линейным автономным уравнением. Далквист предложил исследование устойчивости численных схем применительно к нелинейным системам, удовлетворяющим условию монотонности. Соответствующие концепции были определены как G-устойчивость для многоступенчатых методов (и связанных одноэлементных методов) и B-устойчивость (Butcher, 1975) для методов Рунге – Кутты. Применение метода Рунге – Кутты к нелинейной системе., что подтверждает , называется B-стабильной , если из этого условия следует для двух численных решений.
Позволять , а также быть тремя матрицы, определяемые
Метод Рунге – Кутты называется алгебраически устойчивым [30], если матрицы а также оба неотрицательно определены. Достаточным условием B-устойчивости [31] является: а также неотрицательно определенные.
Вывод метода четвертого порядка Рунге – Кутты.
В целом метод порядка Рунге – Кутты можно записать как:
где:
- приращения, полученные при оценке производных от на -й порядок.
Мы развиваем вывод [32] для метода четвертого порядка Рунге – Кутты, используя общую формулу с оценивается, как описано выше, в начальной, средней и конечной точках любого интервала ; таким образом, выбираем:
а также иначе. Начнем с определения следующих величин:
где а также . Если мы определим:
и для предыдущих соотношений мы можем показать, что следующие равенства справедливы до :
где:
полная производная от относительно времени.
Если теперь выразить общую формулу, используя то, что мы только что вывели, мы получим:
и сравнивая это с рядом Тейлора из вокруг :
получаем систему ограничений на коэффициенты:
который при решении дает как указано выше.
Смотрите также
Метод Эйлера
Список методов Рунге – Кутты
Численные методы решения обыкновенных дифференциальных уравнений
Метод Рунге – Кутта (SDE)
Общие линейные методы
Интегратор групп Ли
Заметки
^ "Метод Рунге-Кутта" . Dictionary.com . Проверено 4 апреля 2021 года .
^ ДЕВРИС, Пол Л.; ХАСБУН, Хавьер Э. Первый курс вычислительной физики. Второе издание. Jones and Bartlett Publishers: 2011. стр. 215.
^ a b Аткинсон (1989 , с. 423), Хайрер, Норсетт и Ваннер (1993 , с. 134), Кау и Калу (2008 , §8.4) и Стоер и Булирш (2002 , с. 476) не учитывают множитель h в определении этапов. Ашер и Петцольд (1998 , стр. 81), Бутчер (2008 , стр. 93) и Изерлес (1996 , стр. 38) используют значения y в качестве ступеней.
^ а б Süli & Mayers 2003 , стр. 328
^ Press et al. 2007 , стр. 907
^ Iserles 1996 , стр. 38
^ Iserles 1996 , стр. 39
^ Iserles 1996 , стр. 39
^ В качестве контрпримера рассмотрим любую явную двухэтапную схему Рунге-Кутты с а также а также выбран случайно. Этот метод является непротиворечивым и (в общем) сходящимся первого порядка. С другой стороны, одноэтапный метод с несовместимо и не может сходиться, хотя тривиально .
^ Мясник 2008 , стр. 187
^ Butcher 2008 , стр. 187-196
^ а б Süli & Mayers 2003 , стр. 352
^ Hairer, Nørsett & Wanner (1993 , с. 138) относятся к Kutta (1901) .
^ Сули и Майерсом 2003 , стр. 327
Перейти ↑ Lambert 1991 , p. 278
^Дорман, младший; Принц, П.Дж. (октябрь 1978 г.). «Новые алгоритмы Рунге – Кутты для численного моделирования в динамической астрономии». Небесная механика . 18 (3): 223–232. DOI : 10.1007 / BF01230162 .
^Фельберг, Э. (октябрь 1974 г.). Классические формулы Рунге – Кутты – Нистрома седьмого, шестого и пятого порядков с пошаговым управлением для общих дифференциальных уравнений второго порядка (Отчет) (НАСА TR R-432 ed.). Центр космических полетов им. Маршалла, штат Алабама: Национальное управление по аэронавтике и исследованию космического пространства.
Рунге, Карл Дэвид Tolmé (1895 г.), "Убер умереть numerische Auflösung фон Differentialgleichungen" , Mathematische Annalen , Springer , 46 (2): 167-178, DOI : 10.1007 / BF01446807.
Кутта, Мартин (1901), "Beitrag zur näherungsweisen Integration Totaler Differentialgleichungen", Zeitschrift für Mathematik und Physik , 46 : 435–453.
Ascher, Uri M .; Петцольд, Линда Р. (1998), Компьютерные методы для обыкновенных дифференциальных уравнений и дифференциально-алгебраических уравнений , Филадельфия: Общество промышленной и прикладной математики , ISBN 978-0-89871-412-8.
Аткинсон, Кендалл А. (1989), Введение в численный анализ (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN 978-0-471-50023-0.
Мясник, Джон С. (май 1963 г.), «Коэффициенты для изучения Рунге-Кутта интеграционных процессов», журнал Австралийской математического общества , 3 (2): 185-201, DOI : 10,1017 / S1446788700027932.
Мясник, Джон К. (1975), "Свойство устойчивости неявных методов Рунге-Кутта", БИТ , 15 (4): 358-361, DOI : 10.1007 / bf01931672.
Бутчер, Джон К. (2008), Численные методы для обыкновенных дифференциальных уравнений , Нью-Йорк: John Wiley & Sons , ISBN 978-0-470-72335-7.
Cellier, F .; Кофман, Э. (2006), Моделирование непрерывных систем , Springer Verlag , ISBN 0-387-26102-8.
Форсайт, Джордж Э .; Малькольм, Майкл А .; Молер, Клив Б. (1977), Компьютерные методы математических вычислений , Прентис-Холл (см. главу 6).
Хайрер, Эрнст; Норсетт, Сиверт Пол; Ваннер, Герхард (1993), Решение обыкновенных дифференциальных уравнений I: нежесткие задачи , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-3-540-56670-0.
Хайрер, Эрнст; Ваннер, Герхард (1996), Решение обыкновенных дифференциальных уравнений II: Жесткие и дифференциально-алгебраические задачи (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-3-540-60452-5.
Изерлес, Ари (1996), Первый курс численного анализа дифференциальных уравнений , Cambridge University Press , ISBN 978-0-521-55655-2.
Ламберт Дж. Д. (1991), Численные методы для обыкновенных дифференциальных систем. Проблема начальной ценности , John Wiley & Sons , ISBN 0-471-92990-5
Кау, Аутар; Калу, Эгву (2008), Численные методы с приложениями (1-е изд.), Autarkaw.com.
Press, William H .; Теукольский, Саул А .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (2007), «Раздел 17.1 Метод Рунге-Кутты» , Численные рецепты: Искусство научных вычислений (3-е изд.), Cambridge University Press , ISBN 978-0-521-88068-8. Также раздел 17.2. Адаптивное управление размером шага по Рунге-Кутте .
Стоер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-95452-3.
Сули, Эндре; Майерс, Дэвид (2003), Введение в численный анализ , Cambridge University Press , ISBN 0-521-00794-1.
Тан, Делин; Чен, Чжэн (2012), «Об одной общей формуле метода Рунге-Кутты четвертого порядка» (PDF) , Журнал математических наук и математического образования , 7 (2): 1–10.
справочник по продвинутой дискретной математике (код - mcs033)
Джон К. Батчер: «Серия B: алгебраический анализ численных методов», Springer (SSCM, том 55)), ISBN: 978-3030709556 (апрель 2021 г.).
Реализация библиотеки компонентов трекера в Matlab - реализует 32 встроенных алгоритма Рунге-Кутта в RungeKStep, 24 встроенных алгоритма Рунге-Кутта-Нистрома в RungeKNystroemSStepи 4 общих алгоритма Рунге-Кутта-Нистрома в RungeKNystroemGStep.