Чехарда интеграции

В численном анализе чехарда — это метод численного интегрирования дифференциальных уравнений вида ${\ddot {x}}={\frac {d^{2}x}{dt^{2}}}=A(x),$ или эквивалент формы ${\dot {v}}={\frac {dv}{dt}}=A(x),\;{\dot {x}}={\frac {dx}{dt}}=v,$ особенно в случае динамической системы классической механики .

В разных дисциплинах этот метод известен под разными названиями. В частности, он похож на скоростной метод Верле , который является вариантом интегрирования Верле . Интеграция Leapfrog эквивалентна обновлению позиций $x(t)$ и скорости $v(t)={\dot {x}}(t)$ в разные чередующиеся моменты времени расположены в шахматном порядке так, что « перепрыгивают » друг через друга.

Интегрирование чехарды — это метод второго порядка , в отличие от интегрирования Эйлера , который является только первым порядком, но требует такого же количества вычислений функции на шаг. В отличие от интегрирования Эйлера, оно устойчиво при колебательном движении, пока шаг по времени $\Delta t$ является постоянным, и $\Delta t<2/\omega$ . ^[1]

Используя коэффициенты Йошиды и многократно применяя интегратор чехарды с правильными временными шагами, можно создать интегратор гораздо более высокого порядка.

Алгоритм

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

{\begin{aligned}a_{i}&=A(x_{i}),\\v_{i+1/2}&=v_{i-1/2}+a_{i}\,\Delta t,\\x_{i+1}&=x_{i}+v_{i+1/2}\,\Delta t,\end{aligned}}

где $x_{i}$ это позиция на шаге $i$ , $v_{i+1/2\,}$ это скорость или первая производная от $x$ , на шаге $i+1/2\,$ , $a_{i}=A(x_{i})$ ускорение или вторая производная $x$ , на шаге $i$ , и $\Delta t$ - размер каждого временного шага. Эти уравнения можно выразить в форме, которая также дает скорость с целыми шагами: ^[2]

{\begin{aligned}x_{i+1}&=x_{i}+v_{i}\,\Delta t+{\tfrac {1}{2}}\,a_{i}\,\Delta t^{\,2},\\v_{i+1}&=v_{i}+{\tfrac {1}{2}}(a_{i}+a_{i+1})\,\Delta t.\end{aligned}}

Однако в этой синхронизированной форме временной шаг $\Delta t$ должна быть постоянной для поддержания стабильности. ^[3]

Синхронизированную форму можно преобразовать в форму «удар-дрейф-удар»;

{\begin{aligned}v_{i+1/2}&=v_{i}+a_{i}{\frac {\Delta t}{2}},\\x_{i+1}&=x_{i}+v_{i+1/2}\Delta t,\\v_{i+1}&=v_{i+1/2}+a_{i+1}{\frac {\Delta t}{2}},\end{aligned}}

который в основном используется там, где требуются переменные временные шаги. Разделение расчета ускорения на начало и конец шага означает, что если временное разрешение увеличивается в два раза ( $\Delta t\rightarrow \Delta t/2$ ), то потребуется только один дополнительный (затратный в вычислительном отношении) расчет ускорения.

Одно из применений этого уравнения - моделирование гравитации, поскольку в этом случае ускорение зависит только от положения гравитирующих масс (а не от их скоростей), хотя интеграторы более высокого порядка (такие как методы Рунге – Кутты чаще используются ). .

Есть два основных преимущества отказа от интеграции применительно к задачам механики. Во-первых, это обратимость во времени метода чехарды. Можно интегрировать n шагов вперед, а затем изменить направление интегрирования и интегрировать n шагов назад, чтобы прийти к той же исходной позиции. Вторая сильная сторона — это ее симплектическая природа, которая иногда допускает сохранение (слегка измененной) энергии динамической системы ( это верно только для некоторых простых систем ). Это особенно полезно при вычислении орбитальной динамики, поскольку многие другие схемы интегрирования, такие как метод Рунге – Кутты (четвертого порядка) , не сохраняют энергию и позволяют системе существенно дрейфовать с течением времени.

Из-за своей обратимости во времени и того, что это симплектический интегратор , чехарда также используется в гамильтониане Монте-Карло , методе извлечения случайных выборок из распределения вероятностей, общая нормализация которого неизвестна. ^[4]

Алгоритмы Йошиды

Интегратор-чехарда может быть преобразован в интеграторы более высокого порядка, используя методы Харуо Ёсиды . В этом подходе чехарда применяется на нескольких различных временных шагах. Оказывается, что при последовательном использовании правильных временных шагов ошибки компенсируются, и можно легко создать интеграторы гораздо более высокого порядка. ^[5]^[6]

Интегратор Йошида 4-го порядка

Один шаг в рамках интегратора Йошида 4-го порядка требует четырех промежуточных шагов. Положение и скорость вычисляются в разное время. Требуется всего три (дорогих в вычислительном отношении) расчета ускорения.

Уравнения для интегратора 4-го порядка для обновления положения и скорости:

{\begin{aligned}x_{i}^{1}&=x_{i}+c_{1}\,v_{i}\,\Delta t,\\v_{i}^{1}&=v_{i}+d_{1}\,a(x_{i}^{1})\,\Delta t,\\x_{i}^{2}&=x_{i}^{1}+c_{2}\,v_{i}^{1}\,\Delta t,\\v_{i}^{2}&=v_{i}^{1}+d_{2}\,a(x_{i}^{2})\,\Delta t,\\x_{i}^{3}&=x_{i}^{2}+c_{3}\,v_{i}^{2}\,\Delta t,\\v_{i}^{3}&=v_{i}^{2}+d_{3}\,a(x_{i}^{3})\,\Delta t,\\x_{i+1}&\equiv x_{i}^{4}=x_{i}^{3}+c_{4}\,v_{i}^{3}\,\Delta t,\\v_{i+1}&\equiv v_{i}^{4}=v_{i}^{3}\\\end{aligned}}

где $x_{i},v_{i}$ - исходное положение и скорость, $x_{i}^{n},v_{i}^{n}$ — промежуточное положение и скорость на промежуточном этапе $n$ , $a(x_{i}^{n})$ это ускорение в положении $x_{i}^{n}$ , и $x_{i+1},v_{i+1}$ — конечное положение и скорость при одном шаге Йошиды четвертого порядка.

Коэффициенты $(c_{1},c_{2},c_{3},c_{4})$ и $(d_{1},d_{2},d_{3})$ получены в ^[6] (см. уравнение (4.6))

{\begin{aligned}w_{0}&\equiv -{\frac {\sqrt[{3}]{2}}{2-{\sqrt[{3}]{2}}}},\\w_{1}&\equiv {\frac {1}{2-{\sqrt[{3}]{2}}}},\\c_{1}&=c_{4}\equiv {\frac {w_{1}}{2}},c_{2}=c_{3}\equiv {\frac {w_{0}+w_{1}}{2}},\\d_{1}&=d_{3}\equiv w_{1},d_{2}\equiv w_{0}\\\end{aligned}}

Все промежуточные этапы образуют один $\Delta t$ шаг, который подразумевает, что сумма коэффициентов равна единице: ${\textstyle \sum _{i=1}^{4}c_{i}=1}$ и ${\textstyle \sum _{i=1}^{3}d_{i}=1}$ . Обратите внимание, что положение и скорость вычисляются в разное время, а некоторые промежуточные шаги выполняются в обратном направлении во времени. Для иллюстрации этого приведем числовые значения $c_{n}$ коэффициенты: $c_{1}=0.6756$ , $c_{2}=-0.1756$ , $c_{3}=-0.1756$ , $c_{4}=0.6756.$

См. также

Ссылки

^ К.К. Бердсолл и А.Б. Лэнгдон, Физика плазмы с помощью компьютерного моделирования , McGraw-Hill Book Company, 1985, стр. 56.
^ 4.1 Два способа написать чехарду
^ Скил, Р.Д., «Переменный размер шага дестабилизирует метод Штёмера/чехарды/Верле», BIT Numerical Mathematics , Vol. 33, 1993, с. 172–175.
^ Бишоп, Кристофер (2006). Распознавание образов и машинное обучение . Нью-Йорк: Springer-Verlag . стр. 548–554. ISBN 978-0-387-31073-2 .
^ "./Ch07.HTML" .
^ Jump up to: ^а ^б Ёсида, Харуо (1990). «Построение симплектических интеграторов высшего порядка». Буквы по физике А. 150 (5–7): 262–268. дои : 10.1016/0375-9601(90)90092-3 .

Внешние ссылки

[1] , Физика Университета Дрекселя .

[1] К.К. Бердсолл и А.Б. Лэнгдон, Физика плазмы с помощью компьютерного моделирования , McGraw-Hill Book Company, 1985, стр. 56.

[2] 4.1 Два способа написать чехарду

[3] Скил, Р.Д., «Переменный размер шага дестабилизирует метод Штёмера/чехарды/Верле», BIT Numerical Mathematics , Vol. 33, 1993, с. 172–175.

[4] Бишоп, Кристофер (2006). Распознавание образов и машинное обучение . Нью-Йорк: Springer-Verlag . стр. 548–554. ISBN 978-0-387-31073-2 .

[5] "./Ch07.HTML" .

[Yoshida1990-6] Jump up to: ^а ^б Ёсида, Харуо (1990). «Построение симплектических интеграторов высшего порядка». Буквы по физике А. 150 (5–7): 262–268. дои : 10.1016/0375-9601(90)90092-3 .

[1]

[2]

[3]

[4]

[5]

[6]

v т и Численные методы для решения обыкновенных дифференциальных уравнений
Методы первого порядка	метод Эйлера Обратный Эйлер Полунеявный Эйлер Экспоненциальный Эйлер
Методы второго порядка	Интеграция Верлет Скорость Верле Правило трапеции Алгоритм Бимана Метод средней точки метод Хойна Метод Ньюмарка-бета Чехарда интеграции
Методы высшего порядка	Экспоненциальный интегратор Методы Рунге-Кутты Список методов Рунге – Кутты Линейный многошаговый метод Общие линейные методы Формула обратного дифференцирования Ёсида Метод Гаусса – Лежандра
Теория	Симплектический интегратор