math - 用于游戏物理的 Runge-Kutta (RK4) 集成

Question

Gaffer on Games 有一个 great article关于使用RK4 integration为了更好的游戏物理。实现很简单，但其背后的数学让我感到困惑。我在概念层面上了解导数和积分，但已经很长时间没有操作过方程了。

这是 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 处的导数求平均值？求四阶导数的平均值与使用较小时间步长进行简单的欧拉积分有何不同？

<小时/>

阅读下面已接受的答案以及其他几篇文章后，我了解了 RK4 的工作原理。回答我自己的问题:

谁能简单地解释一下 RK4 的工作原理吗？

RK4 takes advantage of the fact that we can get a much better approximation of a function if we use its higher-order derivatives rather than just the first or second derivative. That's why the Taylor series converges much faster than Euler approximations. (take a look at the animation on the right side of that page)

具体来说，为什么我们要对 0.0f、0.5f、0.5f 和 1.0 处的导数进行平均f？

The Runge-Kutta method is an approximation of a function that samples derivatives of several points within a timestep, unlike the Taylor series which only samples derivatives of a single point. After sampling these derivatives we need to know how to weigh each sample to get the closest approximation possible. An easy way to do this is to pick constants that coincide with the Taylor series, which is how the constants of a Runge-Kutta equation are determined.

This article made it clearer for me. Notice how (15) is the Taylor series expansion while (17) is the Runge-Kutta derivation.

求四阶导数的平均值与使用较小时间步长进行简单的欧拉积分有何不同？

Mathematically, it converges much faster than doing many Euler approximations. Of course, with enough Euler approximations we can gain equal accuracy to RK4, but the computational power needed doesn't justify using Euler.

Answer 1

就实际数学而言，这可能有点过于简单化，但它是作为 Runge Kutta 集成的直观指南。

给定某个时间 t1 的数量，我们想知道另一个时间 t2 的数量。通过一阶微分方程，我们可以知道该量在 t1 时的变化率。我们无法确定其他任何事情；剩下的就是猜测了。

欧拉积分是最简单的猜测方法:使用 t1 处精确已知的变化率从 t1 线性外推到 t2。这通常会给出一个不好的答案。如果 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 的三分之一的点，另一个指向 t2 的 2/3 的点，以及位于 t2 的点。四个导数的平均值的权重会有所不同。在实践中，这并没有真正的帮助，但可能在测试中占有一席之地，因为它应该给出相同的答案，但会提供一组不同的舍入误差。