Fast Semi-numerical Algorithms for Chebyshev Series
Algorithmique semi-numérique rapide des séries de Tchebychev
Résumé
A Chebyshev series is an expansion in the basis of Chebyshev polynomials of the first kind. These series are important in approximation theory. Unlike Taylor series, their algorithmic aspects are not very developed in computer algebra. This thesis proposes new algorithms for these series. A first part gives fast algorithms that convert a truncated Chebyshev series into a truncated Taylor series and vice versa, and others that multiply or divide two truncated Chebyshev series. The rest of the thesis is devoted to Chebyshev series that are solutions of a linear differential equation with polynomial coefficients. In this class, the coefficients of series are solutions of a linear recurrence. This thesis show how to compute this recurrence efficiently, then how to use it for the efficient computation of approximated coefficients despite numerical instabilities. These algorithms lead to an efficient computation of the approximation by polynomials of fixed degree on a segment for solutions of linear differential equations. Finally, the computation of recurrences for the coefficients of series is generalized to the case of generalized Fourier series. The document is illustrated by examples using implementations developed during this thesis.
Une série de Tchebychev est un développement dans la base des polynômes de Tchebychev. Ces séries sont importantes en théorie de l'approximation. Contrairement aux séries de Taylor, l'algorithmique en calcul formel autour d'elles n'est pas très développée. Cette thèse propose de nouveaux algorithmes pour ces séries. Une première partie présente des algorithmes rapides pour convertir une série de Tchebychev tronquée en une série de Taylor tronquée et réciproquement, et pour multiplier ou diviser deux séries de Tchebychev tronquées. Le reste de la thèse porte sur les séries de Tchebychev solutions d'une équation différentielle linéaire à coefficients polynomiaux. Dans cette classe, les coefficients des séries sont solutions d'une récurrence linéaire. Cette thèse montre comment calculer cette récurrence efficacement, puis comment l'utiliser pour obtenir un calcul approché efficace des coefficients malgré des instabilités numériques. Ces algorithmes mènent au calcul efficace d'une approximation sur un segment par un polynôme de degré fixé d'une fonction solution d'une équation différentielle linéaire. Enfin, le calcul des récurrences pour les coefficients de séries est généralisé au cas des séries de Fourier généralisées. L'ensemble est illustré d'exemples à partir de programmes développés durant cette thèse.