En analyse numérique, l’algorithme de Clenshaw[1] est une méthode récursive permettant d'évaluer un polynôme comme combinaision linéaire des polynômes de Tchebychev. Elle peut se voir comme une généralisation de la méthode de Horner qui évalue une combinaison linéaire de monômes.
Cette méthode peut être étendue aux classes de fonctions définies par une relation de récurrence d'ordre 2[2].
Algorithme
Soit
une suite de fonctions vérifiant la relation de récurrence d'ordre 2

où les coefficients
et
sont connus. On remarquera que dans la plupart des cas,
est indépendant de Modèle:Math, et
est une constante ne dépendant ni de Modèle:Math ni de Modèle:Math.
L'objectif est donc de calculer la somme

À partir des coefficients
, on calcule les valeurs
par la formule de récurrence inverse :
![{\displaystyle {\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\[.5em]b_{k}(x)&=a_{k}+\alpha _{k}(x)\,b_{k+1}(x)+\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0512b38df578af019439beb0ffe233c909025d80)
La combinaision linéaire des
vérifie :

Fox et Parker ont étudié le comportement et la stabilité de ce type d'algorithme[3].
La méthode de Horner vue comme celle de Clenshaw
Un cas simple de l'algorithme apparait en considérant un polynôme de la forme
.
On obtient alors

et les coefficients deviennent alors
et
.
Ainsi, la formule de récurrence pour calculer la somme est

et ici, le résultat est
,
ce qui permet de retrouver le résultat de la méthode de Horner.
Cas particulier des séries de Tchebychev
Soit une série de Tchebychev tronquée

Les coefficients de la relation de récurrence dans les polynômes de Tchebychev sont

avec les conditions initiales

La formule de récurrence devient alors

et la somme finale devient

Un moyen d'évaluer ce polynôme est de calculer la récurrence à un pas supplémentaire, en posant

(avec un coefficient a0 double) puis
![{\displaystyle p_{n}(x)=b_{0}(x)-xb_{1}(x)-a_{0}={\frac {1}{2}}\left[b_{0}(x)-b_{2}(x)\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/600fa0464bfb62267581e20a02a969fbd449bcc6)
Applications géodesiques
L'algorithme de Clenshaw est beaucoup utilisé dans les applications géodésiques, où on parle plutôt de sommation de Clenshaw[4]. Une simple application est de sommer les séries trigonométriques pour calculer un arc de méridien. Ces sommes s'écrivent sous la forme

Mis à part le premier terme
, le reste peut se voir comme une somme de la forme voulue. Le terme initial dans une telle somme disparait car
.
En utilisant les relations de trigonométrie, on trouve la relation de récurrence nécessaire :

avec les coefficients correspondants

et l'évaluation de la série est donnée par
![{\displaystyle {\begin{aligned}b_{n+1}(\theta )&=b_{n+2}(\theta )=0,\\[.3em]b_{k}(\theta )&=C_{k}+2b_{k+1}(\theta )\cos \theta -b_{k+2}(\theta )\quad (n\geq k\geq 1).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/679086dde3deda6ef31c632f25f0fcebf471250e)
La dernière étape est simplifiée du fait que
, ce qui donne
; reste le terme
traité séparément :

L'algorithme ne nécessite ainsi que le calcul de
et
.
Voir aussi
Références
Modèle:Traduction/Référence
Modèle:Portail