Algorithme de Clenshaw

Soit ${\displaystyle \phi _{k},\;k=0,1,\ldots }$ une suite de fonctions vérifiant la relation de récurrence d'ordre 2

${\displaystyle \phi _{k+1}(x)=\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x),}$

où les coefficients ${\displaystyle \alpha _{k}}$ et ${\displaystyle \beta _{k}}$ sont connus. On remarquera que dans la plupart des cas, ${\displaystyle \alpha (x)}$ est indépendant de k, et ${\displaystyle \beta }$ est une constante ne dépendant ni de x ni de k.

L'objectif est donc de calculer la somme

${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}\phi _{k}(x)}$

À partir des coefficients ${\displaystyle a_{0},\ldots ,a_{n}}$, on calcule les valeurs ${\displaystyle b_{k}(x)}$ 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}}}$

La combinaision linéaire des ${\displaystyle \phi _{k}}$ vérifie :

${\displaystyle S(x)=\phi _{0}(x)a_{0}+\phi _{1}(x)b_{1}(x)+\beta _{1}(x)\phi _{0}(x)b_{2}(x).}$

Fox et Parker ont étudié le comportement et la stabilité de ce type d'algorithme^[3].

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

${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}x^{k}}$.

On obtient alors

${\displaystyle {\begin{aligned}\phi _{0}(x)&=1,\\\phi _{k}(x)&=x^{k}=x\phi _{k-1}(x)\end{aligned}}}$

et les coefficients deviennent alors ${\displaystyle \alpha (x)=x}$ et ${\displaystyle \beta =0}$.

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

${\displaystyle b_{k}(x)=a_{k}+xb_{k+1}(x)}$

et ici, le résultat est

${\displaystyle S(x)=a_{0}+xb_{1}(x)=b_{0}(x)}$,

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

Soit une série de Tchebychev tronquée

${\displaystyle p_{n}(x)=a_{0}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\cdots +a_{n}T_{n}(x).}$

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

${\displaystyle \alpha (x)=2x,\quad \beta =-1,}$

avec les conditions initiales

${\displaystyle T_{0}(x)=1,\quad T_{1}(x)=x.}$

La formule de récurrence devient alors

${\displaystyle b_{k}(x)=a_{k}+2xb_{k+1}(x)-b_{k+2}(x)}$

et la somme finale devient

${\displaystyle p_{n}(x)=a_{0}+xb_{1}(x)-b_{2}(x).}$

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

${\displaystyle b_{0}(x)=2a_{0}+2xb_{1}(x)-b_{2}(x),}$

(avec un coefficient a₀ 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].}$

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

${\displaystyle m(\theta )=C_{0}\,\theta +C_{1}\sin \theta +C_{2}\sin 2\theta +\cdots +C_{n}\sin n\theta .}$

Mis à part le premier terme ${\displaystyle C_{0}\,\theta }$, le reste peut se voir comme une somme de la forme voulue. Le terme initial dans une telle somme disparait car ${\displaystyle \phi _{0}(\theta )=\sin 0\theta =\sin 0=0}$.

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

${\displaystyle \sin k\theta =2\cos \theta \sin(k-1)\theta -\sin(k-2)\theta ,}$

avec les coefficients correspondants

${\displaystyle \alpha _{k}(\theta )=2\cos \theta ,\quad \beta _{k}=-1.}$

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}}}$

La dernière étape est simplifiée du fait que ${\displaystyle \phi _{0}(\theta )=\sin 0=0}$, ce qui donne ${\displaystyle b_{1}(\theta )\sin(\theta )}$ ; reste le terme ${\displaystyle C_{0}\,\theta }$ traité séparément :

${\displaystyle m(\theta )=C_{0}\,\theta +b_{1}(\theta )\sin \theta .}$

L'algorithme ne nécessite ainsi que le calcul de ${\displaystyle \cos \theta }$ et ${\displaystyle \sin \theta }$.

• Méthode de Horner pour le calcul de polynômes sous forme monomiale
• Algorithme de De Casteljau pour le calcul de polynômes sous forme de Bézier

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Clenshaw algorithm » (voir la liste des auteurs).

• Portail de l'analyse