math - resueltos - runge kutta method

Integración de Runge-Kutta(RK4) para la física del juego

Question

Gaffer on Games tiene un excelente artículo sobre el uso de la integración RK4 para una mejor física del juego. La implementación es sencilla, pero las matemáticas detrás de eso me confunden. Comprendo derivadas e integrales a nivel conceptual, pero no he manipulado las ecuaciones en mucho tiempo.

Aquí está el peso de la implementación de 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;
}

¿Alguien puede explicar en términos simples cómo funciona RK4? Específicamente, ¿por qué estamos promediando los derivados a 0.0f , 0.5f , 0.5f y 1.0f? ¿Cómo se diferencia el promedio de los derivados hasta el 4to orden de hacer una integración simple de Euler con un paso de tiempo más pequeño?

Después de leer la respuesta aceptada a continuación, y varios otros artículos, tengo una idea de cómo funciona RK4. Para responder mis propias preguntas:

¿Alguien puede explicar en términos simples cómo funciona RK4?

RK4 aprovecha el hecho de que podemos obtener una mejor aproximación de una función si usamos sus derivadas de orden superior en lugar de solo la primera o segunda derivada. Es por eso que la serie Taylor converge mucho más rápido que las aproximaciones de Euler. (Eche un vistazo a la animación en el lado derecho de esa página)

Específicamente, ¿por qué estamos promediando los derivados a 0.0f , 0.5f , 0.5f y 1.0f ?

El método de Runge-Kutta es una aproximación de una función que muestrea derivadas de varios puntos dentro de un intervalo de tiempo, a diferencia de la serie de Taylor, que solo muestra derivados de un solo punto. Después de muestrear estos derivados, necesitamos saber cómo pesar cada muestra para obtener la aproximación más cercana posible. Una forma fácil de hacerlo es seleccionar constantes que coincidan con la serie de Taylor, que es cómo se determinan las constantes de una ecuación de Runge-Kutta.

Este artículo lo dejó más claro para mí. Observe cómo (15) es la expansión de la serie Taylor, mientras que (17) es la derivación de Runge-Kutta.

¿Cómo se diferencia el promedio de los derivados hasta el 4to orden de hacer una integración simple de Euler con un paso de tiempo más pequeño?

Matemáticamente, converge mucho más rápido que haciendo muchas aproximaciones de Euler. Por supuesto, con suficientes aproximaciones de Euler podemos obtener la misma precisión que RK4, pero la potencia computacional necesaria no justifica el uso de Euler.

Answer 1

En cuanto a su pregunta, ¿por qué? Recuerdo una vez que escribí un simulador de tela donde la tela era una serie de resortes interconectados en los nodos. En el simulador, la fuerza ejercida por el resorte es proporcional a la extensión del resorte. La fuerza causa la aceleración en el nodo, que causa la velocidad que mueve el nodo que estira el resorte. Hay dos integrales (aceleración integradora para obtener velocidad e integración de velocidad para obtener posición) y si son inexactas, los errores bola de nieve: demasiada aceleración causa demasiada velocidad que causa demasiado estiramiento que causa aún más aceleración, haciendo que todo el sistema inestable.

Es difícil de explicar sin gráficos, pero lo intentaré: di que tienes f (t), donde f (0) = 10, f (1) = 20 yf (2) = 30.

Una integración adecuada de f (t) sobre el intervalo 0 <t <1 le daría la superficie bajo el gráfico de f (t) en ese intervalo.

La integración de la regla rectangular aproxima esa superficie a un rectángulo donde la amplitud es el delta en el tiempo y la longitud es el nuevo valor de f (t), por lo que en el intervalo 0 <t <1, producirá 20 * 1 = 20, y en el siguiente intervalo 1

Ahora bien, si trazara estos puntos y dibujara una línea a través de ellos, verá que en realidad es triangular, con una superficie de 30 (unidades) y, por lo tanto, la integración de Euler es inadecuada.

Para obtener una estimación más precisa de la superficie (integral) puede tomar intervalos más pequeños de t, evaluando, por ejemplo, f (0), f (0.5), f (1), f (1.5) y f (2).

Si todavía me siguen, el método RK4 es simplemente una forma de estimar los valores de f (t) para t0 <t <t0 + dt inventados por personas más inteligentes que yo para obtener estimaciones precisas de la integral.

(pero como otros han dicho, lea el artículo de Wikipedia para una explicación más detallada. RK4 está en la categoría de integración numérica )

Answer 2

Esto puede ser un poco simplificado en cuanto a las matemáticas reales, pero significa una guía intuitiva para la integración de Runge Kutta .

Dada alguna cantidad en algún momento t1 , queremos saber la cantidad en otro momento t2 . Con una ecuación diferencial de primer orden, podemos conocer la tasa de cambio de esa cantidad en t1 . No hay nada más que podamos saber con certeza; el resto es adivinar.

La integración de Euler es la forma más simple de adivinar: extrapolar linealmente de t1 a t2, usando la tasa de cambio conocida en t1 . Esto generalmente da una mala respuesta. Si t2 está lejos de t1, esta extrapolación lineal no coincidirá con ninguna curvatura en la respuesta ideal. Si tomamos muchos pequeños pasos de t1 a t2 , tendremos el problema de la resta de valores similares. Los errores de redondeo arruinarán el resultado.

Así que refinamos nuestra conjetura. Una forma es seguir adelante y hacer esta extrapolación lineal de todos modos, y luego esperar que no esté muy lejos de la verdad, usar la ecuación diferencial para calcular una estimación de la tasa de cambio en t2 . Esto, promediado con la tasa de cambio (precisa) en t1 , representa mejor la pendiente típica de la respuesta verdadera entre t1 y t2 . Usamos esto para hacer una nueva extrapolación lineal de t1 a t2 . No es obvio si deberíamos tomar el promedio simple, o dar más peso a la tasa en t1 , sin hacer los cálculos para estimar los errores, pero hay una opción aquí. En cualquier caso, es una mejor respuesta que Euler.

Quizás sea mejor hacer nuestra extrapolación lineal inicial a un punto en el tiempo a medio camino entre t1 y t2 , y usar la ecuación diferencial para calcular la tasa de cambio allí. Esto da aproximadamente una buena respuesta como el promedio que acabamos de describir. Luego, use esto para una extrapolación lineal de t1 a t2 , ya que nuestro propósito es encontrar la cantidad en t2 . Este es el algoritmo de punto medio.

Puede imaginar el uso de la estimación de punto medio de la tasa de cambio para hacer otra extrapolación lineal de la cantidad desde t1 hasta el punto medio. Con la ecuación diferencial obtenemos una mejor estimación de la pendiente allí. Usando esto, terminamos extrapolando desde t1 hasta t2 donde queremos una respuesta. Este es el algoritmo de Runge Kutta .

¿Podríamos hacer una tercera extrapolación al punto medio? Claro, no es ilegal, pero el análisis detallado muestra una disminución en la mejora, de modo que otras fuentes de error dominan el resultado final.

Runge Kutta aplica la ecuación diferencial al punto inicial t1, dos veces al punto medio y una vez al punto final t2. Los puntos intermedios son una cuestión de elección. Es posible usar otros puntos entre t1 y t2 para hacer esas estimaciones mejoradas de la pendiente. Por ejemplo, podríamos usar t1 , un punto un tercio del camino hacia t2, otro 2/3 el camino hacia t2 , y en t2 . Los pesos para el promedio de los cuatro derivados serán diferentes. En la práctica, esto realmente no ayuda, pero podría tener un lugar en las pruebas, ya que debería dar la misma respuesta pero proporcionará un conjunto diferente de errores de redondeo.

Answer 3

RK4 en el sentido más simple está haciendo una función de aproximación que se basa en 4 derivadas y puntos para cada paso de tiempo: su condición inicial en el punto inicial A, una primera pendiente aproximada B basada en el punto A en su paso de tiempo / 2 y la pendiente desde A, una tercera aproximación C, que tiene un valor de corrección para la pendiente en B para reflejar los cambios de forma de su función, y finalmente una pendiente final basada en la pendiente corregida en el punto C.

Así que, básicamente, este método permite calcular usando un punto de partida, un punto medio promediado que tiene correcciones integradas en ambas partes para ajustar la forma y un punto final doblemente corregido. Esto hace la contribución efectiva de cada punto de datos 1/6 1/3 1/3 y 1/6, por lo que la mayoría de su respuesta se basa en sus correcciones para la forma de su función.

Resulta que el orden de una aproximación RK (Euler se considera un RK1) corresponde a cómo se escala su precisión con pasos de tiempo más pequeños.

La relación entre las aproximaciones RK1 es lineal, por lo que para 10 veces la precisión obtienes aproximadamente 10 veces mejor convergencia.

Para RK4, 10 veces la precisión te proporciona una convergencia aproximadamente 10 ^ 4 veces mejor. Entonces, mientras su tiempo de calcinación aumenta linealmente en RK4, aumenta su precisión polinomialmente.