\documentclass[11pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ {\`a} placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{14\baselineskip}
\topmargin=-6\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit{\'e} de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP24 Algo. d'Euclide \hspace{1cm}}\hfill   agreg 2011 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
%%\begin{multicols}{2}
% restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de  Sqrt
\exotitre{Suites de Sturm}
% !s!<c>
%---------------------------------------------------------------------------------------
%|                          Suites de Sturm                                             |
%----------------------------------------------------------------------------------------
%!s!
{\sc D{\'e}finition: } {\it Soit $R\in \reel(x)$. On dit que $R$ a un saut de $-\infty$ {\`a}
$+\infty$ en un r{\'e}el $t$ si $\lim_{x\to t,x<t} R(x)=-\infty$ et $\lim_{x\to
  t,x>t} R(x)=+\infty$. On appelle indice de Cauchy $I_{a,b}(R)$ le nombre de
sauts dans $]a,b[$ de  $-\infty$ {\`a} $+\infty$ moins le nombre de sauts dans
$]a,b[$ de  $+\infty$ {\`a} $-\infty$.} 

{\sc Exemple:} Si $R$ n'a que des p{\^o}les simples, $I_{a,b}(R)$ est la somme des
signes des r{\'e}sidus des p{\^o}les de $R$ qui sont dans $]a,b[$.


\bigskip
On consid{\`e}re une famille $P_1\dots P_n$ d'{\'e}l{\'e}ments de $\reel[x]$ et deux r{\'e}els
$a,b$ avec $a<b$. On dit que $(P_1,\dots, P_n)$ est de Sturm sur $[a,b]$ si:
\begin{itemize}
\item[-] $\forall k \in\{2,\dots,n-1\}, \forall x \in ]a,b[, P_k(x)=0
  \Rightarrow P_{k-1}(x)P_{k+1}(x)<0$
\item[-] $\forall x \in ]a,b[, P_n(x)\neq 0$  
\end{itemize}
On dira que c'est une suite de sturm g{\'e}n{\'e}ralis{\'e}e s'il existe un {\'e}l{\'e}ment $d$ de
$\reel[x]$ divisant tous les $P_i$ pour $i$ appartenant {\`a} $\{1,\dots,n\}$ tel
que $(P_i/d)$ soit de Sturm.

{\sc Proposition: }{\it Si $(P_i)_{1 \leq i\leq n}$ est une suite de Sturm g{\'e}n{\'e}ralis{\'e}e
sur $[a,b]$ telle que $P_1(a).P_1(b)\neq 0$, alors $I_{a,b}(R)=V(a)-V(b)$ o{\`u}
V(x) est le nombre de variation de signes dans la suite des termes non nuls de $P_1(x),\dots,P_n(x)$}

{\bf Application:} On souhaite trouver le nombre de z{\'e}ros d'un polyn{\^o}me $P$
dans l'intervalle $[a,b]$. On pose $P_1=P$ et $P_2=P'$. Puis on note pour $i>2$
$P_i$ l'oppos{\'e} du reste de la division de $P_{i-2}$ par $P_{i-1}$. Alors $P_i$
est de Sturm g{\'e}n{\'e}ralis{\'e} sur $[a,b]$ et l'indice de Cauchy de $P_1/P_2$ est le
nombre de z{\'e}ros de $P$ dans $[a,b]$.
\qu Etudier les fonctions \code{sign} (quelle est la valeur retourn{\'e}e, ou
-1,0,2) et \code{horner}. Comment evaluer un polyn{\^o}me du type:
\verb/P:=2*x^3+4*x-5/ en $\sqrt{3}$?
% sign(-5);sign(0);sign(3);//on teste ce que fait sign
% P:=2*x^3+4*x-5;
% horner(P,sqrt(3));
\qu Ecrire un programme qui calcule les $P_i$.
\qu En d{\'e}duire un programme qui calcule le nombre de z{\'e}ros de $P$ dans
$[a,b]$. (On n'utilisera pas la commande sturm de votre logiciel.)
%!s!<p>
% mysturm:=proc(P,a,b)
% local P1,P2,tmp,sa,sb,ho,v;
% P1:=P;P2:=diff(P,x);
% sa:=sign(horner(P1,a));
% sb:=sign(horner(P1,b));
% v:=0;//la difference des variations de signe.
% while(P2<>0)
% {
%   tmp:=P2;P2:=-rem(P1,P2,x);P1:=tmp;
%   ho:=sign(horner(P1,a));//vaut -1,0,1
%   if ((ho<>0)&&(ho<>sa)){sa:=ho;v++;} 
%   ho:=sign(horner(P1,b));
%   //on peut remarquer que (ho<>0)&&(ho<>sb) equivaut a: 
%   if (ho*sb=-1){sb:=ho;v--;} 
% }
%v;
%end;
%!s!
%P:=(x+1)^4*(x+2)*(x+4)^5*(x+3);
%mysturm(P,-5.5,1.5);
%mysturm(P,-3.5,1.5);
%mysturm(P,-2.5,1.5);
\qu Etudier la commande xcas correspondante ainsi que sa documentation. Quelle
diff{\'e}rence constatez vous?
%sturmab(P,-5.5,1.5);//par xcas seuls les changements de signe sont comptabilises, les zeros pairs ne comptent pas
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!s!<c>
% ---------------------------------------------------------------------------------------------------------
%!s! 
\exotitre{Polyn{\^o}me orthogonaux; approximants}
(Cf matrices creuses ou d{\'e}codage de codes cycliques). On consid{\`e}re un polyn{\^o}me $U=\sum_{i=0}^N u_i.x^i$ de terme constant non nul. On
note $(a_k,b_k,r_k)$ les 
coefficients de Bezout et le reste obtenus {\`a} l'{\'e}tape $k$ de l'algorithme
d'Euclide {\'e}tendu, de sorte que l'on ait: $a_k.x^{2n}+b_k.U=r_k$. On rappelle que
si l'on a une {\'e}galit{\'e} du type $$S.U=T+O(x^{2n})$$ o{\`u} $\deg S \leq n$ et $\deg T
<n$ alors il existe un unique entier $k$ tel que $\deg r_k \leq \deg T < \deg
r_{k-1}$, et il existe un polyn{\^o}me $W$  tel que $\deg W < \deg r_{k-1}-\deg r_k$
et $S=W.b_k, T=W.r_k$
\qu Cr{\'e}er une proc{\'e}dure donnant $S$ et $T$ s'ils sont premiers  entre eux. (Sans
utiliser la fonction bezout ni pad{\'e} de votre logiciel.
%!s!<p>
% ST:=proc(U,n)
% local a,aa,b,bb,r,rr,T,S,q;
% r:=U;rr:=x^(2*n);
% a:=1;b:=0;
% aa:=0;bb:=1;
% while (degree(r)>=n)
% {
%   q:=quo(r,rr);
%   tmp:=rr;rr:=normal(r-q*rr);r:=tmp;
%   tmp:=aa;aa:=normal(a-q*aa);a:=tmp;
%   tmp:=bb;bb:=normal(b-q*bb);b:=tmp;
%   print("ca doit etre nul",normal(a*U+x^(2*n)*b-r));
% };
% S:=a;T:=r;
% S,T;
% end;
% !s!
% normal( (x^3+1)*(x^3-1)*(x^2+x+1));
% !s!<c>
% on doit donc trouver S=x^3+1; T=-x^2-x-1 a facteur  pres 
%!s!
% ST((x^3-1)*(x^2+x+1),3);
\qusqu En utilisant une fonction d'orthogonalisation d{\'e}j{\`a} impl{\'e}ment{\'e}e, appliqu{\'e}e au
produit scalaire de matrice $(u_{i+j})_{0\leq i,j\leq n}$ donner un orthogonalis{\'e}
de la famille $\{1,x,\dots,x^n\}$ pour quelques valeurs de $U$.
%!s!<m>
% MU:=proc(U,n)
% local PU;
% PU:=[seq(coeff(convert(series(U,x=0,2*n),polynom),x,j),j=0..2*n+1)];
% matrix(n+1,n+1,(ii,jj)->PU[ii+jj]);
% end;
% !s!
% !s!<m>
% scalU:=proc(p,q,n)
% local PU;
% ([seq(coeff(p,x,ii),ii=0..n)]*MU(U,n)*transpose([seq(coeff(q,x,ii),ii=0..n)]))[0];
% end;
% !s!
\squ Etudier le cas o{\`u} $U$ est le d{\'e}veloppement en s{\'e}rie de
$${1\over {x+{1 \over {x^2+{1 \over {x^3+x+1+{1\over {x+2+{1\over x}}}}}}}}}$$
% purge(u):;U:=add(u[ii]*x^ii,ii=0..6);
% scalU(1,x,3);scalU(x^2,x^2,3);
% U:=1/(x+1/(x^2+1/(x^3+x+1+1/(x+2+1/x))));
% factor(gramschmidt([1,x,x^2,x^3,x^4],(p,q)->scalU(p,q,4)));
\squ Retrouver ces r{\'e}sultats avec l'algorithme\footnote{On pourra introduire le
  polyn{\^o}me r{\'e}ciproque de $S$ d{\'e}fini par $\hat{S}(x)=x^{\deg S}S(\frac{1}{x})$}
pr{\'e}c{\'e}dent.
%S:=[seq(pade(U,x,2*ii-1,ii),ii=1..4)]
%!s!<c>
%On constate bien que les denominateurs des approximants de pade coincident a facteur
%pres avec les polyn{\^o}mes reciproques des orthonormalises de schmidt
%(NB le polynome reciproque d'une polynome est le polynome cree a
%partir de la suite des coefficients pris dans l'ordre inverse. (Le
%facteur vient de la norme 1)
%!s!
%!s!<m>
%recip:=proc(P)
%normal(x^degree(P)*subst(P,x=1/x))
%end;
%!s!
%seq(recip(denom(ii)),ii=S); //donne bien les polyn{\^o}mes obtenus par gramschmidt
%
\qu Matrices creuses; polyn{\^o}me minimal: On se donne une matrice $M$ de taille
$N$ ayant au plus $c$ termes non nuls par ligne.
\squ Etudier (dans la documentation de xcas) l'algorithme utilis{\'e} par xcas pour
calculer le polyn{\^o}me minimal d'une matrice. Motiver la m{\'e}thode probabiliste en
explicitant les mauvais cas.
\squ Si $M$ est inversible, expliquer comment r{\'e}soudre un syst{\`e}me $M.a=b$
lorsque l'on connait $P$. Calculer le nombre d'op{\'e}rations sur le corps de base
si l'on connait $P$, et comparer le au cout du pivot de Gauss.
\squ On note $P_{u,v}$ un g{\'e}n{\'e}rateur de l'id{\'e}al $\{P, ^t v.P(M).u=0\}$. Montrer de
m{\^e}me qu'il existe des vecteurs $v,u$ tels que $P_{u,v}$ soit le polyn{\^o}me minimal
de $M$. Motiver le choix al{\'e}atoire de $u,v$.
\squ On note $u_l=^t v.M^l.u$ et $p_0,\dots,p_n$ les coefficients suivants de
$P_{u,v}(x)=\sum_{i=0}^n p_{n-i}x^i$. On pose $U=\sum\nolimits_{i=0}^{2n}u_i x^i $. On a alors
l'{\'e}galit{\'e}: $$P_{u,v}.U+x^{2n}Q=T$$
o{\`u} $\deg(T)<n$ et $\deg(P_{u,v}\leq n$. On peut donc trouver $P_{u,v}$ par la
m{\'e}thode pr{\'e}c{\'e}dente.

%%\newpage
%%\end{multicols}

\end{document}

