Comprobación heurística de estabilidad numérica

12

Suponga que tengo una función de valor real de algunas variables que quiero evaluar numéricamente. En general, la fórmula para puede contener productos, racionales, funciones transitorias, etc., y será demasiado tiempo para investigar analíticamente su estabilidad numérica. O al menos tomará mucho tiempo hacerlo en la práctica. Suponga que no tengo un equivalente más corto con estabilidad garantizada. ¿Existe un procedimiento metódico para analizar la estabilidad numérica def(x1,,xN)xiff. Pienso en compararlo con resultados de precisión arbitrarios obtenidos usando un sistema de álgebra computacional. Digamos que la función se implementará en C usando funciones stdlib y precisión simple o doble. ¿Qué cantidades debo comparar para cuantificar la calidad de la aproximación con precisión finita? ¿Cómo determino los valores críticos de las variables? ¿Cómo puedo elegir el compilador y las optimizaciones del compilador para que otras personas puedan reproducir fácilmente los resultados? ... Sé que la configuración del problema es probablemente genérica para dar buenas respuestas. Pero sigo pensando que este es un problema común en informática y me pregunto si hay referencias que propongan estándares para realizar dicho análisis.

Highsciguy
fuente

Respuestas:

7

Lo que está buscando es lo que se llama "Análisis automático de errores" y es el tema del Capítulo 26 del libro de Higham "Precisión y estabilidad de los algoritmos numéricos", 2ª ed., SIAM Publishers.

Una técnica que describe es usar la optimización de búsqueda directa: intente formular su problema como un problema de optimización y use el algoritmo de optimización para encontrar coeficientes o valores de parámetros que maximicen o minimicen una cantidad relacionada con la precisión de su algoritmo / fórmula. Él usa el ejemplo del factor de crecimiento en Eliminación Gaussiana (qué matriz maximiza este factor de crecimiento) o las raíces de un cúbico (como respondí en una de sus preguntas anteriores).

Le sugiero que obtenga una copia de este libro, lea los capítulos introductorios y este capítulo 26 y las referencias en él.

GertVdE
fuente
3

Evalúe su función varias veces (3 suele ser suficiente) con todas las entradas ligeramente perturbadas aleatoriamente por ulp. La desviación estándar de los tres resultados le dará una medida cruda (pero generalmente suficiente) de sensibilidad numérica. Puede comparar esto con la sensibilidad esperada de la linealización y formar el cociente para obtener una estimación de estabilidad.±1

Tenga en cuenta que la estabilidad numérica pregunta cuánto peor se compara el error real en la evaluación de una particular con el error esperado del análisis de sensibilidad al cambiar las entradas por ulp; El último error expresado en ulps define la condición del problema. La condición puede ser muy mala para un algoritmo estable (ejemplo: cerca de ) y la estabilidad puede ser pobre para una función muy bien condicionada (ejemplo: cerca de ).x±11/xx=01/(1x)1/(1+x)x=0

Arnold Neumaier
fuente
0

Lo que GertVdE describe es el error numérico. Esto puede ser lo que está buscando, pero no es lo mismo que la estabilidad numérica como se indica en el título de la pregunta. La estabilidad numérica esencialmente pregunta si los valores cercanos de las variables de entrada producen valores cercanos de la salida. En otras palabras, si una fórmula comose cumple para alguna constante moderada . Para esto, puede analizar la derivada de o, si su función no varía enormemente en sus propiedades sobre su dominio, simplemente intente esto para un grupo de pares .

|f(x+ε)f(x)|C|ε|
Cfx,ϵ
Wolfgang Bangerth
fuente
¿Y qué se puede hacer si las funciones varían enormemente sobre su dominio o si no hay un derivado factible disponible? ¿Existen otras técnicas o terminaríamos con un enfoque de Monte Carlo?
André
1
-1: Explica la noción de condición, no de estabilidad numérica.
Arnold Neumaier