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[1][2]) é 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[3]:

${\displaystyle \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:

${\displaystyle \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:

${\displaystyle x=0,3721478693}$

${\displaystyle y=0,3720230572}$

O resultado exato de sua subtração é dado por:

${\displaystyle x-y=0,0001248121}$

Se esta subtração for feita com apenas 5 dígitos na mantissa, os resultados obtidos serão:

${\displaystyle f(x)=0,37215}$

${\displaystyle f(y)=0,37202}$

${\displaystyle f(x)-f(y)=0,00013}$

O resultado desta operação de diferença em ponto flutuante é de:

${\displaystyle 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:

${\displaystyle \left|{\frac {(f(x)-f(y))-(x-y)}{(x-y)}}\right|\approx 4\%}$

O erro gerado acima possui um valor maior que o esperado.[4] 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

${\displaystyle f(x)={\frac {1-\cos x}{x^{2}}}}$

cuja aproximação de Taylor é dada por:

${\displaystyle f(x)={\frac {1-\cos x}{x^{2}}}={\frac {1}{2}}-{\frac {1}{6}}x^{2}+O(x^{4})}$

Pelo critério de Leibniz[5] 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 ${\displaystyle x=1,1\cdot 10^{-8}}$ e uma precisão de 16 dígitos decimais, tem-se:

• ${\displaystyle \cos x={\color {RoyalPurple}0,9999999999999999}88897769753748434595763683319091796875}$

Valor de ponto flutuante mais próximo com resposta exata para 16 casas decimais

• ${\displaystyle 1-\cos x=1,1102\cdot 10^{-16}}$

Estimação imprecisa da resposta exata (6,05 . 10 ^-17)

• ${\displaystyle {\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[3]:

${\displaystyle f(x)={\frac {1}{2}}\left({\frac {\operatorname {sen}({\frac {x}{2}})}{x/2}}\right)^{2}}$

e ${\displaystyle x=1,1\cdot 10^{-8}}$, chega-se a ${\displaystyle f(x)=0,5}$ , que é o resultado que esperaríamos encontrar.

Teorema da perda de precisão[6]

Considere x e y números positivos, normalizados em ponto flutuante com representação binária, com x > y e

${\displaystyle q\leq r\leq p}$

${\displaystyle 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.[7]

Exemplo

Considere a expressão abaixo:

${\displaystyle 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:

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

Sendo assim, calculamos y por:

${\displaystyle 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:

${\displaystyle 1-{\frac {\operatorname {sen} x}{x}}>2^{-1}={\frac {1}{2}}}$

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

${\displaystyle \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:

${\displaystyle \cos(x+2n\pi )=\cos(x)}$

${\displaystyle \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:

${\displaystyle x=33278,21-5296\cdot 2\pi =2,46}$

Assim, notamos que o resultado tem apenas 3 algarismos significativos. Ao calcularmos o cosseno:

${\displaystyle \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:

${\displaystyle ax^{2}+bx+c=0}$

Para acharmos as raízes deste tipo de equação, utilizamos a fórmula de Bhaskara: ${\displaystyle x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}.}$

Porém, para casos onde ${\displaystyle b^{2}>>4ac}$ , então ${\displaystyle {\sqrt {b^{2}-4ac}}\approx \left|b\right|}$. Assim, ao tentarmos determinar a segunda raiz ${\displaystyle x_{2}={\frac {-b+{\sqrt {b^{2}-4ac}}}{2a}}.}$ , tem-se um cancelamento catastrófico, pois ${\displaystyle 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[3]:

${\displaystyle -b\pm {\sqrt {b^{2}-4ac}}=}$

${\displaystyle =-b+\left|b\right|{\sqrt {1-{\frac {4c}{b^{2}}}}}}$

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

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

Sendo b > 0, a segunda raiz pode ser determinada por: ${\displaystyle {\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}\approx -{\frac {c}{b}}}$

Outra fonte comum de erro é quando ${\displaystyle 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

Referências

1. Cláudio, Dalcídio Moraes; Marins, Jussara Maria (1994). Cálculo Numérico Computacional. Teoria e Prática 2ª ed. São Paulo: Atlas. p. 43. ISBN 85-224-1043-7  !CS1 manut: Nomes múltiplos: lista de autores (link)
2. Dorn, William S.; McCracken, Daniel D (1972). Cálculo Numérico com Estudos de Casos em Fortran IV. Rio de Janeiro: Campus/Edusp. p. 129. ISBN 85-7001-018-4  !CS1 manut: Nomes múltiplos: lista de autores (link)
3. Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. Cap 1, p. 19
4. L.A.Sphaier, L.S.B.Alves. Representação de Números, Erros Numéricos e Aritmética Computacional. Disponível em www.sphaier.com
5. Geraldo Ávila. Introdução à Análise Matemática. [S.l.: s.n.] ISBN 8521201680 
6. «Cálculo numérico». Universidade Federal do Rio Grande do Sul. Consultado em 11 de março de 2018 
7. D. Kincaid and E. W. Cheney. Numerical Analysis: Mathematics of Scientific Computing. Brooks/Cole Publishing Company, Paci_c Grove, CA, 1990.