Cancelamento catastrófico

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.

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\mathrm{\Delta }a-b\mathrm{\Delta }b}{a-b}\right|\le \max (\left|\mathrm{\Delta }a\right|,\left|\mathrm{\Delta }b\right|)\frac{\left|a\right|+\left|b\right|}{|a-b|}$

Deste modo, o erro relativo é grande quando:

$|a-b|<<\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\mathrm{\%}$

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=0,999999999999999988897769753748434595763683319091796875$

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{\mathrm{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\le r\le p$

$2^{-p}\le 1-\frac{y}{x}\le 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-\mathrm{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:

$\mathrm{sen}x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots$

Sendo assim, calculamos y por:

$x-\mathrm{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{\mathrm{sen}x}{x}>2^{-1}=\frac{1}{2}$

Sendo sen(x) > 0, o valor de x calculado é:

$\left|x\right|\ge 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:

$a{x}^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|(1-\frac{2c}{b^2}+...)$

$\approx -b+\left|b\right|(1-\frac{2c}{b^2})$

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

• Predefinição:Link mantido pelo projeto REAMAT da Universidade Federal do Rio Grande do Sul