Метод інтегрування з перекрокуванням

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

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

Інтеграція за допомогою методу інтегрування з перекрокуванням є методом другого порядку, на відміну від інтеграції Ейлера, яка є лише першого порядку, але вимагає такої ж кількості оцінок функції на крок. На відміну від інтегрування Ейлера, воно є стабільним для коливального руху, доки крок часу $\mathrm{\Delta }t$ постійна, і $\mathrm{\Delta }t\le 2/\omega$

Використовуючи коефіцієнти Йосіди, застосовуючи інтегратор перекрокування кілька разів з правильними часовими кроками, можна створити інтегратор набагато вищого порядку.

Алгоритм

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

$\begin{array}{cc}{a}_i& =A(x_i),\\ v_{i+1/2}& =v_{i-1/2}+a_i\mathrm{\Delta }t,\\ x_{i+1}& =x_i+v_{i+1/2}\mathrm{\Delta }t,\end{array}$

де $x_i$ це положення на кроці $i$, $v_{i+1/2}$ є швидкістю або першою похідною $x$, на крок $i+1/2$, $a_i=A(x_i)$ є прискоренням або другою похідною $x$, на крок $i$, і $\mathrm{\Delta }t$ це розмір кожного кроку часу. Ці рівняння можна виразити у формі, яка також дає швидкість з цілими кроками:

$\begin{array}{cc}{x}_{i+1}& =x_i+v_i\mathrm{\Delta }t+\frac{1}{2}{a}_i\mathrm{\Delta }{t}^2,\\ v_{i+1}& =v_i+\frac{1}{2}(a_i+a_{i+1})\mathrm{\Delta }t.\end{array}$

Однак у цьому синхронізованому вигляді час-крок $\mathrm{\Delta }t$ має бути постійним для підтримки стабільності.

Синхронізовану форму можна змінити на форму «кік-дрифт-кік»;

$\begin{array}{cc}{v}_{i+1/2}& =v_i+a_i\frac{\mathrm{\Delta }t}{2},\\ x_{i+1}& =x_i+v_{i+1/2}\mathrm{\Delta }t,\\ v_{i+1}& =v_{i+1/2}+a_{i+1}\frac{\mathrm{\Delta }t}{2},\end{array}$

який в основному використовується там, де потрібні змінні часові кроки. Поділ розрахунку прискорення на початок і кінець кроку означає, що якщо часова роздільна здатність збільшується у два рази ( $\mathrm{\Delta }t\to \mathrm{\Delta }t/2$ ), то потрібен лише один додатковий розрахунок прискорення.

Це рівняння використовується в гравітаційному моделюванні, оскільки в цьому випадку прискорення залежить лише від положення гравітуючих мас (а не від їхніх швидкостей), хоча частіше використовуються інтегратори вищого порядку (такі як методи Рунге–Кутта ). .

У методі інтегрування з перекрокуванням є дві основні переваги при застосуванні до задач механіки. Перша - це оборотність методу у часі. Можна інтегрувати вперед на n кроків, а потім змінити напрямок інтегрування і інтегрувати назад на n кроків, щоб прийти до тієї самої початкової позиції. Другою перевагою методу є його симлектична природа, яка іноді дозволяє зберігати (дещо змінену) енергію динамічної системи (проте це справедливо лише для певних простих систем). Це особливо корисно при обчисленні орбітальної динаміки, оскільки багато інших схем інтегрування, таких як метод Рунге-Кутта (4-го порядку), не зберігають енергію і дозволяють системі суттєво дрейфувати з часом.

Через свою оборотність у часі та тому, що це симплектичний інтегратор, інтеграція з перекрокуванням також використовується в гамільтонівському методі Монте-Карло, методі отримання випадкових вибірок із розподілу ймовірностей, загальна нормалізація якого невідома.

Алгоритми Йосіди

Метод інтегрування з перекрокуванням може бути перетворений в інтегратори вищого порядку за допомогою методів Харуо Йосіди . У цьому підході перекрокування застосовується до кількох різних часових кроків. Виявляється, коли правильні часові кроки використовуються послідовно, помилки скасовуються, і можна легко створити інтегратори набагато вищого порядку.

Інтегратор Йосіди 4-го порядку

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

Рівняння для інтегратора 4-го порядку для оновлення положення та швидкості:

$\begin{array}{cc}{x}_i^1& =x_i+c_1{v}_i\mathrm{\Delta }t,\\ v_i^1& =v_i+d_{1}a(x_i^1)\mathrm{\Delta }t,\\ x_i^2& =x_i^1+c_2{v}_i^1\mathrm{\Delta }t,\\ v_i^2& =v_i^1+d_{2}a(x_i^2)\mathrm{\Delta }t,\\ x_i^3& =x_i^2+c_3{v}_i^2\mathrm{\Delta }t,\\ v_i^3& =v_i^2+d_{3}a(x_i^3)\mathrm{\Delta }t,\\ x_{i+1}& \equiv x_i^4=x_i^3+c_4{v}_i^3\mathrm{\Delta }t,\\ v_{i+1}& \equiv v_i^4=v_i^3\\ \end{array}$

де $x_i,v_i$ початкове положення та швидкість, $x_i^n,v_i^n$ є проміжним положенням і швидкістю на проміжному кроці $n$, $a(x_i^n)$ це прискорення в положенні $x_i^n$, і $x_{i+1},v_{i+1}$ є кінцевою позицією та швидкістю під одним кроком Йосіди 4-го порядку.

Коефіцієнти $(c_1,c_2,c_3,c_4)$ і $(d_1,d_2,d_3)$ отримані в (див. рівняння (4.6))

$\begin{array}{cc}{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{array}$

Усі проміжні кроки утворюють одне ціле $\mathrm{\Delta }t$ крок, який означає, що сума коефіцієнтів дорівнює одиниці: ${\sum }_{i=1}^4{c}_i=1$ і ${\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.$

Див. також

• Чисельні методи для звичайних диференціальних рівнянь
• Симплектичне інтегрування
• Інтегрування Ейлера
• Інтеграція Verlet
• Інтеграція Рунге–Кутта