Factorisation des polynômes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, la factorisation d'un polynôme consiste à écrire celui-ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d'écrire le polynôme initial en produit de plusieurs polynômes non inversibles. Un polynôme non inversible pour lequel aucune factorisation de ce type n'existe s'appelle un polynôme irréductible.

La décomposition d'un polynôme en produits de polynômes irréductibles existe, et a une propriété d'unicité (à un facteur inversible près), pour tout polynôme à coefficients réels ou complexes. Ceci est encore vrai lorsque les coefficients sont dans un anneau factoriel, que le polynôme soit à une ou plusieurs indéterminées. Cette propriété est, pour l'ensemble des polynômes, analogue au théorème fondamental de l'arithmétique pour l'ensemble des entiers.

La recherche d'une factorisation est un problème algorithmique de difficulté variable suivant, en premier lieu, l'anneau de coefficients considéré, et en second lieu, la taille de ces coefficients et le degré du polynôme.

La factorisation d'un polynôme est utile pour réduire une fonction rationnelle en éléments simples.

Polynômes à coefficients réels ou complexes[modifier | modifier le code]

Polynômes à coefficients réels[modifier | modifier le code]

Méthodes élémentaires[modifier | modifier le code]

Les identités remarquables et la propriété de distributivité de la multiplication sur l'addition fournissent des méthodes élémentaires de factorisation de polynômes

Exemples

  • 3x^2+9 = 3(x^2+3)
  • 4x^2-8x=4x(x-2)
  • x^2+2ax+a^2=(x+a)^2
  • x^2-b^2=(x-b)(x+b)
  • \forall n \ge 1,\, x^n - r^n=(x-r)(x^{n-1}+rx^{n-2}+ \cdots r^kx^{n-1-k}+\cdots+ r^{n-1})

La première des factorisations ne décompose pas le polynôme en produit de polynômes de degré moindre. Cependant, elle offre l'avantage de présenter un polynôme dont le coefficient du terme de plus haut degré est 1. De tels polynômes sont dits unitaires et sont utilisés dans les décompositions pour garantir l'unicité de celles-ci.

La dernière factorisation offre un moyen de prouver que tout polynôme P possédant r comme racine peut s'écrire

P(x)=(x-r)Q(x)

où Q est de degré inférieur au degré de P.

Cependant, en pratique, quand une racine r est connue, la factorisation précédente se calcule plutôt en utilisant une division de polynôme ou la méthode de Horner.

Polynômes irréductibles[modifier | modifier le code]

Les polynômes irréductibles dans \R sont les polynômes qui ne peuvent pas se décomposer en produit de deux polynômes de degrés supérieurs ou égaux à un. En particulier, les polynômes de degré 1 sont donc irréductibles.

Un polynôme de degré 2 qui pourrait s'écrire comme produit de polynômes de degré 1 possèderait des racines réelles. Par contraposée, un polynôme de degré 2 ne possédant pas de racine réelle est irréductible. C'est le cas de tous les polynômes de degré 2 dont le discriminant est négatif (voir l'article Équation du second degré).

On démontre que les seuls polynômes à coefficient réels irréductibles sont de ce type (polynômes de degré 1 ou polynome de degré 2 dont le discriminant est négatif). Ce résultat est une conséquence du théorème de d'Alembert-Gauss, qui porte sur les polynômes à coefficients complexes.

Ainsi le polynôme

P(x)=x^4+4

qui ne semble pas factorisable de manière simple et ne possède pas de racine n'est pas irréductible (en fait, il est factorisable grâce à l'identité de Sophie Germain).

P(x)=x^4+4x^2+4 - 4x^2 = (x^2+2)^2 - (2x)^2 = (x^2-2x+2)(x^2+2x+2)

Ce même théorème de D'alembert Gauss permet aussi de prouver que tout polynôme P à coefficients réels possède une décomposition unique (à l'ordre près) de la forme suivante:

P(x) = a_n(x-r_1)^{\alpha_1}\cdots (x-r_k)^{\alpha_k} = a_n \prod_{i=1}^k p_i(x)^{\alpha_i}

où les p_i sont des polynômes irréductibles unitaire (le coefficient du terme de plus haut degré est 1) de degré 2.

Racines et factorisation[modifier | modifier le code]

Le lien existant entre les racines d'un polynôme et sa factorisation justifie les études portant sur ses racines. Les recherches s'orientent dans deux directions : recherche de racines exactes éventuellement par incursion dans les complexes et recherche de racines approchées.

La première voie a conduit à l'étude des coefficients des polynômes, qui d'après le théorème de Viète, s'expriment comme polynômes symétriques des racines. Cette voie de recherche, fructueuse sur les polynômes de degré 3 et 4, et sur certains polynômes de degré supérieur a laissé croire qu'il serait possible de déterminer toutes les racines d'un polynôme en utilisant seulement des opérations de somme, produit, quotient et extraction de racine nième, quitte à passer par les complexes. Si les racines d'un polynôme s'écrivent effectivement ainsi, on dit qu'il est résoluble par radicaux. Dans le courant du XIXe siècle, Niels Henrik Abel démontre que les équations polynomiales de degré supérieur ou égal à 5 ne sont pas toutes résolubles par radicaux (théorème d'Abel). Une classification des équations résolubles par radicaux est donnée par la théorie de Galois.

La seconde voie est la recherche de racines approchées de polynômes. Ce sont les algorithmes de recherche d'un zéro d'une fonction dont un des classiques est la méthode de Newton. Ces méthodes nécessitent de déterminer combien de racines se trouvent dans un intervalle donné. Descartes par sa règle des signes permet de déterminer le nombre de changements de signe d'un polynôme en observant seulement le signe de ses coefficients et par la même le nombre de racines. Le théorème de Sturm permet de déterminer le nombre de racines dans un intervalle donné d'un polynôme ne comportant que des racines simples. Il permet aussi de séparer les racines dans des intervalles distincts.

Polynômes à coefficients complexes[modifier | modifier le code]

Comme il est indiqué dans la section précédente, la recherche des polynômes irréductibles à coefficients réels et la factorisation des polynômes nécessite une incursion dans les complexes où les factorisations ont une présentation simple.

Dans l'ensemble des complexes les seuls polynômes irréductibles sont les polynômes de degré 1 et tout polynôme P complexe de degré n se décompose de manière unique sous la forme suivante :

P(x)= a_n\prod_{i=1}^k (x-r_i)^{\alpha_i}

avec \sum_{i=1}^k \alpha_i = n

La racine r_i est dite d'ordre \alpha_i.

Mais les mêmes difficultés persistent sur la mise en place effective d'une factorisation.

Exemples[modifier | modifier le code]

Considérons le polynôme X^4-1 \, à coefficients dans \ \R ou \mathbb{C}.

  • L'identité remarquable a^2-b^2 = (a+b)(a-b) \, donne :
X^4-1=(X^2+1)(X^2-1) \,
puis :
\ X^4-1=(X^2+1)(X-1)(X+1).
Ceci est la factorisation en produit de facteurs irréductibles à coefficients dans \ \R.

Ainsi,on a le signe de X^4-1 \, en fonction de X (réel, bien entendu) :

X < -1 ou X > 1 ⇒ P(X) > 0

-1 < X < 1 ⇒ P(X) < 0


  • La factorisation en produit de facteurs irréductibles à coefficients dans \mathbb{C} est :
\ X^4-1 = (X+i)(X-i)(X-1)(X+1).

Plus généralement, on sait factoriser dans \mathbb C puis dans \R, tout polynôme P de la forme X^n -a où a > 0. Si on note

b=\sqrt[n]a

les racines de P sont :

r_k=be^{i2k\pi/n}

et P a pour décomposition dans \mathbb C:

P(X)= \prod_{k=0}^{n-1}(X-be^{i2k\pi/n})

La décomposition dans \R consiste à regrouper les racines conjuguées. La décomposition est différente selon que n est pair ou impair.

Polynômes à coefficients dans un anneau[modifier | modifier le code]

Lorsque les coefficients ne sont pas réels ou complexes, les polynômes irréductibles peuvent être de degré supérieur à 2 et l'existence d'une factorisation en produit de polynômes irréductible n'est pas garantie.

Polynômes irréductibles[modifier | modifier le code]

On appelle polynôme irréductible tout polynôme P non inversible dont les seuls diviseurs sont les polynômes inversibles et les polynômes associés à P. En d'autres termes

P est irréductible ssi \forall (Q,R) \in A[X]^2 \quad P=QR \Rightarrow exactement l'un des deux facteurs Q ou R est inversible.

Même sur un anneau intègre,

  • un polynôme de degré 0 ou 1 n'est pas nécessairement irréductible. Par exemple dans \Z[X], 6=2\times 3 et 6X=2\times(3X).
  • un polynôme irréductible de degré (supérieur ou) égal à 2 n'a pas de racine, mais un polynôme de degré 2 sans racine n'est pas nécessairement irréductible. Par exemple dans \Z[X], 2X^2+2=2\times(X^2+1).

Des polynômes réductibles sur \R peuvent se révéler irréductibles sur \mathbb Q : X^2-2 est réductible dans \R[X] mais irréductible dans \Q[X] .

Le lemme de Gauss permet d'affirmer que tout polynôme non constant et irréductible dans \Z[X] l'est aussi dans \mathbb Q[X].

Le critère d'Eisenstein fournit une condition suffisante pour qu'un polynôme de \Z[X] soit irréductible : il suffit de trouver un nombre premier divisant tous les coefficients de P sauf le coefficient de terme de plus haut degré et tel que p^2 ne divise pas le terme constant. Ainsi

X^4-9X^3+3X^2-6X+15 est irréductible dans \Z[X] car 3 divise tous les coefficients sauf celui du terme de degré 4 et 9 ne divise pas 15.

Factorisation[modifier | modifier le code]

Article détaillé : Anneau factoriel.

Si A est un anneau intègre dont tous les éléments possèdent une décomposition en facteurs irréductibles unique à un inversible près, c'est-à-dire si A est un anneau factoriel alors tout polynôme de A[X] possède aussi une décomposition unique en produit de polynômes irréductibles à un inversible près.

Un corps étant un exemple d'anneau factoriel, tout polynôme non constant de  \mathbb K[X] possède une décomposition unique sous forme de produit de polynômes unitaires irréductibles multiplié par une constante.

Polynômes en plusieurs indéterminées[modifier | modifier le code]

Si A est un anneau factoriel, A[X] est factoriel, puis A[X][Y] = A[X,Y] est aussi factoriel et il en est de même de A[X_1,X_2,\cdots,X_n]. Un polynôme à n indéterminées sur un anneau factoriel est donc toujours décomposable de manière unique (à un inversible près) en produits de polynômes irréductibles.

Algorithmes de décomposition[modifier | modifier le code]

Suivant la nature de l'anneau des coefficients considéré, les algorithmes de factorisation des polynômes en produits d'irréductibles sont de difficulté variable.

Dans le cas de coefficients réels ou complexes, l'obtention d'une factorisation exacte avec des coefficients en écriture décimale est en général impossible, puisque l'écriture d'une racine requiert une infinité de décimales. Cependant de nombreux algorithmes, dont le plus célèbre est la méthode de Newton, permettent d'obtenir des approximations aussi bonnes que souhaitées. Un tel algorithme itératif, sous de bonnes conditions de départ, peut doubler (voire mieux) le nombre de décimales obtenues à chaque itération. Des conditions de départ acceptables peuvent être obtenues en utilisant au préalable des algorithmes de séparation des racines. Le cas des racines multiples, ou extrêmement rapprochées, nécessite des considérations particulières.

Dans le cas des polynômes à coefficients dans les corps finis, pour un polynôme fixé, il n'existe qu'un nombre fini de diviseurs potentiels, les polynômes de degré inférieur. Un algorithme naïf consiste donc à factoriser un polynôme en testant sa divisibilité par les polynômes de degré inférieur, de manière analogue à l'algorithme naïf de division des entiers. Toutefois, des algorithmes bien plus efficaces existent. Ils ont été découverts entre la fin des années 1960 et le début des années 1980, et sont de complexité polynomiale, déterministe ou probabiliste, par exemple l'algorithme de Berlekamp, ou celui de Cantor-Zassenhaus.

De la factorisation des polynômes à coefficients dans les corps finis se déduisent des algorithmes de factorisation dans d'autres domaines. D'abord pour les polynômes dont les coefficients sont des nombres p-adiques, avec la restriction, comme dans le cas des coefficients réels et complexes, qu'on ne peut obtenir en temps fini qu'un nombre fini de terme d'un développement p-adique (les facteurs irréductibles peuvent être de tout degré, et pas seulement de degré 1 ou 2 comme dans les cas réels et complexes). Ceci peut se faire grâce à une version algorithmique du lemme de Hensel. Ensuite, pour les polynômes à coefficients rationnels, ou dans des corps de nombres. Le passage d'une factorisation dans le domaine des coefficients p-adiques à une factorisation à coefficients rationnels est possible car la deuxième s'obtient en regroupant convenablement les facteurs de la première. Il est possible soit de tester toutes ces combinaisons, ce qui peut être de complexité algorithmique exponentielle, soit de ramener ce problème à un problème algorithmique d'algèbre linéaire de type sac à dos. Ces algorithmes progressent encore au début des années 2000 (voir algorithme de van Hoeij).

Enfin, parvenir à la factorisation des polynômes à coefficients entiers est équivalent algorithmiquement à parvenir conjointement à factoriser les entiers et les polynômes à coefficients rationnels.

Articles connexes[modifier | modifier le code]