//img.uscri.be/pth/aba89ba408d590b7e708d10b7bd7cd0741a486ba
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

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

De
4 pages
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 ...
Voir plus Voir moins
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=Ai1remAi i+ + 3Retourner lesAi. Complexité:O(D2)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=Ai1divAi Ai+1=Ai1AiQi Ui+1=Ui1QiUietUi+1=Ui1QiUi 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 deX3X=0 etX23X+2=0=PGCDX1=0 (X+5)(X23X+2) +1(X3X) =X1, !Combinaisons algébriques Vl’intersection des courbes définies parA=3Y23Y+X21,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)
Du PGCD à l’algèbre linéaire
Dun anneau euclidien,Kson corps de fraction,
5 / 19
Di[X] ={fD[X]|deg(f)i} A=apXp+∙ ∙ ∙+a0etB=bqXq+∙ ∙ ∙+b0dansD[X]de degrés resp.p etq. hA,Bi=hRiavec deg(R)<min(p,q),
A=RVetB=RUUA+BV=0 Φ : (U,V)Dq1[X]×Dp1[X]UA+VBDp+q1[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:=3Y23Y+X21:B:=Y2+X2: >rem(B,rem(A,B,Y),Y); 5/9X21/94/9X4 Le resteprécédentle dernier reste non nul est13Y2X2 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) : Xq1A2ap∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙a00∙ ∙ ∙03 . . . . . ..0........ . . . . . . . . . .. . . . 0 . A0∙ ∙ ∙0ap ∙ ∙ ∙ ∙ ∙ ∙∙ ∙ ∙ ∙ ∙ ∙a0 SyHa(A,B) =Sylv(A,B)t=Xp1B bq∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙b00∙ ∙ ∙ ∙ ∙ ∙0 . . . . . .0........ . . . . . . . . . . . . . . . . . . . . . . . B...46..0 ∙∙ ∙ ∙......0bq ∙∙ ∙ ∙ ∙ ∙ ∙...b0057 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 existeUK[X]etVK[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(Xxi)etB=bqQjq=1(Xyj), alors p q Res(A,B) =apqbpqY Y(xiyj) 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 A1A,A2B i2,R11 Tant queAi6=0 Faire Ai+1Ai1modAi Ri(1)didi1LC(Ai)di1diRi1 i+ + SiAi6=0 returnRi1LC(Ai)deg(Ai1)Sinon return 0 Correction: Si deg(Ai)>0, Res(A,B) =RiRes(Ai,Ai+1) Si deg(Ai)0, SiAi=0 Res(Ai1,Ai) =0 Sinon Res(Ai,Ai1) =LC(Ai)deg(Ai1) Complexité :O(p2)
S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5)
9 / 19
11 / 19
Propriétés du résultant
SiA=apQpi=1(Xxi) Res(A,B)apYB(xi) =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
Xq1A2ap ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙∙ ∙ ∙a00∙ ∙ ∙03 . . . . . . . . . . . . . . 0 . . . . . . . . . .. . . . . 0 . A0∙ ∙ ∙0ap ∙ ∙ ∙∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙a0 SyHa(A,B) =Sylv(A,B)t=Xp1B bq ∙ ∙ ∙ ∙ ∙ ∙∙ ∙ ∙b00 ∙ ∙ ∙∙ ∙ ∙0 . . . . . .0........ . . . . . . . . . . . . . . . . . . . . . . . ...B64..0 ∙∙ ∙ ∙......0bq∙ ∙ ∙ ∙ ∙ ∙ ∙...b0075 SiAetBsont de degré total borné pard, le degré de ResY(A,B)est borné pard2 On peut faire mieux :(degY(A) +degY(B))max(degX(A),degX(B))
S. Graillat & M. Safey (Univ. Paris 6)
Polynômes interpolants
MODEL (cours nr5)
13 / 19
Entrée :`+1 rationnels distinctsa0, . . . ,a`et`+1 rationnelsv0, . . . ,v`. Sortie :l’unique polynômeFde degré`tel que pour tout 0i`, F(ai) =vi.Fest donné par aj) F=i=X`0viQQjj66==ii((aXiaj)
CalculerP=Qi`=0(Xai) En déduire tous lesQj6=i(Xaj) En déduire tous lesQj6=i(aiaj) 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 totauxd Pourd2+1 valeursedansQtelles queap(e)6=0 oubq(e)6=0 calculer Res(A(X,e),B(X,e)) Interpoler le résultat
Complexité : O(d2×d2)+C(d2)où on noteC(`)le coût de l’interpolation d’un polynôme à partir de degré`. Coût total :O(d4)
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr5)
14 / 19