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

modifier

Soit ϕk,k=0,1,… une suite de fonctions vérifiant la relation de récurrence d'ordre 2

ϕk+1(x)=αk(x)ϕk(x)+βk(x)ϕk−1(x),

où les coefficients αk et βk sont connus. On remarquera que dans la plupart des cas, α(x) est indépendant de k, et β est une constante ne dépendant ni de x ni de k.

L'objectif est donc de calculer la somme

S(x)=∑k=0nakϕk(x)

À partir des coefficients a0,…,an, on calcule les valeurs bk(x) par la formule de récurrence inverse :

bn+1(x)=bn+2(x)=0,bk(x)=ak+αk(x)bk+1(x)+βk+1(x)bk+2(x).

La combinaision linéaire des ϕk vérifie :

S(x)=ϕ0(x)a0+ϕ1(x)b1(x)+β1(x)ϕ0(x)b2(x).

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

modifier

Un cas simple de l'algorithme apparait en considérant un polynôme de la forme

S(x)=∑k=0nakxk.

On obtient alors

ϕ0(x)=1,ϕk(x)=xk=xϕk−1(x)

et les coefficients deviennent alors α(x)=x et β=0.

Ainsi, la formule de récurrence pour calculer la somme est

bk(x)=ak+xbk+1(x)

et ici, le résultat est

S(x)=a0+xb1(x)=b0(x),

ce qui permet de retrouver le résultat de la méthode de Horner.

Cas particulier des séries de Tchebychev

modifier

Soit une série de Tchebychev tronquée

pn(x)=a0+a1T1(x)+a2T2(x)+⋯+anTn(x).

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

α(x)=2x,β=−1,

avec les conditions initiales

T0(x)=1,T1(x)=x.

La formule de récurrence devient alors

bk(x)=ak+2xbk+1(x)−bk+2(x)

et la somme finale devient

pn(x)=a0+xb1(x)−b2(x).

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

b0(x)=2a0+2xb1(x)−b2(x),

(avec un coefficient a0 double) puis

pn(x)=b0(x)−xb1(x)−a0=12[b0(x)−b2(x)].

Applications géodésiques

modifier

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

m(θ)=C0θ+C1sin⁡θ+C2sin⁡2θ+⋯+Cnsin⁡nθ.

Mis à part le premier terme C0θ, le reste peut se voir comme une somme de la forme voulue. Le terme initial dans une telle somme disparait car ϕ0(θ)=sin⁡0θ=sin⁡0=0.

En utilisant les relations de trigonométrie, on trouve la relation de récurrence nécessaire :

sin⁡kθ=2cos⁡θsin⁡(k−1)θ−sin⁡(k−2)θ,

avec les coefficients correspondants

αk(θ)=2cos⁡θ,βk=−1.

et l'évaluation de la série est donnée par

bn+1(θ)=bn+2(θ)=0,bk(θ)=Ck+2bk+1(θ)cos⁡θ−bk+2(θ)(n≥k≥1).

La dernière étape est simplifiée du fait que ϕ0(θ)=sin⁡0=0, ce qui donne b1(θ)sin⁡(θ) ; reste le terme C0θ traité séparément :

m(θ)=C0θ+b1(θ)sin⁡θ.

L'algorithme ne nécessite ainsi que le calcul de cos⁡θ et sin⁡θ.

Voir aussi

modifier

Références

modifier
  1. ↑ DOI 10.1090/S0025-5718-1955-0071856-0 Dans ce papier, on utilise la forme étendue des polynômes de Tchebychev de première espèce Tn∗(x)=Tn(2x−1).
  2. ↑ (en) WH Press, SA Teukolsky, WT Vetterling et BP Flannery, Numerical Recipes : The Art of Scientific Computing, New York, Cambridge University Press, , 3e éd., 1235 p. (ISBN 978-0-521-88068-8, lire en ligne), chap. 5.4.2 (« Clenshaw's Recurrence Formula »)
  3. ↑ L. Fox et I. B. Parker, « Chebyshev Polynomials in Numerical Analysis », Oxford mathematical handbooks, Oxford University Press,‎ (ISBN 0-19-859614-6)
  4. ↑ C. C. Tscherning et K. Poder, « Some Geodetic applications of Clenshaw Summation », Bolletino di Geodesia e Scienze Affini, vol. 41, no 4,‎ , p. 349–375 (lire en ligne)