¿Cómo se prueba una implementación numérica de solucionador de ODE?

26

Estoy a punto de comenzar a trabajar en una biblioteca de software de solucionadores numéricos de EDO , y estoy luchando sobre cómo formular pruebas para las implementaciones de solucionadores. Mi ambición es que la biblioteca, eventualmente, incluirá solucionadores para problemas no rígidos y rígidos, y al menos un solucionador implícito (más o menos a la par con las capacidades de las oderutinas en Matlab ), por lo que la metodología de prueba debe reflejar los diversos Tipos de problemas y criterios para diferentes solucionadores.

Mi problema ahora es que no sé por dónde comenzar con esta prueba. Se me ocurren algunas formas diferentes de probar la salida de un algoritmo:

  • Pruebe un problema que tenga una solución analítica y verifique que la solución numérica esté dentro de los niveles de tolerancia para todos los puntos de datos devueltos. Esto requiere el conocimiento de una serie de problemas analíticos que exhiben todas las propiedades con las que quiero que trabajen los diferentes solucionadores (rigidez, problemas implícitos, etc.), que no tengo, al menos no fuera de mi cabeza.

    Este método prueba los resultados de un método solucionador. Por lo tanto, no hay garantía de que el solucionador realmente funcione, solo que funciona para el problema de prueba dado . Por lo tanto, sospecho que se necesita una gran cantidad de problemas de prueba para verificar con seguridad que el solucionador funciona.

  • Calcule manualmente la solución por unos pocos pasos de tiempo usando los algoritmos que pretendo implementar, y luego haga lo mismo con los solucionadores y verifique que los resultados sean los mismos. Esto no requiere el conocimiento de la verdadera solución al problema, pero a su vez requiere bastante trabajo práctico.

    Este método, por el contrario, sólo prueba el algoritmo , el cual está bien para mí - si alguien más ha demostrado que el 4 º orden funciona de Runge-Kutta, no me siento una necesidad desesperada de. Sin embargo, me preocupa que sea muy engorroso formular casos de prueba, ya que no conozco un buen método para generar los datos de la prueba (excepto tal vez a mano, lo que será mucho trabajo ...).

Los dos métodos anteriores tienen serias limitaciones para mí con mi conocimiento actual: no conozco un buen conjunto de problemas de prueba para el primero y no conozco un buen método para generar datos de prueba para el segundo.

¿Hay otras formas de verificar los solucionadores numéricos de EDO? ¿Existen otros criterios sobre las implementaciones que deberían verificarse? ¿Hay algún recurso bueno (gratuito) para probar los solucionadores de ODE por ahí 1 ?

EDITAR:
Dado que esta pregunta es muy amplia, quiero aclarar un poco. El conjunto de pruebas que quiero crear cumplirá dos propósitos principales:

  1. Verificando que los solucionadores funcionan según lo esperado, para los problemas que están destinados a resolver. En otras palabras, un solucionador de problemas no rígidos puede volverse loco en un problema rígido, pero debería funcionar bien en problemas no rígidos. Además, si hay otros solucionadores en la biblioteca que ofrecen una mayor precisión, puede que no sea necesario aplicar resultados muy precisos, solo "lo suficientemente precisos". Por lo tanto, parte de mi pregunta es qué pruebas deben usarse para qué solucionadores; o, al menos, cómo se debe razonar para decidir eso.

  2. Prueba de cordura al instalar la biblioteca. Estas pruebas no necesitan (no deberían) ser elaboradas o llevar mucho tiempo; solo los conceptos básicos que se pueden ejecutar en menos de 5 segundos, pero que alertarán al usuario si algo está fuera de lo común. Por lo tanto, también necesito una forma de construir pruebas que sean muy simples, pero que aún me digan algo sobre el estado de la biblioteca.


1 Sí, he estado buscando en Google, pero la mayoría de lo que encuentro son notas de clase con ejemplos muy triviales, con la notable excepción del conjunto de pruebas CWI ODE de Bari que no sé si, o cómo, yo podría usar para mis propósitos, ya que trata solucionadores mucho más sofisticados que los que quiero probar ...

Tomás Aschan
fuente
2
@ user75064: ¡Absolutamente! No sabía que ese sitio incluso existía =) Cualquier modificación, siéntase libre de migrarme allí.
Tomas Aschan
Hay enlaces a otros conjuntos de pruebas en esta respuesta en Math Stack Exchange .
Geoff Oxberry
@ GeoffOxberry: He encontrado varios de esos antes. La mayoría de ellos están implementados en FORTRAN, y supone que el lector quiere probar los solucionadores en el mismo idioma, lo que agrega otra fuente de error ... Sin embargo, un par (los artículos sobre la suite DETEST) resultaron realmente útiles. ¡Muchas gracias!
Tomas Aschan

Respuestas:

12

Esta es una pregunta muy amplia y voy a darte algunas cosas para pensar (algunas ya están incluidas en tu publicación, pero se repiten aquí para completar).

Alcance de los problemas

  • Debe definir la interfaz de cómo especificar problemas.
  • ¿Va a permitir parámetros que se puedan arreglar o variar para las soluciones?
  • ¿Va a permitir que los parámetros de perturbación perturben levemente los problemas y vea si aún son solucionables (por ejemplo, un parámetro que se definirá en cualquier lugar) en un problema específico?ϵ
  • ¿Vas a permitir una precisión infinita?
  • ¿Vas a probar la velocidad y la sensibilidad a la precisión numérica?
  • ¿Ha elegido dos (tal vez más) bibliotecas que ya existen para comparar resultados?
  • ¿Cómo elegirá los criterios de detención, utilizará varios métodos y permitirá que el usuario seleccione o defina los suyos?
  • ¿Vas a medir el error usando varias medidas y permitirás al usuario activarlas y desactivarlas?
  • ¿Has mirado los paquetes profesionales como Computer-Algebra-Systems (CAS) y has entendido todas las opciones que permiten?
  • ¿Va a permitir la visualización de resultados y / o comparaciones y / o parcelas?

Recomendaciones de problemas

  • Debe escribir una especificación de prueba que defina el origen de los problemas, el alcance de cómo se probaron los problemas, la captura de resultados y las métricas de ejecución de las rutinas.
  • Ciertamente buscaría en otras bibliotecas los problemas que están usando (quizás archivos de prueba).
  • Iría a las bibliotecas universitarias y revisaría libros sobre EDO y sacaría problemas de todo tipo, aquellos con forma cerrada conocida o soluciones numéricas únicamente.
  • Caso 1: Queremos tantas variaciones de problemas de solución de forma cerrada como podamos obtener para comparar resultados exactos versus numéricos.
  • Caso 2: Iría a cada libro de análisis numérico que pueda encontrar y capturar los ejemplos trabajados y duplicarlos. Además, capturaría los conjuntos de problemas, particularmente los que tienen alguna patología que existe en la mayoría de los libros (sensibilidad a este o aquel tipo).
  • Caso 3: Iría a diferentes ramas de las matemáticas aplicadas como Física, Ecología, Biología, Economía, et. y capturar problemas de cada uno de esos dominios para validar que su lenguaje de especificación para problemas permita tales ejemplos.
  • Caso 4: Investigaría artículos / revistas que contienen los ejemplos más útiles en los que el autor en particular tuvo que modificar un enfoque particular para tener en cuenta alguna patología o rareza o dureza.
  • Caso 5: Busque en la web ejemplos adicionales. Para rigidez , vea las referencias aquí y examínelas TODAS para descubrir problemas de prueba. Aquí hay algunos ejemplos de MATLAB para leer detenidamente.

Esto no es único. Si mira el libro "Métodos numéricos para la optimización sin restricciones y ecuaciones no lineales" de Dennis y Schnabel, Apéndice B, "Problemas de prueba", puede ver cómo lo hicieron. Después de desarrollar uno de los escritos de algoritmos más bellos que he visto, arrojaron una serie de problemas que se volvieron locos. ¡Tuviste que ajustar aquí y allá! Incluyeron cinco problemas muy diferentes y patológicos que tensaron las capacidades de los solucionadores. Esto me ha enseñado que podemos seguir arrojando problemas a los algoritmos que son incapaces de manejar por una gran cantidad de razones. Tenga en cuenta que incluso tomaron prestados este conjunto de problemas de More ', Garbow y Hillstrom (también puede buscar esa referencia y quizás haya otros que pueda usar como guía).

En otras palabras, esta no es una tarea trivial. Necesita casos de prueba de respuesta conocida que siempre le permitan probar la validez de las actualizaciones y no romper las cosas. Es decir, un conjunto repetido y extenso de problemas de bajo a alto, de fácil a difícil, de posible a imposible, ... También necesita una colección de problemas que sus solucionadores no pueden manejar para comprender realmente sus limitaciones.

Amzoti
fuente
2

Una verificación de cordura que ejecuto contra mis solucionadores de ODE es simplemente verificarlo en sistemas lineales más pequeños calculando exactamente el exponencial de la matriz del sistema. es decir, dado

dudt=Au

verifique el error en

exp(tA)u0u^(t)

donde es su solución calculada. De esta manera, no necesita conocer ninguna solución analítica real (suponiendo que tenga algún equivalente de 'expm'), pero aún puede tener una idea de si su solucionador está haciendo lo que debería ser.u^(t)

Simplemente no calcules la exponencial con uno de tus pasos en el tiempo (es decir, dudoso método número 6 :) http://www.cs.cornell.edu/cv/researchpdf/19ways+.pdf )

Reid.Atcheson
fuente
Solo una nota: los integradores DE se consideraron "dudosos" en el sentido de que eran bastante ineficientes en comparación con el escalado + el cuadrado, no debido a la inexactitud.
JM
1

Puede intentar investigar el "Método de soluciones manufacturadas", que es una metodología general utilizada para probar la implementación de códigos que resuelven PDE (puede usarse para encontrar errores matemáticos y de codificación). Me imagino que podría adaptarse para trabajar para resolver EDO, si su metodología de solución es lo suficientemente general.

http://prod.sandia.gov/techlib/access-control.cgi/2000/001444.pdf

Kris Kuhlman
fuente