Les polynômes
Une suite finie de nombres, et pourtant une fonction, une courbe, des racines. Avec les polynômes, on calcule comme avec les entiers : on additionne, on multiplie, on divise avec un reste, on cherche un PGCD, on factorise. Cinq planches pour voir que tout ce que l'on sait sur les nombres entiers se retrouve chez eux, puis jusqu'où leurs racines sont fragiles.
Vue d'ensemble : qu'est-ce qu'un polynôme ?
Un polynôme à une indéterminée X est une expression de la forme
P = anXn + an−1Xn−1 + … + a1X + a0
Les nombres a0, …, an sont ses coefficients. Ils sont pris dans un ensemble de nombres où l'on sait additionner et multiplier : les rationnels ℚ, les réels ℝ, les complexes ℂ, ou même un corps fini 𝔽p, les entiers modulo un nombre premier p. Le plus grand n tel que an ≠ 0 est le degré de P, et an son coefficient dominant. L'ensemble des polynômes à coefficients dans un corps K se note K[X].
La lettre X n'est pas un nombre inconnu : c'est un simple marqueur de position. Un polynôme est sa liste de coefficients. On peut ensuite y remplacer X par un nombre, et l'on obtient une fonction. C'est le double visage du polynôme, au cœur de la première planche.
| Entiers ℤ | Polynômes K[X] | Planche |
|---|---|---|
| écriture en base 10 | liste des coefficients | 1 |
| division euclidienne, reste < diviseur | division euclidienne, degré du reste < degré du diviseur | 2 |
| diviseurs, nombres premiers | racines, polynômes irréductibles | 3 et 4 |
| PGCD par l'algorithme d'Euclide, identité de Bézout | le même algorithme, la même identité | 4 |
| décomposition en facteurs premiers | factorisation en irréductibles, qui dépend du corps | 4 |
Deux visages : une liste de nombres et une fonction
Comment passer des coefficients à la courbe, et comment multiplie-t-on deux polynômes sans jamais tracer de courbe ?
La méthode de Horner range le calcul autrement : P(x) = (((a₄x + a₃)x + a₂)x + a₁)x + a₀. Il ne faut plus que n multiplications au lieu de n(n+1)/2, et c'est exactement ainsi que les calculatrices évaluent les polynômes.
Un polynôme n'est pas toujours sa fonction
Sur ℝ, deux polynômes qui prennent les mêmes valeurs partout ont les mêmes coefficients. Sur un corps fini, ce n'est plus vrai : le polynôme Xp − X n'est pas nul, et pourtant il s'annule en chaque élément de 𝔽p (petit théorème de Fermat).
La division euclidienne
Peut-on diviser un polynôme par un autre comme on divise 47 par 5 = 9 reste 2 ? Oui, et le reste est « plus petit » que le diviseur au sens du degré.
A = B·Q + R avec deg R < deg B
Pour tout A et tout B non nul, le quotient Q et le reste R existent et sont uniques. On les obtient en éliminant à chaque étape le terme de plus haut degré : on le divise par le terme dominant de B, on retranche, et l'on recommence tant que le degré reste trop grand. Les calculs ci-dessous sont faits en fractions exactes.
Diviser par X − a : la méthode de Horner, encore
Quand le diviseur est X − a, le reste est un nombre, et ce nombre vaut A(a). Le tableau de Horner donne d'un seul coup les coefficients du quotient (ligne du bas) et le reste (dernière case).
Racines, multiplicité et factorisation
Combien de racines a un polynôme ? Où sont-elles quand la courbe ne coupe pas l'axe ? Et que disent les coefficients des racines ?
Le théorème de d'Alembert-Gauss affirme que tout polynôme de degré n ≥ 1 à coefficients complexes a exactement n racines dans ℂ, à condition de compter chacune avec sa multiplicité. Il se factorise alors entièrement : P = an(X − z1)(X − z2)…(X − zn). Si les coefficients sont réels, les racines non réelles vont par paires conjuguées, symétriques par rapport à l'axe réel.
Ici, on fait l'inverse du calcul habituel : déplacez les racines à la souris dans le plan complexe (à gauche), et le polynôme se reconstruit (à droite). Une racine réelle glisse sur l'axe ; une paire conjuguée se déplace d'un bloc, et en touchant l'axe elle devient une racine double.
Les deux lectures vertes sont les relations de Viète (1591) : sans connaître les racines, les coefficients donnent déjà leur somme et leur produit. La lecture rouge fait le trajet retour : partant des seuls coefficients, l'algorithme de Durand-Kerner (Weierstrass, 1891) retrouve les racines numériquement, et l'on mesure l'écart avec celles que vous avez placées.
PGCD, Bézout et polynômes irréductibles
Les polynômes ont-ils leurs « nombres premiers » ? Oui : les polynômes irréductibles. Mais qui est irréductible dépend du corps où l'on travaille.
L'algorithme d'Euclide, tel quel
Comme pour les entiers, le PGCD de A et B s'obtient par divisions successives : on divise A par B, puis B par le reste, et ainsi de suite ; le dernier reste non nul, rendu unitaire (coefficient dominant 1), est le PGCD. En remontant les calculs, on obtient l'identité de Bézout : deux polynômes U et V tels que AU + BV = PGCD(A, B). Les racines communes de A et B sont exactement les racines du PGCD.
Le deuxième couple montre une application classique : PGCD(P, P′) révèle les racines multiples. Ici P = (X − 1)³(X + 2), et le PGCD vaut (X − 1)², ce qui signale une racine de multiplicité 3 sans l'avoir cherchée.
Compter les irréductibles sur 𝔽p
Un polynôme est irréductible s'il n'est pas le produit de deux polynômes de degré au moins 1. Sur un corps fini 𝔽p, il n'y a que pn polynômes unitaires de degré n : on peut tous les fabriquer, rayer tous les produits, et compter ce qui reste. C'est le crible d'Ératosthène pour les polynômes. Gauss avait trouvé la formule exacte du résultat :
Np(n) = 1⁄n Σd | n μ(d) pn/d ≈ pn/n
Ici μ est la fonction de Möbius : μ(d) vaut 0 si d est divisible par un carré, et sinon (−1)k, où k est le nombre de facteurs premiers de d.
Environ un polynôme unitaire de degré n sur n est irréductible : c'est l'analogue exact du théorème des nombres premiers, où environ un entier sur ln N est premier autour de N, et n joue ici le rôle de ln N.
X⁴ + 1 : irréductible sur ℚ, réductible partout ailleurs
Sur ℚ, X⁴ + 1 est irréductible : il n'a pas de racine rationnelle (ni 1 ni −1 ne conviennent), et aucun produit de deux facteurs du second degré à coefficients entiers ne le donne. Sur ℝ, il se factorise : X⁴ + 1 = (X² + √2 X + 1)(X² − √2 X + 1). Sur ℂ, il a quatre racines eiπ/4, e3iπ/4, e5iπ/4, e7iπ/4. Et modulo chaque nombre premier p, on le factorise par recherche exhaustive :
Signature : la fragilité des racines
Les coefficients déterminent les racines. Mais à quel point ? Une infime retouche d'un coefficient peut-elle déplacer les racines de beaucoup ?
En 1959, James H. Wilkinson teste un programme de recherche de racines sur un polynôme qui semble inoffensif : celui dont les racines sont 1, 2, 3, …, 20.
W(X) = (X − 1)(X − 2)…(X − 20) = X20 − 210 X19 + … + 20!
Il remplace le coefficient −210 par −210 − 2−23, soit une retouche d'environ 6·10−8 % du coefficient. Les racines 10 à 19 quittent l'axe réel et deviennent complexes ; l'une d'elles se retrouve à 16,73 ± 2,81 i. Wilkinson racontera plus tard que ce fut l'expérience la plus traumatisante de sa carrière d'analyste numérique. On refait ici son calcul pour W − ε Xn−1, en évaluant le polynôme sous forme de produit pour ne perdre aucune précision.
La sensibilité se calcule. Si l'on perturbe W en W − εXn−1, la racine k se déplace, au premier ordre, de
δk ≈ ε · κk avec κk = kn−1 / |W′(k)| = kn−1 / ((k − 1)! (n − k)!)
Pour n = 20, la racine la plus sensible est k = 16 : le numérateur vaut 1619 ≈ 7,6·1022, le dénominateur 15!·4! ≈ 3,1·1013, et l'amplification atteint κ16 ≈ 2,4·109. Avec ε = 2−23, la prévision du premier ordre annonce un déplacement de près de 290 : elle n'a plus de sens, mais elle dit bien que la racine ne peut pas rester en place. Pour ε très petit, la prévision et la mesure coïncident ; dès que ε·κk devient comparable à l'écart entre deux racines voisines, le premier ordre ne suffit plus, deux racines se heurtent et partent dans le plan complexe.
Prenons maintenant tous les polynômes de degré n dont les coefficients valent +1 ou −1, appelés polynômes de Littlewood. Comme P et −P ont les mêmes racines, on fixe le coefficient dominant à +1 : il en reste 2n. On calcule toutes leurs racines (méthode d'Aberth) et on les reporte dans le plan complexe.
Une brève histoire
En résumé
Calculer
Un polynôme est une liste de coefficients. On l'additionne, on le multiplie (convolution des coefficients) et on le divise avec un reste de degré plus petit, exactement comme les entiers.
Factoriser
Racine a ⇔ facteur X − a. Sur ℂ, tout se factorise en degré 1 ; sur ℝ, en degrés 1 et 2 ; sur ℚ et sur 𝔽p, il existe des irréductibles de tout degré, environ un sur n.
Se méfier
Les racines dépendent continûment des coefficients, mais parfois avec une amplification gigantesque. Les racines multiples et les grands degrés sont les cas dangereux.
Pour aller plus loin
Structure. K[X] est un anneau euclidien, donc principal : tout idéal est formé des multiples d'un seul polynôme. C'est ce qui fait marcher Bézout et l'unicité de la factorisation en irréductibles. Avec deux indéterminées ou plus, K[X, Y] n'est plus principal, et l'on entre dans l'algèbre commutative et la géométrie algébrique (VIII.9).
Corps de rupture. Quotienter K[X] par un polynôme irréductible donne un nouveau corps où ce polynôme a une racine : ℝ[X]/(X² + 1) = ℂ, et 𝔽p[X]/(P) est le corps fini à pn éléments. C'est la construction utilisée dans la page sur les structures algébriques.
Résolubilité. La question « peut-on exprimer les racines par des radicaux ? » mène de Lagrange (VIII.4 et VIII.5) à la théorie de Galois.
Approximation. Les polynômes approchent toute fonction continue sur un segment (théorème de Weierstrass). Les meilleures approximations s'obtiennent avec les polynômes de Tchebychev ; l'interpolation aux points équidistants peut au contraire diverger (phénomène de Runge).
Calcul des racines en pratique. Les logiciels construisent la matrice compagnon du polynôme et calculent ses valeurs propres par l'algorithme QR ; les méthodes d'Aberth et de Durand-Kerner servent pour les grands degrés et en précision multiple.