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

Метод Стёрмера — Верле́ — численный метод решения задачи Коши для дифференциальных уравнений. Часто используется для нахождения траектории материальной точки, движущейся по закону : для вычисления траекторий частиц в моделях молекулярной динамики и в компьютерных играх. Метод Верле более устойчив, чем более простой метод Эйлера, и имеет при этом другие качества, необходимые для моделирования физических процессов в реальном времени.


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

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

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

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

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

Алгоритм Верле используется для вычисления следующего местоположения точки по текущему и прошлому, без использования скорости. Формула получается следующим образом. Записывается разложение в ряд Тейлора вектора местоположения точки в моменты времени и .

Где
 — координаты точки,
 — скорость,
 — ускорение,
 — рывок (производная ускорения по времени).
Сложив эти 2 уравнения и выразив , получим:

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

Особенности

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

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

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

Свойства

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

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

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

  • метод Нюстрёма 2-го порядка;
  • композиция симплектического метода Эйлера с его сопряжённым;
  • расщепляющий метод для систем вида ;
  • разделённый метод Рунге—Кутты для систем , заданный таблицами Бутчера (англ.)

Применение

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

Примечания

  1. 1 2 Ernst Hairer, Christian Lubich, Gerhard Wanner. Geometric numerical integration illustrated by the Störmer–Verlet method (англ.) // Acta Numerica. — 2003-5. — Vol. 12. — P. 399–450. — ISSN 1474-0508 0962-4929, 1474-0508. — DOI:10.1017/S0962492902000144.
  2. 1 2 Ernst Hairer, Christian Lubich, Gerhard Wanner. Geometric Numerical Integration. — Berlin/Heidelberg: Springer-Verlag, 2006. — (Springer Series in Computational Mathematics). — ISBN 9783540306634.
  3. Sergio Blanes, Fernando Casas. A Concise Introduction to Geometric Numerical Integration. — Chapman and Hall/CRC, 2016-06-06. — (Monographs and Research Notes in Mathematics). — ISBN 9781482263428, 9781482263442.

Ссылки