Licence de Mathématiques L3 Algèbre effective

Description

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

Informations

• Publié par: vehot
• Nombre de lectures: 35
• Langue: Français

Extrait

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. Le p2)=(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 sell lccae stre e quha er z suav(uolu é fone lain dbeso erétnémie  dnima erèqinu? eu m eLoins qu'on puiss eidere tsq eul itorlg'aEud'e hmen edilcap dner e cos unnte nstael! ispm  rimP   uo a,c(ro=pr:cdpg>  .sèrp )sellun noes ntantconsles ri e à  d  e'ts sc( ; nd gc p ) x) efi(mer,b,adcgp,b(r a else b=0 then b(;) i  f )b p irtn cgp eL no ued ed d sttes le tiluSo s.eroce  tec zmmnen  pctio  ) rint tnemni ssrevelbiitduar pes llé éédetmrni éuap orx polynômes est  xb gp ,ma,)(errdb, c() 0pro,a0bcdit slenehtfibtnirp)gc)pa(b0f1 indee  dodb≠;0ihelodne)rem,,ab;; := r( a,,; ;; rbl  =: laco =  :0wbb:=; a0 a b:=b=a0; hile 0; 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 ; 01 14 1315 02625527 0277 18 8 x 8956318552844763 000985 4 4 9 3483968 93981389 09 38950081 x 3 1268 980580 x 1 6 4 17562071615021 38 56 0095 0181 83 21 0059 2 x 18 x795x35 2 x96 3 x64 4 9x 5 5##−7 ); ## 1,p2 3 722549802 18005938 08610633 # 5 ##−#  drpco eL =:b ar ne r := ab x()print dcgpp(ti,1p(,)2p p : >drgc tes s st 4539350844584267 99 2 # 8 x 68 7701233541740101793715961 852 6016 80089213 024235084539426744858 8 68 662685289860691914574879905425 7676292420 000985 9 4 62864899 18348 #x 182132678 7195081478186109 6792 13 67 60491554 3 1 1 x 5455 62872831 6017 1 11179383960 2869384345527026 31598754 2 x#− 2 − 69 14707718462871458649290759667198 5480625 x# 1260042 15308810450987877336178596460045 48176301 71578041 9255820279411703818767065922273737734694 5260 952 − 8707488580384915409656013776430587517851 71696 140 30322815195309463327515309598187884908165458 x 2 2 − 7163583117199488 0913695988535 4924423674144936 43332744 1275 20 \754206185629237525610354840381072 2048316618901473 991129 \176346373

0 − 533066108 # 208945227 4 # 671650209 3 # 1268181012 2 # 6171215056 38950081 38950081 x 38950081 x 38950081 x 38950081 x − 8 1 2 4 0 5 7 5 7 2 1 7 3 0 5 2 8 6 9 2 8 8 6 6 51 9 3 3 1 8 5 4 0 3 1 # 998318939634784524 3 15554839706937106111 2 4850900876231281 x − 14552702628693843 x 29613957845994886629 # 4850900876231281 x 8438161097818081471955145069431 # 82 7 6 6 6 7 6 6 2 2 8 9 8 2 5 4 8 2 9 0 0 8 6 0 9 5 6 3 9 9 1 3 4 5 1 4 7 7 5 6 8 2 4 4 9 8 7 5 9 4 0 46 5 8 4 8 25 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 1 2( − ncc(1 ) 2 # ncc(1 ) # 2 ncc(0 ) 2 − 3 ncc(0 ))   2 − 1   = − tcoeffs  :  4 2 − 1

  − 1 − 1 # 3     1  n  2 ncc(1) 4 ncc(1)2ncc(0) # 4 ncc(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;