66Construction d’une suite de SturmModélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB0(MODEL) il suffit d’appliquer l’algorithme d’Euclide au couple (f;f )Entrée : Deux polynômes A et B dansK[X ] (oùK est un corps) avecoCours n 5 : Résolution de systèmes bivariés – Algorithme deg(A) deg(B).Sortie : La suite des restes euclidiens.d’Euclide et Algèbre linéaireEuclide1 A = A et A = B0 1Stef Graillat & Mohab Safey El Din 2 Tant que A = 0iA =A remAi+1 i 1 iUniversité Pierre et Marie Curie (Paris 6) i + +3 Retourner les A .i2Complexité : O(D ) où D est le degré de f.S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 1 / 19 S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 2 / 19Propriétés Relation de BézoutEuclideEtendu1 A = A et A = B et U = 1 et V = 00 1 0 0Le dernier élément non nul de la suite renvoyée par Euclide(A;B) est2 Tant que A = 0ile PGCD de A et B.Q =A divAi i 1 iImplantation : Prendre garde à ne pas calculer 0 dans les divisions A =A A Qi+1 i 1 i ieuclidiennes. U =U Q U et U =U Q Ui+1 i 1 i i i+1 i 1 i ii + +Forte croissance des coefficients (à tester en TME).3 Retourner les A .Idée : Faire du calcul modulaire et utiliser le Théorème des restes ichinois (chrem)Proposition 1Pour tout i, On a A U +A V = A .0 i 1 i iS. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 3 / 19 S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 4 / 19Rappel : Motivation initiale Objectif3 ...
Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB (MODEL) Cours no5 : Résolution de systèmes bivariés – Algorithme d’Euclide et Algèbre linéaire
Stef Graillat & Mohab Safey El Din
Université Pierre et Marie Curie (Paris 6)
S. Graillat & M. Safey (Univ. Paris 6)
Propriétés
MODEL (cours nr5)
1 / 19
Le dernier élément non nul de la suite renvoyée par Euclide(A,B)est le PGCD deAetB. Implantation : Prendre garde à ne pas calculer 0 dans les divisions euclidiennes. Forte croissance des coefficients (à tester en TME). Idée: Faire du calcul modulaire et utiliser le Théorème des restes chinois (chrem)
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr5)
3 / 19
Construction d’une suite de Sturm
il suffit d’appliquer l’algorithme d’Euclide au couple(f,f0) Entrée: Deux polynômesAetBdansK[X](oùKest un corps) avec deg(A)≥deg(B). Sortie: La suite des restes euclidiens. Euclide 1A0=AetA1=B 2Tant queAi6=0 Ai+1=Ai−1remAi i+ + 3Retourner lesAi. Complexité:O(D2)oùDest le degré def.
S. Graillat & M. Safey (Univ. Paris 6)
Relation de Bézout
MODEL (cours nr5)
EuclideEtendu 1A0=AetA1=BetU0=1 etV0=0 2Tant queAi6=0 Qi=Ai−1divAi Ai+1=Ai−1−AiQi Ui+1=Ui−1−QiUietUi+1=Ui−1−QiUi i+ + 3Retourner lesAi. Proposition 1 Pour tout i , On a A0Ui+A1Vi=Ai.
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
2 / 19
4 / 19
Rappel : Motivation initiale Solutions deX3−X=0 etX2−3X+2=0=⇒PGCD→X−1=0 (X+5)(X2−3X+2) +1(X3−X) =X−1, !Combinaisons algébriques Vl’intersection des courbes définies parA=−3Y2−3Y+X2−1,B= −Y2+X2 C’ st un ensemble fini de points e (−1,−1),(1,−1),(−12,−12),(21,−21) deg(Gcd(A(−1,Y),B(−1,Y))≥1 deg(Gcd(A(1,Y),B(1,Y))≥1 deg(Gcd(A(1/2,Y),B(1/2,Y))≥1 deg(Gcd(A(−1/2,Y),B(−1/2,Y))≥ 1
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
A=RVetB=RU⇒UA+BV=0 Φ : (U,V)∈Dq−1[X]×Dp−1[X]→UA+VB∈Dp+q−1[X] Di[X]est un D-espace vectoriel de dimension finie. Interpréter les polynômes deDi[X]comme desvecteurs de Di+1 Représentation matricielle deΦ
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
7 / 19
Objectif
Étant donnéF(X,Y) =G(X,Y) =0, réécrire à changement linéaire de variable près l’ensemble des solutions sous la forme :R(X) =0,Y=Q(X). >A:=−3∗Y2−3∗Y+X2−1:B:=−Y2+X2: >rem(B,rem(A,B,Y),Y); 5/9X2−1/9−4/9X4 Le resteprécédentle dernier reste non nul est−1−3Y−2X2 Nécessité de « séparer » les solutions par changement de variables ; Rôle de la suite des restes euclidiens dans la résolution ; Les deux derniers restes non nuls sont importants ; On veut néanmoins éviter la croissance des coefficients observée sur la suite des restes euclidiens classique.
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
6 / 19
8 / 19
Propriétés du résultant
Res(A,B) =0 ssi il existeU∈K[X]etV∈K[X] avecdeg(U)<qetdeg(V)<ptel queUA+VB=0. Res(A,B) =0si et seulement siAetBont un facteur commun dans K[X]. SoitAetBdansD[X]. Il existeUetVdansD[X]tels que deg(U)<q, deg(V)<petRes(A,B) =UA+VB. SoitA=apQip=1(X−xi)etB=bqQjq=1(X−yj), alors p q Res(A,B) =apqbpqY Y(xi−yj) i=1j=1
Corollaire :Res(A,BC) =Res(A,B)Res(A,C)
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr5)
De l’algorithme d’Euclide au calcul du résultant
Entrée :AetBdansK[Y]de degrésp>q A1←A,A2←B i←2,R1←1 Tant queAi6=0 Faire Ai+1←Ai−1modAi Ri←(−1)didi−1LC(Ai)di−1−diRi−1 i+ + SiAi6=0 returnRi−1LC(Ai)deg(Ai−1)Sinon return 0 Correction: Si deg(Ai)>0, Res(A,B) =RiRes(Ai,Ai+1) Si deg(Ai)≤0, SiAi=0 Res(Ai−1,Ai) =0 Sinon Res(Ai,Ai−1) =LC(Ai)deg(Ai−1) Complexité :O(p2)
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
Relation forte entre résultant et suite des restes euclidiens
S. Graillat & M. Safey (Univ. Paris 6)
Inconvénients
MODEL (cours nr5)
10 / 19
La croissance anormale descoefficients intermédiairesreste ! Ca devient ingérable quand les coefficients sont des polynômes (on manipule alors des fractions rationnelles) Idée quand on a des polynômes dansZ[X]: Utiliser le théorème de spécialisation pour faire des calculs modulo des nombres premiers et reconstruire le résultat final (voir en TD-TP). Permet de limiter la croissance des coefficients ! Première alternative : Procédé similaire pour les polynômes dans Q[X][Y] Borne sur le degré du résultant ? Algorithme modulaire Deuxième alternative : Faire des calculs de pseudo-restes et prédire le contenu – Divisions exactes. Polynômes sous-résultants (proportionnels aux restes euclidiens) (Voir en TD-TP)
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
12 / 19
Bornes sur le degré
Évaluer le degré deRes(A,B)revient à évaluer le degré du déterminant de la matrice de Sylvester