Интеграция (RK4) Рунге-Кутта для игровой физики
gcc будет обычно использовать логические сдвиги на неподписанных переменных и для сдвигов влево на переменных со знаком. Арифметический сдвиг вправо является действительно важным, потому что это подпишется, расширяют переменную.
желание gcc будет использовать это, когда применимо, как другие компиляторы, вероятно, сделают.
2 ответа
Это может быть немного упрощено с точки зрения реальной математики, но подразумевается как интуитивное руководство по интеграции Рунге Кутта .
Приведено некоторое количество в какой-то момент ] t1 , мы хотим узнать величину в другое время t2 . С помощью дифференциального уравнения первого порядка мы можем узнать скорость изменения этой величины в t1 . Больше мы ничего не можем знать наверняка; остальное только догадывается.
Интегрирование Эйлера - это самый простой способ угадать: линейно экстраполировать от t1 до t2, используя точно известную скорость изменения в t1 . Обычно это дает плохой ответ. Если t2 далеко от t1, эта линейная экстраполяция не сможет сопоставить любую кривизну в идеальном ответе. Если мы сделаем много маленьких шагов от t1 до t2 , мы У меня возникнет проблема с вычитанием похожих значений. Ошибки округления испортят результат.
Итак, мы уточняем наше предположение. Один из способов - все равно проделать эту линейную экстраполяцию, а затем, надеясь, что она не так уж далека от истины, использовать дифференциальное уравнение для вычисления оценки скорости изменения в t2 . Это, усредненное с (точной) скоростью изменения в t1 , лучше представляет типичный наклон истинного ответа между t1 и t2 . Мы используем это, чтобы сделать новую линейную экстраполяцию от до t1 до t2 . Не очевидно, следует ли нам брать простое среднее значение или придавать больший вес скорости на t1 , не выполняя математических вычислений для оценки ошибок, но здесь есть выбор. В любом случае это ' это лучший ответ, чем дает Эйлер.
Возможно, лучше сделать нашу первоначальную линейную экстраполяцию к моменту времени на полпути между t1 и t2 , и использовать дифференциальное уравнение для вычисления скорости изменений там. Это дает примерно такой же хороший ответ, как и только что описанное среднее значение. Затем используйте это для линейной экстраполяции от t1 до t2 , так как наша цель - найти величину в t2 . Это алгоритм средней точки.
Вы можете представить себе использование средней точки оценки скорости изменения, чтобы сделать еще одну линейную экстраполяцию величины от t1 до средней точки. С помощью дифференциального уравнения мы получаем лучшую оценку крутизны. Используя это, мы заканчиваем экстраполяцией от t1 до t2 , где нам нужен ответ. Это алгоритм Рунге Кутта .
Можем ли мы сделать третью экстраполяцию к средней точке? Конечно, это не незаконно, но подробный анализ показывает убывающее улучшение, так что другие источники ошибок доминируют над окончательным результатом.
Рунге Кутта применяет дифференциальное уравнение к начальной точке t1, дважды к средней точке и один раз к конечной точке t2. Промежуточные точки - это вопрос выбора. Можно использовать другие точки между t1 и t2 для выполнения этих улучшенных оценок наклона. Например, мы могли бы использовать t1 , точку на одну треть пути к t2, еще на 2/3 пути к t2 и на t2 . Веса для среднего четырех производных будут разными. На практике это не очень помогает, но может иметь место при тестировании, поскольку должно дать тот же ответ, но предоставит другой набор ошибок округления.
Что касается вашего вопроса, почему: я помню, как однажды писал имитатор ткани, где ткань представлял собой серию пружин, соединенных между собой в узлах. В симуляторе сила пружины пропорциональна тому, насколько пружина растянута. Сила вызывает ускорение в узле, что вызывает скорость, которая перемещает узел, растягивающий пружину. Есть два интеграла (интегрирование ускорения для получения скорости и интегрирование скорости для определения положения), и если они неточны, ошибки снежного кома: слишком большое ускорение вызывает слишком большую скорость, что вызывает слишком большое растяжение, что вызывает еще большее ускорение, что делает всю систему нестабильно.
Это сложно объяснить без графики, но я попробую: скажем, у вас есть f (t), где f (0) = 10, f (1) = 20 и f (2) = 30.
Правильное интегрирование f (t) на интервале 0 Интегрирование по правилу прямоугольника аппроксимирует эту поверхность прямоугольником, где ширина - это дельта во времени, а длина - это новое значение f (t), поэтому в интервале 0 Теперь, если вы начертите эти точки и проведете через них линию, вы увидите, что на самом деле она треугольная, с поверхностью 30 (единиц), и, следовательно, интегрирование Эйлера неадекватно. Чтобы получить Для более точной оценки поверхности (интеграла) вы можете брать меньшие интервалы t, оценивая, например, f (0), f (0,5), f (1), f (1,5) и f (2). Если вы все еще следите за мной, тогда метод RK4 - это просто способ оценки значений f (t) для t0 (но как говорили другие, прочтите статью в Википедии для более подробного объяснения. RK4 относится к категории численного интегрирования )