Algorithme de Clenshaw

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].

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