Интеграция Рунге-Кутта (RK4) для игровой физики

Gaffer on Games имеет отличную статью об использовании интеграции RK4 для лучшей физики игры. Реализация прост, но математика за ней меня смущает. Я понимаю производные и интегралы на концептуальном уровне, но долгое время не манипулировал уравнениями.

Здесь главная задача Gaffer:

void integrate(State &state, float t, float dt)
{
     Derivative a = evaluate(state, t, 0.0f, Derivative());
     Derivative b = evaluate(state, t+dt*0.5f, dt*0.5f, a);
     Derivative c = evaluate(state, t+dt*0.5f, dt*0.5f, b);
     Derivative d = evaluate(state, t+dt, dt, c);

     const float dxdt = 1.0f/6.0f * (a.dx + 2.0f*(b.dx + c.dx) + d.dx);
     const float dvdt = 1.0f/6.0f * (a.dv + 2.0f*(b.dv + c.dv) + d.dv)

     state.x = state.x + dxdt * dt;
     state.v = state.v + dvdt * dt;
}

Может кто-нибудь объяснить простыми словами, как работает RK4? В частности, почему мы усредняем производные от 0.0f, 0.5f, 0.5f и 1.0f?. Как усреднение производных до 4-го порядка отличается от простого интегрирования эйлеров с меньшим временным временем?

После прочтения принятого ниже ответа и нескольких других статей, я понимаю, как работает RK4. Чтобы ответить на мои вопросы:

Может кто-нибудь объяснить простыми словами, как работает RK4?

RK4 использует тот факт, что мы можем получить гораздо лучшее приближение функции, если мы используем ее производные более высокого порядка, а не просто первая или вторая производная. Вот почему серия Тейлорасходится намного быстрее, чем Эйлер приближения. (взгляните на анимация с правой стороны страница)

В частности, почему мы усредняем производные от 0.0f, 0.5f, 0.5f и 1.0f?

Метод Рунге-Кутты является аппроксимация функции, которая образцы производных нескольких точек в течение времени, в отличие от Тейлора серия, в которой производятся только производные одной точки. После отбора проб эти производные нам нужно знать, как для взвешивания каждого образца, чтобы получить возможно ближайшее приближение. простой способ сделать это - выбрать константы, совпадающие с Серии Тейлора, константы уравнения Рунге-Кутты определяются.

В этой статье стало понятнее меня. Обратите внимание, что (15) - это Тейлор в то время как (17) является Рунге-Кутта.

Как усредняют производные до 4-го порядка, отличные от простого интегрирования эйлеров с меньшим значением времени?

Математически он сходится много быстрее, чем многие Эйлеры приближения. Конечно, с достаточным количеством Эйлера мы можем получить равные точность до RK4, но вычислительная необходимая мощность не оправдывает использование Эйлер.

Ответы

Ответ 1

Это может быть немного упрощенным до фактической математики, но подразумевается как интуитивное руководство по интеграции Runge Kutta.

Учитывая некоторое количество в некоторый момент времени t1, мы хотим знать количество в другое время t2. С дифференциальным уравнением первого порядка мы можем знать скорость изменения этой величины при t1. Мы ничего не знаем наверняка; остальные гадают.

Интеграл Эйлера - это самый простой способ угадать: линейно экстраполировать от t1 до t2, используя точно известную скорость изменения при t1. Обычно это дает плохой ответ. Если t2 далека от t1, эта линейная экстраполяция не будет соответствовать любой кривизне в идеальном ответе. Если мы возьмем много небольших шагов от t1 до t2, у нас будет проблема вычитания аналогичных значений. Ошибки округления разрушают результат.

Итак, мы уточняем наше предположение. Один из способов заключается в том, чтобы идти вперед и делать эту линейную экстраполяцию в любом случае, а затем надеясь, что она не слишком далека от истины, используйте дифференциальное уравнение для вычисления оценки скорости изменения при t2. Это, усредненный с (точной) скоростью изменения при t1, лучше отражает типичный наклон истинного ответа между t1 и t2. Мы используем это, чтобы сделать новую линейную экстраполяцию от t1 до t2. Это не очевидно, если мы должны взять простое среднее значение или дать больше веса скорости t1, не делая математику для оценки ошибок, но здесь есть выбор. В любом случае, это лучший ответ, чем дает Эйлер.

Возможно, лучше, сделайте нашу начальную линейную экстраполяцию до точки в промежутке времени между t1 и t2 и используйте дифференциальное уравнение для вычисления темпа изменения там. Это дает примерно такой же хороший ответ, как только что описанное выше. Затем используйте это для линейной экстраполяции от t1 до t2, так как наша цель - найти величину at t2. Это алгоритм средней точки.

Вы можете представить, используя среднюю оценку скорости изменения, чтобы сделать еще одну линейную экстраполяцию количества от t1 до середины. С дифференциальным уравнением мы получаем лучшую оценку наклона. Используя это, мы заканчиваем экстраполяцией от t1 вплоть до t2, где мы хотим получить ответ. Это алгоритм Runge Kutta.

Можно ли сделать третью экстраполяцию в середину? Конечно, это не незаконно, но подробный анализ показывает уменьшение улучшения, так что другие источники ошибок доминируют в конечном результате.

Рунге Кутта применяет дифференциальное уравнение к внутренней точке t1, дважды к средней точке и один раз в конечной точке t2. Взаимосвязь между пунктами является вопросом выбора. Можно использовать другие точки между t1 и t2 для получения этих улучшенных оценок наклона. Например, мы могли бы использовать t1, точку на треть, путь к t2, другой 2/3 путь к t2 и в t2. Весы для среднего числа четырех производных будут разными. На практике это действительно не помогает, но может иметь место в тестировании, поскольку он должен дать тот же ответ, но будет предоставлять другой набор ошибок округления.

Ответ 2

Что касается вашего вопроса, почему: я помню, как однажды написал симулятор ткани, где ткань была рядом пружин, соединенных в узлах. В симуляторе сила, действующая на spring, пропорциональна протяженности spring. Сила вызывает ускорение на node, которое вызывает скорость, которая перемещает node, которая растягивает spring. Есть два интеграла (интеграция ускорения для получения скорости и интеграция скорости, чтобы получить положение), и если они неточны, ошибки снежки: слишком большое ускорение вызывает слишком большую скорость, что вызывает слишком большое растяжение, что вызывает еще большее ускорение, что делает всю систему неустойчиво.

Трудно объяснить без графики, но я постараюсь: скажем, что у вас есть f (t), где f (0) = 10, f (1) = 20 и f (2) = 30.

Собственное интегрирование f (t) на интервале 0 < t < 1 даст вам поверхность под графиком f (t) над этим интервалом.

Интеграция правил прямоугольника аппроксимирует эту поверхность прямоугольником, где ширина - это дельта во времени, а длина - новое значение f (t), поэтому в интервале 0 < t < 1, он даст 20 * 1 = 20, а в следующем интервале 1

Теперь, если вы должны были начертить эти точки и провести через них линию, вы увидите, что она на самом деле треугольная, с поверхностью 30 (единиц), и поэтому интеграция Эйлера неадекватна.

Для получения более точной оценки поверхности (интеграла) вы можете взять меньшие интервалы t, оценивая, например, f (0), f (0,5), f (1), f (1.5) и f (2).

Если вы по-прежнему следуете за мной, метод RK4 - это просто способ оценки значений f (t) для t0 < t < t0 + dt, изобретенный людьми умнее меня для получения точных оценок интеграла.

(но, как говорили другие, прочитайте статью Wikipedia для более подробного объяснения. RK4 находится в категории числовая интеграция)

Ответ 3

RK4 в простейшем смысле делает функцию приближения, которая основана на 4 производных и указывает на каждый временной шаг: ваше начальное условие в начальной точке A, первый аппроксимированный наклон B на основе точки данных A на вашем временном шаге /2 и наклон от A, третье приближение C, которое имеет значение коррекции для наклона в B, чтобы отразить изменения формы вашей функции и, наконец, окончательный наклон, основанный на скорректированном наклоне в точке C.

Таким образом, в основном этот метод позволяет рассчитать, используя начальную точку, усредненную среднюю точку, которая имеет исправления, встроенные в обе части для настройки фигуры, и двукратно исправленную конечную точку. Это обеспечивает эффективный вклад от каждой точки данных 1/6 1/3 1/3 и 1/6, поэтому большая часть вашего ответа основана на ваших корректировках для формы вашей функции.

Оказывается, что порядок RK-приближения (Euler считается RK1) соответствует тому, как его точность масштабируется с меньшими временными шагами.

Взаимосвязь между приближениями RK1 является линейной, поэтому в 10 раз точность вы получаете примерно в 10 раз лучше сходимости.

Для RK4 в 10 раз точность дает вам примерно в 10-4 раза лучшую сходимость. Поэтому, пока ваше время вычисления линейно возрастает в RK4, оно увеличивает вашу точность полиномиально.