Factorisation des polynômes Préparation agrégation option C

Publié par

Niveau: Supérieur, Bac+8

  • revision


Factorisation des polynômes Préparation agrégation 2006, option C Révision : 4/05/07 Ce texte discute plusieurs méthodes de localisation de racines d'un polynôme P (X) de degré n n'ayant que des racines simples. Si P est à coefficients entiers ou entiers de Gauss, on peut toujours se ramener au cas où P n'a pas de racines multiples (par factorisation “square-free”), on peut aussi décider d'appliquer un algorithme de facto- risation exact (par exemple Berlekamp, Cantor-Zassenhaus) pour si possible diminuer le degré du polynôme dont on cherche les racines. Ce texte est très largement inspiré de discussions avec M. Eisermann 1 La méthode de Newton. La méthode la plus utilisée dans les logiciels est certainement la méthode de New- ton, on cherche une racine r de P , on élimine la racine trouvée en prenant le quotient Q de P par X ? r, on recommence alors avec Q. Cette méthode est simple mais présente plusieurs inconvénients : – si le point de départ de la recherche est éloigné d'une racine, la méthode de Newton n'a pas de raison de converger (en tous cas en un nombre raisonnable d'itérations) – les erreurs d'arrondis se cumulent à chaque élimination de racine On peut remédier à ces inconvénients par exemple en ajoutant un préfacteur dans la formule de Newton un+1 = un ? ? P (un) P ?(un) , ? ?]0, 1] pour le premier, et en effectuant quelques itérations supplémentaires sur les racines approchées

  • méthode

  • polynôme de degré

  • racine

  • rectangle ? du plan complexe

  • polynôme

  • calcul des racines par la méthode de newton avec élimination

  • rectangle ?

  • proche en proche


Publié le : mardi 29 mai 2012
Lecture(s) : 55
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 4
Voir plus Voir moins
Factorisation des polynômes
Préparation agrégation 2006, option C
Révision : 4/05/07
Ce texte discute plusieurs méthodes de localisation de racines d'un polynômeP(X) de degrénn'ayant que des racines simples. SiPest à coefficients entiers ou entiers de Gauss, on peut toujours se ramener au cas oùPn'a pas de racines multiples (par factorisation “square-free”), on peut aussi décider d'app liquer un algorithme de facto-risation exact (par exemple Berlekamp, Cantor-Zassenhaus) pour si possible diminuer le degré du polynôme dont on cherche les racines. Ce texte est très largement inspiré de discussions avec M. Eisermann
1 Laméthode de Newton. La méthode la plus utilisée dans les logiciels est certainement la méthode de New-ton, on cherche une racinerdeP, on élimine la racine trouvée en prenant le quotientQ dePparXr, on recommence alors avecQ. Cette méthode est simple mais présente plusieurs inconvénients : – sile point de départ de la recherche est éloigné d'une racine, la méthode de Newton n'a pas de raison de converger (en tous cas en un nombreraisonnable d'itérations) – leserreurs d'arrondis se cumulent à chaque élimination deracine On peut remédier à ces inconvénients par exemple en ajoutant un préfacteur dans la formule de Newton P(un) un+1=unλ ,λ]0,1] 0 P(un) pour le premier, et en effectuant quelques itérations supplémentaires sur les racines approchées deQavec le polynôme initialP.
2 Parhomotopie On présente dans cette section une autre méthode qui détermine simultanément les racines dePolynôme. L'idée est de construire un chemin de polynômes reliant un p dont les racines sont connues au polynômeP, en suivant les racines le long du chemin. Soit donc : n n Pt=tP+ (1t)(x1), P0=x1, P1=P
1
Pour passer det= 0àt= 1, il faut trouver un chemin dans le plan complexe tel que les racines dePtrestent simples, afin de pouvoir suivre les racines mais aussi pour pouvoir appliquer la méthode de Newton : pour trouver les racines dePtt(Δt <<1) on appliquera quelques itérations de la méthode de Newton en prenant les racines de Ptcomme valeurs initiales. De proche en proche, on arrivera à calculer simultanément toutes les racines deP. SoitRle résultant dePtet de sa dérivée. Comme le but de l'algorithme est de calculer les valeurs approchés de racines d'un polynome, onne peut pas utiliser un algorithme de recherche de racines approchées deRpour savoir quel chemin utiliser pour reliert= 0ett= 1. MaisRest un polynôme à coefficients entiers, on peut donc calculer sa suite de Sturm et localiser les racines réelles deR. SiRn'a pas de racine réelles dans[0,1], alors on peut rester dans l'intervalle[0,1]. Dans le cas contraire (par exemple siR(t= 0)etR(t= 1)ne sont pas de même signe), il faut passer dans le complexe. On peut par exemple utiliser une ligne polygonale[0,1/2(1 +ik)][1/2(1 +ik),1], il existe forcément unkentier tel que la ligne polygonale ne contient pas de racines du résultant. Pour déterminer une valeur dekqui convient, on paramètre chaque segment à l'aide d'un paramètre réel, par exemple pou r le premier segment : u t= (1+ik), u[0,1] 2 puis on remplace dansR, qui devient un polynômeR1(u)à coefficients complexes. Pour savoir s'il a des racines réellesu[0,1], on utilise les suites de Sturm sur le 2 polynôme|R1|(u)qui est à coefficients réels. 4 Exemple : on prend le polynômeP=x5x1, on vérifie facilement que Rne s'annule pas sur[0,1], les racines suivent les chemins représentés sur la figure suivante :
2
3 Lessuites de Sturm complexes Il s'agit ici de généraliser le résultat de localisation de racines réelles d'un po-lynôme à coefficients réels. On compter les racines à l'intérieur d'un rectangleγdu plan complexe et on effectue une dichotomie pour diminuer la taille du rectangle s'il contient des racines, jusqu'à la précision souhaitée. On suppose quePne s'annule pas sur le rectangleγ. Pour compter les racines, on calcule le nombre de tours que faitP(z)autour de 0 lorsquezparcourt le rectangle γou décrémente lorsque. Plus précisément, on calcule un indice que l'on incrémente P(z)traverse l'axe réel (=P(z) = 0) en tenant compte du sens de traversée et du signe de<P(z)lorsque=P(z) = 0: si<P(z)>0et=P(z)croit ou si<P(z)<0 et=P(z)ans le sensdécroit, on augmente l'indice de 1 (car on tourne autour de 0 d trigonométrique), sinon on diminue l'indice de 1. Le nombrede racines dePdansγ est alors égal au nombre de tours autour de 0 c'est-à-dire à l' indice divisé par 2. Calcul de l'indice de manière exacte On utilise une généralisation des suites de Sturm. Sur un segment[a, b]du rectangleγ, on définit : Q(t) =P(a+t(ba)), t[0,1] PosonsS(t) ==Q(t)etR(t) =<Q(t)et supposons queSetRsont premiers entre eux. On forme alors la suite des opposés des restes des divisions euclidiennes comme 0 pour les suites de Sturm réelles avecPetPet on compte le nombre de changements de signes ent= 0ett= 1. On montre que la différence entre ces 2 nombres est égal à la variation de l'indice sur le segment[a, b]: – onvérifie que le nombre de changements de signes ne varie pas lorsquetaug-mente sauf siSs'annule. – SiSs'annule en croissant avecRpositif, alors ce nombre diminue de 1 alors que l'indice augmente de 1, on regarde les 3 autres cas et on concl ut. Pour calculer l'indice surγ, il suffit de sommer les 4 indices sur chaque coté. On divise ensuite par 2 pour obtenir le nombre de racines. Traitement des cas particuliers: – SiSs'annule en un sommet deγ, cela ne pose pas de problèmes, car pour le nombre de changements de signe, tout se passe comme siSétait du signe deR en ce sommet (ce qui revient à déformer un peuγ). Il faut néanmoins s'assurer quePéliminantne s'annule pas sur un sommet de rectangle, ce que l'on fait en les racines rationnelles complexes dePau préalable. – SiSetRne sont pas premiers entre eux. Si leur pgcdGest de degré inférieur strict au degré deP, alors on peut utiliserGpour factoriserPen 2 polynômes de degré strictement plus petit et recommencer avec ces 2 polynômes. Si leur pgcd est de degré maximal, alorsPest à une constante complexecprès un multiple du pgcdGdeRetS, etGest un polynôme à coefficients réels. En multipliantPpar une constante complexe adéquate, on peut supposer que la constantecest réelle. On peut compter les racines dePsur le segment[a, b]par isolation des racines deG. On montre ensuite que sur un segment parallèle à[a, b]situé à l'intérieur 02 au rectangle à distance, on aS(t) =Q(t) +O()etR(t) =Q(t) +O(), le calcul de l'indice sur le segment parallèle à[a, b]infiniment proche est alors
3
0 égal à celui obtenu en prenant la suites de Sturm réelle deQetQentret= 0 ett= 1. Exemple: 3 Nombre de racines complexes dex+ix+ 1dans le rectangle de sommets opposés 0 et1 +i. 3 – Surle segment[0,1],Q(t) =P(t)doncS(t) =tetR(t) =t+ 1. La suite 3 de Sturm est formée det, t+ 1,t,1, en 0 un changement de signe, en 1 1 changement de signe, contribution à l'indice de 0. 3 2 – Sur[1,1 +i], on trouveS(t) =t+ 3t+ 1etR(t) =3tt+ 2. La suite de Sturm est formée deS, R,(20t11)/9,657/400. En 0, un changement de signe, en 1, aussi, indice 0. 2 32 – Sur[1 +i, i],S= 3t7t+ 3,R=t+ 3t2, on trouve que la contribution à l'indice est de 1 3 2 – Sur[i,0],S=t3t+ 3t1,R=t, la suite est doncS, R,1, ent= 0on a un changement de signe et ent= 10 changements de signe, la contribution à l'indice est de 1. On obtient donc un indice de 2, donc 1 racine complexe dans le rectangle. Remarque Pour l'implémentation de cette méthode, on utilise l'algor ithme du sous-résultant pour calculer la suite de Sturm et on conserve la liste des quotients au lieu de la liste des restes, car il est plus efficace d'évaluer un quotient ent= 0ett= 1qu'un reste puisque un quotient de la suite est génériquement de degré 1.
4 Suggestions – Représentationde la variation des racines en fonction detdans la méthode d'ho-motopie. Cas où deux racines se croisent. – Localisationdes racines réelles (suites de Sturm). – Expliquerla méthode des suites de Sturm complexes en complétant certaines esquisses de démonstrations. Illustrer cette méthode. – Quepeut-on dire du point de vue efficacité des algorithmes nécessaire au calcul des suites de Sturm complexe ? (changement d'origineQ(t) =P(a+t(ba)), algorithme d'Euclide, ...) – Connaissez-vousdes méthodes de calculs de racines rationnelles d'un polynôme ? Peuvent-elles se généraliser à la recherche de racines rationnelles complexes ? – Calculdes racines par la méthode de Newton avec élimination (en utilisant uni-quement l'algorithme de Horner), illustration des problèmes évoqués pour cette méthode. Bassins d'attraction des racines pour une suite ré currente définie par la méthode de Newton. – Interactionsentre factorisation exacte et approchée.
4
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.