Évaluation rapide (approximative) du polynôme de Tchebychev

9

Existe-t-il un moyen préféré de mettre en œuvre une évaluation rapide (approximative) du polynôme d'interpolation de Chebyshev sur une grille uniforme (compte tenu des valeurs de fonction aux nœuds de Chebyshev)? Mon problème est que l'interpolation devient lente lorsque le degré du polynôme interpolateur augmente.

Les idées suivantes me sont venues à l'esprit:

  • Essayez d'adapter les techniques FFT non uniformes (NFFT)
  • Utilisez FFT pour calculer les dérivées aux nœuds de Chebyshev, potentiellement après avoir d'abord consulté une grille plus fine (Chebyshev). Utilisez ensuite une interpolation cubique par morceaux pour une évaluation (approximative).
  • Utilisez une formule qui utilise uniquement des valeurs de fonction (et potentiellement des dérivés) aux nœuds Chebyshev "proches" (cela est lié à une technique NFFT spécifique).
Thomas Klimpel
la source
Jetez un oeil à chebfun ! C'est toute une bibliothèque qui se base sur des représentations de fonctions au moyen de polynômes de Chebyshev. Il est open source, hautement optimisé et bien entretenu et je suppose que s'il existe un moyen préféré pour l'évaluation ponctuelle d'un polynôme, vous le trouverez là.
Jan

Réponses:

11

Avez-vous pensé à utiliser l' interpolation barycentrique ? Une description détaillée sur la façon de le faire efficacement pour les nœuds Chebyshev est donnée dans la section 5 de ce document.

nmO(nm)

Mise à jour

Une autre alternative, si vous avez les coefficients de Chebyshev de votre polynôme interpolatoire, est d'utiliser l' algorithme de Clenshaw . Si vous n'avez que les valeurs de fonction aux nœuds de Chebyshev, mais devez évaluer le polynôme plusieurs fois, vous pouvez calculer les coefficients avec une FFT.

L'algorithme de Clenshaw est un peu plus rapide que l'interpolation barycentrique car il ne nécessite que des ajouts et des multiplications, et qu'il vectorise également très bien.

Pedro
la source
Actuellement, je le fais en précalculant les poids par rapport aux valeurs de fonction aux nœuds Chebyshev pour un point d'évaluation spécifique, puis j'évalue ce point pour toutes les interpolations que je dois faire (il y en a beaucoup, tous avec des nœuds Chebyshev identiques et des points d'évaluation identiques) , puis passez au point d'évaluation suivant.
Thomas Klimpel
[1,1]±1±1/2