<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% \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 Ã&nbsp; 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&gt;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Ã&nbsp; 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}
</pre></body></html>