Cancelamento catastrófico - Catastrophic cancellation

Na análise numérica , o cancelamento catastrófico é o fenômeno que subtrair boas aproximações de dois números próximos pode resultar em uma péssima aproximação da diferença dos números originais.

Por exemplo, suponha que você tenha dois pinos de madeira, um longo e o outro longo. Se você medi-los com uma régua que é boa apenas até o centímetro, pode obter aproximações e . Dependendo de suas necessidades, essas podem ser boas aproximações, em erro relativo , dos comprimentos verdadeiros: as aproximações apresentam erros de menos de 2% dos comprimentos verdadeiros ,. ${\ 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 \%}$

No entanto, se você subtrair os comprimentos aproximados , obterá , embora a verdadeira diferença entre os comprimentos seja . A diferença das aproximações,, está com erro de 100% da magnitude da diferença dos valores verdadeiros ,. ${\ 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}}}$

O cancelamento catastrófico pode acontecer mesmo se a diferença for calculada exatamente, como no exemplo acima - não é uma propriedade de nenhum tipo particular de aritmética como a aritmética de ponto flutuante ; em vez disso, é inerente à subtração, quando as entradas são as próprias aproximações. De fato, na aritmética de ponto flutuante, quando as entradas estão próximas o suficiente, a diferença de ponto flutuante é calculada exatamente, pelo lema de Sterbenz - não há erro de arredondamento introduzido pela operação de subtração de ponto flutuante.

Análise formal

Formalmente, o cancelamento catastrófico acontece porque a subtração é mal condicionada nas entradas próximas: mesmo se as aproximações e tiverem pequenos erros relativos e de valores verdadeiros e , respectivamente, o erro relativo da diferença aproximada da diferença verdadeira é inversamente proporcional à diferença verdadeira: ${\ 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 {align} {\ 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 { alinhado}}}$$

Assim, o erro relativo da diferença exata das aproximações da diferença dos números verdadeiros é ${\ displaystyle {\ tilde {x}} - {\ tilde {y}}}$${\ displaystyle xy}$

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

que pode ser arbitrariamente grande se as entradas verdadeiras e forem próximas. ${\ displaystyle x}$${\ displaystyle y}$

Em algoritmos numéricos

Subtrair os números próximos na aritmética de ponto flutuante nem sempre causa um cancelamento catastrófico, ou mesmo qualquer erro - pelo lema de Sterbenz , se os números forem próximos o suficiente, a diferença de ponto flutuante é exata. Mas o cancelamento pode amplificar erros nas entradas que surgiram de arredondamento em outra aritmética de ponto flutuante.

Exemplo: diferença de quadrados

Dados os números e , a tentativa ingênua de calcular a função matemática pela aritmética de ponto flutuante está sujeita a um cancelamento catastrófico quando e estão próximos em magnitude, porque a subtração irá ampliar os erros de arredondamento no quadrado. A fatoração alternativa , avaliada pela aritmética de ponto flutuante , evita o cancelamento catastrófico porque evita a introdução de erro de arredondamento que leva à subtração. ${\ 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 exemplo, se e , então o verdadeiro valor da diferença é . Na aritmética IEEE 754 binary64 , avaliar a fatoração alternativa dá o resultado correto exatamente (sem arredondamento), mas avaliar a expressão ingênua dá o número de ponto flutuante mais próximo de , do qual apenas metade dos dígitos estão corretos e a outra metade (sublinhado) são lixo. ${\ 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}) \ aproximadamente 1,8626451518330422 \ times 10 ^ {- 9}}$${\ displaystyle (x + y) (xy)}$${\ displaystyle x ^ {2} -y ^ {2}}$${\ displaystyle 1,8626451 {\ underline {49230957}} \ vezes 10 ^ {- 9}}$

Exemplo: arco seno complexo

Ao calcular a função de arco seno complexo , pode-se ficar tentado a usar a fórmula logarítmica diretamente:

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

No entanto, suponha que seja . Então e ; chame a diferença entre eles - uma diferença muito pequena, quase zero. Se é avaliado em aritmética de ponto flutuante, 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)}$$

com qualquer erro , onde denota arredondamento de ponto flutuante, então computando a diferença ${\ displaystyle \ delta \ neq 0}$${\ displaystyle \ operatorname {fl} (\ cdots)}$

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

de dois números próximos, ambos muito próximos de , pode amplificar o erro em uma entrada por um fator de - um fator muito grande porque era quase zero. Por exemplo, if , o valor verdadeiro de é aproximadamente , mas usando a fórmula logarítmica ingênua na aritmética IEEE 754 binary64 pode resultar , com apenas cinco dos dezesseis dígitos corretos e o restante (sublinhado) todo lixo. ${\ displaystyle -y}$${\ displaystyle \ delta}$${\ displaystyle 1 / \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle z = -1234567i}$${\ displaystyle \ arcsin (z)}$${\ displaystyle -14.71937803983977i}$${\ displaystyle -14,719 {\ underline {644263563968}} i}$

No caso de for , usar a identidade evita o cancelamento porque mas , então a subtração é efetivamente adicionada com o mesmo sinal que não 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}$

Exemplo: conversão Radix

As constantes numéricas em programas de software são frequentemente escritas em decimal, como no fragmento C double x = 1.000000000000001;para declarar e inicializar uma variável binária64 IEEE 754 chamada x. No entanto, não é um número de ponto flutuante binário64; o mais próximo, que será inicializado neste fragmento, é . Embora a conversão de raiz de ponto flutuante decimal para ponto flutuante binário incorra apenas em um pequeno erro relativo, o cancelamento catastrófico pode amplificá-lo para um muito maior: ${\ 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}

A diferença é . Os erros relativos de partir e de partir são ambos abaixo e a subtração de ponto flutuante é calculado exatamente pela Sterbenz lema. ${\ displaystyle 1.000000000000002-1.000000000000001}$${\ displaystyle 0,000000000000001 = 1,0 \ vezes 10 ^ {- 15}}$x${\ displaystyle 1.000000000000001}$y${\ displaystyle 1.000000000000002}$${\ displaystyle 10 ^ {- 15} = 0,0000000000001 \%}$y - x

Mas mesmo que as entradas sejam boas aproximações, e mesmo que a subtração seja calculada exatamente, a diferença das aproximações tem um erro relativo de mais da diferença dos valores originais escritos em decimal: o cancelamento catastrófico amplificou um pequeno erro na conversão da raiz em um grande erro na saída. ${\ displaystyle {\ tilde {y}} - {\ tilde {x}} = (1 + 9 \ cdot 2 ^ {- 52}) - (1 + 5 \ cdot 2 ^ {- 52}) = 4 \ cdot 2 ^ {- 52} \ aproximadamente 8,88 \ vezes 10 ^ {- 16}}$${\ displaystyle 11 \%}$${\ displaystyle 1.0 \ times 10 ^ {- 15}}$

Cancelamento benigno

O cancelamento às vezes é útil e desejável em algoritmos numéricos. Por exemplo, os algoritmos 2Sum e Fast2Sum dependem desse cancelamento após um erro de arredondamento para calcular exatamente qual foi o erro em uma operação de adição de ponto flutuante como um número de ponto flutuante em si.

A função , se avaliada ingenuamente em pontos , perderá a maioria dos dígitos de no arredondamento . No entanto, a função em si é bem condicionada nas entradas próximas . Reescrevendo 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}}}$$

${\ 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)}$

Referências