\documentclass[12pt,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}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP11 \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{Polyn\^ome minimal. (Cf Probl\`emes de rang et applications )}
%!s!<c>
%-------------------------Polynome minimal-----------------------------------------------
%!s!
\qusqu Comment cr\'eer un polyn\^ome \`a partir de la liste de ses coefficients. (NB:
Pour xcas, un polyn\^ome n'est autre que la liste des coefficients. Ex: $x^2+1$
est un symbole pour xcas. 
%v:=[seq(ii,ii=1..8)];
%poly2symb(v,x);
\squ Comment renverser une liste?
%revlist(v);
\squ Comment \'evaluer un polyn\^ome lorsqu'il est sous forme d'un symbole. Comment
le faire \`a partir de la liste de ses  coefficients.
% P:=x^2+1;LP:=[1,0,1];
% subst(P,x=sqrt(2));
%unapply(P,x)(sqrt(2));//c'est preferable et plus Ex pour creer une fonction
% peval(LP,sqrt(2));
Soit $v$ un vecteur et $u$ un endomorphisme de $E$ (E ev de dim $n$). On note
$P_{u,v}$ un g\'en\'erateur de l'id\'eal: $\{P \in k[x], P(u)(v)=0\}$.
\qu Expliquer sur un exemple de taille $n$ al\'eatoire (on commencera par
$n=8$)comment on peut trouver $P_{u,v}$ \`a partir d'une recherche de noyau. 
% n:=8:;v:=[seq(ii,ii=1..n)]; A:=matrix(n,n,(i0,j0)-> rand(20)-10);
% B:=v; AA:=v;
%!s!<c>
% eviter cette syntaxe maple en mode xcas: for ii from 1 to n do AA:=A*AA;B:=B,AA; od;
%!s!
% for(ii:=1;ii<=n;ii++){ AA:=A*AA;B:=B,AA;}
% N:=nullspace(transpose([B]))[0];
% !s!<c>
%Attention, les polyn\^omes commencent a la puissance maximale, il faut inverser l'ordre
%!s! 
% P:=poly2symb(revlist(N),x);
% normal(subst(P,x=A));
\qu Recommencer sur un exemple o\`u $P_{u,v}$ est de degr\'e inf\'erieur \`a la dimension
de $E$. 
% A:=diag(companion(x^4-1,x),companion((x^2-1)^2,x));
% B:=v; AA:=v
%!s!<c>
% eviter cette syntaxe maple en mode xcas: for ii from 1 to n do AA:=A*AA;B:=B,AA; od;
% !s!
% for(ii:=1;ii<=n;ii++){ AA:=A*AA;B:=B,AA;}
% nullspace(B);
%N:=nullspace(transpose([B]))[0];
% P:=poly2symb(revlist(N),x);
% normal(subst(P,x=A));
\squ Optimiser le calcul des $A^k(v)$, et regardez si le polyn\^ome obtenu annule
$A$. Estimer le nombre d'op\'erations sur le corps de base.
% !s!<c>
%On a calcul\'e les A^k(v) par recurence. AA est un vecteur donc A*AA a un cout de
%n^2, et l'on fait n tours, donc c'est en O(n^3)
%!s!
\squ Justifier l'interet de cette m\'ethode pour trouver le polyn\^ome minimal de
$u$.
% !s!<c>
% Il existe toujours un vecteur v tel que P_(u,v)=pmin(u), les vecteurs a eviter
% sont dans ker(P(u)) ou P divise pmin, donc nom fini despace vectoriels a eviter.  
%!s!
\qu Etudiez dans la documentation de xcas les diff\'erentes options pour calculer
le polyn\^ome caract\'eristique. Expliquez l'int\'eret de l'option pmin. Illustrez sur
des exemples.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{ODE}
\qu Etudiez la fonction de dessin de champ de vecteurs. Comment faire apparaitre
la solution passant par le point o\`u l'on clique avec las souris?
\qu Etudiez l'exemple ODE d'xcas.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Localisation des z\'eros. Th Rolle, Suites de Sturm}
% !s!<c>
%---------------------------------------------------------------------------------------
%|                          Suites de Sturm                                             |
%----------------------------------------------------------------------------------------
%!s!
{\sc D\'efinition: } {\it Soit $R\in \reel(x)$. On dit que $R$ a un saut de $-\infty$ \`a
$+\infty$ en un r\'eel $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\^oles simples, $I_{a,b}(R)$ est la somme des
signes des r\'esidus des p\^oles de $R$ qui sont dans $]a,b[$.


\bigskip
On consid\`ere une famille $P_1\dots P_n$ d'\'el\'ements de $\reel[x]$ et deux r\'eels
$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\'en\'eralis\'ee s'il existe un \'el\'ement $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\'en\'eralis\'ee
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\'eros d'un polyn\^ome $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\'en\'eralis\'e sur $[a,b]$ et l'indice de Cauchy de $P_1/P_2$ est le
nombre de z\'eros de $P$ dans $[a,b]$.
\qu Etudier les fonctions \code{sign} (quelle est la valeur retourn\'ee, ou
-1,0,2) et \code{horner}. Comment evaluer un polyn\^ome 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\'eduire un programme qui calcule le nombre de z\'eros 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\'erence constatez vous?
%sturmab(P,-5.5,1.5);//par xcas seuls les changements de signe sont comptabilises, les zeros pairs ne comptent pas

%\newpage
%\end{multicols}

\end{document}

