Cancelación catastrófica

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

En análisis numérico , cancelación catastrófica ^{[1] [2]} es el fenómeno por el cual 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, si hay dos montantes, uno largo y otro largo, y se miden con una regla que solo sirve al centímetro, entonces las aproximaciones podrían resultar ser y . Estas pueden ser buenas aproximaciones, con un error relativo , a las longitudes reales: las aproximaciones tienen un error de menos del 2% de las longitudes reales, . ${\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 verdadera diferencia entre las longitudes sea . 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 los insumos; se aplica tanto a los insumos grandes como a los pequeños. Depende únicamente de qué tan grande sea la diferencia y del error de las entradas. Exactamente el mismo error surgiría al restar de as aproximaciones a y , o al restar de as 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}}}$

Puede ocurrir una cancelación catastrófica 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 los datos de entrada son en sí mismos aproximaciones. De hecho, en 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 se introduce ningún error de redondeo 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 entradas cercanas: incluso si las aproximaciones y tienen pequeños errores relativos y de los valores verdaderos y , respectivamente, el error relativo de la diferencia de las aproximaciones 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 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 son cercanos. ${\displaystyle x}$ ${\displaystyle y}$

En algoritmos numéricos

Restar números cercanos en aritmética de punto flotante no siempre causa una cancelación catastrófica, o incluso cualquier 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 aritméticas de punto flotante.

Ejemplo: diferencia de cuadrados

Dados los números y , el ingenuo intento 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 similares en magnitud, porque la resta puede exponer los errores de redondeo en la elevación al cuadrado. La factorización alternativa , evaluada mediante la aritmética de punto flotante , evita una cancelación catastrófica porque evita introducir errores de redondeo en 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 verdadero valor de la diferencia es . En la aritmética binaria 64 de IEEE 754 , la evaluación de la factorización alternativa da el resultado correcto exactamente (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 , se pierden 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 complejo , uno puede verse tentado a utilizar la fórmula logarítmica directamente:

$${\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 cercanos 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 usar la ingenua fórmula logarítmica en la aritmética binaria 64 del IEEE 754 puede dar , con solo cinco de dieciséis dígitos correctos y el resto (subrayado) todo incorrecto. ${\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 for , usar la identidad evita la cancelación porque pero , por lo que la resta es efectivamente una suma con el mismo signo que no 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 Radix

Las constantes numéricas en los programas de software a menudo se escriben en decimal, como en el fragmento C para declarar e inicializar una variable binaria64 IEEE 754 denominada . Sin embargo, no es un número de punto flotante binario64; 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 a uno mucho mayor:double x = 1.000000000000001;x ${\displaystyle 1.000000000000001}$x ${\displaystyle 1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}}$

doble 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 from y from están a continuación 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 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 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 en el redondeo . Sin embargo, la función en sí está bien condicionada en entradas cercanas a . Reescribiéndolo como ${\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}}}$$

^[2] ${\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. Müller, Jean-Michel; Brunie, Nicolás; de Dinechin, Florent; Jeannerod, Claude-Pierre; Joldes, Mioara; Lefèvre, Vicente; 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.{{cite book}}: CS1 maint: location (link)
2. 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 . 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 .