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
9 pages
Résumé des notions précédemment vuesModélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB(MODEL)o Codes correcteurs d’erreurs linéairesCours n 4 : Polynômes univariés, isolation de solutionsEspaces vectoriels et matricesréelles et algorithme d’EuclideDimension, RangCalculs élémentaires en algèbre linéaireStef Graillat & Mohab Safey El Din Corps fini de cardinalité un nombre premierApplication à des codes spécifiquesUniversité Pierre et Marie Curie (Paris 6)Et maintenant on passe à un monde moins discret...S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr4) 1 / 20 S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr4) 2 / 20Résumé des notions précédemment vues Solutions réelles de polynômes : Contexte applicatifEn algèbre linéaire : apparaissent naturellement (valeurs propres dematrices)Valeurs propres en image :Codes correcteurs d’erreurs linéairesTechnique d’analyse en composantes principales (télédétection et imageEspaces vectoriels et matricesmulti-spectrale)Dimension, Rang Courbes algébriques apparaissent naturellement (Bézier patches)Calculs élémentaires en algèbre linéaire En IA :Valeurs propres aussi!Corps fini de cardinalité un nombre premierProblèmes d’optimisation non linéaires s’expriment souventApplication à des codes spécifiquespolynmialement (algébriquement)Et maintenant on passe à un monde moins discret... En Calcul scientifique :Sciences de l’ingénieur : Robotique, vision 3d, ...
Voir plus Voir moins
ModÉlisation et rÉsolutions numÉrique et symbolique de problÈmes via les logiciels Maple et MATLAB (MODEL)
o Cours n 4 : PolynÔmes univariÉs, isolation de solutions rÉelles et algorithme d’Euclide
Stef Graillat & Mohab Safey El Din
UniversitÉ Pierre et Marie Curie (Paris 6)
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
RÉsumÉ des notions prÉcÉdemment vues
Codes correcteurs d’erreurs linaires Espaces vectoriels et matrices Dimension, Rang Calculs lmentaires en algbre linaire Corps fini de cardinalit un nombre premier Application À des codes spcifiques Et maintenant on passe À un monde moins discret...
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
1 / 20
2 / 20
RÉsumÉ des notions prÉcÉdemment vues
Codes correcteurs d’erreurs linaires Espaces vectoriels et matrices Dimension, Rang Calculs lmentaires en algbre linaire Corps fini de cardinalit un nombre premier Application À des codes spcifiques Et maintenant on passe À un monde moins discret...
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Solutions rÉelles de polynÔmes : Contexte applicatif
2 / 20
En algbre linaire : apparaissent naturellement (valeurs propres de matrices) Valeurs propres en image : Technique d’analyse en composantes principales (tÉlÉdÉtection et image multi-spectrale) Courbes algÉbriques apparaissent naturellement (BÉzier patches) En IA : Valeurs propres aussi ! ProblÈmes d’optimisationnon linÉairess’expriment souvent polynmialement (algÉbriquement) En Calcul scientifique : Sciences de l’ingÉnieur : Robotique, vision 3d, stabilisation de systÈmes dynamiques Gros progrÈs algorithmiques rÉcents
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
3 / 20
Un exemple : le tracÉ de courbes certifiÉ
Algorithme naif de balayage perpendiculairement À un axe ; Identifier les points oÙ une « catastrophe » (points critiques, asymptotes) se produit par rapport À notre axe ; On peut commencer par identifier leurs projections sur notre axe. On a besoin de savoir isoler les racines d’un polynÔmes en une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Un exemple : le tracÉ de courbes certifiÉ
4 / 20
Algorithme naif de balayage perpendiculairement À un axe ; Identifier les points oÙ une « catastrophe » (points critiques, asymptotes) se produit par rapport À notre axe ; On peut commencer par identifier leurs projections sur notre axe. On a besoin de savoir isoler les racines d’un polynÔmes en une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
4 / 20
Un exemple : le tracÉ de courbes certifiÉ
Algorithme naif de balayage perpendiculairement À un axe ; Identifier les points oÙ une « catastrophe » (points critiques, asymptotes) se produit par rapport À notre axe ; On peut commencer par identifier leurs projections sur notre axe. On a besoin de savoir isoler les racines d’un polynÔmes en une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Objectif 1 : RÉsoudref(X,Y) =g(X,Y) =0
SoitCune courbe dfinie parf(X,Y) =0 f etz= (x,y)Ctelle que(z)6=0 ou X f (z)6=0. Y
4 / 20
Une droite de vecteur directeurv= (a,b)est tangente ÀCen(x,y) 1 ff ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z XY normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=limzz0. 0 ||zz 2 Si on projette sur l’axe des absisses (celui desX), les « points f critiques » sont prcisment ceux pour lesquelsf(X,Y) = =0 Y Pour rsoudre, on va se ramener au cas d’une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
5 / 20
Objectif 1 : RÉsoudref(X,Y) =g(X,Y) =0
SoitCune courbe dfinie parf(X,Y) =0 f etz= (x,y)Ctelle que(z)6=0 ou X f (z)6=0. Y
1 Une droite de vecteur directeurv= (a,b)est tangente ÀCen(x,y) ff ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z XY normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=limzz0. 0 ||zz Si on projette sur l’axe des absisses (celui desX), les « points 2 f critiques » sont prcisment ceux pour lesquelsf(X,Y) = =0 Y Pour rsoudre, on va se ramener au cas d’une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Objectif 1 : RÉsoudref(X,Y) =g(X,Y) =0
SoitCune courbe dfinie parf(X,Y) =0 f etz= (x,y)Ctelle que(z)6=0 ou X f (z)6=0. Y
5 / 20
Une droite de vecteur directeurv= (a,b)est tangente ÀCen(x,y) 1 ff ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z XY normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=limzz0. 0 ||zz Si on projette sur l’axe des absisses (celui desX), les « points 2 f critiques » sont prcisment ceux pour lesquelsf(X,Y=) = 0 Y Pour rsoudre, on va se ramener au cas d’une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
5 / 20
Objectif 1 : RÉsoudref(X,Y) =g(X,Y) =0
SoitCune courbe dfinie parf(X,Y) =0 f etz= (x,y)Ctelle que(z)6=0 ou X f (z)6=0. Y
1 Une droite de vecteur directeurv= (a,b)est tangente ÀCen(x,y) ff ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z XY normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=limzz0. 0 ||zz 2 Si on projette sur l’axe des absisses (celui desX), les « points f critiques » sont prcisment ceux pour lesquelsf(X,Y) = =0 Y Pour rsoudre, on va se ramener au cas d’une variable.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Objectif 2 : Isoler les solutions rÉelles def(X) =0
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
5 / 20
6 / 20
PolynÔmes univariÉs : codage et propriÉtÉs ÉlÉmentaires
SoitKun corps etXune indtermine. 1
D X i K[X] ={ciX|ciK,DN} i=0
Le degr defest le plus petit entierDtel queci6=0 2 3 Codage dense : tableau des coefficients. Codage creux : tableau des coefficients non-nuls et des exposants. 4 L’ensemble des polynÔmes est unK-espace vectoriel (de dimension 5 infinie). L’ensemble des polynÔmes de degrDest unK-espace vectoriel de 6 dimension finieD+1.
S. Graillat & M. Safey (Univ. Paris 6)
StratÉgie d’isolation
MODEL (cours nr4)
SoitfQ[X]. Isolation dans un intervalleI= [a,b] Compter le nombre de racines defdans[a,b] 1 2 S’il n’y a pas de racines retourner une liste vide 3 S’il y a une et une seule racine retournerI a+b Procder par dichotomie (appels rcursifs avecI1= [a,]et 4 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, on a besoin d’une borne sur le max des valeurs absolues des racines.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
7 / 20
9 / 20
PolynÔmes univariÉs : propriÉtÉs (suite)
1 Les fonctions polynomiales sontcontinuesetdrivables. Un polynÔme univari de degrDaDracines complexes (comptes 2 avec multiplicit). LeThorme des valeurs intermdiairess’applique : pour tout 3 c[f(a),f(b)], il existeu[a,b]tel quef(u) =c. 4 LeThorme de Rolles’applique : soita<btel quef(a)f(b)<0, 0 alors il existsc[a,b]tel quef(c) =0.
S. Graillat & M. Safey (Univ. Paris 6)
StratÉgie d’isolation
MODEL (cours nr4)
SoitfQ[X]. Isolation dans un intervalleI= [a,b] 1 Compter le nombre de racines defdans[a,b] S’il n’y a pas de racines retourner une liste vide 2 S’il y a une et une seule racine retournerI 3 a+b 4 Procder par dichotomie (appels rcursifs avecI1= [a,]et 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, on a besoin d’une borne sur le max des valeurs absolues des racines.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
8 / 20
9 / 20
StratÉgie d’isolation
SoitfQ[X]. Isolation dans un intervalleI= [a,b] 1 Compter le nombre de racines defdans[a,b] S’il n’y a pas de racines retourner une liste vide 2 3 S’il y a une et une seule racine retournerI a+b Procder par dichotomie (appels rcursifs avecI1= [a,]et 4 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, on a besoin d’une borne sur le max des valeurs absolues des racines.
S. Graillat & M. Safey (Univ. Paris 6)
StratÉgie d’isolation
MODEL (cours nr4)
SoitfQ[X]. Isolation dans un intervalleI= [a,b] 1 Compter le nombre de racines defdans[a,b] 2 S’il n’y a pas de racines retourner une liste vide 3 S’il y a une et une seule racine retournerI a+b 4 Procder par dichotomie (appels rcursifs avecI1= [a,]et 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, on a besoin d’une borne sur le max des valeurs absolues des racines.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
9 / 20
9 / 20
StratÉgie d’isolation
SoitfQ[X]. Isolation dans un intervalleI= [a,b] Compter le nombre de racines defdans[a,b] 1 S’il n’y a pas de racines retourner une liste vide 2 S’il y a une et une seule racine retournerI 3 a+b Procder par dichotomie (appels rcursifs avecI1= [a,]et 4 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, on a besoin d’une borne sur le max des valeurs absolues des racines.
S. Graillat & M. Safey (Univ. Paris 6)
PremiÈres bornes
MODEL (cours nr4)
P D i Soitf=XQ[X]. i=0 Proposition 1 Siαet que aest une racine complexe de f D=1, alors |α|<1+max(|ai|,0iD1).
9 / 20
Proposition 2 (Borne de Lagrange-MacLaurin) Posons m=max({i|0iD1,ai<0})et B=max({−ai|0iD1,ai<0})(B=0par convention si tous les aisont positifs ou nuls). Siαest uneracine rÉelle positivealors, ende f supposant que aD=1et que a06=0, on a nm α <1+B.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
10 / 20
Majoration du nombre de racines
DÉfinition 1 On dÉfinit lesigne,sign(a), d’un ÉlÉment aRpar un entier valant0si a=0,1si a>0et1si a<0. Lenombre de changements de signes V(a)dans une suite, a=a1,∙ ∙ ∙,ak,d’ÉlÉments deR\ {0}est dÉfini par induction sur k par :
V(a1) =0 V(a1,∙ ∙ ∙,ak1) +1sisign(ak1ak) =1 V(a1,∙ ∙ ∙,ak) = V(a1,∙ ∙ ∙,ak1)sinon P D i Sif=aiXR[X], on noteV(f)le nombreV(a0, . . . ,aD). i=0
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Majoration du nombre de racines (suite)
11 / 20
Proposition 3 (Lemme de Descartes) Soit fR[X]non identiquement nul. Le nombre de racines rÉelles strictement positives (comptÉes avec multiplicitÉs) de f est Égal À V(f)modulo 2. est bornÉ par V(f). P D i ConsÉquence :Soitf=aiXR[X]. i=0 1 SiV(f) =0, alorsfn’a pas de racines relles strictement positives ; 2 SiV(f) =1, alorsfa une et une seule racine relle strictement positive.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
12 / 20
Majoration du nombre de racines (suite)
Proposition 3 (Lemme de Descartes) Soit fR[X]non identiquement nul. Le nombre de racines rÉelles strictement positives (comptÉes avec multiplicitÉs) de f est Égal À V(f)modulo 2. est bornÉ par V(f). P D i ConsÉquence :Soitf=aiXR[X]. i=0 SiV(f) =0, alorsfn’a pas de racines relles strictement positives ; 1 SiV(f) =1, alorsfa une et une seule racine relle strictement 2 positive.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
Calcul du nombre de racines : Suite de Sturm
12 / 20
DÉfinition 2 Soit fR[X]pour un intervalle donnÉ. Une suite de Sturm associÉe À f [a,b]Rest une suite de polynÔmes deR[X] [f0(X), . . .fs(X)]tels que : f0=f 1 fsn’a aucune racine rÉelle dans[a,b]; 2 pour0<i<s, siα[a,b]est tel que fi(α) =0, alors 3 fi1(α)fi+1(α)<0: siα[a,b]est tel que f0(α) =0, alors 4 f0f1(α)<0 f0f1(α+)>0
pour toute valeur desuffisamment petite (f0f1est une fonction croissante enα).
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
13 / 20
Calcul du nombre de racines : Vers le ThÉorÈme de Sturm
SoitfR[X]etS(X) = [f0(X), . . .fs(X)]une suite de Sturm associe Àf surI. On noteVstu(f(c)) =V(f0(c), . . .fs(c))pour toutcR. SiI=R, on dfinitVstu(f(+))(resp.Vstu(f(−∞))) comme tant le nombre devariations de signes dans la suite des coefficients de plus haut degr des polynÔmes deS(X)(resp.S(X)). Proposition 4 Si I= [a,b]alors Vstu(f(b))Vstu(f(a))est Égal au nombre de racines rÉelles de f dans[a,b].
Corollaire 1 Vstu(f(+))Vstu(f(−∞))est Égal au nombre de racines rÉelles de f dansR.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
14 / 20
Calcul du nombre de racines : Vers le ThÉorÈme de Sturm
SoitfR[X]etS(X) = [f0(X), . . .fs(X)]une suite de Sturm associe Àf surI. On noteVstu(f(c)) =V(f0(c), . . .fs(c))pour toutcR. SiI=R, on dfinitVstu(f(+))(resp.Vstu(f(−∞))) comme tant le nombre devariations de signes dans la suite des coefficients de plus haut degr des polynÔmes deS(X)(resp.S(X)). Proposition 4 Si I= [a,b]alors Vstu(f(b))Vstu(f(a))est Égal au nombre de racines rÉelles de f dans[a,b].
Corollaire 1 Vstu(f(+))Vstu(f(−∞))est Égal au nombre de racines rÉelles de f dansR.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
14 / 20
Calcul du nombre de racines : Vers le ThÉorÈme de Sturm
SoitfR[X]etS(X) = [f0(X), . . .fs(X)]une suite de Sturm associe Àf surI. On noteVstu(f(c)) =V(f0(c), . . .fs(c))pour toutcR. SiI=R, on dfinitVstu(f(+))(resp.Vstu(f(−∞))) comme tant le nombre devariations de signes dans la suite des coefficients de plus haut degr des polynÔmes deS(X)(resp.S(X)). Proposition 4 Si I= [a,b]alors Vstu(f(b))Vstu(f(a))est Égal au nombre de racines rÉelles de f dans[a,b].
Corollaire 1 Vstu(f(+))Vstu(f(−∞))est Égal au nombre de racines rÉelles de f dansR.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
14 / 20
Calcul du nombre de racines : Vers le ThÉorÈme de Sturm
SoitfR[X]sans racince relle multiple dans[a,b]. Proposition 5 0 On pose f0=ff , 1=f . et on construit par induction les polynÔmes fii=2. . .s en posant fi2=fi1gifiet en stoppant la construction À l’indice s tel que fsn’admet aucune racine rÉelle dans[a,b].La suite ainsi construite est une suite de Sturm associÉe À f pour[a,b].
0 ThÉorÈme de Sturm :On posef0=f,f1=f. et on construit par induction les polynÔmesfii=2. . .sen posantfi2=fi1gifi, deg(fi)<deg(fi1), et en stoppant la construction À l’indicestel que 0 fs2=fs1gs,gstant le PGCD defetf. La suite ainsi construite est une suite de Sturm associe Àfpour[a,b]aveca,btels quef(a)f(b)6=0.
S. Graillat & M. Safey (Univ. Paris 6)
MODEL (cours nr4)
15 / 20