用于游戏物理的 Runge-Kutta (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 处的导数求平均值？求四阶导数的平均值与使用较小时间步长进行简单的欧拉积分有何不同？
阅读下面已接受的答案以及其他几篇文章后，我了解了 RK4 的工作原理。回答我自己的问题：
有人可以简单地解释一下 RK4 的工作原理吗？
RK4 利用了以下事实： 我们可以得到更好的近似值 如果我们使用一个函数的 高阶导数而不是 只是一阶或二阶导数。 这就是为什么泰勒级数 收敛速度比欧拉快得多 近似值。 （看看 右侧的动画 页）
具体来说，为什么我们要对 0.0f、0.5f、0.5f 和 1.0f 处的导数进行平均？
龙格-库塔方法是一种 函数的近似值 采样几个点的导数 与泰勒不同，在一个时间步内 仅对衍生品进行采样的系列 的一个点。取样后 我们需要知道这些衍生品如何 称量每个样品以获得 可能的最接近的近似值。一个 做到这一点的简单方法是选择 符合的常数 泰勒级数，这就是 龙格-库塔方程的常数 已确定。
这篇文章更清楚地说明了 我。注意
(15)是泰勒函数 系列扩展，而(17)是 龙格-库塔推导。
求四阶导数的平均值与使用较小时间步长进行简单的欧拉积分有何不同？
从数学上来说，它收敛很多 比做许多欧拉更快 近似值。当然，只要有足够的 欧拉近似我们可以获得相等的 精度达到 RK4，但计算量 所需的电力并不能证明使用的合理性 欧拉。
Gaffer on Games has a great article about using RK4 integration for better game physics. The implementation is straightforward, but the math behind it confuses me. I understand derivatives and integrals on a conceptual level, but haven't manipulated equations in a long while.
Here's the brunt of Gaffer's implementation:
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;
}
Can anybody explain in simple terms how RK4 works? Specifically, why are we averaging the derivatives at 0.0f, 0.5f, 0.5f, and 1.0f? How is averaging derivatives up to the 4th order different from doing a simple euler integration with a smaller timestep?
After reading the accepted answer below, and several other articles, I have a grasp on how RK4 works. To answer my own questions:
Can anybody explain in simple terms how RK4 works?
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)
Specifically, why are we averaging the derivatives at 0.0f, 0.5f, 0.5f, and 1.0f?
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.
How is averaging derivatives up to the 4th order different from doing a simple euler integration with a smaller timestep?
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
就实际数学而言，这可能有点过于简单化，但它可以作为 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。这就是龙格库塔算法。我们可以对中点进行第三次外推吗？当然，这并不违法，但详细的分析显示改进逐渐减弱，因此其他错误来源主导了最终结果。
Runge Kutta 将微分方程应用于初始点 t1，两次应用于中点，一次应用于最终点 t2。中间点是一个选择问题。可以使用
t1和t2之间的其他点来改进斜率估计。例如，我们可以使用t1，一个指向 t2 的三分之一的点，另一个指向t2的 2/3 的点，以及位于t2的点。四个导数的平均值的权重会有所不同。在实践中，这并没有真正的帮助，但可能在测试中占有一席之地，因为它应该给出相同的答案，但会提供一组不同的舍入误差。This may be a bit oversimplified so far as actual math, but meant as an intuitive guide to
Runge Kuttaintegration.Given some quantity at some time
t1, we want to know the quantity at another timet2. With a first-order differential equation, we can know the rate of change of that quantity att1. There is nothing else we can know for sure; the rest is guessing.Euler integration is the simplest way to guess: linearly extrapolate from
t1to t2, using the precisely known rate of change att1. This usually gives a bad answer. If t2 is far from t1, this linear extrapolation will fail to match any curvature in the ideal answer. If we take many small steps from t1 tot2, we'll have the problem of subtraction of similar values. Roundoff errors will ruin the result.So we refine our guess. One way is to go ahead and do this linear extrapolation anyway, then hoping it's not too far off from truth, use the differential equation to compute an estimate of the rate of change at
t2. This, averaged with the (accurate) rate of change att1, better represents the typical slope of the true answer betweent1andt2. We use this to make a fresh linear extrapolation from tot1tot2. It's not obvious if we should take the simple average, or give more weight to the rate att1, without doing the math to estimate errors, but there is a choice here. In any case, it's a better answer than Euler gives.Perhaps better, make our initial linear extrapolation to a point in time midway between
t1andt2, and use the differential equation to compute the rate of change there. This gives roughly as good an answer as the average just described. Then use this for a linear extrapolation fromt1tot2, since our purpose it to find the quantity att2. This is the midpoint algorithm.You can imagine using the mid-point estimate of the rate of change to make another linear extrapolation of the quantity from
t1to the midpoint. With the differential equation we get an better estimate of the slope there. Using this, we end by extrapolating fromt1all the way tot2where we want an answer. This is theRunge Kuttaalgorithm.Could we do a third extrapolation to the midpoint? Sure, it's not illegal, but detailed analysis shows diminishing improvement, such that other sources of error dominate the final result.
Runge Kutta applies the differential equation to the intial point t1, twice to the midpoint, and once at the final point t2. The in-between points are a matter of choice. It is possible to use other points between
t1andt2for making those improved estimates of the slope. For example, we could uset1, a point one third the way toward t2, another 2/3 the way towardt2, and att2. The weights for the average of the four derivatives will be different. In practice this doesn't really help, but might have a place in testing since it ought to give the same answer but will provide a different set of round off errors.最简单意义上的 RK4 是创建一个基于 4 个导数和每个时间步长点的近似函数：起点 A 处的初始条件、基于时间步长/2 处的数据点 A 的第一个近似斜率 B 以及A 的斜率，第三个近似值 C ，它具有 B 处斜率的校正值以反映函数的形状变化，最后是基于 C 点校正斜率的最终斜率。
所以基本上，此方法允许您使用一个起点，一个平均中点，两个部分都内置了校正以调整形状，以及一个双重校正的终点。这使得每个数据点的有效贡献为 1/6 1/3 1/3 和 1/6，因此您的大部分答案都是基于您对函数形状的更正。
事实证明，RK 近似的阶数（欧拉被认为是 RK1）对应于其精度如何随较小时间步长缩放。
RK1 近似值之间的关系是线性的，因此精度提高 10 倍时，收敛效果大约提高 10 倍。
对于 RK4，10 倍的精度可以使收敛效果提高约 10^4 倍。因此，当您的计算时间在 RK4 中线性增加时，它会以多项式方式提高您的准确性。
RK4 in the simplest sense is making a approximation function that that is based on 4 derivatives and point for each time step: Your initial condition at starting point A, a first approximated slope B based on data point A at your time step/2 and the slope from A, a third approximation C , which has an correction value for the slope at B to reflect the shape changes of your function, and finally a final slope based on the corrected slope at point C.
So basically this method lets you calculate using a starting point, an averaged midpoint which has corrections built into both parts to adjust for the shape, and a doubly corrected endpoint. This makes the effective contribution from each data point 1/6 1/3 1/3 and 1/6, so most of your answer is based on your corrections for the shape of your function.
It turns out that the order of an RK approximation (Euler is considered an RK1) corresponds to how its accuracy scales with smaller time steps.
The relationship between RK1 approximations is linear, so for 10 times the precision you get roughly 10 times better convergence.
For RK4, 10 times the precision yields you about 10^4 times better convergence. So while your calcuation time increases linearly in RK4, it increases your accuracy polynomially.
至于你的问题为什么：我记得曾经写过一个布料模拟器，其中布料是一系列在节点处互连的弹簧。在模拟器中，弹簧施加的力与弹簧拉伸的距离成正比。该力会在节点处产生加速度，从而产生移动节点的速度，从而拉伸弹簧。有两个积分（积分加速度以获得速度，积分速度以获得位置），如果它们不准确，误差就会滚雪球：加速度太大导致速度太大，速度太大导致拉伸太大，从而导致更大的加速度，从而使整个系统不稳定。
没有图形很难解释，但我会尝试：假设你有 f(t)，其中 f(0) = 10、f(1) = 20 和 f(2) = 30。
f 的正确积分(t)在0＜0的区间内t < 1 将为您提供该区间内 f(t) 图表下方的曲面。
矩形法则积分用一个矩形来近似该表面，其中宽度是时间增量，长度是 f(t) 的新值，因此在区间 0 < 0 内。 t < 1 ，它将产生 20 * 1 = 20，并且在下一个间隔 1
现在，如果您要绘制这些点并通过它们画一条线，您会发现它实际上是三角形，表面积为 30（单位），因此欧拉积分是不充分的。
为了更准确地估计表面（积分），您可以采用较小的 t 间隔，例如 f(0)、f(0.5)、f(1)、f(1.5) 和 f(2) 进行评估。
如果您仍在关注我，那么 RK4 方法只是一种估计 t0 < 时 f(t) 值的方法。 t < t0+dt 是由比我聪明的人发明的，用于准确估计积分。
（但正如其他人所说，请阅读维基百科文章以获取更详细的解释。RK4 属于 数值类别集成)
As to your question why: I recall once writing a cloth simulator where the cloth was a series of springs interconnected at nodes. In the simulator, the force exerted by the spring is proportional to how far the spring is stretched. The force causes acceleration at the node, which causes velocity which moves the node which stretches the spring. There are two integrals (integrating acceleration to get velocity, and integrating velocity to get position) and if they are inaccurate, the errors snowball: Too much acceleration causes too much velocity which causes too much stretch which causes even more acceleration, making the whole system unstable.
It is difficult to explain without graphics, but I'll try: Say you have f(t), where f(0) = 10, f(1) = 20, and f(2) = 30.
A proper integration of f(t) over the interval 0 < t < 1 would give you the surface under the graph of f(t) over that interval.
The rectangle rule integration approximates that surface with a rectangle where the breadth is the delta in time and the length is the new value of f(t), so in the interval 0 < t < 1 , it will yield 20 * 1 = 20, and in the next interval 1
Now if you were to plot these points and draw a line through them you'll see that it is actually triangular, with a surface of 30 (units), and therefore the Euler integration is inadequate.
To get a more accurate estimation of the surface (integral) you can take smaller intervals of t, evaluating at for example f(0), f(0.5), f(1), f(1.5) and f(2).
If you're still following me, the RK4 method is then simply a way of estimating values of f(t) for t0 < t < t0+dt invented by people smarter than myself for getting accurate estimates of the integral.
(but as others have said, read the Wikipedia article for a more detailed explanation. RK4 is in the category of numerical integration)