Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB

Stef Graillat & Mohab Safey El Din

Description

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

Informations

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

Extrait

Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB (MODEL) Cours n o 5 : 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,f 0 ) Entrée: Deux polynômesAetBdansK[X](oùKest un corps) avec deg(A)≥deg(B). Sortie: La suite des restes euclidiens. Euclide 1 A 0 =AetA 1 =B 2 Tant queA i 6=0 A i+1 =A i−1 remA i i+ + 3 Retourner lesA i . Complexité:O(D 2 )oùDest le degré def.

S. Graillat & M. Safey (Univ. Paris 6)

Relation de Bézout

MODEL (cours nr5)

EuclideEtendu 1 A 0 =AetA 1 =BetU 0 =1 etV 0 =0 2 Tant queA i 6=0 Q i =A i−1 divA i A i+1 =A i−1 −A i Q i U i+1 =U i−1 −Q i U i etU i+1 =U i−1 −Q i U i i+ + 3 Retourner lesA i . Proposition 1 Pour tout i , On a A 0 U i +A 1 V i =A i .

S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)

2 / 19

4 / 19

Rappel : Motivation initiale Solutions deX 3 −X=0 etX 2 −3X+2=0=⇒PGCD→X−1=0 (X+5)(X 2 −3X+2) +1(X 3 −X) =X−1, !Combinaisons algébriques Vl’intersection des courbes définies parA=−3Y 2 −3Y+X 2 −1,B= −Y 2 +X 2 C’ st un ensemble fini de points e (−1,−1),(1,−1),(− 1 2 ,− 1 2 ),( 2 1 ,− 2 1 ) 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)

Du PGCD à l’algèbre linéaire

Dun anneau euclidien,Kson corps de fraction,

5 / 19

D i [X] ={f∈D[X]|deg(f)≤i} A=a p X p +∙ ∙ ∙+a 0 etB=b q X q +∙ ∙ ∙+b 0 dansD[X]de degrés resp.p etq. hA,Bi=hRiavec deg(R)<min(p,q),

A=RVetB=RU⇒UA+BV=0 Φ : (U,V)∈D q−1 [X]×D p−1 [X]→UA+VB∈D p+q−1 [X] D i [X]est un D-espace vectoriel de dimension finie. Interpréter les polynômes deD i [X]comme desvecteurs de D i+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∗Y 2 −3∗Y+X 2 −1:B:=−Y 2 +X 2 : >rem(B,rem(A,B,Y),Y);
5/9X 2 −1/9−4/9X 4 Le resteprécédentle dernier reste non nul est−1−3Y−2X 2 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)

Du PGCD à l’algèbre linéaire

Matrice transposée (Sylvester-Habicht) de la matrice associée à cette application (matrice de Sylvester) : X q−1 A 2 a p ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙a 0 0∙ ∙ ∙0 3 . . . . . . .0 . . . . . . . . . . . . . . . . . .. .  . .  0 . A0∙ ∙ ∙0a p  ∙ ∙ ∙ ∙ ∙ ∙∙ ∙ ∙ ∙ ∙ ∙a 0 SyHa(A,B) =Sylv(A,B) t = X p−1 B b q ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙b 0 0∙ ∙ ∙ ∙ ∙ ∙0 . . .  . . . 0 . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . . B . . . 4 6 . . 0 ∙∙ ∙ ∙ . . ∙ . ∙ . . . 0b q  ∙∙ ∙ ∙ ∙ ∙ ∙ . . ∙ . ∙b 0 0 5 7 Le résultant deAetBest le déterminant de cette matrice

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=a p Q i p =1 (X−x i )etB=b q Q j q =1 (X−y j ), alors p q Res(A,B) =a pq b p q Y Y (x i −y j ) 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 A 1 ←A,A 2 ←B i←2,R 1 ←1 Tant queA i 6=0 Faire A i+1 ←A i−1 modA i R i ←(−1) d i d i−1 LC(A i ) d i−1 −d i R i−1 i+ + SiA i 6=0 returnR i−1 LC(A i ) deg(A i−1 ) Sinon return 0 Correction: Si deg(A i )>0, Res(A,B) =R i Res(A i ,A i+1 ) Si deg(A i )≤0, SiA i =0 Res(A i−1 ,A i ) =0 Sinon Res(A i ,A i−1 ) =LC(A i ) deg(A i−1 ) Complexité :O(p 2 )

S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)

9 / 19

11 / 19

Propriétés du résultant

SiA=a p Q p i=1 (X−x i ) Res(A,B)a p Y B(x i ) = q

SoitRtel queA=BQ+R(avec deg(R)<deg(B)), Res(A,B) = (−1) deg(A)deg(B) LC(B) deg(A)−deg(R) Res(B,R)

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

X q−1 A 2 a p  ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙∙ ∙ ∙a 0 0∙ ∙ ∙0 3 . . . . . . . . . . . . . . 0 . . . . . . . . . .. .  .  .  .  0 . A0∙ ∙ ∙0a p  ∙ ∙ ∙∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙a 0 SyHa(A,B) =Sylv(A,B) t = X p−1 B b q  ∙ ∙ ∙ ∙ ∙ ∙∙ ∙ ∙b 0 0 ∙ ∙ ∙∙ ∙ ∙0 . . . . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B 6 4 . . 0 ∙∙ ∙ ∙ . ∙ . . ∙ . . . 0b q ∙ ∙ ∙ ∙ ∙ ∙ ∙ . ∙ . . ∙b 0 0 7 5 SiAetBsont de degré total borné pard, le degré de Res Y (A,B)est borné pard 2 On peut faire mieux :(deg Y (A) +deg Y (B))max(deg X (A),deg X (B))

S. Graillat & M. Safey (Univ. Paris 6)

Polynômes interpolants

MODEL (cours nr5)

13 / 19

Entrée :`+1 rationnels distinctsa 0 , . . . ,a ` et`+1 rationnelsv 0 , . . . ,v ` . Sortie :l’unique polynômeFde degré≤`tel que pour tout 0≤i≤`, F(a i ) =v i .Fest donné par a j ) F= i= X ` 0 v i Q Q j j 6 6 = = i i ( ( a X i − − a j )

CalculerP= Q i ` =0 (X−a i ) En déduire tous les Q j6=i (X−a j ) En déduire tous les Q j6=i (a i −a j ) Faire la recombinaison Coût totalO(` 2 )

S. Graillat & M. Safey (Univ. Paris 6)

MODEL (cours nr5)

15 / 19

Algorithme modulaire

Entrée :AetBdansQ[Y,X]de degrés totaux≤d Pourd 2 +1 valeursedansQtelles quea p (e)6=0 oub q (e)6=0 calculer Res(A(X,e),B(X,e)) Interpoler le résultat

Complexité : O(d 2 ×d 2 )+C(d 2 )où on noteC(`)le coût de l’interpolation d’un polynôme à partir de degré≤`. Coût total :O(d 4 )

S. Graillat & M. Safey (Univ. Paris 6)

MODEL (cours nr5)

14 / 19