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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \vec{x}(t + \Delta t) = \vec{x}(t) + \vec{v}(t)\Delta t + \frac{\vec{a}(t) \Delta t^2}{2} + \frac{\vec{b}(t) \Delta t^3}{6} + O(\Delta t^4), }[/math]

[math]\displaystyle{ \vec{x}(t - \Delta t) = \vec{x}(t) - \vec{v}(t)\Delta t + \frac{\vec{a}(t) \Delta t^2}{2} - \frac{\vec{b}(t) \Delta t^3}{6} + O(\Delta t^4), }[/math]

где

[math]\displaystyle{ \vec{x} }[/math] — координаты точки,

[math]\displaystyle{ \vec{v} }[/math] — скорость,

[math]\displaystyle{ \vec{a} }[/math] — ускорение,

[math]\displaystyle{ \vec{b} }[/math] — рывок (производная ускорения по времени).

Сложив эти 2 уравнения и выразив [math]\displaystyle{ \vec{x}(t + \Delta t) }[/math], получим

[math]\displaystyle{ \vec{x}(t + \Delta t) = 2\vec{x}(t) - \vec{x}(t - \Delta t) + \vec{a}(t) \Delta t^2 + O(\Delta t^4). }[/math]

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

Особенности

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

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

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

Свойства

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

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

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

• метод Нюстрёма 2-го порядка;
• композиция симплектического метода Эйлера с его сопряжённым;
• расщепляющий метод для систем вида [math]\displaystyle{ \dot{\vec{q}} = f(\vec{p}),\ \dot{\vec{p}} = g(\vec{q}) }[/math];
• разделённый метод Рунге—Кутты для систем [math]\displaystyle{ \dot{\vec{q}} = f(\vec{q},\vec{p}),\ \dot{\vec{p}} = g(\vec{q},\vec{p}) }[/math], заданный таблицами Бутчера[math]\displaystyle{ \begin{array}{c|cc} 0 & 0 & 0 \\ 1 & 1/2 & 1/2 \\ \hline & 1/2 & 1/2 \\ \end{array} \qquad \begin{array}{c|cc} 1/2 & 1/2 & 0 \\ 1/2 & 1/2 & 0 \\ \hline & 1/2 & 1/2 \\ \end{array} }[/math]

Применение

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

Ссылки

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