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, ...
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 linaires Espaces vectoriels et matrices Dimension, Rang Calculs lmentaires en algbre linaire Corps fini de cardinalit un nombre premier Application À des codes spcifiques 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 linaires Espaces vectoriels et matrices Dimension, Rang Calculs lmentaires en algbre linaire Corps fini de cardinalit un nombre premier Application À des codes spcifiques 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 algbre linaire : 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.
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=limz→z0. 0 ||zz 2 Si on projette sur l’axe des absisses (celui desX), les « points ∂f critiques » sont prcisment ceux pour lesquelsf(X,Y) = =0 ∂Y Pour rsoudre, on va se ramener au cas d’une variable.
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=limz→z0. 0 ||zz Si on projette sur l’axe des absisses (celui desX), les « points 2 ∂f critiques » sont prcisment ceux pour lesquelsf(X,Y) = =0 ∂Y Pour rsoudre, on va se ramener au cas d’une variable.
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=limz→z0. 0 ||zz Si on projette sur l’axe des absisses (celui desX), les « points 2 ∂f critiques » sont prcisment ceux pour lesquelsf(X,Y=) = 0 ∂Y Pour rsoudre, on va se ramener au cas d’une variable.
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=limz→z0. 0 ||zz 2 Si on projette sur l’axe des absisses (celui desX), les « points ∂f critiques » sont prcisment ceux pour lesquelsf(X,Y) = =0 ∂Y Pour rsoudre, 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 indtermine. 1
D X i K[X] ={ciX|ci∈K,D∈N} 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)
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 Procder par dichotomie (appels rcursifs avecI1= [a,]et 4 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, 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 sontcontinuesetdrivables. Un polynÔme univari de degrDaDracines complexes (comptes 2 avec multiplicit). LeThorme des valeurs intermdiairess’applique : pour tout 3 c∈[f(a),f(b)], il existeu∈[a,b]tel quef(u) =c. 4 LeThorme 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 Procder par dichotomie (appels rcursifs avecI1= [a,]et 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, 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 Procder par dichotomie (appels rcursifs avecI1= [a,]et 4 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, 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 Procder par dichotomie (appels rcursifs avecI1= [a,]et 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, 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 Procder par dichotomie (appels rcursifs avecI1= [a,]et 4 2 a+b I2= [,b] 2 Pour gnraliser sur les rels, 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(|ai|,0≤i≤D−1).
9 / 20
Proposition 2 (Borne de Lagrange-MacLaurin) Posons m=max({i|0≤i≤D−1,ai<0})et B=max({−ai|0≤i≤D−1,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 √ 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=a1,∙ ∙ ∙,ak,d’ÉlÉments deR\ {0}est dÉfini par induction sur k par :
V(a1) =0 V(a1,∙ ∙ ∙,ak−1) +1sisign(ak−1ak) =−1 V(a1,∙ ∙ ∙,ak) = V(a1,∙ ∙ ∙,ak−1)sinon P D i Sif=aiX∈R[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 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=aiX∈R[X]. i=0 1 SiV(f) =0, alorsfn’a pas de racines relles strictement positives ; 2 SiV(f) =1, alorsfa une et une seule racine relle 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=aiX∈R[X]. i=0 SiV(f) =0, alorsfn’a pas de racines relles strictement positives ; 1 SiV(f) =1, alorsfa une et une seule racine relle 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] [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 fi−1(α)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
Soitf∈R[X]etS(X) = [f0(X), . . .fs(X)]une suite de Sturm associe Àf surI. On noteVstu(f(c)) =V(f0(c), . . .fs(c))pour toutc∈R. SiI=R, on dfinitVstu(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
Soitf∈R[X]etS(X) = [f0(X), . . .fs(X)]une suite de Sturm associe Àf surI. On noteVstu(f(c)) =V(f0(c), . . .fs(c))pour toutc∈R. SiI=R, on dfinitVstu(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
Soitf∈R[X]etS(X) = [f0(X), . . .fs(X)]une suite de Sturm associe Àf surI. On noteVstu(f(c)) =V(f0(c), . . .fs(c))pour toutc∈R. SiI=R, on dfinitVstu(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
Soitf∈R[X]sans racince relle 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 fi−2=fi−1gi−fiet 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 posantfi−2=fi−1gi−fi, deg(fi)<deg(fi−1), et en stoppant la construction À l’indicestel que 0 fs−2=fs−1gs,gstant le PGCD defetf. La suite ainsi construite est une suite de Sturm associe Àfpour[a,b]aveca,btels quef(a)f(b)6=0.