Меню Главная Случайная статья Настройки Метод Стёрмера — Верле Материал из https://ru.wikipedia.org Метод Стёрмера — Верле — численный метод решения задачи Коши для дифференциальных уравнений. Часто используется для нахождения траектории материальной точки, движущейся по закону ${\displaystyle {\ddot {\vec {x}}}={\vec {a}}({\vec {x}},t)}$: для вычисления траекторий частиц в моделях молекулярной динамики и в компьютерных играх. Метод Верле более устойчив, чем более простой метод Эйлера, и имеет при этом другие качества, необходимые для моделирования физических процессов в реальном времени. Содержание 1 История и названия 2 Основной алгоритм 3 Особенности 4 Свойства 5 Применение 6 Примечания 7 Ссылки История и названия Был использован[1] Исааком Ньютоном в первой книге «Начал» для доказательства второго закона Кеплера. Назван в честь французского физика Лу Верле, который использовал метод для моделирования динамики молекул, и норвежского астрофизика Карла Стёрмера. Метод (и эквивалентные ему) называется по-разному в зависимости от области применения[1][2]: метод Стёрмера, метод Энке — в астрономии; метод Верле — в молекулярной динамике; метод лягушки (англ. leapfrog)— в области уравнений в частных производных. Основной алгоритм Алгоритм Верле используется для вычисления следующего местоположения точки по текущему и прошлому, без использования скорости. Формула получается следующим образом. Записывается разложение в ряд Тейлора вектора ${\displaystyle {\vec {x}}(t)}$ местоположения точки в моменты времени ${\displaystyle (t+\Delta t)}$ и ${\displaystyle (t-\Delta t)}$: ${\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}),}$ ${\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}),}$ где ${\displaystyle {\vec {x}}}$ — координаты точки, ${\displaystyle {\vec {v}}}$ — скорость, ${\displaystyle {\vec {a}}}$ — ускорение, ${\displaystyle {\vec {b}}}$ — рывок (производная ускорения по времени). Сложив эти 2 уравнения и выразив ${\displaystyle {\vec {x}}(t+\Delta t)}$, получим ${\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}).}$ Таким образом, значение радиус-вектора точки может быть вычислено без знания скорости. Особенности Основная особенность алгоритма состоит в возможности накладывать на систему точек различные ограничения. Например, можно связать некоторые из них твёрдыми стержнями заданной длины. При этом алгоритм работает следующим образом: Вычисляются новые положения тел (см. формулу выше). Для каждой связи удовлетворяется соответствующее ограничение, то есть расстояние между точками делается таким, каким оно должно быть. Шаг 2 повторяется несколько раз, тем самым все условия удовлетворяются (разрешается система условий). Данный метод, несмотря на многократное повторение шага 2, очень эффективен. Свойства Метод является характерным методом геометрического численного интегрирования и обладает следующими свойствами[2][3]: принадлежит классу одношаговых общих линейных методов; имеет 2-й порядок точности; является симметричным (самосопряжённым) интегратором; является симплектическим интегратором; сохраняет фазовый объём для ряда систем; сохраняет линейные первые интегралы систем. Может рассматриваться как: метод Нюстрёма 2-го порядка; композиция симплектического метода Эйлера с его сопряжённым; расщепляющий метод для систем вида ${\displaystyle {\dot {\vec {q}}}=f({\vec {p}}),\ {\dot {\vec {p}}}=g({\vec {q}})}$; разделённый метод Рунге—Кутты для систем ${\displaystyle {\dot {\vec {q}}}=f({\vec {q}},{\vec {p}}),\ {\dot {\vec {p}}}=g({\vec {q}},{\vec {p}})}$, заданный таблицами Бутчера[англ.]$${\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}}}$$ Применение Популярность у разработчиков компьютерных игр метод получил в 2000 году с выходом игры Hitman: Codename 47. Примечания 1 2 Ernst Hairer, Christian Lubich, Gerhard Wanner. Geometric numerical integration illustrated by the Strmer–Verlet method (англ.) // Acta Numerica. — 2003-5. — Vol. 12. — P. 399–450. — ISSN 1474-0508 0962-4929, 1474-0508. — doi:10.1017/S0962492902000144. 1 2 Ernst Hairer, Christian Lubich, Gerhard Wanner. Geometric Numerical Integration. — Berlin/Heidelberg: Springer-Verlag, 2006. — (Springer Series in Computational Mathematics). — ISBN 9783540306634. Ссылки Лекция «Реализация физики на основе интегрирования Верлета» на сайте GameDev.ru Перевод статьи «Advanced Character Physics» Пример реализации интегрирования Верле на Java