% \documentclass[landscape,12pt,a4paper]{article}
% \textwidth 26cm
% \evensidemargin 0mm
% \oddsidemargin 0mm
% \topmargin 0mm
\documentclass{article}
\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight26.7cm
\parskip=3pt
\parindent=0pt

\usepackage{graphicx}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{times}
\usepackage{ifpdf}
\usepackage{makeidx}
\ifpdf
 \usepackage[pdftex,colorlinks]{hyperref}
\else
 \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
 \fi

\newtheorem{rem}{Remarque}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\faux}{$\square\;$}
\newcommand{\vrai}{$\square\;$}
%\newcommand{\vrai}{$\boxtimes\;$}
\newcommand{\itemf}{\item\faux}
\newcommand{\itemv}{\item\vrai}

\newtheorem{exo}{Exercice}[section]


\begin{document}

\noindent M1 Alg\`ebre effective \hfill Localisation des racines \hfill UGA

{\bf Exercice 1~: Suites de Sturm}\\
Soit $P=-x^7+x^4+12x-5$. 
\begin{enumerate}
\item Calculer la suite de Sturm de $P$
 en utilisant l'instruction de division euclidienne
de polynômes de la calculatrice
\item Déterminer le nombre de racines réelles de $P$ comprises
entre -2 et 0 en utilisant les suites de Sturm, on donnera les
d\'etails des calculs. En déduire un rationnel approchant une racine
réelle négative de $P$ par dichotomie à 0.01 près.
\item
D\'eterminer le nombre total de racines r\'eelles
de ce polyn\^ome en utilisant une majoration du module des racines.
\item Déterminer des intervalles d'isolation de toutes les racines réelles
de $P$.
\end{enumerate}

{\bf Exercice 2~: Méthode de localisation hybride}\\
Soit $P(x)=x^5+3x+1$.
\begin{enumerate}
\item D\'eterminer des valeurs approch\'ees
des racines complexes de $P$ (instruction \verb|proot| de Xcas). 
\item En d\'eduire des boules dans le
plan complexe contenant exactement une racine de $P$ et
de rayon plus petit que \verb|1e-11|. 
\item En utilisant une étape de la m\'ethode
de Newton avec du calcul exact, d\'eterminer des valeurs approch\'ees
certifi\'ees \`a \verb|1e-20| pr\`es des racines complexes de $P$.
\item Combien d'étapes de la méthode de Newton sont nécessaires
pour obtenir une approximation certifiée avec une précision
fixée $\varepsilon>0$~? Indication~: on double approximativement
la pr\'ecision \`a chaque it\'eration
\item Peut-on en estimer le cout~? Indication~: pour la derni\`ere
it\'eration, on peut arrondir le num\'erateur et le d\'enominateur
d'une racine approch\'ee $z$ \`a $k=O(-\ln(\varepsilon))$ bits,
et montrer que le cout de Horner en $z$ est
en $O(n^2k^2)$ avec $n$=degre$(P)$.
\end{enumerate}

{\bf Exercice 3~: Factorisation sur les rationnels}\\
Soit $P(x)=x^5+x+1$.
\begin{enumerate}
\item
Calculer avec un logiciel des valeurs numériques approchées des racines
complexes de $P$. 
\item Trouver les combinaisons de racines
dont la somme est entière (aux arrondis près). 
\item En déduire la factorisation
en facteurs irréductibles sur $\mathbb{Z}$ de $P$.
\item
Que peut-on dire de la complexité de cette méthode pour trouver la
factorisation d'un polynôme de $\mathbb{Q}[X]$ de degré $n$~?
\end{enumerate}

{\bf TP exercice 1~: Sturm}\\
Implémenter le calcul de la suite de Sturm en calculant la liste des
quotients afin d'optimiser les calculs en un point.
Puis faire une fonction qui détermine le nombre de changements de signe
(on pourra commencer par enlever les 0 avec \verb|remove|) et enfin
une fonction qui renvoie le nombre de racines réelles d'un polynôme
dans un intervalle.

{\bf TP exercice 2~: Règle de Descartes}\\
Soit le polyn\^ome $P(x)=2\,x^{3}-x^{2}-4\,x+1$.
On veut d\'eterminer des intervalles d'isolation des racines r\'eelles
positives de $P$.
\begin{enumerate} 
\item Impl\'ementer la r\`egle de Descartes sur $]0,+\infty[$
(nombre de racines $\leq$ au nombre de changements de signe des
coefficients). On peut utiliser \verb|coeffs| pour avoir la
liste des coefficients de $P$.
\item Pour faire de m\^eme sur $]0,1[$, on fait d'abord
le changement de variables $x\rightarrow 1/x$ 
($\tilde{P}(x)=x^3P(1/x)$) qui permet
de se ramener \`a des racines dans $]1,+\infty[$ puis  
$x \rightarrow x+1$ ($\tilde{P}(x)=P(x+1)$) sur $]0,+\infty[$.
On peut utiliser \verb|revlist| pour calculer $\tilde{P}$
et \verb|ptayl| pour faire le changement d'origine.
\item Pour faire de m\^eme sur $]a,b[$, on pose $P(x)=Q((b-a)t+a)$.
\item D\'eterminer une majoration $M$ des racines de $P$ en module.
Puis par dichotomie, trouver des intervalles d'isolation
des racines de $P$.
\end{enumerate}

{\bf TP exercice 3~: localisation hybride}\\
Programmer la recherche approchée
de racines complexes en utilisant la méthode
de Newton. Pour éliminer implicitement les racines $z_j$ de $P$ déjà déterminées
$$ P(x) = Q(x) \prod_{j=1}^k (x-z_j) $$
on utilise le pas de Newton modifié~:
$$ z-\frac{Q(z)}{Q'(z)}=z-\frac{1}{\frac{Q'(z)}{Q(z)}}
= z-\frac{1}{\frac{P'(z)}{P(z)}-\sum_{j=1}^k \frac{1}{z-z_j}} $$

\end{document}
