Analyse

Les polynômes de Tchebychev

Un cosinus déguisé en polynôme, le polynôme qui oscille le moins possible, et la base sur laquelle repose presque tout le calcul numérique des fonctions. On écrit aussi « Tchebycheff », l'ancienne transcription française du nom de Pafnouti Tchebychev (1821-1894).

L'idée en une phrase

Le nombre cos(nθ) ne dépend que de cos θ, et il en dépend polynomialement : cos 2θ = 2cos²θ − 1, cos 3θ = 4cos³θ − 3cos θ, et ainsi de suite. En posant x = cos θ, on obtient un polynôme T_n tel que

T_n(cos θ) = cos(nθ) pour tout θ, c'est-à-dire T_n(x) = cos(n arccos x) sur [−1 ; 1].

Ces polynômes se calculent de proche en proche par la récurrence T₀ = 1, T₁ = x, T_n+1 = 2x T_n − T_n−1, qui vient de la formule cos((n+1)θ) + cos((n−1)θ) = 2 cos θ cos(nθ). Les cinq planches montrent pourquoi cette famille, née chez Tchebychev d'un problème de mécanique (rendre une bielle la plus rectiligne possible), est devenue l'outil de base pour représenter une fonction par un polynôme. Tous les nombres affichés sont calculés dans la page et contrôlés par une seconde méthode indépendante.

Un cosinus déguisé en polynôme

Un point P tourne sur le cercle d'un angle θ ; son ombre sur le diamètre horizontal est x = cos θ. Un second point Q tourne n fois plus vite, d'un angle nθ ; son ombre vaut cos(nθ) = T_n(x). La courbe de droite reporte, pour chaque ombre de P, l'ombre de Q.

Le cercle : P à l'angle θ (bleu), Q à l'angle nθ (rouge, la spirale compte les tours). Les deux ombres sont sur le diamètre.

La courbe y = T_n(x) : le point rouge a pour abscisse l'ombre de P et pour ordonnée l'ombre de Q.

degré n 5

angle θ 40°

x = cos θ (ombre de P)

—

angle de Q : nθ

—

T_n(x) = cos(n arccos x)

—

même valeur par la récurrence 2x T_n − T_n−1

—

écart cosinus / récurrence

—

écart cosinus / forme développée (coefficients entiers, Horner)

—

coefficient dominant 2ⁿ⁻¹

—

Ce qu'il faut voir. L'ombre de Q reste toujours entre −1 et 1 : T_n ne sort jamais de la bande [−1 ; 1] sur [−1 ; 1], alors que son coefficient dominant vaut 2ⁿ⁻¹ (524 288 pour n = 20). Les énormes coefficients se compensent presque parfaitement. La récurrence retrouve le cosinus à l'arrondi près ; la forme développée, elle, perd des chiffres quand n grandit (comparez l'écart orange à n = 5 et à n = 20) : on calcule un polynôme de Tchebychev par la récurrence, jamais par ses coefficients.

Coefficients, racines, extrémums et orthogonalité

Puisque T_n(cos θ) = cos(nθ), tout se lit sur le cercle. Les n racines sont les ombres des angles (2k−1)π/(2n), régulièrement espacés sur le demi-cercle : vues sur le diamètre, elles se serrent près des bords. Les n+1 extrémums, aux ombres des angles kπ/n, valent alternativement +1 et −1. Enfin les T_k sont orthogonaux : l'intégrale de T_k·T_m pondérée par 1/√(1−x²) est nulle dès que k ≠ m.

En gris pâle T₀ à T_n−1, en bleu T_n. Points rouges : racines, obtenues en projetant des points équidistants du demi-cercle (même échelle sur les deux axes). Points violets : extrémums ±1.

Matrice de Gram : case (k, m) = ∫ T_k T_m /√(1−x²) dx, calculée par la quadrature de Gauss-Tchebychev à N nœuds. Bleu : valeur attendue (π ou π/2) ; blanc : zéro ; rouge : écart d'autant plus foncé qu'il est grand.

degré n 6

nœuds de quadrature N 12

—

coefficient dominant (entier exact)

—

somme des coefficients = T_n(1)

—

récurrence contre formule fermée de Tchebychev

—

max |T_n(racine)| (doit être 0)

—

max | |T_n(extrémum)| − 1 |

—

plus grand terme hors diagonale

—

plus grand écart sur la diagonale (π et π/2)

—

diagnostic de la quadrature

—

Ce qu'il faut voir. Avec N ≥ n+1 nœuds, la matrice est diagonale à l'arrondi près : les T_k forment une base orthogonale, comme les cosinus d'une série de Fourier — ce sont d'ailleurs ces cosinus, vus à travers le changement de variable x = cos θ. Baissez N sous n+1 : des cases rouges apparaissent, car le produit T_kT_m devient trop oscillant pour N points (c'est le repliement). Les racines, serrées près de ±1, vont resservir en planche 4.

Le polynôme qui oscille le moins

Parmi tous les polynômes unitaires de degré n (coefficient dominant égal à 1), lequel reste le plus près de zéro sur [−1 ; 1] ? Pas xⁿ, qui monte jusqu'à 1 au bord. La réponse de Tchebychev (1854) est t_n = T_n/2ⁿ⁻¹, dont l'écart maximal vaut seulement 2¹⁻ⁿ. On perturbe ici t_n en lui ajoutant ε·q, où q est un polynôme de degré inférieur tiré au hasard : le résultat p reste unitaire, mais il déborde toujours de la bande.

t_n = 2¹⁻ⁿT_np = t_n + εqxⁿles n+1 sommets de t_nbande ±2¹⁻ⁿ

degré n 5

perturbation ε 0,35

‖t_n‖ mesuré / exact 2¹⁻ⁿ

—

‖xⁿ‖ / ‖t_n‖ (= 2ⁿ⁻¹)

—

‖p‖ / ‖t_n‖ (toujours ≥ 1)

—

sommets de t_n où p sort de la bande

—

2 000 essais : plus petit rapport ‖p‖/‖t_n‖

—

2 000 essais : plus petit nombre de sommets dépassés

—

Pourquoi on ne peut pas faire mieux. Si un polynôme unitaire p restait strictement dans la bande, la différence p − t_n serait négative à chaque sommet haut et positive à chaque sommet bas : elle changerait n fois de signe, donc aurait n racines. Or elle est de degré au plus n−1 (les xⁿ se sont annulés) : elle serait nulle. Le compteur rouge le montre — quelle que soit la direction q et le signe de ε, au moins un sommet est dépassé. Cette équioscillation (n+1 sommets de même hauteur, de signes alternés) est la signature de toute meilleure approximation.

Où placer les points d'interpolation ?

Interpoler, c'est faire passer un polynôme de degré n par n+1 points de la courbe. L'erreur s'écrit f(x) − P(x) = f⁽ⁿ⁺¹⁾(ξ)·ω(x)/(n+1)!, où ω(x) = (x−x₀)…(x−x_n) est le polynôme unitaire des nœuds. D'après la planche 3, ω est le plus petit possible quand les nœuds sont les racines de T_n+1 : alors ω = T_n+1/2ⁿ. Comparez avec des nœuds équidistants, sur l'exemple célèbre de Runge.

fonction finterpolation, nœuds équidistantsinterpolation, nœuds de Tchebychev

erreur max, équidistantserreur max, Tchebychevconstante de Lebesgue, équidistantsconstante de Lebesgue, Tchebychev

fonction

degré n 12

erreur max, nœuds équidistants

—

erreur max, nœuds de Tchebychev

—

constante de Lebesgue Λ, équidistants (mesurée / asymptote 2ⁿ⁺¹/(e n ln n))

—

Λ Tchebychev (mesurée / borne (2/π)ln(n+1) + 1)

—

‖ω‖ équidistants / ‖ω‖ Tchebychev

—

‖ω‖ Tchebychev mesuré contre 2⁻ⁿ

—

contrôle : barycentrique contre série Σc_kT_k (cosinus discrets)

—

Ce qu'il faut voir. Avec des nœuds équidistants, l'interpolation de Runge s'affole aux deux bords et l'erreur augmente avec n ; aux nœuds de Tchebychev, elle diminue régulièrement. La constante de Lebesgue Λ dit pourquoi : c'est le facteur par lequel une petite erreur sur les valeurs (ne serait-ce que l'arrondi de la machine) peut être amplifiée. Elle double presque à chaque degré en équidistant, et ne croît que comme un logarithme chez Tchebychev. Même pour exp(x), fonction parfaitement sage, l'interpolation équidistante touche 2·10⁻¹⁴ vers n = 14, puis se dégrade jusqu'à 6·10⁻¹⁰ à n = 30 : ce sont les arrondis, multipliés par Λ, alors que Tchebychev reste à 3·10⁻¹⁵.

Signature : approcher une fonction avec des T_k

Toute fonction régulière sur [−1 ; 1] se développe en série de Tchebychev f = Σ c_k T_k, avec c_k = (2/π)∫₀^π f(cos θ) cos(kθ) dθ : c'est la série de Fourier de θ ↦ f(cos θ). Trois volets : ce que la décroissance des coefficients révèle de la fonction, pourquoi tronquer cette série donne presque la meilleure approximation possible, et une application en électronique où l'équioscillation devient un objet physique.

La vitesse à laquelle les c_k tendent vers zéro dépend de la distance aux singularités complexes de f. Si f est analytique à l'intérieur de l'ellipse de foyers ±1 dont la somme des demi-axes vaut ρ (ellipse de Bernstein), alors |c_k| décroît comme ρ^−k. Pour 1/(1+a²x²), les pôles ±i/a fixent ρ = (1+√(1+a²))/a.

log₁₀|c_k| en fonction de k (points bleus). Ligne rouge : pente théorique −log₁₀ ρ. Grisé : niveau de l'arrondi machine.

Plan complexe : l'intervalle [−1 ; 1] en bleu, des ellipses de Bernstein en gris, en rouge la plus grande ellipse sans singularité et les pôles.

fonction

paramètre a 5,0

ρ théorique

—

ρ mesuré (pente des coefficients)

—

écart des c_k à la formule exacte

—

termes nécessaires pour |c_k| < 10⁻¹⁵

—

erreur max de la série tronquée à ce rang

—

Ce qu'il faut voir. Pour a = 5 (la fonction de Runge), la pente mesurée redonne ρ ≈ 1,2198 : les pôles ±0,2 i, invisibles sur l'axe réel, dictent le nombre de termes. Faites glisser a : quand les pôles s'approchent de l'intervalle, l'ellipse s'aplatit et il faut des centaines de termes. Pour exp(x), sans aucune singularité, la décroissance est plus rapide que toute exponentielle (c_k = 2I_k(1), fonction de Bessel). Pour |x|, la pointe en 0 est sur l'intervalle même : ρ = 1, et les coefficients ne décroissent plus qu'en 1/k².

La meilleure approximation p* de degré n (celle qui minimise l'écart maximal) est caractérisée par l'équioscillation : son erreur atteint n+2 fois la même hauteur ±E_n avec des signes alternés (théorème de Tchebychev). L'algorithme de Remez la construit en échangeant des points jusqu'à ce que l'erreur soit parfaitement nivelée. On la compare à deux approximations presque gratuites : la série tronquée S_n et l'interpolation aux nœuds de Tchebychev I_n.

erreur de la meilleure approximation (Remez)erreur de la série tronquée S_nerreur de l'interpolation I_npoints d'équioscillation

fonction

degré n 4

meilleure erreur E_n (Remez)

—

‖f − S_n‖ et rapport à E_n

—

‖f − I_n‖ et rapport à E_n

—

points d'équioscillation (attendu : au moins n+2)

—

nivellement : (max|e| − |E|)/|E| après Remez

—

borne théorique ‖f−I_n‖ ≤ (1+Λ_n)E_n

—

Ce qu'il faut voir. La courbe bleue touche au moins n+2 fois sa bande, de signes alternés : c'est l'équioscillation de la planche 3, à l'œuvre sur n'importe quelle fonction. Les courbes orange et violette ne sont pas parfaitement nivelées, mais leur erreur ne dépasse la meilleure possible que d'un petit facteur : de 1,04 à 1,3 pour exp(x), jamais plus de 3 dans les cas proposés ici, et toujours sous la borne 1 + Λ. Voilà pourquoi les bibliothèques de calcul — et les logiciels comme Chebfun — se contentent de tronquer ou d'interpoler aux nœuds de Tchebychev : on obtient presque l'optimum sans le chercher.

Un filtre passe-bas électronique doit laisser passer les fréquences ω < 1 et couper les autres. Le filtre de Tchebychev a pour gain |H(ω)|² = 1/(1 + ε²T_n(ω)²). Dans la bande passante, T_n oscille entre −1 et 1 : le gain ondule entre 1 et 1/(1+ε²), avec exactement l'équioscillation de la planche 3. Au-delà de ω = 1, T_n(ω) = ch(n argch ω) croît comme 2ⁿ⁻¹ωⁿ : la coupure est bien plus raide que celle du filtre de Butterworth 1/(1 + ε²ω²ⁿ), qui a la même atténuation en ω = 1 mais aucune ondulation.

Gain en décibels de 0 à 3. Bleu : Tchebychev ; orange : Butterworth de même ordre ; trait rouge : la fréquence ω_s où l'on veut couper.

Loupe sur la bande passante : l'ondulation équioscillante, entre 0 dB et −r dB.

ordre n 4

ondulation r 1,0 dB

ω_s 1,50

ε = √(10^r/10 − 1)

—

ondulation mesurée sur la courbe (max − min dans [0 ; 1])

—

atténuation en ω_s : Tchebychev

—

atténuation en ω_s : Butterworth

—

ordre Butterworth nécessaire pour faire aussi bien

—

T_n(ω_s) : ch(n argch ω) contre récurrence

—

Ce qu'il faut voir. Pour un même ordre — donc le même nombre de bobines et de condensateurs — Tchebychev coupe beaucoup plus fort, et l'avantage tend vers 6,02(n−1) dB loin de la bande, la trace du coefficient dominant 2ⁿ⁻¹. Le prix à payer est l'ondulation dans la bande passante. C'est la propriété minimax de la planche 3, transportée dans un circuit : parmi les gains polynomiaux qui restent dans la tolérance sur [0 ; 1], T_n est celui qui monte le plus vite ensuite.

Repères historiques

1854Tchebychev publie la Théorie des mécanismes connus sous le nom de parallélogrammes : pour rendre le mouvement d'un parallélogramme de Watt le plus rectiligne possible, il cherche le polynôme qui s'écarte le moins de zéro. Les polynômes qui portent son nom y apparaissent.
1859Il généralise dans Sur les questions de minima qui se rattachent à la représentation approximative des fonctions : naissance de la théorie de la meilleure approximation uniforme et de l'équioscillation.
1901Carl Runge montre que l'interpolation en points équidistants de 1/(1+25x²) diverge près des bords quand le degré augmente.
1912Serge Bernstein relie la vitesse de la meilleure approximation à l'analyticité de la fonction dans les ellipses de foyers ±1.
1914Georg Faber prouve qu'aucun choix de nœuds ne fait converger l'interpolation pour toutes les fonctions continues : les nœuds de Tchebychev sont presque optimaux, pas miraculeux.
1934Evgueni Remez publie l'algorithme d'échange qui calcule la meilleure approximation polynomiale.
1938Cornelius Lanczos fait des séries de Tchebychev un outil de calcul pratique (économisation des séries, méthode tau).
1955Charles Clenshaw donne la récurrence qui évalue une somme Σc_kT_k de façon stable, toujours utilisée dans les bibliothèques numériques.
2004Zachary Battles et Lloyd N. Trefethen présentent Chebfun : calculer avec des fonctions comme avec des nombres, en les représentant par leurs interpolants de Tchebychev.

En résumé

Un cosinus déguisé

T_n(cos θ) = cos(nθ). Tout en découle : la récurrence, les bornes ±1, les racines serrées aux bords, l'orthogonalité héritée de celle des cosinus.

Le moins oscillant

Parmi les polynômes unitaires de degré n, T_n/2ⁿ⁻¹ s'écarte le moins de zéro, de 2¹⁻ⁿ seulement. L'équioscillation qui le caractérise caractérise aussi toute meilleure approximation.

La base de l'approximation

Nœuds de Tchebychev pour interpoler, séries de Tchebychev pour développer : on obtient presque la meilleure approximation sans la chercher, avec un nombre de termes fixé par les singularités complexes de la fonction.

Pour aller plus loin

Seconde espèce. Les polynômes U_n définis par U_n(cos θ) = sin((n+1)θ)/sin θ vérifient la même récurrence avec U₁ = 2x, et T_n′ = n U_n−1. Ils sont orthogonaux pour le poids √(1−x²).

Équation différentielle. T_n est solution de (1−x²)y″ − x y′ + n²y = 0, qui n'est autre que y″ + n²y = 0 écrite dans la variable x = cos θ.

Quadrature. Intégrer l'interpolant aux points de Tchebychev donne la règle de Clenshaw-Curtis, presque aussi précise que Gauss et beaucoup plus simple à mettre en œuvre ; la quadrature de Gauss-Tchebychev de la planche 2 est exacte pour les polynômes de degré au plus 2N−1, pondérés par 1/√(1−x²).

Composition. T_m(T_n(x)) = T_mn(x), puisque cos(m·nθ) = cos(mnθ). Hors de [−1 ; 1], T_n(x) = ch(n argch x) : c'est le polynôme qui croît le plus vite parmi ceux qui restent bornés par 1 sur l'intervalle — l'idée exploitée par le filtre de la planche 5 et par l'accélération de Tchebychev des méthodes itératives.

Lectures. L. N. Trefethen, Approximation Theory and Approximation Practice (SIAM, 2013 ; édition augmentée 2019) ; T. J. Rivlin, Chebyshev Polynomials (Wiley, 2ᵉ éd. 1990) ; J. C. Mason et D. C. Handscomb, Chebyshev Polynomials (CRC, 2003).

L'idée en une phrase

Un cosinus déguisé en polynôme

Coefficients, racines, extrémums et orthogonalité

Le polynôme qui oscille le moins

Où placer les points d'interpolation ?

Signature : approcher une fonction avec des Tk

Repères historiques

En résumé

Un cosinus déguisé

Le moins oscillant

La base de l'approximation

Signature : approcher une fonction avec des T_k