¿Cómo puedo resolver numéricamente un ODE a

8

Supongamos que tenemos un problema de valor inicial de la forma donde x 0R n se conoce exactamente (es decir, con precisión ilimitada) y podemos evaluar eficientemente f : R nR n con cualquier precisión. Es decir, tenemos un cuadro negro que, dado un vector xR n y un entero M , devuelve una aproximación a f ( x ) . Me gustaría saber si hay algún método práctico para obtener una aproximación a x ( t f )

dxdt=f(x)x(0)=x0
x0Rnf:RnRnxRnMf(x) garantizada para ser correcta a dígitos en el tiempo polinomio en MMMx(tf)(donde tfR es un tiempo final determinado) que es probablemente correcto para dígitosN .

Claramente, esto no será posible para cualquier función , ya que f puede tener un comportamiento loco que altera drásticamente la solución verdadera, pero no se recoge en un número razonable de evaluaciones. Por lo tanto, también estoy interesado en saber qué tipo de condiciones de buen comportamiento enf:RnRnf (por ejemplo, todas las derivadas parciales existen y están limitadas, una pequeña constante de Lipschitz, etc.) sería necesario para hacer esto.f

David Zhang
fuente
Los métodos más comunes serían inadecuados porque tienen errores que se comportan como , por lo que requerir h s10 - M conduce a un número de pasos exponencial en M : 1 / h 10 M / s . Presumiblemente, algunos métodos como los métodos espectrales le permitirían hacer esto si puede mostrar que el error es exponencialmente pequeño en 1 / h . Dado que cada paso es un número finito de operaciones racionales en números de longitud O ( M )hshs10MM1/h10M/s1/hO(M) , sin contar las evaluaciones de recuadro negro, cada una toma tiempo polinomial en , presumiblemente es el tamaño del paso lo que más importa. M
Kirill
@Kirill: En un enfoque espectral (o utilizando otros métodos ODE tradicionales), creo que el OP necesitaría conocer las constantes principales de los asintóticos para obtener un certificado de precisión. Estas constantes provendrían del análisis o el cálculo a través de la aritmética de intervalos.
Geoff Oxberry

Respuestas:

9

Me gustaría saber si hay algún método práctico para obtener una aproximación a (donde t fR es un tiempo final determinado) que es probablemente correcto para Nx(tf)tfRN dígitos.

Todo depende de su opinión sobre la practicidad de la aritmética de intervalos. Hay integradores validados disponibles, como COSY código del grupo de Martin Berz. Probablemente desee ver los documentos de Neumaier, Nedialkov, Berz y Makino, Chachuat, Stadtherr y quizás algunos otros grupos. Sus artículos tienden a usar las frases "modelo de Taylor", "integrador validado" y "aritmética de intervalos", entre otros.

f:RnRnff (por ejemplo, todas las derivadas parciales existen y están limitadas, una pequeña constante de Lipschitz, etc.) sería necesario para hacer esto.

Rnf(x)

kCk

Desde la perspectiva del usuario, estos integradores se reducen a dos (-ish) cosas:

  • f
  • ¿Puedo aumentar este código fuente para que sea compatible con una biblioteca de diferenciación automática, así como con una biblioteca aritmética de intervalos?

fkk modelos Taylor de orden.

En cuanto a los métodos típicos de resolución de ODE, para comentar la respuesta de Wolfgang:

No creo que pueda obtener un certificado de que el error está por debajo de cierto número, pero obtendrá que la estimación está por debajo de su tolerancia.

Cualquier método que tenga un estimador de error incorporado tiene la información a la que se refiere Wolfgang. Por lo general, esto significa que el método de integración realmente calcula dos (o más soluciones; por ejemplo, DOP853 calcula 3 soluciones) soluciones y las compara a través de alguna norma. La suposición es que la solución de orden superior es más precisa, lo que en realidad puede no ser cierto, dependiendo del problema dado, el paso de tiempo, las condiciones iniciales, etc. La solución devuelta por una implementación podría ser cualquiera de las soluciones candidatas calculadas. Tomando el caso común de Runge-Kutta 4 (5) como ejemplo, uno podría devolver la solución de cuarto orden o la solución de quinto orden; los enfoques típicos usan las fórmulas de Dormand-Prince, que minimizan el error en la solución de quinto orden y devuelven eso, en lugar de la solución de cuarto orden, porque la solución de quinto orden es más probable que sea más precisa. Además de analizar los problemas de estabilidad, creo que debería analizar el control de errores (Sección II.4 de Hairer y Wanner); La estabilidad es necesaria, pero no suficiente para la precisión.

MM

Geoff Oxberry
fuente
Estoy tentado a retractar mi respuesta porque @ geoffoxberry es mucho mejor que la mía ...
Wolfgang Bangerth
2

La primera de sus preguntas es algo que realmente puede obtener de la mayoría de los integradores de ODE enlatados, ya que todos, de una forma u otra, realizan un seguimiento de las estimaciones del error. No creo que pueda obtener un certificado de que el error está por debajo de cierto número, pero obtendrá ese cálculo está por debajo de su tolerancia.

f(x)ff

Wolfgang Bangerth
fuente