Метод Стёрмера — Верле

Метод Стёрмера — Верле́ — численный метод решения задачи Коши для дифференциальных уравнений. Часто используется для нахождения траектории материальной точки, движущейся по закону $\ddot{\overrightarrow{x}}=\overrightarrow{a}(\overrightarrow{x},t)$: для вычисления траекторий частиц в моделях молекулярной динамики и в компьютерных играх. Метод Верле более устойчив, чем более простой метод Эйлера, и имеет при этом другие качества, необходимые для моделирования физических процессов в реальном времени.

История и названия

Был использован Исааком Ньютоном в первой книге «Начал» для доказательства второго закона Кеплера.

Назван в честь французского физика Лу Верле, который использовал метод для моделирования динамики молекул, и норвежского астрофизика Карла Стёрмера.

Метод (и эквивалентные ему) называется по-разному в зависимости от области применения:

• метод Стёрмера, метод Энке — в астрономии;
• метод Верле — в молекулярной динамике;
• метод лягушки (Шаблон:Lang-en)— в области уравнений в частных производных.

Основной алгоритм

Алгоритм Верле используется для вычисления следующего местоположения точки по текущему и прошлому, без использования скорости. Формула получается следующим образом. Записывается разложение в ряд Тейлора вектора $\overrightarrow{x}(t)$ местоположения точки в моменты времени $(t+\mathrm{\Delta }t)$ и $(t-\mathrm{\Delta }t)$:

$\overrightarrow{x}(t+\mathrm{\Delta }t)=\overrightarrow{x}(t)+\overrightarrow{v}(t)\mathrm{\Delta }t+\frac{\overrightarrow{a}(t)\mathrm{\Delta }{t}^2}{2}+\frac{\overrightarrow{b}(t)\mathrm{\Delta }{t}^3}{6}+O(\mathrm{\Delta }{t}^4),$

$\overrightarrow{x}(t-\mathrm{\Delta }t)=\overrightarrow{x}(t)-\overrightarrow{v}(t)\mathrm{\Delta }t+\frac{\overrightarrow{a}(t)\mathrm{\Delta }{t}^2}{2}-\frac{\overrightarrow{b}(t)\mathrm{\Delta }{t}^3}{6}+O(\mathrm{\Delta }{t}^4),$

где

$\overrightarrow{x}$ — координаты точки,

$\overrightarrow{v}$ — скорость,

$\overrightarrow{a}$ — ускорение,

$\overrightarrow{b}$ — рывок (производная ускорения по времени).

Сложив эти 2 уравнения и выразив $\overrightarrow{x}(t+\mathrm{\Delta }t)$, получим

$\overrightarrow{x}(t+\mathrm{\Delta }t)=2\overrightarrow{x}(t)-\overrightarrow{x}(t-\mathrm{\Delta }t)+\overrightarrow{a}(t)\mathrm{\Delta }{t}^2+O(\mathrm{\Delta }{t}^4).$

Таким образом, значение радиус-вектора точки может быть вычислено без знания скорости.

Особенности

Основная особенность алгоритма состоит в возможности накладывать на систему точек различные ограничения. Например, можно связать некоторые из них твёрдыми стержнями заданной длины. При этом алгоритм работает следующим образом:

1. Вычисляются новые положения тел (см. формулу выше).
2. Для каждой связи удовлетворяется соответствующее ограничение, то есть расстояние между точками делается таким, каким оно должно быть.
3. Шаг 2 повторяется несколько раз, тем самым все условия удовлетворяются (разрешается система условий).

Данный метод, несмотря на многократное повторение шага 2, очень эффективен.

Свойства

Метод является характерным методом геометрического численного интегрирования и обладает следующими свойствами:

• принадлежит классу одношаговых общих линейных методов;
• имеет 2-й порядок точности;
• является симметричным (самосопряжённым) интегратором;
• является симплектическим интегратором;
• сохраняет фазовый объём для ряда систем;
• сохраняет линейные первые интегралы систем.

Может рассматриваться как:

• метод Нюстрёма 2-го порядка;
• композиция симплектического метода Эйлера с его сопряжённым;
• расщепляющий метод для систем вида $\dot{\overrightarrow{q}}=f(\overrightarrow{p}),\dot{\overrightarrow{p}}=g(\overrightarrow{q})$;
• разделённый метод Рунге—Кутты для систем $\dot{\overrightarrow{q}}=f(\overrightarrow{q},\overrightarrow{p}),\dot{\overrightarrow{p}}=g(\overrightarrow{q},\overrightarrow{p})$, заданный таблицами Шаблон:Не переведено$$\begin{array}{ccc}0& 0& 0\\ 1& 1/2& 1/2\\ & 1/2& 1/2\end{array}\begin{array}{ccc}1/2& 1/2& 0\\ 1/2& 1/2& 0\\ & 1/2& 1/2\end{array}$$

Применение

Популярность у разработчиков компьютерных игр метод получил в 2000 году с выходом игры Hitman: Codename 47.

Ссылки

• Лекция «Реализация физики на основе интегрирования Верлета» на сайте GameDev.ru
• Перевод статьи «Advanced Character Physics»
• Пример реализации интегрирования Верле на Java