Comptage et localisation de racines-Algorithme de Fadeev

Alaeddine Ben Rhouma

Informations

• Publié par: ALEDINE.BENRHOUMA
• Publié le: 06 mai 2015
• Nombre de lectures: 18
• Langue: Français

Extrait

Agrégation interne de Mathématiques Académie de Guyane
TP n˚1
Compatge et localisation de racines-Interpolation
polynomiale-Algorithme de Fadeev
I. Comptage de racines par les formes quadratiques
SoitP2R[X] un polynôme de degrén dont on note ; ; les racines complexes comptées avec1 n
nP
imultiplicité. Pour n2N, on note S = .i k
k=1
Rappelons que les S sont réels puisqu’on peut les calculer avec les formules de Newton qui nousi
donnent une expression en fonction des polynômes symétriques élémentaires, eux-mêmes fonction
des coefficients de P.
On définit A , la matrice de Sylvester-Hermite associée au polynôme P, symétrique réelle définieP
comme suit :
0 1
S S S0 1 n 1
B CS S S1 2 nB C
B C: : :B CA =P B C: : :B C
@ A: : :
S S Sn 1 n 2n 1
iEn remarquant que S = trace((C )), où C est la matrice compagnon de P, écrire uni P P
programme qui prend en entrée un polynôme réel P et qui nous fournit à la sortie la
signature de sa matrice de Sylvester-Hermite.
II. Comptage de racines par la suite de Sturm
Définition : suite de Sturm
Soient P et Q deux polynômes deR[X]. On définit la suite de Sturm comme la suite de polynômes
P ;P ; ;P définis de la manière suivante :0 1 m
8
P =P> 0><
P =Q1
P est le reste de la division euclidienne de P par P pour i<m> i+1 i 1 i:
P est au signe près le dernier reste non nul dans l’algorithme d’Euclidem
Soit a2R. On définit V(P;Q;a) comme la variation de la suite :
(P (a);P (a); ;P (a))0 1 m
On notera que le polynôme P est un PGCD de P et Q.m
Théorème de Sturm
Avec les notations de la définition précédente, supposons que P(a)P(b)=0. On a alors :
0 0Le nombre de racines réelles distinctes dans [a;b]=V(P;P ;a) V(P;P ;b)
Alaeddine BEN RHOUMA 1 Algèbre
6Agrégation interne de Mathématiques Académie de Guyane
- Écrire un programme qui prend en entrée un polynôme P et un intervalle [a;b] et qui
fournit en sortie le nombre de racines réelles distinctes de P dans l’intervalle [a;b].
III. Algorithme de Fadeev
Soit A2M (R). on définit les matrices B par récurrence :n k
8
< B =I0 n
tr(AB )k 1: B =AB I pour k2 J1;nKk k 1 n
k
n n 1On a alors au signe près, le polynôme caractéristique deA : (X)=X +a X ++a X+aA 1 n 1 n
tr(AB )k 1
avec a = pour tout k2 J1;nKk
k
- Écrire un programme qui prend en entrée une matrice A et nous fournit à la sortie la
liste des coefficients de son polynôme caractéristique.
- Dans le cas où A est inversible, expliquer comment peut-on calculer son inverse grâce à
l’algorithme de Fadeev.
IV. Algorithme des différences divisées
Étant donnés des réels (x) deux à deux distincts, on définit les polynômes de Newton ()i 0in i 0in
de la manière suivante :
8
=1< 0
i 1Q
(X)= (X x) pour i2 J1;nK: i i
k=0
On rappelle que les () forment une base de K [X] et que le polynôme d’interpolation dei 0in n
Lagrange aux points (x;f(x)) dans cette base est donnée par :i i 0in
P(X)=f[x ]+f[x ;x ](X x ]++f[x ; ;x ](X x )(X x );0 0 1 0 0 n 0 n 1
où les f[x ; ;x ] pour k2 J0;nK, sont les différences divisées.0 k
- Écrire un programme qui prend en entrée (x;y) et nous fournit à la sortie la listei i 0in
des différences divisées.
- Dans le cas où on décide de rajouter un point d’interpolation (x ;y ), écrire unn+1 n+1
programme qui calcule uniquement f[x ; ;x ] en utilisant la liste des différences0 n+1
divisées obtenue à l’aide des points (x;y) .i i 0in
Quel est le nombre d’opérations effectuées en fonction de n?
Alaeddine BEN RHOUMA 2 Algèbre