# Cancelamento catastrófico

Cancelamento catastrófico (ou perda de significância ou ainda cancelamento subtrativo) é um efeito que ocorre em operações envolvendo aritmética de ponto flutuante, sendo caracterizado por um aumento substancial do erro relativo nos resultados destas. O exemplo característico deste tipo de erro é quando há a subtração de dois números muito próximos.

## Apresentação do problema geral

Seja x = (a - b) e X = (a - b), onde a = a(1 + Δa) e b = b(1 + Δb), e os valores Δa e Δb tidos como erros relativos de arredondamentos por armazenamento ou computações prévias. A partir dos dados, pode-se chegar a seguinte expressão:
    $\left|{\frac {x-X}{x}}\right|=\left|{\frac {-a\Delta a-b\Delta b}{a-b}}\right|\leq \max \left(\left|\Delta a\right|,\left|\Delta b\right|\right){\frac {\left|a\right|+\left|b\right|}{\left|a-b\right|}}$
Deste modo, o erro relativo é grande quando:
    $\left|a-b\right|<<\left|a\right|+\left|b\right|$
e ocorre quando tem-se o cancelamento catastrófico. Assim, só existe um cancelamento catastrófico quando existirem erros nos dados.

### Exemplo

Considere os números racionais x e y com dez dígitos:
    $x=0,3721478693$
    $y=0,3720230572$
O resultado exato de sua subtração é dado por:
    $x-y=0,0001248121$
Se esta subtração for feita com apenas 5 dígitos na mantissa, os resultados obtidos serão:
    $f(x)=0,37215$
    $f(y)=0,37202$
    $f(x)-f(y)=0,00013$
O resultado desta operação de diferença em ponto flutuante é de:
    $f(x)-f(y)=0,00013=0,13000\times 10^{-3}$
Vemos que mesmo possuindo cinco dígitos, os últimos três dígitos não têm significância alguma. Calculando-se o erro relativo:
    $\left|{\frac {(f(x)-f(y))-(x-y)}{(x-y)}}\right|\approx 4\%$
O erro gerado acima possui um valor maior que o esperado. Este tipo de erro é denominado cancelamento catastrófico, e pode ser evitado em várias situações.

### Outro exemplo

Seja a função dada por
    $f(x)={\frac {1-\cos x}{x^{2}}}$
cuja aproximação de Taylor é dada por:
    $f(x)={\frac {1-\cos x}{x^{2}}}={\frac {1}{2}}-{\frac {1}{6}}x^{2}+O(x^{4})$
Pelo critério de Leibniz aplicado à série de taylor de f(x) dentro do intervalo -10$^{-7}$≤ x ≤ 10$^{-7}$, o valor de f(x) poderia ser aproximado por 0.5 com quatorze dígitos significativos. No entanto, o gráfico do resultado obtido usando uma precisão Double IEEE 754 é:
Para explicar tal fenômeno, consideremos $x=1,1\cdot 10^{-8}$ e uma precisão de 16 dígitos decimais, tem-se:
* $\cos x={\color {RoyalPurple}0,9999999999999999}88897769753748434595763683319091796875$
             Valor de ponto flutuante mais próximo com resposta exata para 16 casas decimais
* $1-\cos x=1,1102\cdot 10^{-16}$
             Estimação imprecisa da resposta exata (6,05 . 10 $^{-17}$)
* ${\frac {1-\cos x}{x^{2}}}=0,9175$
             80% maior que a resposta exata (0,5)
Vemos que os 16 dígitos são insuficientes para aproximar o valor de f(x). A subtração em si é exata, mas produz resultado da ordem do erro de cos(x). Assim, a subtração supervalorizou a importância do erro anterior.
Porém, cabe ressaltar que na realidade o problema não está na subtração em si, mas no arredondamento anterior a ela. Logo, uma alteração na equação pode tornar o cálculo numericamente estável.
Por exemplo, se usarmos a identidade trigonométrica 1-cos(x)=2sen²(x/2) para reescrever f(x) na forma:
    $f(x)={\frac {1}{2}}\left({\frac {\operatorname {sen}({\frac {x}{2}})}{x/2}}\right)^{2}$
e $x=1,1\cdot 10^{-8}$, chega-se a $f(x)=0,5$ , que é o resultado que esperaríamos encontrar.

## Teorema da perda de precisão

Considere x e y números positivos, normalizados em ponto flutuante com representação binária, com x > y e
    $q\leq r\leq p$
    $2^{-p}\leq 1-{\frac {y}{x}}\leq 2^{-q}$
Então, no mínimo p e no máximo q dígitos binários são perdidos na subtração de x por y.

### Exemplo

Considere a expressão abaixo:
    $y\leftarrow x-\operatorname {sen} x$
Espera-se que haja uma perda de significância para valores de x muito pequenos. Para solucionar esse problema, usa-se uma fórmula alternativa, escrevendo o seno em forma de série de Taylor:
    $\operatorname {sen} x=x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-{\frac {x^{7}}{7!}}+\cdots$
Sendo assim, calculamos y por:
    $x-\operatorname {sen} x={\frac {x^{3}}{3!}}-{\frac {x^{5}}{5!}}+{\frac {x^{7}}{7!}}+\cdots$
Tendo valores muito pequenos de x, podemos usar uma série truncada, pois os termos de alta ordem acabam sendo desprezíveis. Usando o teorema da perda de precisão, e estabelecendo que a perda seja de no máximo um bit binário (q=1) na subtração acima, tem-se:
    $1-{\frac {\operatorname {sen} x}{x}}>2^{-1}={\frac {1}{2}}$
Sendo sen(x) > 0, o valor de x calculado é:
    $\left|x\right|\geq 1,9;$ para q = 1
Por fim, a expressão x - sen(x) só pode ser utilizada para |x| ≥ 1,9. Naturalmente, o pior caso (o maior erro de arredondamento) ocorre em |x| = 1,9. Para outros valores de x, outra configuração deve ser utilizada para continuar evitando a perda de mais de um dígito binário. Todavia, faz-se necessário uma análise de erro de truncamento da série, para que este não seja elevado.

## Cancelamento Catastrófico em avaliação de funções matemáticas

Inúmeras funções matemáticas são comumente avaliadas utilizando sub-rotinas específicas, onde pode ocorrer cancelamento catastrófico. Peguemos como exemplo a avaliação da função cosseno com x = 33278,21. Note que x possui 7 dígitos de precisão. O problema que ocorre na avaliação de cos(x) é devido às rotinas empregadas que usualmente utilizam um artifício denominado redução de ordem. Este consiste no uso das identidades trigonométricas:
    $\cos(x+2n\pi )=\cos(x)$
    $\cos(-x)=-\cos(\pi -x)$
Onde 0 ≤ x ≤ 2π, para simplificar os cálculos.
Calculando o argumento reduzido para x = 33278,21 utilizando 7 dígitos de precisão:
    $x=33278,21-5296\cdot 2\pi =2,46$
Assim, notamos que o resultado tem apenas 3 algarismos significativos. Ao calcularmos o cosseno:
    $\cos(2,460000)=-0,7765703$
Este resultado pode fazer-nos concluir erroneamente que o número acima contém sete dígitos significativos. No entanto, temos que no máximo três dígitos são significativos. A rotina empregada no cálculo do cosseno não sabe que o número inicial (2,46) só tinha três dígitos de precisão e por isso calcula como se fosse 2,460000 com todos os algarismos sendo significativos.

## Caso das Equações de Segundo Grau

Seja a equação do segundo grau:
    $ax^{2}+bx+c=0$
Para acharmos as raízes deste tipo de equação, utilizamos a fórmula de Bhaskara: $x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}.$
Porém, para casos onde $b^{2}>>4ac$ , então ${\sqrt {b^{2}-4ac}}\approx \left|b\right|$. Assim, ao tentarmos determinar a segunda raiz $x_{2}={\frac {-b+{\sqrt {b^{2}-4ac}}}{2a}}.$ , tem-se um cancelamento catastrófico, pois $f({\sqrt {b^{2}-4ac}})$ não é exata e a subtração leva a uma supervalorização do erro.
A inexatidão no cálculo da segunda raiz pode ser atenuada se modificarmos a expressão de maneira a evitar a subtração dos dois valores muito próximos. Assim, evitamos o cancelamento catastrófico realizando o cancelamento na própria expressão, antes de realizarmos as operações:
    $-b\pm {\sqrt {b^{2}-4ac}}=$
                            $=-b+\left|b\right|{\sqrt {1-{\frac {4c}{b^{2}}}}}$
                            $=-b+\left|b\right|\left(1-{\frac {2c}{b^{2}}}+...\right)$
                            $\approx -b+\left|b\right|\left(1-{\frac {2c}{b^{2}}}\right)$
Sendo b > 0, a segunda raiz pode ser determinada por: ${\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}\approx -{\frac {c}{b}}$
Outra fonte comum de erro é quando $b^{2}\approx 4ac$. Neste caso, no entanto, nenhum rearranjo algébrico pode evitar o problema. Uma alternativa para tentar melhorar a resposta é aumentar a precisão da solução.

## Veja também

* Número de condicionamento de uma função