\documentclass{article}
\textwidth 15.5cm
\oddsidemargin=0mm
\topmargin=-7mm
\textheight 21 cm
\usepackage{pst-plot,color} 
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[francais]{babel}
\usepackage{xspace}
\newcommand{\bs}{\symbol{92}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newtheorem{theorem}{Theorem}
\newtheorem{defn}{Definition}
%\textheight=23.5cm
%\textwidth=17.5cm
%\topmargin=-7mm
%\oddsidemargin=-10mm
 \usepackage[ps2pdf,
            breaklinks=true,
            colorlinks=true,
            linkcolor=red,
            citecolor=green
            ]{hyperref}

\usepackage{times}

\begin{document}

\title{Factorisation des polyn\^omes}
\author{Pr\'eparation agr\'egation 2006, option C}
\date{R\'evision: 4/05/07}

\maketitle

Ce texte discute plusieurs m\'ethodes de localisation de racines 
r\'eelles ou/et complexes d'un polyn\^ome $P(X)$ de degré $n$.

{\em Ce texte est tr\`es largement inspir\'e d'id\'ees de M. Eisermann}

\section{Introduction}
Si $P$ est \`a coefficients entiers 
(ou rationnels, ou entiers de Gauss), on peut toujours se ramener au cas o\`u
$P$ n'a pas de racines multiples (par calcul de PGCD, c'est la
factorisation ``square-free''), 
on peut aussi d\'ecider d'appliquer
un algorithme de factorisation exact (par exemple Berlekamp,
Cantor-Zassenhaus) pour si possible diminuer le degr\'e du
polyn\^ome dont on cherche \`a localiser les racines.

{\bf On supposera dans tout ce qui suit que l'on cherche \`a localiser
les racines d'un polyn\^ome dont toutes les racines sont simples.}

On pr\'esente ici principalement deux m\'ethodes~:
\begin{itemize}
\item la m\'ethode de Newton et des am\'eliorations pour \'eviter le
probl\`eme de la recherche de la valeur initiale de la suite it\'erative
\item la g\'en\'eralisation des suites de Sturm aux racines complexes
\end{itemize}

\section{La m\'ethode de Newton.}
La m\'ethode de Newton est une m\'ethode 
fr\'equemment impl\'ement\'ee par les logiciels de calcul
scientifique et formel. Dans sa forme la plus simple, on cherche
une racine $r$ de $P$, on \'elimine la racine trouv\'ee en prenant le
quotient $Q$ de $P$ par $X-r$, on recommence alors avec $Q$.
Cette m\'ethode pr\'esente plusieurs inconv\'enients~:
\begin{itemize}
\item si le point de d\'epart de la recherche est \'eloign\'e d'une
  racine, la m\'ethode de Newton n'a pas de raison de converger
(en tous cas en un nombre raisonnable d'it\'erations)
\item les erreurs d'arrondis se cumulent \`a chaque \'elimination
de racine
\end{itemize} 
On peut rem\'edier au premier inconv\'enient par exemple par
des algorithmes d'alg\`ebre lin\'eaire. Ainsi en appliquant quelques
it\'erations de la m\'ethode de la puissance \`a la matrice 
companion $M$ du polyn\^ome $P$
$$ v_{n+1}=Mv_n, \quad v_0 \mbox{ al\'eatoire}$$
on peut obtenir une estimation de la plus grande racine complexe
en module du polyn\^ome (si $P$ est \'a coefficients r\'eels
il peut \^etre n\'ecessaire de faire des it\'erations sur $M+\alpha i$, 
pour d\'ecoupler une paire de racines complexes conjugu\'ees),
puis on affine en prenant cette estimation
comme valeur initiale de la m\'ethode de Newton.
Pour att\'enuer le probl\`eme des erreurs d'arrondi \`a chaque
\'elimintation de racine, on peut
effecter quelques it\'erations de Newton
suppl\'ementaires sur les racines approch\'ees de $Q$ avec le
polyn\^ome initial $P$. On peut aussi utiliser la factorisation
de Schur de la matrice companion pour avoir une estimation
simultan\'ee de toutes les racines du polyn\^ome (m\'ethode
utilis\'ee par Xcas), on peut
aussi utiliser la m\'ethode d'Aberth, qui consiste \`a faire pour
$k \in [1,n]$ une it\'eration
de Newton sur l'estimation $z_k$ d'une des racines
en prenant comme fonction~:
$$ \frac{P(x)}{\prod_{1\leq j \leq n, j\neq k}(x-z_j)}$$

Lorsqu'on a trouv\'e une racine approch\'ee $z$ d'un polyn\^ome
$P$ de degr\'e $n$, on peut en d\'eduire
que le disque du plan complexe de centre $z$ et
de rayon $n|P(z)/P'(z)|$ contient au moins une racine,
en effet~:
\[ \frac{P'}{P}=\sum_{k=1}^n \frac{1}{z-z_j} \]
si toutes les racines $z_j$ sont en-dehors du disque, on peut minorer $|z-z_j|$
et donc majorer $|P'(z)/P(z)|$. Pour certifier l'existence d'une racine
dans un disque, on prendra une racine approch\'ee 
$z \in \Q[i]$ pour calculer le rayon exact du disque.

\section{Par homotopie}
On pr\'esente dans cette section une autre m\'ethode qui d\'etermine
simultan\'ement les racines de $P$. L'id\'ee est de construire
un chemin de polyn\^omes reliant un polyn\^ome dont les racines
sont connues au polyn\^ome $P$, en suivant les racines le long
du chemin. Soit donc~:
\[ P_t=tP+(1-t)(x^n-1), \quad P_0=x^n-1,\ P_1=P \]
Pour passer de $t=0$ à $t=1$, il faut trouver
un chemin dans le plan complexe tel que les racines de $P_t$ restent
simples, afin de pouvoir suivre les racines mais aussi pour pouvoir
appliquer la m\'ethode de Newton~: pour trouver 
les racines de $P_{t+\Delta t}$ ($\Delta t << 1$) on appliquera
quelques it\'erations de la méthode de Newton
en prenant les racines de $P_t$ comme valeurs initiales.
De proche en proche, on arrivera \`a calculer simultanément 
toutes les racines de $P$.

Soit $R$ le r\'esultant de $P_t$ et de sa dérivée. Comme le but
de l'algorithme est de calculer les valeurs approch\'es de racines
d'un polynome, on ne peut pas utiliser un algorithme de recherche
de racines approch\'ees de $R$ pour savoir quel chemin utiliser
pour relier $t=0$ et $t=1$.
Mais $R$ est un polyn\^ome \`a coefficients entiers, on peut
donc calculer sa suite de Sturm et localiser les racines r\'eelles
de $R$. Si $R$ n'a pas de racine r\'eelles
dans $[0,1]$, alors on peut rester dans l'intervalle $[0,1]$.
Dans le cas contraire (par exemple si $R(t=0)$ et $R(t=1)$
ne sont pas de m\^eme signe), il faut passer dans le complexe.
On peut par exemple utiliser
une ligne polygonale $[0,1/2(1+i*k)] \cup [1/2(1+i*k),1]$,
il existe forcément un $k$ entier tel que la ligne polygonale ne
contient pas de racines du résultant. 
Pour déterminer une valeur de $k$ qui convient, 
on param\`etre chaque segment \`a l'aide d'un
param\`etre r\'eel, par exemple pour le premier segment~:
\[ t=\frac{u}{2}(1+ik), \quad u\in [0,1] \]
puis on remplace dans $R$, qui devient un polynôme $R_1(u)$ à coefficients
complexes. Pour savoir s'il a des racines r\'eelles $u\in [0,1]$,
on utilise les suites de Sturm sur le polyn\^ome $|R_1|^2(u)$
qui est \`a coefficients r\'eels.

Exemple~: on prend le polyn\^ome $P=x^4-5x-1$, on v\'erifie facilement
que $R$ ne s'annule pas sur $[0,1]$, les racines suivent les chemins
repr\'esent\'es sur la figure suivante~:
\begin{center}
\psset{unit=2cm}
\begin{pspicture}(-2.0,-2.0)(2.0,2.000)
\psset{linewidth=.5pt}
\psset{arrowsize=2pt 4}
\psset{linecolor=black}
\psline[linestyle=dashed]{->}(-2,0.0000)(2,0.0000)
\psline[linestyle=dashed]{->}(0.0000,-2)(0.0000,2)
\psset{linecolor=black}
\psline[fillcolor=black](     0.000000,     1.000000)(    -0.012500,     1.000078)(    -0.025000,     1.000313)(    -0.037500,     1.000705)(    -0.049999,     1.001255)(    -0.062498,     1.001966)(    -0.074995,     1.002840)(    -0.087490,     1.003878)(    -0.099980,     1.005085)(    -0.112464,     1.006463)(    -0.124939,     1.008016)(    -0.137402,     1.009748)(    -0.149849,     1.011663)(    -0.162275,     1.013765)(    -0.174675,     1.016057)(    -0.187043,     1.018543)(    -0.199371,     1.021227)(    -0.211652,     1.024110)(    -0.223878,     1.027197)(    -0.236039,     1.030487)(    -0.248126,     1.033982)(    -0.260129,     1.037682)(    -0.272036,     1.041584)(    -0.283839,     1.045688)(    -0.295526,     1.049988)(    -0.307086,     1.054482)(    -0.318510,     1.059162)(    -0.329788,     1.064023)(    -0.340912,     1.069056)(    -0.351872,     1.074252)(    -0.362663,     1.079603)(    -0.373277,     1.085098)(    -0.383710,     1.090728)(    -0.393957,     1.096481)(    -0.404016,     1.102346)(    -0.413884,     1.108314)(    -0.423560,     1.114372)(    -0.433044,     1.120512)(    -0.442337,     1.126722)(    -0.451440,     1.132994)(    -0.460355,     1.139318)(    -0.469085,     1.145685)(    -0.477632,     1.152087)(    -0.486001,     1.158517)(    -0.494195,     1.164967)(    -0.502219,     1.171432)(    -0.510076,     1.177905)(    -0.517771,     1.184381)(    -0.525308,     1.190855)(    -0.532693,     1.197322)(    -0.539929,     1.203779)(    -0.547022,     1.210221)(    -0.553975,     1.216646)(    -0.560794,     1.223050)(    -0.567482,     1.229431)(    -0.574044,     1.235787)(    -0.580484,     1.242116)(    -0.586806,     1.248416)(    -0.593014,     1.254685)(    -0.599111,     1.260922)(    -0.605102,     1.267126)(    -0.610990,     1.273296)(    -0.616779,     1.279431)(    -0.622470,     1.285531)(    -0.628069,     1.291594)(    -0.633577,     1.297621)(    -0.638998,     1.303611)(    -0.644335,     1.309564)(    -0.649589,     1.315479)(    -0.654765,     1.321357)(    -0.659863,     1.327197)(    -0.664888,     1.332999)(    -0.669840,     1.338764)(    -0.674722,     1.344492)(    -0.679536,     1.350182)(    -0.684285,     1.355835)(    -0.688970,     1.361451)(    -0.693593,     1.367031)(    -0.698155,     1.372574)(    -0.702659,     1.378080)(    -0.707107,     1.383551)(    -0.711499,     1.388986)(    -0.715837,     1.394386)(    -0.720123,     1.399751)(    -0.724358,     1.405081)(    -0.728544,     1.410377)(    -0.732682,     1.415640)(    -0.736772,     1.420868)(    -0.740817,     1.426063)(    -0.744817,     1.431226)(    -0.748774,     1.436356)(    -0.752689,     1.441454)(    -0.756562,     1.446520)(    -0.760395,     1.451555)(    -0.764188,     1.456559)(    -0.767944,     1.461532)(    -0.771661,     1.466475)(    -0.775342,     1.471388)(    -0.778987,     1.476271)(    -0.782597,     1.481125)(    -0.786173,     1.485950)
\psset{linecolor=green}
\psline[fillcolor=green](     1.000000,     0.000000)(     1.012422,     0.000000)(     1.024688,     0.000000)(     1.036798,     0.000000)(     1.048755,     0.000000)(     1.060558,     0.000000)(     1.072211,     0.000000)(     1.083714,     0.000000)(     1.095070,     0.000000)(     1.106281,     0.000000)(     1.117349,     0.000000)(     1.128277,     0.000000)(     1.139067,     0.000000)(     1.149723,     0.000000)(     1.160245,     0.000000)(     1.170638,     0.000000)(     1.180904,     0.000000)(     1.191044,     0.000000)(     1.201063,     0.000000)(     1.210962,     0.000000)(     1.220744,     0.000000)(     1.230412,     0.000000)(     1.239967,     0.000000)(     1.249413,     0.000000)(     1.258752,     0.000000)(     1.267986,     0.000000)(     1.277117,     0.000000)(     1.286148,     0.000000)(     1.295081,     0.000000)(     1.303917,     0.000000)(     1.312660,     0.000000)(     1.321310,     0.000000)(     1.329871,     0.000000)(     1.338344,     0.000000)(     1.346730,     0.000000)(     1.355032,     0.000000)(     1.363251,     0.000000)(     1.371390,     0.000000)(     1.379449,     0.000000)(     1.387431,     0.000000)(     1.395337,     0.000000)(     1.403168,     0.000000)(     1.410927,     0.000000)(     1.418614,     0.000000)(     1.426231,     0.000000)(     1.433780,     0.000000)(     1.441261,     0.000000)(     1.448677,     0.000000)(     1.456027,     0.000000)(     1.463315,     0.000000)(     1.470540,     0.000000)(     1.477704,     0.000000)(     1.484808,     0.000000)(     1.491853,     0.000000)(     1.498841,     0.000000)(     1.505772,     0.000000)(     1.512648,     0.000000)(     1.519468,     0.000000)(     1.526236,     0.000000)(     1.532950,     0.000000)(     1.539613,     0.000000)(     1.546225,     0.000000)(     1.552788,     0.000000)(     1.559301,     0.000000)(     1.565766,     0.000000)(     1.572183,     0.000000)(     1.578554,     0.000000)(     1.584879,     0.000000)(     1.591159,     0.000000)(     1.597394,     0.000000)(     1.603586,     0.000000)(     1.609735,     0.000000)(     1.615842,     0.000000)(     1.621907,     0.000000)(     1.627931,     0.000000)(     1.633915,     0.000000)(     1.639859,     0.000000)(     1.645765,     0.000000)(     1.651631,     0.000000)(     1.657460,     0.000000)(     1.663252,     0.000000)(     1.669007,     0.000000)(     1.674726,     0.000000)(     1.680409,     0.000000)(     1.686057,     0.000000)(     1.691670,     0.000000)(     1.697249,     0.000000)(     1.702795,     0.000000)(     1.708307,     0.000000)(     1.713787,     0.000000)(     1.719234,     0.000000)(     1.724650,     0.000000)(     1.730034,     0.000000)(     1.735387,     0.000000)(     1.740710,     0.000000)(     1.746003,     0.000000)(     1.751266,     0.000000)(     1.756500,     0.000000)(     1.761705,     0.000000)(     1.766881,     0.000000)(     1.772029,     0.000000)
\psset{linecolor=red}
\psline[fillcolor=red](    -1.000000,     0.000000)(    -0.987422,     0.000000)(    -0.974688,     0.000000)(    -0.961799,     0.000000)(    -0.948756,     0.000000)(    -0.935562,     0.000000)(    -0.922220,     0.000000)(    -0.908734,     0.000000)(    -0.895110,     0.000000)(    -0.881353,     0.000000)(    -0.867471,     0.000000)(    -0.853473,     0.000000)(    -0.839370,     0.000000)(    -0.825172,     0.000000)(    -0.810895,     0.000000)(    -0.796553,     0.000000)(    -0.782162,     0.000000)(    -0.767740,     0.000000)(    -0.753307,     0.000000)(    -0.738884,     0.000000)(    -0.724492,     0.000000)(    -0.710154,     0.000000)(    -0.695894,     0.000000)(    -0.681735,     0.000000)(    -0.667701,     0.000000)(    -0.653814,     0.000000)(    -0.640097,     0.000000)(    -0.626572,     0.000000)(    -0.613257,     0.000000)(    -0.600173,     0.000000)(    -0.587334,     0.000000)(    -0.574756,     0.000000)(    -0.562451,     0.000000)(    -0.550429,     0.000000)(    -0.538698,     0.000000)(    -0.527264,     0.000000)(    -0.516131,     0.000000)(    -0.505301,     0.000000)(    -0.494775,     0.000000)(    -0.484551,     0.000000)(    -0.474627,     0.000000)(    -0.464999,     0.000000)(    -0.455662,     0.000000)(    -0.446612,     0.000000)(    -0.437841,     0.000000)(    -0.429342,     0.000000)(    -0.421110,     0.000000)(    -0.413135,     0.000000)(    -0.405411,     0.000000)(    -0.397929,     0.000000)(    -0.390681,     0.000000)(    -0.383660,     0.000000)(    -0.376858,     0.000000)(    -0.370266,     0.000000)(    -0.363877,     0.000000)(    -0.357684,     0.000000)(    -0.351680,     0.000000)(    -0.345857,     0.000000)(    -0.340208,     0.000000)(    -0.334728,     0.000000)(    -0.329409,     0.000000)(    -0.324245,     0.000000)(    -0.319231,     0.000000)(    -0.314360,     0.000000)(    -0.309628,     0.000000)(    -0.305029,     0.000000)(    -0.300557,     0.000000)(    -0.296209,     0.000000)(    -0.291980,     0.000000)(    -0.287865,     0.000000)(    -0.283859,     0.000000)(    -0.279960,     0.000000)(    -0.276162,     0.000000)(    -0.272463,     0.000000)(    -0.268858,     0.000000)(    -0.265345,     0.000000)(    -0.261919,     0.000000)(    -0.258579,     0.000000)(    -0.255321,     0.000000)(    -0.252141,     0.000000)(    -0.249038,     0.000000)(    -0.246009,     0.000000)(    -0.243051,     0.000000)(    -0.240162,     0.000000)(    -0.237340,     0.000000)(    -0.234582,     0.000000)(    -0.231886,     0.000000)(    -0.229250,     0.000000)(    -0.226673,     0.000000)(    -0.224152,     0.000000)(    -0.221686,     0.000000)(    -0.219272,     0.000000)(    -0.216910,     0.000000)(    -0.214598,     0.000000)(    -0.212333,     0.000000)(    -0.210116,     0.000000)(    -0.207944,     0.000000)(    -0.205816,     0.000000)(    -0.203730,     0.000000)(    -0.201686,     0.000000)(    -0.199682,     0.000000)
\psset{linecolor=blue}
\psline[fillcolor=blue](     0.000000,    -1.000000)(    -0.012500,    -1.000078)(    -0.025000,    -1.000313)(    -0.037500,    -1.000705)(    -0.049999,    -1.001255)(    -0.062498,    -1.001966)(    -0.074995,    -1.002840)(    -0.087490,    -1.003878)(    -0.099980,    -1.005085)(    -0.112464,    -1.006463)(    -0.124939,    -1.008016)(    -0.137402,    -1.009748)(    -0.149849,    -1.011663)(    -0.162275,    -1.013765)(    -0.174675,    -1.016057)(    -0.187043,    -1.018543)(    -0.199371,    -1.021227)(    -0.211652,    -1.024110)(    -0.223878,    -1.027197)(    -0.236039,    -1.030487)(    -0.248126,    -1.033982)(    -0.260129,    -1.037682)(    -0.272036,    -1.041584)(    -0.283839,    -1.045688)(    -0.295526,    -1.049988)(    -0.307086,    -1.054482)(    -0.318510,    -1.059162)(    -0.329788,    -1.064023)(    -0.340912,    -1.069056)(    -0.351872,    -1.074252)(    -0.362663,    -1.079603)(    -0.373277,    -1.085098)(    -0.383710,    -1.090728)(    -0.393957,    -1.096481)(    -0.404016,    -1.102346)(    -0.413884,    -1.108314)(    -0.423560,    -1.114372)(    -0.433044,    -1.120512)(    -0.442337,    -1.126722)(    -0.451440,    -1.132994)(    -0.460355,    -1.139318)(    -0.469085,    -1.145685)(    -0.477632,    -1.152087)(    -0.486001,    -1.158517)(    -0.494195,    -1.164967)(    -0.502219,    -1.171432)(    -0.510076,    -1.177905)(    -0.517771,    -1.184381)(    -0.525308,    -1.190855)(    -0.532693,    -1.197322)(    -0.539929,    -1.203779)(    -0.547022,    -1.210221)(    -0.553975,    -1.216646)(    -0.560794,    -1.223050)(    -0.567482,    -1.229431)(    -0.574044,    -1.235787)(    -0.580484,    -1.242116)(    -0.586806,    -1.248416)(    -0.593014,    -1.254685)(    -0.599111,    -1.260922)(    -0.605102,    -1.267126)(    -0.610990,    -1.273296)(    -0.616779,    -1.279431)(    -0.622470,    -1.285531)(    -0.628069,    -1.291594)(    -0.633577,    -1.297621)(    -0.638998,    -1.303611)(    -0.644335,    -1.309564)(    -0.649589,    -1.315479)(    -0.654765,    -1.321357)(    -0.659863,    -1.327197)(    -0.664888,    -1.332999)(    -0.669840,    -1.338764)(    -0.674722,    -1.344492)(    -0.679536,    -1.350182)(    -0.684285,    -1.355835)(    -0.688970,    -1.361451)(    -0.693593,    -1.367031)(    -0.698155,    -1.372574)(    -0.702659,    -1.378080)(    -0.707107,    -1.383551)(    -0.711499,    -1.388986)(    -0.715837,    -1.394386)(    -0.720123,    -1.399751)(    -0.724358,    -1.405081)(    -0.728544,    -1.410377)(    -0.732682,    -1.415640)(    -0.736772,    -1.420868)(    -0.740817,    -1.426063)(    -0.744817,    -1.431226)(    -0.748774,    -1.436356)(    -0.752689,    -1.441454)(    -0.756562,    -1.446520)(    -0.760395,    -1.451555)(    -0.764188,    -1.456559)(    -0.767944,    -1.461532)(    -0.771661,    -1.466475)(    -0.775342,    -1.471388)(    -0.778987,    -1.476271)(    -0.782597,    -1.481125)(    -0.786173,    -1.485950)
\end{pspicture} 
\end{center}


\section{Les suites de Sturm complexes}
Il s'agit ici de g\'en\'eraliser le r\'esultat de localisation
de racines r\'eelles d'un polyn\^ome \`a coefficients r\'eels.
On compte les racines \`a l'int\'erieur d'un rectangle
$\gamma$ du plan complexe et on effectue une dichotomie pour diminuer la
taille du rectangle s'il contient des racines, jusqu'\`a la
pr\'ecision souhait\'ee. 

On suppose que $P$ ne s'annule pas sur
le rectangle $\gamma$. Pour compter les racines, on calcule le
nombre de tours que fait $P(z)$ autour de 0 lorsque $z$ parcourt le rectangle 
$\gamma$. Plus pr\'ecis\'ement, on calcule un indice que l'on incr\'emente
ou d\'ecr\'emente lorsque $P(z)$ traverse l'axe r\'eel ($\Im P(z)=0$) 
en tenant compte du sens de travers\'ee et du signe de $\Re P(z)$ lorsque $\Im
P(z)=0$~: si $\Re P(z)>0$ et $\Im P(z)$ croit ou si 
$\Re P(z)<0$ et $\Im P(z)$ d\'ecroit, on augmente l'indice
de 1 (car on tourne autour de 0 dans le sens trigonom\'etrique),
sinon on diminue l'indice de 1. Le nombre de racines de $P$ dans
$\gamma$ est alors \'egal au nombre de tours autour de 0
c'est-\`a-dire \`a l'indice divis\'e par 2.

{\bf Calcul de l'indice de mani\`ere exacte}\\
On utilise une g\'en\'eralisation des suites de Sturm. Sur un segment
$[a,b]$ du rectangle $\gamma$, on d\'efinit~:
\[ Q(t)=P(a+t(b-a)), \quad t \in [0,1]\]
Posons $S(t)=\Im Q(t)$ et $R(t)=\Re Q(t)$ et supposons que $S$ et $R$
sont premiers entre eux. On forme alors la suite
des oppos\'es des restes des divisions euclidiennes comme pour
les suites de Sturm r\'eelles avec $P$ et $P'$ et on compte
le nombre de changements de signes en $t=0$ et $t=1$. On montre
que la diff\'erence entre ces 2 nombres est \'egal \`a la variation
de l'indice sur le segment $[a,b]$~:
\begin{itemize}
\item on v\'erifie que le nombre
de changements de signes ne varie pas lorsque $t$ augmente sauf
si $S$ s'annule. 
\item Si $S$ s'annule en croissant avec $R$ positif,
alors ce nombre diminue de 1 de m\^eme que l'indice,
on regarde les 3 autres cas et on conclut.
\end{itemize}
Pour calculer l'indice sur $\gamma$, il suffit de sommer les 4 indices
sur chaque cot\'e. On divise ensuite par 2 pour obtenir le nombre
de racines.

{\bf Traitement des cas particuliers~}:
\begin{itemize}
\item Si $S$ s'annule en un sommet de $\gamma$, cela ne pose pas de 
probl\`emes, car pour le nombre de changements de
signe, tout se passe comme si $S$ \'etait du signe
de $R$ en ce sommet (ce qui revient \`a d\'eformer un peu $\gamma$).
Il faut n\'eanmoins s'assurer que $P$ ne s'annule pas sur
un sommet de rectangle, ce que l'on fait en \'eliminant
les racines rationnelles complexes de $P$ au pr\'ealable.
\item Si $S$ et $R$ ne sont pas premiers entre eux. Si leur pgcd $G$
est de degr\'e inf\'erieur strict au degr\'e de $P$, alors on peut utiliser
$G$ pour factoriser $P$ en 2 polyn\^omes de degr\'e strictement plus petit
et recommencer avec ces 2 polyn\^omes. Si leur pgcd est de degr\'e
maximal, alors $P$ est \`a une constante complexe $c$ pr\`es un multiple
du pgcd $G$ de $R$ et $S$, et $G$ est un polyn\^ome \`a coefficients r\'eels.
En multipliant $P$ par une constante complexe ad\'equate, on peut
supposer que la constante $c$ est r\'eelle. On peut compter
les racines de $P$ sur le segment $[a,b]$ par isolation des racines
de $G$.
On montre ensuite que sur un segment
parall\`ele \`a $[a,b]$ situ\'e \`a l'int\'erieur au rectangle \`a
distance $\epsilon$,
on a $S(t)=\epsilon Q'(t)+O(\epsilon^2)$ et $R(t)=Q(t)+O(\epsilon)$, 
le calcul de l'indice
sur le segment parall\`ele \`a $[a,b]$ infiniment proche
est alors \'egal \`a celui obtenu en prenant la suites
de Sturm r\'eelle de $Q$ et $-Q'$ entre $t=0$ et $t=1$.
\end{itemize}

{\bf Exemple}~:\\
Nombre de racines complexes de $x^3+i x +1$ dans le
rectangle de sommets oppos\'es 0 et $1+i$.
\begin{itemize}
\item Sur le segment $[0,1]$, $Q(t)=P(t)$ donc $S(t)=t$ et $R(t)=t^3+1$.
La suite de Sturm est form\'ee de $t,t^3+1,-t,-1$, en 0 un changement
de signe, en 1 1 changement de signe, contribution \`a l'indice de 0.
\item Sur $[1,1+i]$, on trouve $S(t)=-t^3+3t+1$ et $R(t)=-3t^2-t+2$.
La suite de Sturm est form\'ee de $S,R,(-20t-11)/9,-657/400$.
En 0, un changement de signe, en 1, aussi, indice 0.
\item Sur $[1+i,i]$, $S=3t^2-7t+3$, $R=-t^3+3t^2-2$, on trouve que
la contribution \`a l'indice est de 1
\item Sur $[i,0]$, $S=t^3-3t^2+3t-1$, $R=t$, la suite est donc
$S,R,1$, en $t=0$ on a un changement de signe et en $t=1$ 0
changements de signe, la contribution \`a l'indice est de 1.
\end{itemize}
On obtient donc un indice de 2, donc 1 racine complexe dans le
rectangle.

{\bf Remarque}\\
Pour l'impl\'ementation de cette m\'ethode, on utilise l'algorithme
du sous-r\'esultant pour calculer la suite de Sturm et on conserve
la liste des quotients au lieu de la liste des restes, car il est
plus efficace d'\'evaluer un quotient en $t=0$ et $t=1$ qu'un reste
puisque un quotient de la suite est g\'en\'eriquement de degr\'e 1.

\section{Suggestions}
\begin{itemize}
\item Certification des racines renvoy\'ees par la commande
de recherche de racines approch\'ees de votre logiciel
(\verb|proot| en Xcas).
\item Mise en oeuvre de la m\'ethode de la puissance
pour d\'eterminer une valeur approch\'ee d'une racine de
module maximal d'un polyn\^ome.
\item Calcul des racines par la méthode de Newton avec élimination
(en utilisant uniquement l'algorithme de Horner), illustration
des probl\`emes \'evoqu\'es pour cette m\'ethode.
Bassins d'attraction des racines pour une suite r\'ecurrente
d\'efinie par la m\'ethode de Newton.
\item Interactions entre factorisation exacte et approch\'ee.
\item Repr\'esentation de la variation des racines en fonction de $t$
dans la m\'ethode d'homotopie. Cas où deux racines se croisent.
\item Localisation des racines réelles par les suites de Sturm.
\item En utilisant le r\'esultant des polyn\^omes
$\Re P(x+iy)$ et $\Im P(x+iy)$ pour $x,y \in \R$,
montrer qu'on peut localiser la partie r\'eelle et la partie
imaginaire d'un polyn\^ome \`a l'aide de suites de Sturm r\'eelles.
Discuter l'efficacit\'e de cette m\'ethode en fonction du degr\'e.
\item Expliquer la m\'ethode des suites de Sturm complexes
en compl\'etant certaines esquisses de d\'emonstrations du texte.
Illustrer cette m\'ethode.
\item Que peut-on dire du point de vue efficacit\'e des algorithmes
n\'ecessaire au calcul des suites de Sturm complexe? 
(changement d'origine $Q(t)=P(a+t (b-a))$, algorithme d'Euclide, ...)
\item Connaissez-vous des m\'ethodes de calculs de racines
  rationnelles d'un polyn\^ome? Peuvent-elles se g\'en\'eraliser
\`a la recherche de racines rationnelles complexes?
\end{itemize}

\end{document}