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?如何均衍生品多达从做一个小的时间步简单的欧拉积分不同的4阶？

在阅读下面接受的答案和其他几篇文章后,我掌握了RK4的工作原理.回答我自己的问题:

任何人都能用简单的语言解释RK4的工作原理吗？

RK4利用了这样一个事实,即如果我们使用其高阶导数而不仅仅是一阶导数或二阶导数,我们可以得到更好的函数近似.这就是泰勒级数 收敛比欧拉近似快得多的原因.(看一下该页面右侧的动画)

具体而言,我们为什么要在平均的衍生品0.0f,0.5f,0.5f,和1.0f？

Runge-Kutta方法是一个函数的近似值,它在一个时间步长内对几个点的导数进行采样,不像Taylor系列只采样单个点的导数.在对这些衍生物进行采样后,我们需要知道如何称量每个样本以获得最接近的近似值.一个简单的方法是选择与泰勒级数一致的常数,这是确定龙格 - 库塔方程的常数的方法.

这篇文章让我更清楚.请注意(15)泰勒级数展开(17)是如何进行的,而Runge-Kutta推导.

平均导数到4阶不同于使用较小的时间步长进行简单的euler积分？

在数学上,它比许多欧拉近似收敛得快得多.当然,通过足够的欧拉近似,我们可以获得与RK4相同的精度,但是所需的计算能力并不能证明使用欧拉.

DarenW.. 33

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

考虑到某些时间的数量t1,我们希望在另一时间知道数量t2.使用一阶微分方程,我们可以知道该数量的变化率t1.我们无从谈及其他任何事情; 剩下的就是猜测.

欧拉积分是最简单的猜测方法:t1使用精确已知的变化率线性推断从t2到t2 t1.这通常会给出错误的答案.如果t2远离t1,则此线性外推将无法匹配理想答案中的任何曲率.如果我们从t1采取许多小步骤t2,我们将遇到减去相似值的问题.舍入错误将破坏结果.

所以我们改进了猜测.一种方法是继续进行线性外推无论如何,然后希望它与真理不太相似,使用微分方程来计算变化率的估计值t2.这与(准确)变化率的平均值相比t1,更好地代表了t1和之间真实答案的典型斜率t2.我们用它来从一个最新的线性外推t1到t2.我们不应该采用简单的平均值,或者给出更多的权重t1,而不用数学来估计误差,但这里有一个选择.无论如何,这是一个比欧拉给出的更好的答案.

也许更好,让我们最初的线性外推到一个时间点之间的中间t1和t2,并用微分方程来计算的变化率出现.这给出了与刚才描述的平均值大致相同的答案.然后用这个线性外推t1到t2,因为我们的目的是寻找在数量t2.这是中点算法.

您可以想象使用变化率的中点估计来对数量进行另一次线性外推t1到中点.通过微分方程,我们可以更好地估计那里的斜率.使用这个,我们从t1一路推断到t2我们想要答案的地方.这是Runge Kutta算法.

我们可以对中点进行第三次推断吗？当然,这不是非法的,但详细的分析表明改进正在减少,因此其他错误来源主导了最终结果.

Runge Kutta将微分方程应用于初始点t1,两次应用于中点,一次应用于最终点t2.中间点是一个选择问题.可以使用之间的其他点t1并t2用于进行那些改进的斜率估计.例如,我们可以使用t1,相对于t2的三分之一点,另一个2/3的方向t2,以及t2.四种衍生物的平均权重将不同.在实践中,这并没有真正帮助,但可能在测试中占有一席之地,因为它应该给出相同的答案,但会提供一组不同的舍入错误.

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

考虑到某些时间的数量t1,我们希望在另一时间知道数量t2.使用一阶微分方程,我们可以知道该数量的变化率t1.我们无从谈及其他任何事情; 剩下的就是猜测.

欧拉积分是最简单的猜测方法:t1使用精确已知的变化率线性推断从t2到t2 t1.这通常会给出错误的答案.如果t2远离t1,则此线性外推将无法匹配理想答案中的任何曲率.如果我们从t1采取许多小步骤t2,我们将遇到减去相似值的问题.舍入错误将破坏结果.

所以我们改进了猜测.一种方法是继续进行线性外推无论如何,然后希望它与真理不太相似,使用微分方程来计算变化率的估计值t2.这与(准确)变化率的平均值相比t1,更好地代表了t1和之间真实答案的典型斜率t2.我们用它来从一个最新的线性外推t1到t2.我们不应该采用简单的平均值,或者给出更多的权重t1,而不用数学来估计误差,但这里有一个选择.无论如何,这是一个比欧拉给出的更好的答案.

也许更好,让我们最初的线性外推到一个时间点之间的中间t1和t2,并用微分方程来计算的变化率出现.这给出了与刚才描述的平均值大致相同的答案.然后用这个线性外推t1到t2,因为我们的目的是寻找在数量t2.这是中点算法.

您可以想象使用变化率的中点估计来对数量进行另一次线性外推t1到中点.通过微分方程,我们可以更好地估计那里的斜率.使用这个,我们从t1一路推断到t2我们想要答案的地方.这是Runge Kutta算法.

我们可以对中点进行第三次推断吗？当然,这不是非法的,但详细的分析表明改进正在减少,因此其他错误来源主导了最终结果.

Runge Kutta将微分方程应用于初始点t1,两次应用于中点,一次应用于最终点t2.中间点是一个选择问题.可以使用之间的其他点t1并t2用于进行那些改进的斜率估计.例如,我们可以使用t1,相对于t2的三分之一点,另一个2/3的方向t2,以及t2.四种衍生物的平均权重将不同.在实践中,这并没有真正帮助,但可能在测试中占有一席之地,因为它应该给出相同的答案,但会提供一组不同的舍入错误.