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

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

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

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

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

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

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

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

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

$\stackrel{\to <!--\; \to \; -->}{x}(t+\mathrm{\Delta <!--\; \Delta \; -->}t)=\stackrel{\to <!--\; \to \; -->}{x}(t)+\stackrel{\to <!--\; \to \; -->}{v}(t)\mathrm{\Delta <!--\; \Delta \; -->}t+\frac{\stackrel{\to <!--\; \to \; -->}{a}(t)\mathrm{\Delta <!--\; \Delta \; -->}{t}^2}{2}+\frac{\stackrel{\to <!--\; \to \; -->}{b}(t)\mathrm{\Delta <!--\; \Delta \; -->}{t}^3}{6}+O(\mathrm{\Delta <!--\; \Delta \; -->}{t}^4),$${\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}),$ 

$\stackrel{\to <!--\; \to \; -->}{x}(t-<!--\; -\; -->\mathrm{\Delta <!--\; \Delta \; -->}t)=\stackrel{\to <!--\; \to \; -->}{x}(t)-<!--\; -\; -->\stackrel{\to <!--\; \to \; -->}{v}(t)\mathrm{\Delta <!--\; \Delta \; -->}t+\frac{\stackrel{\to <!--\; \to \; -->}{a}(t)\mathrm{\Delta <!--\; \Delta \; -->}{t}^2}{2}-<!--\; -\; -->\frac{\stackrel{\to <!--\; \to \; -->}{b}(t)\mathrm{\Delta <!--\; \Delta \; -->}{t}^3}{6}+O(\mathrm{\Delta <!--\; \Delta \; -->}{t}^4),$${\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}),$ 

где

$\stackrel{\to <!--\; \to \; -->}{x}$${\vec {x}}$  — координаты точки,

$\stackrel{\to <!--\; \to \; -->}{v}$$\vec{v}$  — скорость,

$\stackrel{\to <!--\; \to \; -->}{a}$${\vec {a}}$  — ускорение,

$\stackrel{\to <!--\; \to \; -->}{b}$${\vec {b}}$  — рывок (производная ускорения по времени).

Сложив эти 2 уравнения и выразив $\stackrel{\to <!--\; \to \; -->}{x}(t+\mathrm{\Delta <!--\; \Delta \; -->}t)$${\vec {x}}(t+\Delta t)$ , получим

$\stackrel{\to <!--\; \to \; -->}{x}(t+\mathrm{\Delta <!--\; \Delta \; -->}t)=2\stackrel{\to <!--\; \to \; -->}{x}(t)-<!--\; -\; -->\stackrel{\to <!--\; \to \; -->}{x}(t-<!--\; -\; -->\mathrm{\Delta <!--\; \Delta \; -->}t)+\stackrel{\to <!--\; \to \; -->}{a}(t)\mathrm{\Delta <!--\; \Delta \; -->}{t}^2+O(\mathrm{\Delta <!--\; \Delta \; -->}{t}^4).$${\vec {x}}(t+\Delta t)=2{\vec {x}}(t)-{\vec {x}}(t-\Delta t)+{\vec {a}}(t)\Delta t^{2}+O(\Delta t^{4}).$ 

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

ОсобенностиПравить

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

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

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

СвойстваПравить

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

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

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

• метод Нюстрёма 2-го порядка;
• композиция симплектического метода Эйлера с его сопряжённым;
• расщепляющий метод для систем вида $\stackrel{\dot{}<!--\; \dot{}\; -->}{\stackrel{\to <!--\; \to \; -->}{q}}=f(\stackrel{\to <!--\; \to \; -->}{p}),\stackrel{\dot{}<!--\; \dot{}\; -->}{\stackrel{\to <!--\; \to \; -->}{p}}=g(\stackrel{\to <!--\; \to \; -->}{q})$${\dot {\vec {q}}}=f({\vec {p}}),\ {\dot {\vec {p}}}=g({\vec {q}})$ ;
• разделённый метод Рунге—Кутты для систем $\stackrel{\dot{}<!--\; \dot{}\; -->}{\stackrel{\to <!--\; \to \; -->}{q}}=f(\stackrel{\to <!--\; \to \; -->}{q},\stackrel{\to <!--\; \to \; -->}{p}),\stackrel{\dot{}<!--\; \dot{}\; -->}{\stackrel{\to <!--\; \to \; -->}{p}}=g(\stackrel{\to <!--\; \to \; -->}{q},\stackrel{\to <!--\; \to \; -->}{p})$${\dot {\vec {q}}}=f({\vec {q}},{\vec {p}}),\ {\dot {\vec {p}}}=g({\vec {q}},{\vec {p}})$ , заданный таблицами Бутчера (англ.)
   

ПрименениеПравить

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

СсылкиПравить

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