Интегрирование Верле

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод численного интегрирования Верле (англ. Verlet integration), метод Штёрмера (Störmer's method) — численный метод, используемый для интегрирования уравнений движения материальной точки (\ddot{\vec{x}} = \vec{a}(\vec{x},t)). Часто используется для вычисления траекторий частиц в моделях молекулярной динамики и в компьютерных играх. Метод Верле более устойчив, чем более простой метод Эйлера, и имеет при этом другие качества, необходимые для моделирования физических процессов в реальном времени.

Назван в честь французского физика Лу Верле (фр. Loup Verlet), который своей статьёй 1967 года популяризовал[источник не указан 1841 день] метод, предложенный Карлом Штёрмером (англ. Carl Størmer). Часто некорректно именуется «алгоритмом Верлета», «интеграция Верлета». Популярность у разработчиков компьютерных игр метод получил в 2000 году с выходом игры Hitman: Codename 47.

Также популярен у учеников Иу-9.

Основной алгоритм[править | править вики-текст]

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

\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} + R_{4}(\Delta t)\,
\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} +  R_{4}(\Delta t).\,

Где
\vec{x} — позиция точки,
\vec{v} — скорость,
\vec{a} — ускорение,
\vec{b} — рывок (производная ускорения по времени),

R_{4}(\Delta t) — остаточный член разложения \vec{x} в ряд Тейлора.
Сложив эти 2 уравнения, выразив \vec{x}(t + \Delta t) и записывая остаточный член в асимптотической форме (форме Пеано, локальной форме), получим:

\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, очень эффективен.

Ссылки[править | править вики-текст]