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

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

Informations

• Publié par: Undoi
• Nombre de lectures: 39
• Langue: Français

Extrait

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Éairess’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 ∂f∂f ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z ∂X∂Y normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=lim z→z 0 . 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) ∂f∂f ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z ∂X∂Y normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=lim z→z 0 . 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 ∂f∂f ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z ∂X∂Y normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=lim z→z 0 . 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) ∂f∂f ssi elle contientxeta(z) +b(z) =v.grad(f)0.Elle est z ∂X∂Y normale au vecteur gradient defenz. 0 zz On peut aussi dire quev=lim z→z 0 . 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] ={c i X|c i ∈K,D∈N} i=0

Le degr defest le plus petit entierDtel quec i 6=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)

Soitf∈Q[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 avecI 1 = [a,]et 4 2 a+b I 2 = [,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)

Soitf∈Q[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 avecI 1 = [a,]et 2 a+b I 2 = [,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

Soitf∈Q[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 avecI 1 = [a,]et 4 2 a+b I 2 = [,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)

Soitf∈Q[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 avecI 1 = [a,]et 2 a+b I 2 = [,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

Soitf∈Q[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 avecI 1 = [a,]et 4 2 a+b I 2 = [,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=X∈Q[X]. i=0 Proposition 1 Siαet que aest une racine complexe de f D =1, alors |α|<1+max(|a i |,0≤i≤D−1).

9 / 20

Proposition 2 (Borne de Lagrange-MacLaurin) Posons m=max({i|0≤i≤D−1,a i <0})et B=max({−a i |0≤i≤D−1,a i <0})(B=0par convention si tous les a i sont positifs ou nuls). Siαest uneracine rÉelle positivealors, ende f supposant que a D =1et que a 0 6=0, on a √ n−m α <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 a∈Rpar un entier valant0si a=0,1si a>0et−1si a<0. Lenombre de changements de signes V(a)dans une suite, a=a 1 ,∙ ∙ ∙,a k ,d’ÉlÉments deR\ {0}est dÉfini par induction sur k par :

V(a 1 ) =0  V(a 1 ,∙ ∙ ∙,a k−1 ) +1sisign(a k−1 a k ) =−1 V(a 1 ,∙ ∙ ∙,a k ) = V(a 1 ,∙ ∙ ∙,a k−1 )sinon P D i Sif=a i X∈R[X], on noteV(f)le nombreV(a 0 , . . . ,a D ). 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 f∈R[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=a i X∈R[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 f∈R[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=a i X∈R[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 f∈R[X]pour un intervalle donnÉ. Une suite de Sturm associÉe À f [a,b]∈Rest une suite de polynÔmes deR[X] [f 0 (X), . . .f s (X)]tels que : f 0 =f 1 f s n’a aucune racine rÉelle dans[a,b]; 2 pour0<i<s, siα∈[a,b]est tel que f i (α) =0, alors 3 f i−1 (α)f i+1 (α)<0: siα∈[a,b]est tel que f 0 (α) =0, alors 4  f 0 f 1 (α−)<0 f 0 f 1 (α+)>0

pour toute valeur desuffisamment petite (f 0 f 1 est 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

Soitf∈R[X]etS(X) = [f 0 (X), . . .f s (X)]une suite de Sturm associe Àf surI. On noteV stu (f(c)) =V(f 0 (c), . . .f s (c))pour toutc∈R. SiI=R, on dfinitV stu (f(+∞))(resp.V stu (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 V stu (f(b))−V stu (f(a))est Égal au nombre de racines rÉelles de f dans[a,b].

Corollaire 1 V stu (f(+∞))−V stu (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

Soitf∈R[X]etS(X) = [f 0 (X), . . .f s (X)]une suite de Sturm associe Àf surI. On noteV stu (f(c)) =V(f 0 (c), . . .f s (c))pour toutc∈R. SiI=R, on dfinitV stu (f(+∞))(resp.V stu (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 V stu (f(b))−V stu (f(a))est Égal au nombre de racines rÉelles de f dans[a,b].

Corollaire 1 V stu (f(+∞))−V stu (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

Soitf∈R[X]etS(X) = [f 0 (X), . . .f s (X)]une suite de Sturm associe Àf surI. On noteV stu (f(c)) =V(f 0 (c), . . .f s (c))pour toutc∈R. SiI=R, on dfinitV stu (f(+∞))(resp.V stu (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 V stu (f(b))−V stu (f(a))est Égal au nombre de racines rÉelles de f dans[a,b].

Corollaire 1 V stu (f(+∞))−V stu (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

Soitf∈R[X]sans racince relle multiple dans[a,b]. Proposition 5 0 On pose f 0 =ff , 1 =f . et on construit par induction les polynÔmes f i i=2. . .s en posant f i−2 =f i−1 g i −f i et en stoppant la construction À l’indice s tel que f s n’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 posef 0 =f,f 1 =−f. et on construit par induction les polynÔmesf i i=2. . .sen posantf i−2 =f i−1 g i −f i , deg(f i )<deg(f i−1 ), et en stoppant la construction À l’indicestel que 0 f s−2 =f s−1 g s ,g s 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