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

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


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