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 Exercice 2 : Ce que les tests nous apprennent est que le pgcd de p1 et p2 est une constante, p1 et p2 sont premiers entre eux, on pourrait dire pgcd(p1,p2)=1. Le pgcd de deux polynômes est-il déterminé de manière unique ? Le moins qu'on puisse dire est que l'algorithme d'Euclide ne rend pas une constante simple ! Pour mieux comprendre ce qui se passe, modifiez vos fonctions pour qu'elles affichent chaque reste calculé (vous aurez besoin de

• coefficients entiers


• variable des problèmes de croissance des coefficients


• polynômes intervenant dans le calcul


• relation de bézout de polynômes


• pgcd


• entiers pose sur les polynômes

Informations

• Publié par: vehot
• Nombre de lectures: 44
• 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

Exercice 2 : Ce que les tests nous apprennent est que le pgcd de p1 et p2 est une constante, p1 et

p2 sont premiers entre eux, on pourrait dire pgcd(p1,p2)=1.

Le pgcd de deux polynômes est-il déterminé de manière unique ?

Le moins qu’on puisse dire est que l’algorithme d’Euclide ne rend pas une constante simple !

Pour mieux comprendre ce qui se passe, modifiez vos fonctions pour qu’elles affichent chaque

reste calculé (vous aurez besoin de la fonction

print

)

et recommencez les tests.

Solution

Exercice 3 : Constatez que le dénominateur qui apparaît dans le premier reste est le coefficient du

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 un

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 toute

les constantes non nulles. Donc si

c

1

et

c

2

sont deux constantes non nulles on a

=

(

)

pgcd

,

p

1

p

2

(

)

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

+

q

i

p

i

p

+

i

1

, on a

=

(

)

pgcd

,

p

-

i

1

p

i

(

)

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

,

a b

proc

(

)

:=

local

;

c

( )

print

b

;

=

b

0

a

if

then

;

:=

c

^

( )

lcoeff

b

(

)

-

+

( )

degree

a

( )

degree

b

1

(

)

pgcdr

,

b

(

)

rem

,

,

*

c a b x

else

end if

end proc

pgcdit

,

a0 b0

proc

(

)

:=

local

;

,

, ,

a b c r

:=

a

a0

;

:=

b

b0

;

≠

b

0

while

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

79

4

sans 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

208945227

2

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

+

q

i

p

i

p

+

i

1

et

=

c

i

p

i

+

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

,

,

a b c0

proc

(

)

:=

local

;

c1

( )

print

b

;

=

b

0

a

if

then

;

:=

c1

^

( )

lcoeff

b

(

)

-

+

( )

degree

a

( )

degree

b

1

(

)

pgcdr

,

,

b

/

(

)

rem

,

,

*

c1 a b x

c0 c1

else

end if

end proc

pgcdit

,

a0 b0

proc

(

)

:=

local

;

,

,

,

,

a b c0 c1 r

:=

a

a0

;

:=

b

b0

;

:=

c0

1;

≠

b

0

while

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

-

+

+

+

+

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

,

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

par 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

+

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));

tcoeffs

1

4

2 (

)

-

+

+

-

( )

ncc 1

2

( )

ncc 1

2

( )

ncc 0

2

3

( )

ncc 0

1

-

2

1

n

-

2

1

-

:=

-

-

+

+

1

2

( )

ncc 1

1

4

( )

ncc 1

2

( )

ncc 0

3

4

( )

ncc 0

2

-

1

+

2

1

n

+

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);

O

1

(

)

-

2

1

n

>

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

+

-

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