En el análisis numérico , la cancelación catastrófica [1] [2] es el fenómeno de que restar buenas aproximaciones a dos números cercanos puede producir una muy mala aproximación a la diferencia de los números originales.
Por ejemplo, suponga que tiene dos postes de madera, uno largo y el otro largo. Si los mide con una regla que es buena solo en centímetros, es posible que obtenga aproximaciones y . Dependiendo de sus necesidades, estas pueden ser buenas aproximaciones, en error relativo , a las longitudes reales: las aproximaciones tienen un error de menos del 2% de las longitudes reales,.
Sin embargo, si resta las longitudes aproximadas , obtendrá, aunque la verdadera diferencia entre las longitudes es . La diferencia de las aproximaciones,, tiene un error del 100% de la magnitud de la diferencia de los valores verdaderos, .
La cancelación catastrófica puede ocurrir incluso si la diferencia se calcula exactamente, como en el ejemplo anterior; no es una propiedad de ningún tipo particular de aritmética como la aritmética de punto flotante ; más bien, es inherente a la resta, cuando las entradas son aproximaciones en sí mismas. De hecho, en la aritmética de punto flotante, cuando las entradas están lo suficientemente cerca, la diferencia de punto flotante se calcula exactamente mediante el lema de Sterbenz : no hay error de redondeo introducido por la operación de resta de punto flotante.
Análisis formal
Formalmente, la cancelación catastrófica ocurre porque la resta está mal condicionada en las entradas cercanas: incluso si las aproximaciones y tener pequeños errores relativos y de valores verdaderos y , respectivamente, el error relativo de la diferencia aproximada de la verdadera diferencia es inversamente proporcional a la verdadera diferencia:
Por tanto, el error relativo de la diferencia exacta de las aproximaciones de la diferencia de los números verdaderos es
que puede ser arbitrariamente grande si las verdaderas entradas y están cerca.
En algoritmos numéricos
Restar números cercanos en aritmética de punto flotante no siempre causa una cancelación catastrófica, o incluso ningún error, según el lema de Sterbenz , si los números están lo suficientemente cerca, la diferencia de punto flotante es exacta. Pero la cancelación puede amplificar los errores en las entradas que surgieron del redondeo en otra aritmética de punto flotante.
Ejemplo: diferencia de cuadrados
Números dados y , el ingenuo intento de calcular la función matemática por la aritmética de punto flotante está sujeto a cancelación catastrófica cuando y son de magnitud cercana, porque la resta amplificará los errores de redondeo en el cuadrado. El factoring alternativo, evaluado por la aritmética de punto flotante , evita la cancelación catastrófica porque evita la introducción de errores de redondeo que conducen a la resta. [2]
Por ejemplo, si y , entonces el verdadero valor de la diferencia es . En aritmética IEEE 754 binary64 , evaluando la factorización alternativa da el resultado correcto exactamente (sin redondeo), pero evaluando la expresión ingenua da el número de punto flotante más cercano a , de los cuales solo la mitad de los dígitos son correctos y la otra mitad (subrayados) son basura.
Ejemplo: arcoseno complejo
Al calcular la función arcoseno compleja , uno puede tener la tentación de usar la fórmula logarítmica directamente:
Sin embargo, suponga por . Luego y ; llamar a la diferencia entre ellos—Una diferencia muy pequeña, casi cero. Si se evalúa en aritmética de punto flotante dando
con cualquier error , dónde denota redondeo de punto flotante, luego calcula la diferencia
de dos números cercanos, ambos muy cercanos a , puede amplificar el error en una entrada por un factor de —Un factor muy importante porque era casi cero. Por ejemplo, si, el verdadero valor de es aproximadamente , pero usando la fórmula logarítmica ingenua en la aritmética IEEE 754 binary64 puede dar, con sólo cinco de los dieciséis dígitos correctos y el resto (subrayado) toda basura.
En el caso de por , usando la identidad evita la cancelación porque pero , por lo que la resta es efectivamente una suma con el mismo signo que no se cancela.
Ejemplo: conversión de radix
Las constantes numéricas en los programas de software a menudo se escriben en decimal, como en el fragmento C double x = 1.000000000000001;
para declarar e inicializar una variable IEEE 754 binary64 nombrada x
. Sin emabargo,no es un número de coma flotante binary64; el más cercano, que x
se inicializará en este fragmento, es. Aunque la conversión de base de coma flotante decimal a coma flotante binaria solo incurre en un pequeño error relativo, la cancelación catastrófica puede amplificarlo en uno mucho mayor:
doble x = 1,00000000000000001 ; // redondeado a 1 + 5 * 2 ^ {- 52} doble y = 1.000000000000002 ; // redondeado a 1 + 9 * 2 ^ {- 52} doble z = y - x ; // la diferencia es exactamente 4 * 2 ^ {- 52}
La diferencia es . Los errores relativos de x
desdey de la y
de están ambos debajo , y la resta de coma flotante y - x
se calcula exactamente mediante el lema de Sterbenz.
Pero aunque las entradas son buenas aproximaciones, y aunque la resta se calcula exactamente, la diferencia de las aproximaciones tiene un error relativo de más de la diferencia de los valores originales escritos en decimal: la cancelación catastrófica amplificó un pequeño error en la conversión de la base en un gran error en la salida.
Cancelación benigna
La cancelación es a veces útil y deseable en algoritmos numéricos. Por ejemplo, los algoritmos 2Sum y Fast2Sum se basan en dicha cancelación después de un error de redondeo para calcular exactamente cuál fue el error en una operación de suma de punto flotante como un número de punto flotante en sí mismo.
La función , si se evalúa ingenuamente en los puntos , perderá la mayoría de los dígitos de en redondeo . Sin embargo, la funciónen sí mismo está bien acondicionado en las entradas cercanas. Reescribiéndolo como
Referencias
- ^ Muller, Jean-Michel; Brunie, Nicolas; de Dinechin, Florent; Jeannerod, Claude-Pierre; Joldes, Mioara; Lefèvre, Vincent; Melquiond, Guillaume; Revol, Nathalie; Torres, Serge (2018). Manual de aritmética de coma flotante (2ª ed.). Gewerbestrasse 11, 6330 Cham, Suiza: Birkhäuser. pag. 102. doi : 10.1007 / 978-3-319-76526-6 . ISBN 978-3-319-76525-9.Mantenimiento de CS1: ubicación ( enlace )
- ^ a b c Goldberg, David (marzo de 1991). "Lo que todo informático debería saber sobre la aritmética de punto flotante" . Encuestas de computación ACM . Nueva York, NY, Estados Unidos: Association for Computing Machinery. 23 (1): 5–48. doi : 10.1145 / 103162.103163 . ISSN 0360-0300 . Consultado el 17 de septiembre de 2020 .