Perda de dígitos (II)

O perigo da somar números distantes

Vamos lá?

Na aula passada vimos um exemplo do perigo que pode ser subtrair número próximos. Nesta aula veremos um segundo exemplo, onde não há nenhuma subtração. Será que estaremos em segurança então?

O exemplo do vídeo é para mostrar que a perda de dígitos significativos não aparece apenas quando temos cancelamento pela subtração de números próximos. Vamos analisar o que aconteceu no vídeo.

Seja $S_N = \sum_{k=1}^N k^{-2}.$ É possível mostrar que a sequência $S_1, S_2, S_3,\ldots$ é convergente. Para tanto, basta usar o teste da integral para convergência de séries. Seu limite, $S,$ representado por $S = \sum_{k=1}^\infty k^{-2}$ vale $\pi^2/6$ . Além disso, como os termos de série são todos positivos, $|S-S_N|$ decresce monotonicamente, ou seja, quanto maior for $N$ menor será $|S-S_N|.$

Assim, o algoritmo abaixo estima $S$ computando $S_N$ para um $N$ grande prescrito.

  • $s\leftarrow 0$
  • $k\leftarrow 1$
  • enquanto $k \le N,$ repita:
    • $s\leftarrow s+1/k^2$
    • $k\leftarrow k+1$

Acontece que a medida que $k$ aumenta, aumenta também o valor armazenado em $s$ e diminui a o valor de $1/k^2$ a ser somado a $s.$ Isso pode ser visto no gráfico abaixo.

Neste gráfico (em escala logarítmica) a curva em preto representa o valor que está acumulado na variável $s$ durante o progresso do algoritmo, enquanto que a curva em vermelho representa o valor do termo $1/k^2$ que será somado a $s.$ Observe que, a medida que o algoritmo progride, a diferença entre o valor que está em $s$ e o valor que deve ser acrescido aumenta em várias ordens de magnitude. Quando a iteração chega a $4096,$ a diferença entre $s$ e $1/(4096)^2$ é de mais de 7 ordens de magnitude e por isso, o fator $1/(4096)^2$ não chega mais a contribuir para $s.$ Lembre que em precisão simples, a unidade de arredondamento é da ordem de $10^{-7}.$

A estratégia para evitar esta disparidade de grandezas é trocar a ordem com que a soma é feita.

  • $s\leftarrow 0$
  • $k\leftarrow N$
  • enquanto $k \ge 1,$ repita:
    • $s\leftarrow s+1/k^2$
    • $k\leftarrow k-1$

Neste segundo algoritmo, o valor de $s$ vai progressivamente acumulando os menores termos da soma. Também progressivamente, o valor acrescido a $s,$ $1/k^2$, também cresce, uma vez que o $k$ varia de $N$ a $1.$ No gráfico abaixo, podemos ver o crescimento do valor acumulado em $s,$ assim como o termo $1/k^2$ a ser somado, durante o progresso das iterações. Perceba que a diferença entre as duas curvas nunca chega às 7 ordens de grandeza como no gráfico acima.

Para poder fazer esses experimentos nos Octave é necessário definir a variável s como sendo de precisão simples. Por exemplo, o primeiro algoritmo, traduzido para linguagem do Octave, ficaria assim:

N = 4096;
s = single(0);
k = 1;
while (k <= N)
   s = s + (1/k^2);
   k = k + 1;
endwhile

Com este exemplo mostramos que, em um sistema de ponto flutuante, ao somar números de grandezas muito distintas os dígitos do número menos significativo podem acabar por serem descartados e não influenciar o resultado. Enquanto que para uma única soma isso não tem muita influência, afinal os dígitos que são preservados são os mais significativos mesmo, em um processo acumulativo isso pode ser desastroso. Isto porque os dígitos perdidos em cada soma, se acumulados, poderiam ser significativos para o resultado final. Neste exemplo, foi possível trocar a ordem com que as operações eram feitas. Em outros casos isto pode não ser tão simples.

1. Rode os dois algoritmos descritos no texto, usando o Octave (ou o Octave-Online). Experimente trocar a instrução while por for.

2. Considerando o SPF $\mathbb{F}(10,5,-99,99),$ traduza as operações abaixo em um algoritmo que as compute e, de fato, compute-as:

  1. $10000 + \sum_{k=1}^{25000} 0.4.$
  2. $\left[ \sum_{k=1}^{25000} 0.4 \right]+ 10000.$

(a) $10000$. (b) $20000$.

3. Trabalhando em precisão dupla, ainda haveria diferença no desempenho do algoritmo do exemplo que acumula os termos na ordem direta daquele que acumula na ordem reversa? Faça um experimento numérico para justificar sua conjectura.