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.

Gráfico de ((1+x)-1)/x calculado em sistema de numeração do tipo 'double'. Idealmente o resultado seria 1, o gráfico mostra o efeito da perda de significância na operação (1+x) quando x é pequeno. Quando x se torna menor que o épsilon de máquina, a expressão se torna nula.

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 é:

Cancelamento catastrófico 2

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

Ligações externas

• «Livro de cálculo numérico»  mantido pelo projeto REAMAT da Universidade Federal do Rio Grande do Sul