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: un contexto importante es el álgebra lineal numérica , y otro son los 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 diversa índole, como valores propios muy pequeños o casi coincidentes . Por otro lado, en algoritmos numéricos para ecuaciones diferenciales, la preocupación radica en el aumento de errores de redondeo y/o pequeñas fluctuaciones en los datos iniciales, que podrían provocar una gran desviación de la respuesta final respecto a la solución exacta.

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 intentar seleccionar algoritmos que sean robustos , es decir, que no produzcan un resultado radicalmente diferente ante un cambio mínimo en los datos de entrada.

Un fenómeno opuesto es la inestabilidad . Típicamente, un algoritmo implica un método aproximado, y en algunos casos se podría demostrar que el algoritmo se aproximaría a la solución correcta en algún límite (cuando se utilizan números reales, no números de coma 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 coma flotante pueden magnificarse, en lugar de amortiguarse, lo que provoca que la desviación de la solución exacta crezca exponencialmente. ^{[ 1 ]}

Estabilidad en álgebra lineal numérica

Hay diferentes maneras de formalizar el concepto de estabilidad. Las siguientes definiciones de estabilidad hacia adelante, hacia atrás y mixta se utilizan a menudo en álgebra lineal numérica .

Consideremos el problema a resolver mediante el algoritmo numérico como una función $f$ que mapea 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 "verdadera"; 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 indica 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. ${\frac {|\Delta x|}{|x|}}$ en lugar del error absoluto $Δ x$ .

Se dice que el algoritmo es retroestable 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 de magnitud que, o quizás solo unos pocos órdenes de magnitud mayor que, el error de redondeo unitario .

La definición habitual de estabilidad numérica utiliza un concepto más general, denominado 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$ $como f(x$ $+$ Δx $)$ − $y$ $*$ $sean pequeños . Por lo tanto$ , un algoritmo con estabilidad 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 su error hacia adelante tiene una magnitud similar a la 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 diversos conceptos de estabilidad numérica, como la estabilidad A. Estos se relacionan con algún concepto de estabilidad en el sentido de los 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 se logra a veces incluyendo la difusión numérica . La difusión numérica es un término matemático que asegura que los errores de redondeo y otros errores en el cálculo se distribuyan y no se acumulen para causar 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 aplicados a ecuaciones diferenciales parciales lineales. Estos resultados no son válidos para EDP 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 ${\sqrt {2}}$ , por ejemplo x ₀ = 1.4, y luego calculando estimaciones 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 algunas iteraciones de cada esquema en forma de tabla, con estimaciones iniciales x ₀ = 1.4 y x ₀ = 1.42.

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 para 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, un buen ejemplo de pérdida de significancia se puede dar mediante las dos funciones equivalentes.

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

y

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

y

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

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

Véase también

Notas

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

Referencias

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

Nicholas J. Higham (1996). Precisión y estabilidad de los 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 piensas". Computing in Science & Engineering . 19 (4): 44– 55. arXiv : 1605.04339 . Bibcode : 2017CSE....19d..44M . doi : 10.1109/MCSE.2017.3151254 . S2CID 11288122 .

[2] Esta es una iteración de punto fijo para la ecuación. $x=(x^{2}-2)^{2}+x=f(x)$ , cuyas soluciones incluyen ${\sqrt {2}}$ Las iteraciones siempre se mueven hacia la derecha ya que $f(x)\geq x$ . Por eso $x_{1}=1.4<{\sqrt {2}}$ converge y $x_{1}=1.42>{\sqrt {2}}$ diverge.

[4] El ejemplo es una modificación de uno tomado de Mathews y Fink (1999) .^{[ 2 ]}

[1] Giesela Engeln-Müllges; Frank Uhlig (2 de julio de 1996). Algoritmos numéricos con C. M. Schon (Traductor), F. Uhlig (Traductor) (1 ed.). Saltador. pag. 10.ISBN 978-3-540-60530-0.

[3] Mathews, John H.; Fink, Kurtis D. (1999). "Ejemplo 1.17". Métodos numéricos con MATLAB (3.ª ed.). Prentice Hall. pág. 28.

[ 1 ]

[ nota 1 ]

[ nota 2 ]

[ 2 ]