\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} TP07 M\'ethodes type Newton \hspace{1cm}}\hfill   agreg 2010 (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(1);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{M\'ethode de Newton}
\qu Comment peut on cr\'eer une fonction \`a partir d'un symbole? Par
exemple , si l'on a: \verb/f:=x^2+1;/ cr\'eer une fonction $g$ en
utilisant $f$ sans tout retaper.
% !s!<c>
%astuces, a retenir: sous xcas on utilise unapply qui est en general plus sur
%que la methode suivante avec subs. 
%!s!
% f:=x^2+1; g:=unapply(f,x);expand(g(x+2));
% g:=t->subs(x=t,f);g(x+2);
\qu On consid\`ere la fonction \verb\f:=x->(x^2-2);\ Faites calculer la
d\'eriv\'ee $\frac{df}{dx}$
\qu On cr\'ee la fonction
\linebreak\verb\df:=x->eval(diff(f(x),x))\. Tester si ca marche en
calculant \code{df(x);} et \verb/u:=x^2;df(u);/. Comment d\'eriver une
fonction directement?
% f:=x->x^2-2;
% df:=x->eval(diff(f(x),x));
% df(x);u:=x^2;df(u);
% !s!<c>
% ca ne marche pas toujours, mieux vaut utiliser unapply, Ou mieux,
% deriver une fonction
%!s!
% df:=unapply(diff(f(x),x),x);df(x);df(u);
% D(g);fonction_diff(g);D(g)(5);
\qu Comment travaille t'on avec $k$ chiffres significatifs? Essayer
d'utiliser une variable d'environnement. Quelle est la valeur minimale
du nombre de chiffres significatifs pour obtenir $13.26*2$ \`a $10^{-1}$
pr\`es.
% !s!<c>
% pour changer la valeur par defaut, soit dans le menu, soit avec la variable
% Digits, mais c'est pris en compte a partir de l'evaluation suivante.
% Ex: Digits:=100;sqrt(2.0); sur une meme ligne ne marche pas.
%!s!
% Digits:=1;
% 13*2.;evalf(13*2,3);
% Digits:=2;
% 13.26*2;
\qu On consid\`ere la suite $(u_n)$ obtenue par la m\'ethode de Newton
avec $u_0=1$. Faire \code{U:=1.;} puis affecter \`a $U$ la valeur
suivante de la suite $(u_n)$. En validant cette ligne plusieurs fois,
v\'erifier que votre formule donne bien une valeur approch\'ee de
$\sqrt{2}$.
\qu Comparer avec la m\'ethode de H\'eron d'Alexandrie: On fait la moyenne
de deux approximations de $\sqrt{d}$: $u_0=a; u_{n+1}=\frac{u_n+d/u_n}{2}$
\qu NB: Pour faire un calcul sans afficher le r\'esultat on met \footnote{En mode
  maple. \danger, en mode xcas c'est \code{:;}} \code{:} au
lieu de \code{;} On travaille maintenant avec 1000  d\'ecimales par
d\'efaut. Recommencer le calcul des $u_n$ sans les faire afficher, et \`a
chaque \'etape faites calculer \code{a:=U-evalf(sqrt(2)):} et afficher \code{evalf(a,15);} Grosso modo,
quel est le nombre de d\'ecimales exactes  de $u_{n+1}$ en fonction de
celui de $u_n$. En combien d'\'etapes   obtient on 10000 d\'ecimales
exactes?
\qu Interpr\'eter les illustrations pr\'ec\'edentes en terme de convergence quadratique.
% Digits:=10000;
% U:=1.:
%!s!<c>
% On fait 14 iterations de la methode de Newton, et on affiche la difference
% avec racine de 2. La majoration du reste montre qu'asymptotiquement le nombre
% de decimales exactes est multiplie par 2 a chaque iteration. Ce qui correspond
% bien a une majoration du type: |u_{n+1}-l|<C|u_n-l|^2
%
%!s!
% normal(x-f(x)/df(x));#On trouve x/2 +1/x c'est donc Heron.
% r:=evalf(sqrt(2));#on ne le calcule qu'une fois.
% for i from 1 to 14 do U:=U/2+1/U:a:=U-r:print(evalf(a,15)) od:
% Digits:=10;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% !s!<c>
% -------------------------------------------Jordan, Dunford--------------------------------------
%!s!
\exo\footnote{On pourra dans un premier temps ne lire que l'introduction et
  passer \`a l'exercice suivant si le temps presse.}
Lorsque l'on consid\`ere la d\'ecomposition de Dunford d'un endomorphisme $u=d+n$
de $\complex^n$ et sa preuve utilisant les sous espaces
caract\'eristiques, on ne voit pas comment  trouver $d$ et $n$ sans connaitre les
valeurs propres de $u$, et bien que $d$ et $n$ soient des polyn\^omes
en $u$ les propri\'etes des coefficients de $d$ et $n$ en fonction de
ceux de $u$ sont assez dissimul\'ees. Par exemple, on peut trouver un
argument simple pour montrer que si $u$ est r\'eel, $d$ et $n$ aussi,
mais que peut on dire avec  d'autres corps?
\qu
 Cr\'eer les matrices companion $C_1$ et $C_2$ des polyn\^omes $(x^3-8)^2$ et
$(x^2-4)^3$. Ainsi que la matrice $A$ diagonale par blocs de $C_1$ et $C_2$.
\squ Justifier sans calculs que sa d\'ecomposition de Dunford est r\'eelle.
% !s!<c>
% La decomposition d'une matrice reelle est reelle: par conjugaison et unicite
% de la decomp de Dunford
% !s!
% C1:=companion((X^3-8)^2,X);
% C2:=companion((X^2-4)^3,X);
% A:=diag(C1,C2);
\squ \danger On se mettra en mode complexe, en on activera les racines carr\'ees,
pour donner une chance \`a jordan de fonctionner.
De t\^ete, et aussi avec votre logiciel, donner la forme de jordan de
$A$. 
% cas_setup(0,0,1,1,0,1e-10,10,[1,50,0,25],0,1,0); #mode complexe est racines carrees.
\squ Quelle est sa forme de jordan rationnelle de $A$ (avec et sans
les racines carr\'ees et le mode complexe activ\'es)? Que repr\'esente ses blocs
diagonaux? (On pourra aussi s'aider de \verb/rat_jordan(companion((x^3-2)^2,x));/. Quelle est la d\'ecomposition de dunford de \verb/rat_jordan(A)/?
% rat_jordan(A);
% rat_jordan(companion((x^3-2)^2,x));
\squ Trouver la d\'ecomposition de jordan de $A$ en r\'ecup\'erant la matrice de
passage.
% J:=jordan(A,'Q');Q;
% f:=(i,j)->if i=j then J[i,j] else 0 fi;
% dia:=matrix(op(dim(J)),f);
% S:=normal(Q*dia*Q^(-1));N:=A-S; #on remarque que les coeff sont dans le meme corps que ceux de A
% normal(S*N-N*S); # verification:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{syntaxe pr\'el\'eminaire}
\qu On pose \verb/p:=x^2+1/; En utilisant le symbole $p$, cr\'eer la
fonction $f$ qui \`a $x$ associe la d\'eriv\'ee de $p$. On pose
\verb/u:=x^2;/ v\'erifier \verb/f(x);/ et \verb/f(u);/
% u:=x^2;p:=x^2+1;
% f:=x->eval(diff(p,x));
% f(x);
% f(u); #ca ne convient donc pas. mieux vaut faire unapply.
% f:=unapply(diff(p,x),x);
%f(x);f(u);
\qu Comment obtient t'on les couples de bezout des polyn\^omes. $x^2+2$
et $x$?
%d:=gcdex(x^2+2,x,'s','t');normal((x^2+2)*s+t*x); # attention on trouve d et non 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\N{{\cal N}}  
\exotitre{Mini texte\footnote{Cf
  le\c con polyn\^omes d'endomorphismes, \dots} sur la D\'ecomposition de ``Dunford''}
Nous allons donc fournir une preuve algorithmique de cette
d\'ecomposition qui permettra de r\'esoudre   ces probl\`emes.

Soit $k$ un corps de caract\'eristique nulle, et $k[u]$ une $k$-alg\`ebre
de dimension finie. Notons $m$ le polyn\^ome minimal de $u$ sur $k$. (On suppose
$\deg m>1$).  On a alors $k[u]\simeq k[X]/(m)$. Il s'agit de montrer
qu'il existe des \'el\'ements\footnote{d\'ecomposition semi-simple+nilpotent} $s_u,n_u$ de $k[u]$ tels que: $u=s_u+n_u$,
le polyn\^ome minimal de $s_u$ soit sans facteurs multiples, et 
que $n_u$ soit nilpotent. Nous allons pour cela cr\'eer une suite
r\'ecurrente comme dans la m\'ethode de Newton, qui sera
stationnaire de limite $s_u$. Notons $\N$ le radical nilpotent de
$k[u]$, autrement dit l'ensemble des \'el\'ements nilpotents de $k[u]$
(c'est un id\'eal, et on
pourrait montrer que c'est l'intersection des id\'eaux premiers 
de $k[u]$ ce que l'on n'utilisera pas). Notons $p(u)$ un g\'en\'erateur de $\N$ o\`u $p\in k[X]$. On
remarque alors que $p$ est sans facteurs multiples, nous allons
trouver un \'el\'ement $s$ dans $k[u]$ tel que $p(s)=0$ par la m\'ethode de
Newton (Qui se terminera ici en un nombre fini d'it\'erations).

Comme $p$ et $p'$ sont premiers entre eux, on peut \'ecrire un multiple de $p'(u)$
comme la somme d'un \'el\'ement nilpotent et d'un inversible, ce qui
prouve que $p'(u)$ est un inversible de $k[u]$.

On consid\`ere alors la suite r\'ecurrente d'\'el\'ements  de $k[u]$:
$$u_0=u,u_{n+1}=u_n-p(u_n)/p'(u_n)$$
On peut montrer de l'on a dans $k[X,Y]$:
$$p(X+Y)-p(X)-Y.p'(X) \in (Y^2)$$
On en d\'eduit donc que si la suite est bien d\'efinie jusqu'\`a l'entier
$n$ (ie $p'(u_{n-1})$ est inversible dans $k[u]$), alors  $p(u_n) \in
\N^{2^n}$. Nous pouvons alors montrer que 
$u_{n+1}$ existe encore lorsque $n$ est sup\'erieur \`a $1$ puisque
$p'(u_{n})-p'(u_{n-1})$ est nilpotent. Il est en effet
dans l'id\'eal engendr\'e par $u_{n}-u_{n-1}$ qui est inclus dans 
$(p(u_{n-1}))\subset \N$, et comme l'anneau $k[u]$ est commutatif, la somme
d'un nilpotent et d'un inversible est un inversible.
%%pour obtenir l'inverse de 1+n on regarde la serie: 1/(1+n)
On peut donc conclure que $p'(u_n)$ est inversible et donc que $u_{n+1}$ existe. 
 

Il est maintenant clair que la suite $u_n$ est constante \`a
partir d'un certain rang, notons $s_u$ sa limite, alors l'\'el\'ement
$n_u=u-s_u$ est nilpotent 
% !s!<c>
% n_u est dans l'ideal N car c'est la somme des u_n-u_{n+1} qui sont tous dans N, donc n_u est nilpotent. 
et $p$ est le polyn\^ome minimal de $s_u$.
% Pour tout polynome r, r(u) est somme de r(s_u) et d'un element de N, donc r(s_u)=0 implique
% que r(u) est dans N et donc que p divise r par definition de p. donc p est le pol min de s 
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\qusqu Trouver un exemple \`a coefficients entiers de matrice o\`u l'algorithme
fasse au moins deux 
it\'erations avec des valeurs propres diff\'erentes et non rationnelles.
% !s!<c>
%Pour que l'algorithme fasse au moins 2 iterations, on met un facteur a la
%puissance 5 dans le polynome minimal. Pour etre sur du resultat on prend une
%matrice diagonale par blocs de type compagnon
%!s!
% A:=diag([companion((x^3-2)^5,x),companion(x^5-2*x^2,x)]);
\squ Programmez cette methode pour trouver la r\'eduction de Dunford de votre
exemple, et v\'erifier que N et S commutent bien. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!s!<p>
% Dunford:=proc(A)
% m:=pcar(A,x,lagrange);
% p:=unapply(normal(m/(gcd(m,diff(m,x)))),x);
% dp:=unapply(normal(diff(p(x),x)),x);
% u:=x;
% #on itere
% while rem(p(u),m,x) <> 0 do
% d:=gcdex(m,dp(u),x,'s','t');
% invdp:=t/d;
% u:=rem(u-p(u)*invdp,m,x); 
% od;
% horner(u,A); 
% end proc;
% !s!
% !s!<c>
% Pour avoir au moins deux it\'erations, il faut un facteur de degre au moins 4
% dans le polynome minimal, ce que l'on obtient par exemple avec
%companion((x^3-2)^5,x)
%!s!
% S:=Dunford(A);
% N:=A-S; 
% N*S-S*N; # S et N commutent bien
% mu:=pmin(S,x); gcd(mu,diff(mu,x)); #S est bien diagonalisable
\qu Expliquer pourquoi $p$ est sans facteurs multiples, et comment
trouver facilement $p$ \`a partir de $m$. Justifier la caract\'eristique nulle.
%!s!<c>
%  p = m/D ou D est le pgcd de m et m'
%  NB:en caract q K=F_q(T), m=X^q-T, alors m'=0, mais p n'est pas 1 car
%  l'algebre n'a pas de nilpotents.
%!s!
\qu On pourra expliquer pourquoi dans un anneau commutatif la somme
d'un inversible et d'un nilpotent est un inversible
% !s!<c>
% 1/(e(1+n/e)) se developpe en somme finie, et c'est l'inverse de e+n
%!s!
\qu Pourquoi $n_u$ est il nilpotent, et pourquoi $p$ est il le
polyn\^ome minimal de $s_u$
\qusqu Expliquer le lien avec la d\'ecomposition de Dunford.
\squ Montrer que l'on peut travailler avec le polyn\^ome caract\'eristique
\`a la place du polyn\^ome minimal.



\newpage
\end{multicols}

\end{document}

