Estabilidad numérica

En el subcampo matemático del análisis numérico , la estabilidad numérica es una propiedad generalmente deseable de los algoritmos numéricos . La definición precisa de estabilidad depende del contexto. Uno es álgebra lineal numérica y el otro son algoritmos para resolver ecuaciones diferenciales ordinarias y parciales mediante aproximación discreta.

En álgebra lineal numérica, la principal preocupación son las inestabilidades causadas por la proximidad a singularidades de diversos tipos, como valores propios muy pequeños o casi colisionantes . Por otro lado, en los algoritmos numéricos para ecuaciones diferenciales la preocupación es el crecimiento de errores de redondeo y/o pequeñas fluctuaciones en los datos iniciales que podrían causar una gran desviación de la respuesta final de la solución exacta. ^{[ cita necesaria ]}

Algunos algoritmos numéricos pueden amortiguar las pequeñas fluctuaciones (errores) en los datos de entrada; otros podrían magnificar tales errores. Los cálculos que se puede demostrar que no magnifican los errores de aproximación se denominan numéricamente estables . Una de las tareas comunes del análisis numérico es tratar de seleccionar algoritmos que sean robustos , es decir, que no produzcan un resultado tremendamente diferente para cambios muy pequeños en los datos de entrada.

Un fenómeno opuesto es la inestabilidad . Normalmente, un algoritmo implica un método aproximado y, en algunos casos, se podría demostrar que el algoritmo se acercaría a la solución correcta en algún límite (cuando se utilizan números reales, no números de punto flotante). Incluso en este caso, no hay garantía de que convergerá a la solución correcta, porque los errores de redondeo o truncamiento del punto flotante pueden magnificarse, en lugar de atenuarse, provocando que la desviación de la solución exacta crezca exponencialmente. ^[1]

Estabilidad en álgebra lineal numérica

Existen diferentes formas de formalizar el concepto de estabilidad. Las siguientes definiciones de estabilidad directa, inversa y mixta se utilizan a menudo en álgebra lineal numérica .

Considere el problema a resolver mediante el algoritmo numérico como una función $f$ que asigna los datos $x$ a la solución $y$ . El resultado del algoritmo, digamos $y$ *, normalmente se desviará de la solución "verdadera" $y$ . Las principales causas de error son el error de redondeo y el error de truncamiento . El error directo del algoritmo es la diferencia entre el resultado y la solución; en este caso, $Δ y = y * - y$ . El error hacia atrás es el $Δ x$ más pequeño tal que $f (x + Δ x) = y *$ ; en otras palabras, el error hacia atrás nos dice qué problema realmente resolvió el algoritmo. El error hacia adelante y hacia atrás están relacionados por el número de condición : el error hacia adelante es como máximo tan grande en magnitud como el número de condición multiplicado por la magnitud del error hacia atrás.

En muchos casos, es más natural considerar el error relativo

{\frac {|\Delta x|}{|x|}}

Δ x

Se dice que el algoritmo es estable hacia atrás si el error hacia atrás es pequeño para todas las entradas $x$ . Por supuesto, "pequeño" es un término relativo y su definición dependerá del contexto. A menudo, queremos que el error sea del mismo orden que el redondeo unitario , o quizás sólo unos pocos órdenes de magnitud mayor .

La definición habitual de estabilidad numérica utiliza un concepto más general, llamado estabilidad mixta , que combina el error hacia adelante y el error hacia atrás. Un algoritmo es estable en este sentido si resuelve aproximadamente un problema cercano, es decir, si existe un $Δ x$ tal que tanto $Δ x$ es pequeño como $f (x + Δ x) - y *$ es pequeño. Por tanto, un algoritmo retroestable siempre es estable.

Un algoritmo es estable hacia adelante si su error directo dividido por el número de condición del problema es pequeño. Esto significa que un algoritmo es estable hacia adelante si tiene un error hacia adelante de magnitud similar al de algún algoritmo estable hacia atrás.

Estabilidad en ecuaciones diferenciales numéricas.

Las definiciones anteriores son particularmente relevantes en situaciones donde los errores de truncamiento no son importantes. En otros contextos, por ejemplo al resolver ecuaciones diferenciales , se utiliza una definición diferente de estabilidad numérica.

En las ecuaciones diferenciales ordinarias numéricas , existen varios conceptos de estabilidad numérica, por ejemplo la estabilidad A. Están relacionados con algún concepto de estabilidad en el sentido de sistemas dinámicos , a menudo estabilidad de Lyapunov . Es importante utilizar un método estable al resolver una ecuación rígida .

Sin embargo, se utiliza otra definición en las ecuaciones diferenciales parciales numéricas . Un algoritmo para resolver una ecuación diferencial parcial evolutiva lineal es estable si la variación total de la solución numérica en un tiempo fijo permanece acotada cuando el tamaño del paso llega a cero. El teorema de equivalencia de Lax establece que un algoritmo converge si es consistente y estable (en este sentido). En ocasiones, la estabilidad se logra incluyendo la difusión numérica . La difusión numérica es un término matemático que garantiza que el redondeo y otros errores en el cálculo se dispersen y no se sumen para hacer que el cálculo "explote". El análisis de estabilidad de Von Neumann es un procedimiento comúnmente utilizado para el análisis de estabilidad de esquemas en diferencias finitas aplicado a ecuaciones diferenciales parciales lineales. Estos resultados no son válidos para las PDE no lineales, donde una definición general y consistente de estabilidad se complica por muchas propiedades ausentes en las ecuaciones lineales.

Ejemplo

Calcular la raíz cuadrada de 2 (que es aproximadamente 1,41421) es un problema bien planteado . Muchos algoritmos resuelven este problema comenzando con una aproximación inicial x ₀ a , por ejemplo x ₀ = 1,4, y luego calculando conjeturas mejoradas x ₁ , x ₂ , etc. Uno de esos métodos es el famoso método babilónico , que viene dado por x _k₊₁ = ( x _k + 2/ x _k )/2. Otro método, llamado "método X", viene dado por x _k₊₁ = ( x _k² − 2) ² + x _k . ^{[nota 1]} Algunas iteraciones de cada esquema se calculan en forma de tabla a continuación, con estimaciones iniciales x ₀ = 1,4 y x ₀ = 1,42. ${\sqrt {2}}$

Observe que el método babilónico converge rápidamente independientemente de la estimación inicial, mientras que el método X converge extremadamente lentamente con la estimación inicial x ₀ = 1,4 y diverge para la estimación inicial x ₀ = 1,42. Por tanto, el método babilónico es numéricamente estable, mientras que el método X es numéricamente inestable.

La estabilidad numérica se ve afectada por el número de dígitos significativos que mantiene la máquina. Si se utiliza una máquina que conserva sólo los cuatro dígitos decimales más significativos, las dos funciones equivalentes pueden dar un buen ejemplo de pérdida de significancia.

f(x)=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)

g(x)={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}.

Comparando los resultados de

f(500)=500\left({\sqrt {501}}-{\sqrt {500}}\right)=500\left(22.38-22.36\right)=500(0.02)=10

{\begin{alignedat}{3}g(500)&={\frac {500}{{\sqrt {501}}+{\sqrt {500}}}}\\&={\frac {500}{22.38+22.36}}\\&={\frac {500}{44.74}}=11.17\end{alignedat}}

Al comparar los dos resultados anteriores, queda claro que la pérdida de significancia (causada aquí por una cancelación catastrófica al restar aproximaciones a los números cercanos y , a pesar de que la resta se calcula exactamente) tiene un efecto enorme en los resultados, a pesar de que ambas funciones son equivalentes. , Como se muestra abajo ${\sqrt {501}}$ ${\sqrt {500}}$

{\begin{alignedat}{4}f(x)&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)\\&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right){\frac {{\sqrt {x+1}}+{\sqrt {x}}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {({\sqrt {x+1}})^{2}-({\sqrt {x}})^{2}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {x+1-x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {1}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=g(x)\end{alignedat}}

El valor deseado, calculado con precisión infinita, es 11,174755... ^{[nota 2]}

Ver también

Notas

^ Esta es una iteración de punto fijo para la ecuación , cuyas soluciones incluyen . Las iteraciones siempre se mueven hacia la derecha desde . Por tanto converge y diverge. $x=(x^{2}-2)^{2}+x=f(x)$ ${\sqrt {2}}$ $f(x)\geq x$ $x_{1}=1.4<{\sqrt {2}}$ $x_{1}=1.42>{\sqrt {2}}$
^ El ejemplo es una modificación de uno tomado de Mathews & Fink (1999). ^[2]

Referencias

^ Giesela Engeln-Müllges; Frank Uhlig (2 de julio de 1996). Algoritmos numéricos con CM Schon (Traductor), F. Uhlig (Traductor) (1 ed.). Saltador. pag. 10.ISBN 978-3-540-60530-0.
^ Mateos, John H.; Fink, Kurtis D. (1999). "Ejemplo 1.17". Métodos numéricos que utilizan MATLAB (3ª ed.). Prentice Hall. pag. 28.

Nicolás J. Higham (1996). Precisión y estabilidad de algoritmos numéricos . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 0-89871-355-2.
Richard L. Carga; J. Douglas Faires (2005). Análisis numérico (8ª ed.). Estados Unidos: Thomson Brooks/Cole. ISBN 0-534-39200-8.
Mesnard, Olivier; Barba, Lorena A. (2017). "Dinámica de fluidos computacional reproducible y replicable: es más difícil de lo que cree". Computación en ciencia e ingeniería . 19 (4): 44–55. arXiv : 1605.04339 . Código Bib : 2017CSE....19d..44M. doi :10.1109/MCSE.2017.3151254. S2CID 11288122.