30 Aceleração de Séries

As funções descritas nesse capítulo aceleram a convergência de uma série usando a transformada u de Levin (54). Esse método toma um pequeno número de termos partindo do início de uma série e usa uma aproximação sistemática para calcular um valor extrapolado e uma estimativa de seu erro. A transformada u trabalha para ambas as séries convergentes e divergentes, incluindo séries assintóticas.

Essas funções são declaradas no arquivo de cabeçalho ‘gsl_sum.h’.

30.1 Funções de aceleração

As seguintes funções calculam a transformada u de Levin completa de uma série com seu erro estimado. O erro estimado é calculado por propagação de erros de arredondamento para cada termo até a extrapolação final.

Essas funções foram pensadas para séries analiticas de somatório onde cada termo é conhecido com grande precisão, e os erros de arredondamento são assumidos originarem-se de precisão finita. Eles são tomados para serem erros relativos de ordem GSL_DBL_EPSILON para cada termo.

O cálculo de erro nos valores extrapolados é um processo O(N^2), que é dispendioso em tempo e em recursos de memória. Um rápido mas pouco confiável método que estima o erro da convergência de valores extrapolados é descrito na seguinte seção. Para o método descrito aqui uma tabela completa de valore intermediários e derivadas que consome recursos na forma O(N) deve ser calculado e armazenado, mas isso resulta em uma estimativa de erro confiável.

Function: gsl_sum_levin_u_workspace * gsl_sum_levin_u_alloc (size_t n): Essa função aloca um espaço de trabalho para uma transformada u de Levin de n termos. O tamanho do espaço de trabalho é O(2n^2 + 3n).

Function: void gsl_sum_levin_u_free (gsl_sum_levin_u_workspace * w): Essa função libera a memória associada ao espaço de trabalho w.

Function: int gsl_sum_levin_u_accel (const double * array, size_t array_size, gsl_sum_levin_u_workspace * w, double * sum_accel, double * abserr): Essa função toma os termos de uma série armazenados no vetor estático array de tamanho array_size e calcula o limite extrapolado da série usando uma transformada u de Levin. Espaço de trabalho adicional deve ser fornecido em w. A soma extrapolada é armazenada em sum_accel, com uma estimativa de erro absoluto armazenada em abserr. A atual soma termo a termo é retornada em w->sum_plain. O algoritmo calcula o erro por truncagem (a diferença entre duas sucessivas extrapolações) e erro de arredondamento (propagado a partir dos termos individuais) para escolher um número ótimo de termos para a extrapolação. Todos os termos da série informada através do vetor estático array devem ser diferentes de zero.

30.2 Funções de aceleração sem estimativa de erro

As funções descritas nessa seção calculam a transformada u de Levin de uma série e tenta estimar o erro do “erro por truncagem” na extrapolação, a diferença entre as duas aproximações finais. Usando o método evita a necessidade de calcular uma tabela intermediária de derivadas pelo fato de o erro ser estimado a partir do comportamento do valor extrapolado em si mesmo. Consequentemente esse algoritmo é um processo O(N) e somente requer O(N) termos de armazenamento. Se a série converge suficientemente rápido então esse procedimento pode ser aceitável. É apropriado usar esse método quando for preciso calcular muitas extrapolações de séries com propriedades de convergência similares em alta velocidade. Por exemplo, quando integrando numericamente uma função definida por uma série parametrizada onde o parâmetro varia de forma desprezível. Uma estimativa confiável de erro deve ser calculada primeiramente usando o algoritmo completo descrito acima com o objetivo de verificar a consistência dos resultados.

Function: gsl_sum_levin_utrunc_workspace * gsl_sum_levin_utrunc_alloc (size_t n): Essa função aloca um espaço de trabalho para uma transformada u de Levin de n termos, sem estimativa de erro. O tamanho do espaço de trabalho é O(3n).

Function: void gsl_sum_levin_utrunc_free (gsl_sum_levin_utrunc_workspace * w): Essa função libera a memória associada ao espaço de trabalho w.

Function: int gsl_sum_levin_utrunc_accel (const double * array, size_t array_size, gsl_sum_levin_utrunc_workspace * w, double * sum_accel, double * abserr_trunc): Essa função toma os termos da série no vetor estático array de tamanho array_size e calcula o limite extrapolado da série usando a transformada u de Levin. Espaço de trabalho adicional deve ser fornecido em w. A soma extrapolada é armazenada em sum_accel. A atual soma termo a termo é retornada em w->sum_plain. O algoritmo termina quando a diferença entre duas sucessivas extrapolações alcança um valor baixo ou suficientemente pequeno. A diferença entre esses dois valores é usada como estimativa de erro e é armazenada em abserr_trunc. Para melhorar a confiabilidade do algoritmo os valores extrapolados são substituídos movendo médias quando calculando o erro por truncagem, suavisando quaisquer flutuações.

30.3 Exemplos

O seguinte código calcula uma estimativa de \zeta(2) = \pi^2 / 6 usando a série,

ζ(2) = 1 + 1/2² + 1/3² + 1/4² + ...

Após N termos o erro na soma é O(1/N), fazendo simulação direta da série converge lentamente.

#include <stdio.h>
#include <gsl/gsl_math.h>
#include <gsl/gsl_sum.h>

#define N 20

int
main (void)
{
  double t[N];
  double sum_accel, err;
  double sum = 0;
  int n;
  
  gsl_sum_levin_u_workspace * w 
    = gsl_sum_levin_u_alloc (N);

  const double zeta_2 = M_PI * M_PI / 6.0;
  
  /* terms for zeta(2) = \sum_{n=1}^{\infty} 1/n^2 */

  for (n = 0; n < N; n++)
    {
      double np1 = n + 1.0;
      t[n] = 1.0 / (np1 * np1);
      sum += t[n];
    }
  
  gsl_sum_levin_u_accel (t, N, w, &sum_accel, &err);

  printf ("term-by-term sum = % .16f using %d terms\n", 
          sum, N);

  printf ("term-by-term sum = % .16f using %d terms\n", 
          w->sum_plain, w->terms_used);

  printf ("exact value      = % .16f\n", zeta_2);
  printf ("accelerated sum  = % .16f using %d terms\n", 
          sum_accel, w->terms_used);

  printf ("estimated error  = % .16f\n", err);
  printf ("actual error     = % .16f\n", 
          sum_accel - zeta_2);

  gsl_sum_levin_u_free (w);
  return 0;
}

A saída abaixo mostra que a transformada u de Levin é capaz de obter uma estimativa da soma para 1 parte em 10^10 usando os primeiros 11 termos da série. O erro estimado retornado pela função é também preciso, fornecendo o número correto de dígitos significativos.

$ ./a.out 
term-by-term sum =  1.5961632439130233 using 20 terms
term-by-term sum =  1.5759958390005426 using 13 terms
exact value      =  1.6449340668482264
accelerated sum  =  1.6449340668166479 using 13 terms
estimated error  =  0.0000000000508580
actual error     = -0.0000000000315785

Note que um somatório direto dessa série irá requerer 10^10 termos para encontrar a mesma precisão que a soma acelerada faz com 13 termos.

30.4 Referências e Leituras Adicionais

O algoritmo usado por essas funçẽos são descritos nos seguintes artigos,

T. Fessler, W.F. Ford, D.A. Smith, HURRY: An acceleration algorithm for scalar sequences and series ACM Transactions on Mathematical Software, 9(3):346–354, 1983. and Algorithm 602 9(3):355–357, 1983.

A teoria da transformada u foi mostrada por Levin,

D. Levin, Development of Non-Linear Transformations for Improving Convergence of Sequences, Intern. J. Computer Math. B3:371–388, 1973.

Uma revisão do artigo sobre a Transformada de Levin está disponível online,

Herbert H. H. Homeier, Scalar Levin-Type Sequence Transformations, http://arxiv.org/abs/math/0005209.

Esse documento foi gerado em 23 de Julho de 2013 usando texi2html 5.0.