Estabilidad numérica

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2012) (Learn how and when to remove this message)

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. Una es el álgebra lineal numérica y la otra son los algoritmos para resolver ecuaciones diferenciales ordinarias y parciales mediante aproximación discreta.

En el álgebra lineal numérica, la principal preocupación son las inestabilidades causadas por la proximidad a singularidades de varios tipos, como valores propios muy pequeños o casi en colisión . 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 con respecto a la solución exacta. ^{[ cita requerida ]}

Algunos algoritmos numéricos pueden atenuar las pequeñas fluctuaciones (errores) en los datos de entrada; otros pueden magnificar dichos 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 muy diferente para un cambio muy pequeño en los datos de entrada.

Un fenómeno opuesto es la inestabilidad . Normalmente, un algoritmo implica un método de aproximación 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 reales, no números de punto flotante). Incluso en este caso, no hay garantía de que converja a la solución correcta, porque los errores de redondeo o truncamiento de punto flotante se pueden magnificar, en lugar de amortiguarse, lo que hace que la desviación de la solución exacta crezca exponencialmente. ^[1]

Existen distintas formas de formalizar el concepto de estabilidad. Las siguientes definiciones de estabilidad hacia delante, hacia atrás y mixta se utilizan a menudo en el álgebra lineal numérica .

Considere el problema a resolver por 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 *, generalmente 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 inverso es el Δ x más pequeño tal que f  ( x + Δ x ) = y * ; en otras palabras, el error inverso nos dice qué problema resolvió realmente el algoritmo. El error directo y el inverso están relacionados por el número de condición : el error directo es como máximo tan grande en magnitud como el número de condición multiplicado por la magnitud del error inverso.

En muchos casos, es más natural considerar el error relativo en lugar del error absoluto Δ x .$${\displaystyle {\frac {|\Delta 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 solo 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 un problema cercano de forma aproximada, es decir, si existe un Δ x tal que tanto Δ x es pequeño como f  ( x + Δ x ) − y * es pequeño. Por lo tanto, un algoritmo estable hacia atrás siempre es estable.

Un algoritmo es estable hacia adelante si su error hacia adelante 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 a algún algoritmo estable hacia atrás.

Las definiciones anteriores son particularmente relevantes en situaciones en las que 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 la estabilidad de Lyapunov . Es importante utilizar un método estable al resolver una ecuación rígida .

Otra definición se utiliza en 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 a medida que el tamaño del paso tiende a cero. El teorema de equivalencia de Lax establece que un algoritmo converge si es consistente y estable (en este sentido). La estabilidad a veces 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 distribuyan 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 de diferencias finitas tal como se aplica a ecuaciones diferenciales parciales lineales. Estos resultados no se mantienen para ecuaciones diferenciales parciales no lineales, donde una definición general y consistente de estabilidad se complica por muchas propiedades ausentes en las ecuaciones lineales.

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 estos métodos es el famoso método babilónico , que viene dado por x _{k +1} = ( x _k + 2/ x _k )/2. Otro método, llamado "método X", viene dado por x _{k +1} = ( x _k ² − 2) ² + x _k . ^{[nota 1]} A continuación se calculan en forma de tabla algunas iteraciones de cada esquema, con conjeturas iniciales x ₀ = 1,4 y x ₀ = 1,42.${\displaystyle {\sqrt {2}}}$

Obsérvese que el método babilónico converge rápidamente independientemente de la estimación inicial, mientras que el método X converge extremadamente lento con una estimación inicial x ₀ = 1,4 y diverge con una estimación inicial x ₀ = 1,42. Por lo 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 la cantidad de dígitos significativos que conserva la máquina. Si se utiliza una máquina que conserva solo los cuatro dígitos decimales más significativos, las dos funciones equivalentes pueden dar un buen ejemplo de pérdida de significancia

${\displaystyle f(x)=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)}$y${\displaystyle g(x)={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}.}$

Comparando los resultados de

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

y

${\displaystyle {\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 la cancelación catastrófica de la resta de aproximaciones a los números cercanos y , a pesar de que la resta se calcula con exactitud) tiene un efecto enorme en los resultados, aunque ambas funciones son equivalentes, como se muestra a continuación.${\displaystyle {\sqrt {501}}}$${\displaystyle {\sqrt {500}}}$

${\displaystyle {\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]}

• Algoritmos para calcular la varianza
• Teoría de la estabilidad
• Teoría del caos
• Propagación de la incertidumbre

• Nicholas 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. Burden; J. Douglas Faires (2005). Análisis numérico (8.ª ed.). EE. UU.: 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 crees". Computing in Science & Engineering . 19 (4): 44–55. arXiv : 1605.04339 . Bibcode :2017CSE....19d..44M. doi :10.1109/MCSE.2017.3151254. S2CID  11288122.