Na análise numérica , o algoritmo de Clenshaw , também chamado de soma de Clenshaw , é um método recursivo para avaliar uma combinação linear de polinômios de Chebyshev . O método foi publicado por Charles William Clenshaw em 1955. É uma generalização do método de Horner para avaliar uma combinação linear de monômios .
Ele generaliza para mais do que apenas polinômios de Chebyshev; ele se aplica a qualquer classe de funções que podem ser definidas por uma relação de recorrência de três termos .
Algoritmo de Clenshaw
Em geral, o algoritmo de Clenshaw calcula a soma ponderada de uma série finita de funções :
onde é uma sequência de funções que satisfazem a relação de recorrência linear
onde os coeficientes e são conhecidos antecipadamente.
O algoritmo é mais útil quando são funções que são complicadas para calcular diretamente, mas e são particularmente simples. Nas aplicações mais comuns, não depende de e é uma constante que não depende de nem .
Para realizar a soma de determinada série de coeficientes , calcule os valores pela fórmula de recorrência "reversa":
Observe que este cálculo não faz referência direta às funções . Depois de calcular e , a soma desejada pode ser expressa em termos deles e das funções mais simples e :
Consulte Fox e Parker para obter mais informações e análises de estabilidade.
Exemplos
Horner como um caso especial de Clenshaw
Um caso particularmente simples ocorre ao avaliar um polinômio da forma
-
.
As funções são simplesmente
e são produzidos pelos coeficientes de recorrência e .
Neste caso, a fórmula de recorrência para calcular a soma é
e, neste caso, a soma é simplesmente
-
,
que é exatamente o método usual de Horner .
Caso especial para a série Chebyshev
Considere uma série truncada de Chebyshev
Os coeficientes na relação de recursão para os polinômios de Chebyshev são
com as condições iniciais
Assim, a recorrência é
e a soma final é
Uma maneira de avaliar isso é continuar a recorrência mais uma etapa e calcular
(note o dobrou um 0 coeficiente) seguido por
Comprimento do arco meridiano no elipsóide
O somatório de Clenshaw é amplamente utilizado em aplicações geodésicas . Uma aplicação simples é somar a série trigonométrica para calcular a distância do arco meridiano na superfície de um elipsóide. Estes têm a forma
Deixando de lado o prazo inicial , o restante é um somatório da forma adequada. Não existe um termo principal porque .
A relação de recorrência para é
-
,
tornando os coeficientes na relação de recursão
e a avaliação da série é dada por
A etapa final é particularmente simples porque , portanto, o fim da recorrência é simples ; o termo é adicionado separadamente:
Observe que o algoritmo requer apenas a avaliação de duas grandezas trigonométricas e .
Diferença em comprimentos de arco meridiano
Às vezes, é necessário calcular a diferença de dois arcos meridianos de uma forma que mantenha uma alta precisão relativa. Isso é feito usando identidades trigonométricas para escrever
O somatório de Clenshaw pode ser aplicado neste caso, desde que calculemos
e executemos simultaneamente um somatório de matriz,
Onde
O primeiro elemento de é o valor médio de e o segundo elemento é a inclinação média.
satisfaz a relação de recorrência
Onde
toma o lugar de na relação de recorrência e . O algoritmo de Clenshaw padrão agora pode ser aplicado para produzir
onde estão matrizes 2 × 2. Finalmente temos
Esta técnica pode ser utilizada no limite
e para calcular simultaneamente e a derivada , desde que, na avaliação e , tomemos .
Veja também
Referências