La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Licence de Mathématiques L3 Algèbre effective

18 pages
Niveau: Supérieur, Licence, Bac+3
Licence de Mathématiques 2008-2009 L3 Algèbre effective td 5 : Pgcd de polynômes à une variable Calcul du pgcd et relation de Bézout de polynômes à une variable On va constater que le calcul du pgcd et de la relation de Bézout en utilisant le même algorithme d'Euclide que sur les entiers pose sur les polynômes à une variable des problèmes de croissance des coefficients. Exercice 1 : Ecrire deux fonctions, une récursive et une itérative, qui prennent en entrée deux polynômes a et b en la variable x et rendent le pgcd de a et b , vous aurez besoin de la fonction rem . Tester sur les polynômes suivants : > p1:=x^8+randpoly(x);p2:=randpoly(x); := p1 ? ? ? ? + +x8 85 x5 55 x4 37 x3 35 x2 97 x 50 := p2 + + + + ?79 x5 56 x4 49 x3 63 x2 57 x 59 Vous pouvez consulter l'aide sur randpoly pour savoir ce que fait cette fonction et quelles sont ses options. Solution La récursive : > pgcdr:=proc(a,b) if b=0 then a else pgcdr(b,rem(a,b,x)) fi end; := pgcdr proc( ) end proc,a b if then else end if=b 0 a ( )pgcdr ,b ( )rem , ,a b x L'itérative : > pgcdit:=proc(a0,b0) local a,b,r; a:=a0;b:=b0; while

  • coefficients entiers

  • variable des problèmes de croissance des coefficients

  • polynômes intervenant dans le calcul

  • calcul du pgcd et de la relation de bézout

  • relation de bézout de polynômes

  • pgcd

  • entiers pose sur les polynômes


Voir plus Voir moins
Licence de Mathématiques 2008-2009 L3 Algèbre effective
td 5 : Pgcd de polynômes à une variable
Calcul du pgcd et relation de Bézout de polynômes à une variable
On va constater que le calcul du pgcd et de la relation de Bézout en utilisant le même algorithme d'Euclide que sur les entiers pose sur les polynômes à une variable des problèmes de croissance des coefficients. Exercice 1 : Ecrire deux fonctions, une récursive et une itérative, qui prennent en entrée deux polynômes a   et b  en la variable x  et rendent le pgcd de a  et b , vous aurez besoin de la fonction rem  . Tester sur les polynômes suivants : > p1:=x^8+randpoly(x);p2:=randpoly(x); p1 := x 8 85 x 5 55 x 4 37 x 3 35 x 2 # 97 x # 50 p2 := 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x 59 Vous pouvez consulter l'aide sur randpoly  pour savoir ce que fait cette fonction et quelles sont ses options. Solution La récursive : > pgcdr:=proc(a,b) if b=0 then a else pgcdr(b,rem(a,b,x)) fi end; pgcdr := proc ( a , b ) if b 1 0 then a else pgcdr( b , rem( a , b , x )) end if end proc L'itérative : > pgcdit:=proc(a0,b0) local a,b,r; a:=a0;b:=b0; while b<>0 do r:=rem(a,b,x);a:=b;b:=r od; a end; pgcdit := proc ( a0 , b0 ) local a , b , r ; a := a0 ; b := b0 ; while b 0 do r := rem( a , b , x ); a := b ; b := r end do ; a end proc Les tests : > pgcdr(p1,p2),pgcdit(p1,p2); 1260042946870926695891770141877284645717314901866314820373643671\ 921199375 26292618554200127048353846501147436492449364257217\ 02333444729598853509136, 1260042946870926695891770141877284645717\ 314901866314820373643671921199375 26292618554200127048353846\ 50114743649244936425721702333444729598853509136 Exercice 2 : Ce que les tests nous apprennent est que le pgcd de p1 et p2 est une constante, p1 et
eue  ox,s ertrenp tnimerp os 21.Lep2)=(p1,pgcdri etid ruar nop dilt-ess menôlyop xued ed dcgp dnerc er xuepmocas p, seque sei v sof noomidifzeour qu'ections pc tnehciffa selllccae stree quhaer z suav(uolu é fone lain dbesoerétnémie  dnima erèqinu? eum eLoins qu'on puiss eidere tsq eul itorlg'aEud'e hmen edilcap dner e cos unnte nstael! ispm rimP uoa,c(ro=pr:cdpg> .sèrp )sellun noes ntantconsles ri eà d e'ts sc(; ndgc p) x) efi(mer,b,adcgp,b(r a else b=0 thenb(;)i  f)bp irtncgp eLnoued ed dsttes letiluSos.eroce  tec zmmnen  pctio  ) rinttnemni ssrevelbiitduar pes llé éédetmrni éuap orx polynômes est xbgp,ma,)(errdb,c() 0pro,a0bcditslenehtfibtnirp)gc)pa(b0f1 indee dodb;0ihelodne)rem,,ab;; := r(a,,;;;rbl =:laco=  :0wbb:=; a0 ab:=b=a0;hile0; w 0odb ><er(mr =:ro=pt:di0),ba0c(a lacol :a;r,b,end; := pgcdrpro(ce)dnp or,cba(;b,a,;px)ntri);(rb=:a=:b;do r a ;01141315026255270277188x89563185528447630009854493483968939813890938950081x31268980580x16417562071615021385600950181832100592x18x795x352x963x6449x55##7);##1,p237225498021800593808610633#5### drpcoeL=:b arner := ab x()printdcgpp(ti,1p(,)2p p:>drgctes s st4539350844584267992#8x6877012335417401017937159618526016800892130242350845394267448588686626852898606919145748799054257676292420000985946286489918348#x18213267871950814781861096792136760491554311x54556287283160171111793839602869384345527026315987542x#269147077184628714586492907596671985480625x#12600421530881045098787733617859646004548176301715780419255820279411703818767065922273737734694526095287074885803849154096560137764305875178517169614030322815195309463327515309598187884908165458x2271635831171994880913695988535492442367414493643332744127520\7542061856292375256103548403810722048316618901473991129\176346373
0 533066108 # 208945227 4 # 671650209 3 # 1268181012 2 # 6171215056 38950081 38950081 x 38950081 x 38950081 x 38950081 x 812405757217305286928866519331854031 # 998318939634784524 3 15554839706937106111 2 4850900876231281 x 14552702628693843 x 29613957845994886629 # 4850900876231281 x 8438161097818081471955145069431 # 827666766228982548290086095639913451477568244987594046584825 x 2 76762924208053935476248544688 9935230177101014475169977360161 8529213800894881719583171632 x 24585806188948781590953512733649035915182230371696 14087517851736734500469651038801549078785480625 259377349647660187872739522820292551703794110367184 # 14087517851736734500469651038801549078785480625 x 1260042946870926695891770141877284645717314901866314820373643671\ 921199375 26292618554200127048353846501147436492449364257217\ 02333444729598853509136 0 1260042946870926695891770141877284645717314901866314820373643671\ 921199375 26292618554200127048353846501147436492449364257217\ 02333444729598853509136, 1260042946870926695891770141877284645717\ 314901866314820373643671921199375 26292618554200127048353846\ 50114743649244936425721702333444729598853509136 Exercice 3 : Constatez que le dénominateur qui apparaît dans le premier reste est le coefficient d monôme de tête du premier diviseur à la puissance 4, le nombre d'étapes de cette première division. Avez-vous une explication ? On voudrait éviter l'apparition de fractions : les calculs avec des fractions sont plus coûteux que les calculs sur les entiers (pourquoi ?). Montrez qu'on peut multiplier les polynômes intervenant dans le calcul par des constantes non nulles et que l'algorithme calcule toujours un pgcd des polynômes de départ. A chaque étape de l'algorithme d'Euclide, à chaque division, étant donné un dividende et un diviseur à coefficients entiers on va multiplier le dividende par une puissance suffisante du coefficient du monôme de tête du diviseur pour que le reste soit à coefficients entiers. Donnez u formule pour ce coefficient multiplicateur. Adaptez vos fonctions en ce sens (vous aurez besoin des fonctions coeff  ou lcoeff  et degree ) et refaites les tests. Solution En effet : > 38950081,79^4;
38950081, 38950081 A chaque étape de la division on est obligé de diviser une fois de plus par le coefficient du monôme de tête du diviseur. Les additions de fractions sont très couteuses. Remarquons que les diviseurs et donc le pgcd sont déterminés à multiplication par les inversibles près. Sur les entiers les seuls inversibles sont 1 et -1, cela n'introduit pas beaucoup d'ambiguïté (seulement le signe), mais sur les polynômes les inversibles sont to les constantes non nulles. Donc si c 1  et c 2  sont deux constantes non nulles on a pgcd( p 1 , p 2 ) 1 pgcd( c 1 p 1 , c 2 p 2 ) . L'idée de l'algorithme d'Euclide est que, lorsqu'on fait une division euclidienne p i 1 1 q i p i # p i # 1  , on a pgcd( p i 1 , p i ) 1 pgcd( p i , p i # 1 ) . On peut donc, lors du calcul de la suite de polynômes, multiplier les p   i  par des constantes non nulles sans changer le fait qu'on calcule un pgcd( p 1 , p 2 ) . Pour éviter l'apparition de fractions on doit donc multiplier à chaque étape de l'algorithme d'Euclide le polynôme p   i 1  par le coefficient du monôme de tête de p  i  à la puissance le nombre d'étapes de cette division, soit degré( p i 1 ) degré( p i ) # 1 . > pgcdr:=proc(a,b) local c; print(b); if b=0 then a else c:=lcoeff(b)^(degree(a)-degree(b)+1);pgcdr(b,rem(c*a,b,x)) fi end; pgcdit:=proc(a0,b0) local a,b,c,r; a:=a0;b:=b0; while b<>0 do c:=lcoeff(b)^(degree(a)-degree(b)+1);r:=rem(c*a,b,x);print (r);a:=b;b:=r od; a end; pgcdr := proc ( a , b ) local c ; print( b ); if b 1 0 then a else c := lcoeff( b )^(degree( a ) degree( b ) # 1 ); pgcdr( b , rem( c a , b , x )) end if end proc pgcdit : proc ( a0 , b0 ) = local a , b , c , r ; a := a0 ; b := b0 ; while b 0 do c := lcoeff( b )^(degree( a ) degree( b ) # 1); r := rem( c a , b , x ); print( r );
a : b ; = b := r end do ; a end proc On teste : > pgcdr(p1,p2),pgcdit(p1,p2); 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x 59 533066108 # 208945227 x 4 # 671650209 x 3 # 1268181012 x 2 # 6171215056 x 24623140769595394503 # 8984870456713060716 x 3 46664519120811318333 x 2 # 266525620613953979661 x 345643430604587005776711159465103004648120793357 # 338617137692040776678138789926351134228554822475 x 2 3662696530921461537491041001800459430736501666003 x 873640487941381493973742732262631981768420462387411080727808110\ 4064136145526658251118315506531968355622339225146736 # 9216803897\ 5667625153279314356482095346736541974696345633891930369420904928\ 851740689117776970521380337177367763963344 x 1280100909945756289090922652563656629790506369950115194210381349\ 4916746913603194694690435195913394786265453956866043919627221477\ 9674588479374335953323894856109627570958628543495126775078435343\ 8942133051167219833406930442387126883094911335892771607413701787\ 6953638170278374240000 0 533066108 # 208945227 x 4 # 671650209 x 3 # 1268181012 x 2 # 6171215056 x 24623140769595394503 # 8984870456713060716 x 3 46664519120811318333 x 2 # 266525620613953979661 x 345643430604587005776711159465103004648120793357 # 338617137692040776678138789926351134228554822475 x 2 3662696530921461537491041001800459430736501666003 x 873640487941381493973742732262631981768420462387411080727808110\ 4064136145526658251118315506531968355622339225146736 # 9216803897\ 5667625153279314356482095346736541974696345633891930369420904928\ 851740689117776970521380337177367763963344 x 1280100909945756289090922652563656629790506369950115194210381349\ 4916746913603194694690435195913394786265453956866043919627221477\ 9674588479374335953323894856109627570958628543495126775078435343\ 8942133051167219833406930442387126883094911335892771607413701787\ 6953638170278374240000
0 1280100909945756289090922652563656629790506369950115194210381349\ 4916746913603194694690435195913394786265453956866043919627221477\ 9674588479374335953323894856109627570958628543495126775078435343\ 8942133051167219833406930442387126883094911335892771607413701787\ 6953638170278374240000, 12801009099457562890909226525636566297905\ 0636995011519421038134949167469136031946946904351959133947862654\ 5395686604391962722147796745884793743359533238948561096275709586\ 2854349512677507843534389421330511672198334069304423871268830949\ 113358927716074137017876953638170278374240000 Exercice 4 : Les coefficients restent entiers mais ils deviennent très grands ! Il existe des variantes plus compliquées de l'algorithme d'Euclide qui conservent des coefficients entiers tout en évitant leur croissance rapide : on peut par exemple extraire le pgcd des coefficients, c'est ce qui donnera les plus petits coefficients entiers, mais ce calcul est coûteux. Remarquez expérimentalement sur plusieurs exemples que le coefficient par lequel on multiplie le dividende à une étape divise tous les coefficients du reste de l'étape suivante. On peut donc faire cette division systématiquement. Adaptez vos fonctions pour qu'elles fassent cette simplification. Solution On peut considérer que le nombre de chiffres des coefficients double à chaque étape ! Même s'il vaut mieux travailler avec de grands entiers qu'avec de grandes fractions, cette croissance rend cet algorithme rapidement impraticable. Faisons les expériences suggérées : > (-24623140769595394503+8984870456713060716*x^3-46664519120 811318333*x^2+266525620613953979661*x)/79^4; 632171747463 # 230676553836 x 3 1198059616893 x 2 # 6842748815181 x On constate que le deuxième reste calculé peut-être divisé par 4 79sans qu'apparaisse de fraction. > (345643430604587005776711159465103004648120793357+33861713 7692040776678138789926351134228554822475*x^2-3662696530921 461537491041001800459430736501666003*x)/208945227^2; 7917050173280190161861239550133 # 7756111157533558271705266738275 x 2 83894990146587445785565162225707 x Le troisième reste calculé peut-être divisé par 2089452 2  7 sans qu'apparaisse de fraction, lequel 208945227 est le coefficient de tête du premier reste calculé et admet un facteur premier qui n'est pas petit : > ifactor(208945227); (3 ) (69648409 ) Ca ne peut pas être un hasard, mais la démonstration n'est pas simple. Adaptons nos fonctions. On remarque que pour utiliser que, quand on calcule c i 1 p i 1 1 q i p i # p i # 1  et c i p i 1 q i # 1 p i # 1 # p i # 2  , alors c i 1  divise les coefficients de p i # 2  il faut disposer simultanément de c i 1 et de c i . Pour la version itérative il faut utiliser deux variables qu'on décale en fin de boucle, pour la version récursive il faut transmettre le c i  
courant à l'appel qui calcule la division suivante. > pgcdr:=proc(a,b,c0) local c1; print(b); if b=0 then a else c1:=lcoeff(b)^(degree(a)-degree(b)+1);pgcdr(b,rem(c1*a,b,x )/c0,c1) fi end; pgcdit:=proc(a0,b0) local a,b,c0,c1,r; a:=a0;b:=b0;c0:=1; while b<>0 do   c1:=lcoeff(b)^(degree(a)-degree(b)+1);r:=rem(c1*a,b,x)/c0; print(r);a:=b;b:=r;c0:=c1 od; a end; pgcdr : proc ( a , b , c0 ) = local c1 ; print( b ); if b 1 0 then a else c1 := lcoeff( b )^(degree( a ) degree( b ) # 1 ); pgcdr( b , rem( c1 a , b , x ) c0 , c1 ) end if end proc pgcdit := proc ( a0 , b0 ) local a , b , c0 , c1 , r ; a := a0 ; b := b0 ;  c0 := 1;  while b 0 do c1 := lcoeff( b )^(degree( a ) degree( b ) # 1); r := rem( c1 a , b , x ) c0 ; print( r ); a := b ; b := r ; c0 := c1   end do ; a end proc > pgcdr(p1,p2,1),pgcdit(p1,p2); 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x 59 533066108 # 208945227 x 4 # 671650209 x 3 # 1268181012 x 2 # 6171215056 x 632171747463 # 230676553836 x 3 1198059616893 x 2 # 6842748815181 x
5218511764998453 # 5112429053794275 x 2 55299257112450987 x 960846910507712859551 # 10136821349248954986229 x 89443929025125340905692351 0 2 533066108 # 208945227 x 4 # 671650209 x 3 # 1268181012 x # 6171215056 x 632171747463 # 230676553836 x 3 1198059616893 x 2 # 6842748815181 x 5218511764998453 # 5112429053794275 x 2 55299257112450987 x 960846910507712859551 # 10136821349248954986229 x 89443929025125340905692351 0 89443929025125340905692351, 89443929025125340905692351 C'est quand même beaucoup mieux. Exercice 5 : Estimez la loi de croissance des coefficients dans l'exercice 3 et dans l'exercice 4. Solution On commence par faire une étude expérimentale sur les coefficients de tête des polynômes > evalf(208945227); 0.208945227 10 9 > evalf(8984870456713060716); 0.8984870457 10 19 > evalf(338617137692040776678138789926351134228554822475); 0.3386171377 10 48 > evalf(9216803897566762515327931435648209534673654197469634 5633891930369420904928851740689117776970521380337177367763 963344); 0.9216803898 10 116 > evalf(1280100909945756289090922652563656629790506369950115 1942103813494916746913603194694690435195913394786265453956 8660439196272214779674588479374335953323894856109627570958 6285434951267750784353438942133051167219833406930442387126 8830949113358927716074137017876953638170278374240000); 0.1280100910 10 278 On a l'impression que la taille de ce coefficient est à chaque étape 2 à 3 fois la taille du coefficient de l'étape précédente. Essayons de comprendre cette constatation : une étape courante de l'algorithme, autre que la première, consiste à diviser un polynôme de degré d   p ar un polynôme de degré d   1 . Pour que le reste ait des coefficients entiers on est donc amené à multiplier le dividende par le coefficient de tête du diviseur au carré. Posons ncc n ( )le nombre de chiffres des coefficients à l'étape n  , on a la relation de récurrence ncc( n # 1 ) 1 2 ncc( n ) # ncc( n 1 ) . Que vaut cette suite récurrente ? > tcoeffs:=rsolve(ncc(n+1)=2*ncc(n)+ncc(n-1),ncc(n)); 1 n 12( ncc(1 ) 2 # ncc(1 ) # 2 ncc(0 ) 2 3 ncc(0 )) 2 1 = tcoeffs  : 4 2 1
1 1 # 3 1 n 2ncc(1)4ncc(1)2ncc(0) # 4ncc(0)2 2 # 1 # 2 # 1 Ca n'est pas très lisible et on ne s'intéresse qu'à la croissance de cette suite pas à sa valeur exacte : > asympt(tcoeffs,n,1); 1 O n ( 2 1 ) > evalf(1/(sqrt(2)-1)); 2.414213565 Ce qui confirme l'expérience : le nombre de chiffres des coefficients à l'étape n  est en 2.4 n   ou encore la valeur des coefficients à l'étape n  est en 10 (2.4 n )  ! Recommençons l'étude expérimentale sur les coefficients de tête des polynômes de l'exercice 4 : > evalf(208945227); 0.208945227 10 9 > evalf(230676553836); 0.2306765538 10 12 > evalf(5112429053794275); 0.5112429054 10 16 > evalf(10136821349248954986229); 0.1013682135 10 23 > evalf(89443929025125340905692351); 0.8944392903 10 26 On a l'impression que la croissance du nombre de chiffres est à peu près linéaire. Essayons à nouveau de comprendre : à chaque étape on multiplie le dividende par le coefficient de tête du diviseur au carré mais on divise le reste par le coefficient de tête du diviseur au carré de l'étape précédente. Pour le nombre de chiffres des coefficients à l'étape n  , on a donc la relation de récurrence ncc( n # 1 ) 1 2 ncc( n ) # ncc( n 1 ) 2 ncc( n 1 ) . > tcoeffs:=rsolve(ncc(n+1)=2*ncc(n)+ncc(n-1)-2*ncc(n-1),ncc( n)); tcoeffs := ( ncc(0 ) # ncc(1 )) ( n # 1 ) ncc(1 ) # 2 ncc(0 ) > asympt(tcoeffs,n,1); ( ncc(0 ) # ncc(1 )) n # ncc(0 ) La croissance du nombre de chiffres est effectivement linéaire.
Exercice 6 : Recommencez le travail pour le calcul des coefficients de Bézout : algorithme naïf puis on évite l'apparition de fractions, puis on évite l'apparition de fractions et on contrôle la croissance des coefficients. Solution Euclide de base : > Bezoutr:=proc(a,b) Bezoutraux(a,1,0,b,0,1) end;