Mathematiques assistees par ordinateur Chapitre Arithmetique des polynomes

De
Publié par

Mathematiques assistees par ordinateur Chapitre 3 : Arithmetique des polynomes Michael Eisermann Mat249, DLST L2S4, Annee 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours _ mao Document mis a jour le 6 juillet 2009 1/55

  • arithmetique des polynomes

  • mathematiques assistees par ordinateur chapitre

  • localisation des racines complexes

  • unique corps de cardinal pk

  • decomposition des polynomes et des fractions rationnelles

  • corps


Publié le : mardi 19 juin 2012
Lecture(s) : 41
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 55
Voir plus Voir moins
Math´ematiquesassist´eesparordinateur Chapitre3:Arithme´tiquedespolynˆomes
Michael Eisermann
Mat249, DLST L2S4, Anne´ e 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours # mao Document mis a` jour le 6 juillet 2009
1/55
Objectifs de ce chapitre
Nousallonsdiscuteretapprofondirlarithm´etiquedespolynˆomessur un corps, notamment a` coefficients rationnels, re´ els, complexes.
Afin de proce´ der syste´ matiquement et efficacement, nous introduisons d’abord le vocabulaire ade´ quat (corps et anneaux).
Ensuite on e´ tablira quelques outils fondamentaux, notamment la division euclidienne :S=P Q+Rou`degR <degP, l’algorithme d’Euclide pour calculerpgcd(A, B), l’algorithme d’Euclide-Be´ zout :pgcd(A, B) =AU+BV.
Les applications sont nombreuses ! D´mpositiondespolynˆomesetdesfractionsrationnelles. eco Localisationdesracinesr´eellesdunpolynoˆmere´el(Sturm). Localisation des racines complexes d’un polynoˆ me complexe.
/255
Sommaire
1
2
3
Arithm´etiquedespolynˆomessuruncorps,Euclide,Be´zout Polynomes sur un corps ˆ La division euclidienne Les algorithmes d’Euclide et de Be´ zout
´ Evaluation,racines,de´compositionenfacteursirr´eductibles Fonctionspolynomiales,m´ethodedeHorner,HornerTaylor Multiplicit´eduneracine,r´eductionauxracinessimples D´ecompositiondepolynˆomesenfacteursirre´ductibles
Fractionsrationnelles,e´l´ementssimples,int´egrationsymbolique Le corps des fractions rationnelles D´ecompositiondunefractionenfractionssimples Primitive d’une fraction rationnelle
/355
§1.
Corps Les nombres rationnels(Q,+,), les nombres re´ els(R,+,), et les nombres complexes(C,+,)´iusetn:juosisentdespropri´et es s va
1
(A1 : associativite´ ) (A2:commutativit´e) (A3:´ele´mentneutre) (A4 : e´ le´ ment oppose) ´
(M1 : associativite´ ) (M2 : commutativite´ ) (M3:´el´entneutre) em (M4:´ele´mentinverse)
(D:distributivit´e)
D´enition(corps)
Uncorps(K,+,)es
a, b, c: (a+b) +c=a+ (b+
a, b, c: (a+b) +c=a+ (b+c) a, b:a+b=b+a 0a +: 0a=a ab:a+b= 0
a, b, c: (ab)c=a(bc) a, b:ab=ba 16= 0a: 1a=a a6= 0b:ab= 1
a, b, c:a(b+c) = (ab) + (ac)
Uncorps(K,+,)est un ensembleKmuni de deux ope´ rations, appele´ es addition+ :K×KKet multiplication:K×KK, verifiant tous les axiomes (A1-4), (M1-4), (D) ci-dessus. ´
/455
Corps finis Outre les corpsQ,R,Cil existe beaucoup d’autres exemples ! Sur l’ensembleF2={0,1}ueclohxiauqusn:da`ntmennsox´eu´eel + 0 10 1 0 0 1et0 0 0. 1 1 0 1 0 1 Proposition(lecorpsadeux´el´ements) ` (F2,+,)est un corps. De´ monstration.ine´vreseesixmoLesa.sacselsutontra´eumenn´te Alternative : Si l’on interprete0et1comme«vrai»et«faux»alors la ` multiplicationest la conjonction«et»tandis que l’addition+est la disjonction«ou exclusif»usSottce.vasu´dzerofeovemblilaej`a´eta v´eracit´edesaxiomeslorsdevotreintroductiona`lalogique. Alternative:OnpeutreconnaˆıtreF2comme le quotientZ/2Z. Remarque Lescorpsnissontfortementutilise´senal`ebreetencryptographie. g Tout corps fini est de cardinalpkpour un premierpne,tuqmeiproR´ec. §1.1pour tout premierpetk1il existe un unique corps de cardinalpk.5/55
Les quatre ope´ rations dans un corps Onabr`egeabparab. Au lieu dea+ (bc)on´ecritaussia+bc. Les´ele´ments0et1ainsi que les applicationsa7→ −aeta7→a1 ne figurent pas explicitement dans(K,+,) :, ils s’en de´ duisent L´ele´mentneutredeladditionestunique:si0 +a=aet00+a=a pour toutaK, alors00= 0 + 00= 00+ 0 = 0. 0 Pour toutaKl’oppose´ est unique : Sia+b= 0eta+b= 0alors b += 0b=b+ 0 =b+ (a+b0) = (b+a) +b0= (a+b) +b0= 0 +b0=b0. Onnoteradoncsansambigu¨ıt´eloppose´deapara. Demeˆmele´l´ementneutre1de la multiplication est unique. ´ Pour toutaK\ {0}l’inverse est unique, et sera note para1. On aab= 0ssia= 0oub= 0: sia6= 0alorsb=a1ab= 0. §1.1 6/55
§.1
Anneaux
1
Les entiers(Z,+,)ne forment pas un corps mais un anneau :
De´ finition (anneau)
Unanneau(A,+,)est un ensemble muni de deux ope´ rations dont onexigelesaxiomesci-dessus`alexceptiondeM4(e´l´ementinverse).
Ici tout anneau sera donc suppos ´e commutatif (M2) et unitaire (M3).
D´enition(e´le´mentsinversibles)
SoitaA. On dit quebAest uninversedeasiab= 1. 1 Dans ce cas l’inverse dea parest unique et sera note´a. On appelleaAinversibles’il admet un inverse dansA.
DansZe´emtnisvnreislbmple,lesseuls´elap,exerntsoes1et1. L´ele´ment0n’est jamais inversible : on a toujours0b= 06= 1. Un anneauAtsnue´el´toutsssicorptnemeaA,a6= 0est inversible.
On noteA=A\ {0}lesnmel´ementsbledes´ennon,slu etA×Atsinemenibleverssdsnalesedl´´enseblemA.
/755
§.1
Polynoˆmes
1
SoitKun corps (par exempleQ,R,C).
Unpolynoˆ mesurKest une expression formelle
P=p0+p1X1+p2X2+∙ ∙ ∙+pnXnoup0, p1, p2, . . . , pnK. `
IciXnemeedtunonl´´eleeltn(ebaelofmruenavirnestquK). De meˆ me,Pn’est qu’une expression formelle (et non une fonction).
Ce qui compte est la suite des coefficients dansK:
n n XakXk=XbkXk⇐⇒ak=bkpour toutk= 0, . . . , n k=0k=0
On peut rajouter ou supprimer des termes nuls,0Xn+1. AinsiP=Pmk=0pkXken prolongeant parpn+1=∙ ∙ ∙=pm= 0, voireP=Pk=0pkXken prolongeant parpk= 0pour toutk > n.
Pour l’imple´ mentation il suffit de stocker les coefficients non nuls. Typiquement on stocke la suite(p0, p1, p2, . . . , pn)telle quepn6= 0.
8/55
§.1
L’anneau des polynomes ˆ On note parK[X] sur l’anneaul’ensemble des polynoˆ mesK. On de´ finit l’addition terme par terme : n n XakXk+XbkXk:=X(ak+bk)Xk k=0k=0k=0
1n
Pour obtenirXiXj=Xi+jon de´ finit la multiplication par m n m+n XaiXiXbjXj:=X  XaibjXk i=0j=0k=0i+j=k
Cesd´enitionssetraduisentdirectementenalgorithmedecalcul.
Proposition(lanneaudespolynˆomessurK)
L’ensembleK[X] sur mesdes polynoˆKmuni de l’addition+ et de la multiplication ci-dessus est un anneau.de´ finies
On remarque queaX0+bX0= (a+b)X0etaX0bX0= (ab)X0. Ainsi on obtientKK[X]en identifiantaKavecaX0K[X].
/955
§.1
L’anneau des polynomes : ve´ rification des axiomes ˆ Pourprouverleth´eor`emeilfautve´rierlesaxiomesunparun.
1
Lassociativit´ede(K[X],+)decellede´ecouled(K,+): PakXk+PbkXk+PckXk=P(ak+bk)Xk+PckXk=P[(ak+bk) +ck]Xk=P[ak+ (bk+ck)]Xk =PakXk+P(bk+ck)Xk=PakXk+PbkXk+PckXk
La commutativit ´e de(K[X],+) de celle dede´ coule(K,+): PakXk+PbkXk=P(ak+bk)Xk =P(bk+ak)Xk=PbkXk+PakXk
L´ele´mentneutrede(K[X],+)est le polynoˆ me nul : P0Xk+PakXk=P(0 +ak)Xk=PakXk. Le´l´ementoppose´dePakXkestP(ak)Xk: PakXk+P(ak)Xk=P(ak+ (ak))Xk=P0Xk.
10/55
§1.
L’anneau des polynomes : verification des axiomes ˆ ´ Lassociativit´ede(K[X],)repose sur celle de(K,): hXaiXiXbjXjiXckXki j k =XXhaibjXsiXckXk=XX(aibj)ckXt s i+j= is k t+j+k=t =XXai(bjck)Xt=XaiXihXXbjckXsi t i+j+k=t i s j+k=s =XaiXiXhbjXjXckXki i j k
1
La commutativit ´e de(K[X],)repose sur de celle de(K,): XaiXiXbjXj=XXaibjXs i j s i+j=s =XXbjaiXs=XbjXjXaiXis j+i=s j i
L’e´ le´ ment neutre est1X0ltsee´tivitubirtisad.L.enexercicaiss´eee
115/5
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.