Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Algorithme de Clenshaw
Résumé
En analyse numérique, l’algorithme de Clenshaw 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.
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 k, et est une constante ne dépendant ni de x ni de k.
L'objectif est donc de calculer la somme
À partir des coefficients , on calcule les valeurs par la formule de récurrence inverse :
La combinaision linéaire des vérifie :
Fox et Parker ont étudié le comportement et la stabilité de ce type d'algorithme.
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.
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
L'algorithme de Clenshaw est beaucoup utilisé dans les applications géodésiques, où on parle plutôt de sommation de Clenshaw. 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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.