Cancelación catastrófica - Catastrophic cancellation

En el análisis numérico , la cancelación catastrófica 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 otro largo. Si los mide con una regla que es buena solo en centímetros, puede obtener aproximaciones y . Dependiendo de sus necesidades, estos pueden ser buenas aproximaciones, en error relativo , a las longitudes reales: las aproximaciones son un error de menos del 2% de las longitudes reales, . ${\ Displaystyle L_ {1} = 254,5 \, {\ text {cm}}}$ ${\ Displaystyle L_ {2} = 253.5 \, {\ text {cm}}}$ ${\ Displaystyle {\ tilde {L}} _ {1} = 255 \, {\ text {cm}}}$ ${\ Displaystyle {\ tilde {L}} _ {2} = 253 \, {\ text {cm}}}$ ${\ Displaystyle | L_ {1} - {\ tilde {L}} _ {1} | / | L_ {1} | <2 \%}$

Sin embargo, si resta las longitudes aproximadas , obtendrá , aunque la verdadera diferencia entre las longitudes es . La diferencia de las aproximaciones, , está en error por 100% de la magnitud de la diferencia de los valores verdaderos, . ${\ displaystyle {\ tilde {L}} _ {1} - {\ tilde {L}} _ {2} = 255 \, {\ text {cm}} - 253 \, {\ text {cm}} = 2 \, {\ text {cm}}}$ ${\ Displaystyle L_ {1} -L_ {2} = 254.5 \, {\ text {cm}} - 253.5 \, {\ text {cm}} = 1 \, {\ text {cm}}}$ ${\ Displaystyle 2 \, {\ text {cm}}}$ ${\ Displaystyle 1 \, {\ text {cm}}}$

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 tienen pequeños errores relativos y de valores verdaderos y , respectivamente, el error relativo de la diferencia aproximada de la diferencia verdadera es inversamente proporcional a la diferencia verdadera: ${\ 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 xy}$

{\ Displaystyle {\ begin {alineado} {\ tilde {x}} - {\ tilde {y}} & = x (1+ \ delta _ {x}) - y (1+ \ delta _ {y}) = x-y + x \ delta _ {x} -y \ delta _ {y} \\ & = x-y + (xy) {\ frac {x \ delta _ {x} -y \ delta _ {y}} { xy}} \\ & = (xy) {\ biggr (} 1 + {\ frac {x \ delta _ {x} -y \ delta _ {y}} {xy}} {\ biggr)}. \ end { alineado}}}

Por lo tanto, el error relativo de la diferencia exacta de las aproximaciones de la diferencia de los números verdaderos es ${\ Displaystyle {\ tilde {x}} - {\ tilde {y}}}$ ${\ Displaystyle xy}$

{\ Displaystyle \ left | {\ frac {x \ delta _ {x} -y \ delta _ {y}} {xy}} \ right |.}

que puede ser arbitrariamente grande si las verdaderas entradas y están cerca. ${\ 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 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

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 están cerca en magnitud, porque la resta amplificará los errores de redondeo en el cuadrado. La factorización alternativa , evaluada por la aritmética de punto flotante , evita la cancelación catastrófica porque evita introducir errores de redondeo que conducen a la resta. ${\ 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) (xy)}$ ${\ Displaystyle \ operatorname {fl} (\ operatorname {fl} (x + y) \ cdot \ operatorname {fl} (xy))}$

Por ejemplo, si y , entonces el verdadero valor de la diferencia es . En la aritmética IEEE 754 binary64 , 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 más cercano , del cual solo la mitad de los dígitos son correctos y la otra mitad (subrayado) son basura. ${\ Displaystyle x = 1 + 2 ^ {- 29} \ aproximadamente 1.0000000018626451}$ ${\ Displaystyle y = 1 + 2 ^ {- 30} \ aproximadamente 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) (xy)}$ ${\ Displaystyle x ^ {2} -y ^ {2}}$ ${\ displaystyle 1.8626451 {\ underline {49230957}} \ times 10 ^ {- 9}}$

Ejemplo: arcoseno complejo

Al calcular la función arcoseno compleja , uno puede tener la tentación de usar la fórmula logarítmica directamente:

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

Sin embargo, suponga 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 , 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 usando la fórmula logarítmica ingenua en la aritmética IEEE 754 binary64 puede dar , con solo cinco de los dieciséis dígitos correctos y el resto (subrayado) todo basura. ${\ Displaystyle -y}$ ${\ Displaystyle \ delta}$ ${\ Displaystyle 1 / \ varepsilon}$ ${\ Displaystyle \ varepsilon}$ ${\ Displaystyle z = -1234567i}$ ${\ Displaystyle \ arcsin (z)}$ ${\ displaystyle -14.71937803983977i}$ ${\ displaystyle -14,719 {\ subrayado {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 cancela. ${\ Displaystyle z = iy}$ ${\ Displaystyle y <0}$ ${\ Displaystyle \ arcsin (z) = - \ arcsin (-z)}$ ${\ estilo de texto {\ 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 double x = 1.000000000000001;para declarar e inicializar una variable IEEE 754 binary64 nombrada x. Sin embargo, no es un número de coma flotante binary64; el más cercano, que 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: ${\ Displaystyle 1.000000000000001}$ x ${\ displaystyle 1.0000000000000011102230246251565404236316680908203125 = 1 + 5 \ cdot 2 ^ {- 52}}$

double x = 1.000000000000001;  // rounded to 1 + 5*2^{-52}
double y = 1.000000000000002;  // rounded to 1 + 9*2^{-52}
double z = y - x;              // difference is exactly 4*2^{-52}

La diferencia es . Los errores relativos de desde y de desde se encuentran 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 a pesar de que las entradas son buenas aproximaciones, y aunque la resta se calcula exactamente, la diferencia de las aproximaciones tiene un error relativo superior a 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. ${\ 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 a veces es ú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 el redondeo . Sin embargo, la función en sí está bien acondicionada en entradas cercanas . 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}}}

aprovecha la cancelación para evitar que el error se evalúe directamente. Esto funciona porque la cancelación en el numerador y la cancelación en el denominador se contrarrestan; la función está suficientemente bien condicionada cerca de cero, lo que da una buena aproximación a , y por lo tanto da una buena aproximación a .