Cancelación catastrófica

Pérdida de precisión en el análisis numérico

En el análisis numérico , la cancelación catastrófica ^{[1] [2]} es el fenómeno por el cual restar buenas aproximaciones a dos números cercanos puede producir una aproximación muy mala a la diferencia de los números originales.

Por ejemplo, si hay dos pernos, uno largo y otro largo, y se miden con una regla que solo es válida hasta el centímetro, entonces las aproximaciones podrían ser y . Estas pueden ser buenas aproximaciones, con un error relativo , con respecto a las longitudes verdaderas: las aproximaciones tienen un error de menos del 2% de las longitudes verdaderas, . ${\displaystyle L_{1}=253.51\,{\text{cm}}}$ ${\displaystyle L_{2}=252.49\,{\text{cm}}}$ ${\displaystyle {\tilde {L}}_{1}=254\,{\text{cm}}}$ ${\displaystyle {\tilde {L}}_{2}=252\,{\text{cm}}}$ ${\displaystyle |L_{1}-{\tilde {L}}_{1}|/|L_{1}|<2\%}$

Sin embargo, si se restan las longitudes aproximadas , la diferencia será , aunque la diferencia real entre las longitudes es . La diferencia de las aproximaciones, , tiene un error de casi el 100% de la magnitud de la diferencia de los valores verdaderos, . ${\displaystyle {\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}}$ ${\displaystyle L_{1}-L_{2}=253.51\,{\text{cm}}-252.49\,{\text{cm}}=1.02\,{\text{cm}}}$ ${\displaystyle 2\,{\text{cm}}}$ ${\displaystyle 1.02\,{\text{cm}}}$

La cancelación catastrófica no se ve afectada por el tamaño de las entradas, se aplica tanto a entradas grandes como pequeñas. Depende únicamente de lo grande que sea la diferencia y del error de las entradas. Se produciría exactamente el mismo error al restar de como aproximaciones a y , o al restar de como aproximaciones a y . ${\displaystyle 52\,{\text{cm}}}$ ${\displaystyle 54\,{\text{cm}}}$ ${\displaystyle 52.49\,{\text{cm}}}$ ${\displaystyle 53.51\,{\text{cm}}}$ ${\displaystyle 2.00052\,{\text{km}}}$ ${\displaystyle 2.00054\,{\text{km}}}$ ${\displaystyle 2.0005249\,{\text{km}}}$ ${\displaystyle 2.0005351\,{\text{km}}}$

La cancelación catastrófica puede ocurrir incluso si la diferencia se calcula con exactitud, 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 son lo suficientemente cercanas, la diferencia de punto flotante se calcula con exactitud, 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 tienen pequeños errores relativos y a partir de los valores verdaderos y , respectivamente, el error relativo de la diferencia de las aproximaciones a partir de la diferencia de los valores verdaderos es inversamente proporcional a la diferencia de los valores verdaderos: ${\displaystyle {\tilde {x}}=x(1+\delta _{x})}$ ${\displaystyle {\tilde {y}}=y(1+\delta _{y})}$ ${\displaystyle |\delta _{x}|=|x-{\tilde {x}}|/|x|}$ ${\displaystyle |\delta _{y}|=|y-{\tilde {y}}|/|y|}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle {\tilde {x}}-{\tilde {y}}}$ ${\displaystyle x-y}$

$${\displaystyle {\begin{aligned}{\tilde {x}}-{\tilde {y}}&=x(1+\delta _{x})-y(1+\delta _{y})=x-y+x\delta _{x}-y\delta _{y}\\&=x-y+(x-y){\frac {x\delta _{x}-y\delta _{y}}{x-y}}\\&=(x-y){\biggr (}1+{\frac {x\delta _{x}-y\delta _{y}}{x-y}}{\biggr )}.\end{aligned}}}$$

Por lo tanto, el error relativo de la diferencia exacta de las aproximaciones respecto de la diferencia de los valores verdaderos es ${\displaystyle {\tilde {x}}-{\tilde {y}}}$ ${\displaystyle x-y}$

$${\displaystyle \left|{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right|.}$$

que puede ser arbitrariamente grande si los valores verdaderos y están cerca. ${\displaystyle x}$ ${\displaystyle y}$

En algoritmos numéricos

La resta de números cercanos en aritmética de punto flotante no siempre causa una cancelación catastrófica, o incluso algú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 otras operaciones de aritmética de punto flotante.

Ejemplo: Diferencia de cuadrados

Dados los números y , el intento ingenuo de calcular la función matemática mediante la aritmética de punto flotante está sujeto a una cancelación catastrófica cuando y son de magnitud cercana, porque la resta puede exponer los errores de redondeo en el cuadrado. La factorización alternativa , evaluada mediante la aritmética de punto flotante , evita la cancelación catastrófica porque evita introducir un error de redondeo que conduzca a la resta. ^[2] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle \operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x+y)(x-y)}$ ${\displaystyle \operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (x-y))}$

Por ejemplo, si y , entonces el valor verdadero de la diferencia es . En la aritmética IEEE 754 binary64 , la evaluación de la factorización alternativa da exactamente el resultado correcto (sin redondeo), pero la evaluación de la expresión ingenua da el número de punto flotante , del cual menos de la mitad de los dígitos son correctos y los otros dígitos (subrayados) reflejan los términos faltantes , perdidos debido al redondeo al calcular los valores cuadrados intermedios. ${\displaystyle x=1+2^{-29}\approx 1.0000000018626451}$ ${\displaystyle y=1+2^{-30}\approx 1.0000000009313226}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle 2^{-29}\cdot (1+2^{-30}+2^{-31})\approx 1.8626451518330422\times 10^{-9}}$ ${\displaystyle (x+y)(x-y)}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle 2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}}$ ${\displaystyle 2^{-59}+2^{-60}}$

Ejemplo: Arcoseno complejo

Al calcular la función arcoseno compleja , uno puede verse tentado a utilizar directamente la fórmula logarítmica:

$${\displaystyle \arcsin(z)=i\log {\bigl (}{\sqrt {1-z^{2}}}-iz{\bigr )}.}$$

Sin embargo, supongamos que para . Entonces y ; llame a la diferencia entre ellos —una diferencia muy pequeña, casi cero. Si se evalúa en aritmética de punto flotante dando ${\displaystyle z=iy}$ ${\displaystyle y\ll 0}$ ${\displaystyle {\sqrt {1-z^{2}}}\approx -y}$ ${\displaystyle iz=-y}$ ${\displaystyle \varepsilon }$ ${\displaystyle {\sqrt {1-z^{2}}}}$

$${\displaystyle \operatorname {fl} {\Bigl (}{\sqrt {\operatorname {fl} (1-\operatorname {fl} (z^{2}))}}{\Bigr )}={\sqrt {1-z^{2}}}(1+\delta )}$$

con cualquier error , donde denota redondeo de punto flotante, luego se calcula la diferencia ${\displaystyle \delta \neq 0}$ ${\displaystyle \operatorname {fl} (\cdots )}$

$${\displaystyle {\sqrt {1-z^{2}}}(1+\delta )-iz}$$

de dos números cercanos, ambos muy próximos a , puede amplificar el error en una entrada por un factor de —un factor muy grande porque era casi cero. Por ejemplo, si , el valor verdadero de es aproximadamente , pero utilizando la fórmula logarítmica ingenua en la aritmética binaria IEEE 754 64 puede dar , con solo cinco de dieciséis dígitos correctos y el resto (subrayado) todos incorrectos. ${\displaystyle -y}$ ${\displaystyle \delta }$ ${\displaystyle 1/\varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle z=-1234567i}$ ${\displaystyle \arcsin(z)}$ ${\displaystyle -14.71937803983977i}$ ${\displaystyle -14.719{\underline {644263563968}}i}$

En el caso de para , el uso de 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. ${\displaystyle z=iy}$ ${\displaystyle y<0}$ ${\displaystyle \arcsin(z)=-\arcsin(-z)}$ ${\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$ ${\displaystyle i(-z)=-iz=y}$

Ejemplo: conversión de base

Las constantes numéricas en los programas de software suelen escribirse en decimal, como en el fragmento C para declarar e inicializar una variable IEEE 754 binary64 denominada . Sin embargo, no es un número de punto flotante binary64; el más cercano, que se inicializará en este fragmento, es . Aunque la conversión de base de punto flotante decimal a punto flotante binario solo incurre en un pequeño error relativo, una cancelación catastrófica puede amplificarlo hasta convertirlo en uno mucho mayor:double x = 1.000000000000001;x ${\displaystyle 1.000000000000001}$x ${\displaystyle 1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}}$

double x = 1.000000000000001 ; // redondeado a 1 + 5*2^{-52} double y = 1.000000000000002 ; // redondeado a 1 + 9*2^{-52} double z = y - x ; // la diferencia es exactamente 4*2^{-52}              

La diferencia es . Los errores relativos de desde y de desde están ambos por debajo de , y la resta de punto flotante se calcula exactamente mediante el lema de Sterbenz. ${\displaystyle 1.000000000000002-1.000000000000001}$ ${\displaystyle 0.000000000000001=1.0\times 10^{-15}}$x ${\displaystyle 1.000000000000001}$y ${\displaystyle 1.000000000000002}$ ${\displaystyle 10^{-15}=0.0000000000001\%}$y - x

Pero aunque las entradas son buenas aproximaciones, y aunque la resta se calcula con exactitud, 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 base en un gran error en la salida. ${\displaystyle {\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}}$ ${\displaystyle 11\%}$ ${\displaystyle 1.0\times 10^{-15}}$

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í.

La función , si se evalúa ingenuamente en los puntos , perderá la mayoría de los dígitos de en el redondeo . Sin embargo, la función en sí está bien condicionada en entradas cercanas a . Reescribirla como explota la cancelación en para evitar el error de evaluado directamente. ^[2] Esto funciona porque la cancelación en el numerador y la cancelación en el denominador se contrarrestan entre sí; la función está suficientemente bien condicionada cerca de cero que da una buena aproximación a , y por lo tanto da una buena aproximación a . ${\displaystyle \log(1+x)}$ ${\displaystyle 0<x\lll 1}$ ${\displaystyle x}$ ${\displaystyle \operatorname {fl} (1+x)}$ ${\displaystyle \log(1+x)}$ ${\displaystyle 0}$ $${\displaystyle \log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}}$$ ${\displaystyle {\hat {x}}:=\operatorname {fl} (1+x)-1}$ ${\displaystyle \log(1+x)}$ ${\displaystyle \log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})}$ ${\displaystyle {\hat {x}}=\operatorname {fl} (1+x)-1}$ ${\displaystyle \mu (\xi )=\log(1+\xi )/\xi }$ ${\displaystyle \mu ({\hat {x}})}$ ${\displaystyle \mu (x)}$ ${\displaystyle x\cdot \mu ({\hat {x}})}$ ${\displaystyle x\cdot \mu (x)=\log(1+x)}$

Referencias

1. 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. pág. 102. doi :10.1007/978-3-319-76526-6. ISBN . 978-3-319-76525-9.{{cite book}}: CS1 maint: location (link)
2. Goldberg, David (marzo de 1991). "Lo que todo científico informático debería saber sobre aritmética de punto flotante". Encuestas de computación de la ACM . 23 (1). Nueva York, NY, Estados Unidos: Association for Computing Machinery: 5–48. doi :10.1145/103162.103163. ISSN  0360-0300. S2CID  222008826. Consultado el 17 de septiembre de 2020 .