\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}{15\baselineskip}
\topmargin=-6\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{0.5cm}  tp08: Interpolation \hspace{0.5cm}}\hfill   agreg 2011-2012 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/M1MME})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\it  Astuces du jour pour l'interface:
    
1)  N'oubliez pas la possibilit\'e d'ins\'erer une
  instruction d\'ej\`a tap\'ee en utilisant   \verb/ALT/ fleche haut.

2) Les sorties xcas (ce qui est en noir) peuvent \^etre s\'electionn\'ees et remani\'ees
gr\^ace \`a des op\'erations sur la selection. Ex developper (CTRL n), factoriser
(CTRL f), ou menus deroulants. On peut aussi les copier en tant que Latex avec
CTRL t.
}

\exotitre{en xcas, interpolation}
\qusqu Programmez le polyn\^ome $L_1$ d'interpolation de Lagrange d'une liste
$(x_i,y_i)_{0\leq i\leq n}$ par la formule  de Lagrange (et non par les
diff\'erences divis\'ees). On fera des boucles, et on n'utilisera pas les fonctions
\verb/sum/ et \verb/product/ d'xcas. On retournera une forme d\'evelopp\'ee
simplifi\'ee du polyn\^ome. ( Pr\'ef\'erez \verb/normal/ pour les calculs lourds)
%!s!<p>
% L_1(a):={
%   //a[0]: la liste des x_i, a[1] celle des y_i
%   local s,n,p,j,k;
%   s:=0;n:=coldim(a);
%   for(j:=0;j<n;j++){
%     p:=a[1,j];// on initialise p a chaque tour a y_j
%     for(k:=0;k<n;k++){
%       if(k != j){
%         p:=normal(p*(x-a[0,k])/(a[0,j]-a[0,k]));
%       };
%     };
%     s:=s+p;
%   };
% s
% }:;
% !s!
\qusqu Cr\'eez une fonction \verb/c(a,b,n)/ qui retourne la liste des
$\left(a+\frac{k.(b-a)}{n}\right)_{0\leq k \leq n}$
% c(a,b,n):=[seq(a+k*(b-a)/n,k=0..n)];
% f1:=x->1/(x^2+1);
\squ En utilisant par exemple la commande \verb/apply/, cr\'eez la liste des
\verb/[(c,f1(c)]/ lorsque $c$ d\'ecrit la liste \verb/c(-5,5,3)/ o\`u $f_1$ est
d\'efinie par $f_1:x \mapsto \frac{1}{x^2+1}$
% M:=transpose(apply(j->[j,f1(j)],c(-5,5,3)));
\squ Calculez l'interpolation de Lagrange \`a 4 termes avec votre programme, et
v\'erifiez avec la fonction xcas que c'est  correct.
%L_1(M);
%normal(lagrange(M)-L_1(M)); // doit etre nul
\squ Assurez vous que xcas effectue ce calcul avec des rationnels exacts, et
illustrez la diff\'erence de complexit\'e de ces deux m\'ethodes avec 41 points.
% M:=transpose(apply(j->[j,f1(j)],c(-5,5,40)));
% lag40exact:=L_1(M);
% time(lagrange(M));//xcas utilise les differences divisees
% normal(lagrange(M)-lag40exact);//verification, ca doit etre nul
\squ Illustrez maintenant la r\'epercussion des erreurs d'arrondis selon les 2
m\'ethodes. (On travaillera avec 15 chiffres car en dessous xcas travaille avec
plus de chiffres qu'il n'en affiche). On affichera la norme $2$ du vecteur des
coefficients de la diff\'erence entre le calcul en flottants, et la valeur
approch\'ee du calcul exact. 
% Digits:=15;// On travaille avec 15 chiffres significatifs.
%!s!<c>
%Pour illustrer la repercussion des erreurs d'arrondis dans le cadre d'un calcul
%entierement flottant, on compare les polynomes trouves en utilisant Ma (la
%valeur flottante de M), avec la valeur approchee du polynome de lagrange exact.
%Attention a ce que la forme exacte soit deja developpee et simplifiee, sinon il
%y aura encore de la propagation d'erreur d'arrondis a ce niveau.
%!s!
% Ma:=approx(M); 
% err1:=normal(L_1(Ma)-lag40exact); //l'erreur par lagrange
% err2:=normal(lagrange(Ma)-lag40exact);// l'erreur par differences divisees
% norm(symb2poly(err1,x));// de l'ordre de 10^(-7)
% norm(symb2poly(err2,x));// de l'ordre de 10^(-11) 
\qusqu Repr\'esentez la fonction $f_1$  sur $[-5,5]$
ainsi que ses interpolations de Lagrange \`a $n+1$ points \'equir\'epartis dans cet
intervalle, pour $n\in\{1,\dots,30\}$ (On travaillera en flottants). On pourra
(en mode\footnote{pour les animations il faut ouvrir une zone de g\'eom\'etrie via
  le menu d\'eroulant} g\'eom\'etrie 2D) faire appara\^\i tre un bouton avec la commande \verb/element/
et afficher le dessin correspondant \`a la valeur de $n$ r\'egl\'ee par le
bouton. (on r\'eglera le pas \`a 1). NB: \'etudiez les r\'eglages du bouton de type
clic-clic. NB: La zone g\'eom\'etrie est r\'eevalu\'ee \`a chaque d\'eplacement du bouton,
donc optimisez les calculs dans cette zone. 
\squ Ajoutez sur le dessin les points d'interpolation en gros carr\'e rouge. On
pourra utiliser le raccourci clavier pour obtenir les options graphiques. (il
est rappel\'e dans le menu d\'eroulant)
\squ Pensez vous qu'il y ait une convergence, ou une convergence uniforme sur
$[-5,5]$? 
%!s!<c>
%Ce dessin est calcule une fois pour toute, si l'on met cette instruction qui ne
%d\'epend pas de n dans la partie geometrie, elle sera reevaluee a chaque
%changement de n par le bouton
%!s!
% F1:=plotfunc(f1(x),x=-5..5,,xstep=0.1,display=blue+line_width_3):;

%!s!<g>
% F1;
% n:=element(1..31,1,1);//donne un bouton
% M:=approx(transpose(apply(j->[j,f1(j)],c(-5,5,n))));
% seq(point(j,display=rouge+epaisseur_point_3+point_carre),j=transpose(M))
% L_2:=lagrange(M);
% plotfunc(L_2,x=-5..5,,xstep=0.1,display=black+line_width_2);
% !s!
%!s!<c>
%On constate de gros pics sur les intervalles extremes, laissant penser que la
%convergence n'est pas du tout uniforme, et meme qu'elle diverge dans cette
%zone. 
%!s!
\qu Recommencez avec $f_2: x \mapsto sin(x)$ toujours sur $[-5,5]$.
% f2:=x->sin(x);
% F2:=plotfunc(f2(x),x=-5..5,,xstep=0.1,display=blue+line_width_3):;
%!s!<g>
% F2;
% n:=element(1..31,1,1);
% M:=approx(transpose(apply(j->[j,f2(j)],c(-5,5,n))));
% seq(point(j,display=rouge+epaisseur_point_3+point_carre),j=transpose(M))
% L_2:=lagrange(M);
% plotfunc(L_2,x=-5..5,,xstep=0.1,display=black+line_width_2);
%!s!
\qu Expliquez la diff\'erence de comportement en \'etudiant les d\'eriv\'ees de $f_1$
%d10:=diff(f1(x),x$10); // la d\'eriv\'ee 10ieme
%plot(d10,x=-5..5);
%[seq(((diff@@(2*n))(f1))(0),n=1..5)];//les derivees 2n ieme en 0 de f1 tres lourd.
%series(f1(x),0,12);//Le DL de taylor donne les derivees bien plus rapidement
%d12f1:=f1(x);for(j:=0;j<12;j++){d12f1:=normal(diff(d12f1,x))};d12f1;
%diff(f1(x),x$12);//on derive un symbole plutot qu'une fonction
%normal(diff(f1(x),x$12)-d12f1);//on derive un symbole plutot qu'une fonction
%!s!<c>
%La majoration de l'erreur fait intervenir la derivee n+1 ieme de la fonction
%pour L_n, donc pour le sinus on a une bonne borne, mais pas pour 1/(x^2+1)
% CF aussi la doc: aide>algorithmes html
% !s!
\squ Comparez les diff\'erences d'efficacit\'e entre les 5 m\'ethodes suivantes:
connaitre les d\'eriv\'ees en 0 \`a partir du d\'eveloppement de Taylor, ou trouver la
d\'eriv\'ee formelle ainsi:
\begin{itemize}
\item[a:] \verb/((diff@@(10))(f1))(x)/
\item[b:]  \verb/diff(f1(x),x$10)/  (Astuce: que fait \verb/x$10/  ?)
\item[c:] \verb/d10f1:=f1(x);for(j:=0;j<10;j++){d10f1:=normal(diff(d10f1,x))};d10f1;/
\end{itemize}
Laquelle  est \`a proscrire?
%!s!<c>
%Il faut proscrire l'utilisation de la fonction compos\'ee car il n'y a pas de
%possibilit\'e de simplification \`a chaque \'etape.
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% !s!<c>
%----------------------------calcul du polynome caracteristique par interpolation----------------------------
%!s!
\exotitre{M\'ethode de Lagrange:}
Nous pouvons interpoler le polyn\^ome caract\'eristique en les valeurs
$0\dots n$. Autrement dit, nous calculons $n+1$ d\'eterminants $d_i$, et
la r\'eponse sera: $\sum_{i=0}^n d_i \prod_{j\neq i}
\frac{(x-j)}{(i-j)}$.
\qu Impl\'ementer cette m\'ethode en utilisant la
fonction d\'eterminant pour les rationnels.
%!s!<p>
%monlagrange(A):={
%local n,ii,j,P,L,M;
%n:=dim(A)[0];P:=0;
%for(ii:=0;ii<=n;ii++)
% {
%  M:=1;
%  for(j:=0;j<=n;j++)
%    {
%     if(j!= ii){ M:=M*(x-j)/(ii-j);}
%    }
%  P:=normal(P+det(ii*identity(n)-A)*M);
% }
%};
%!s!
% k:=50:;A:=matrix(k,k,(i0,j0)->rand(21)-10):;
% time(monlagrange(A));
\qu Comparez cette m\'ethode avec le calcul de $\det(x.I-A)$ par la m\'ethode du
pivot. (cf bareiss qui est un pivot sans d\'enominateurs). On \'etudiera la
documentation pour \^etre s\^ur que le logiciel ne calcule pas $\det(x.I-A)$ par
interpolation de Lagrange! 
%
\qu Comparez ces 2 m\'ethodes avec un m\^eme logiciel. Par exemple en
utilisant la fonction d'xcas d\'edi\'ee au polyn\^ome caract\'eristique. On   \'etudiera la
documentation pour \^etre s\^ur de la m\'ethode utilis\'ee.
%time(det(A-x*idn(k),bareiss));
%time(pcar(A,x,lagrange));
\squ Pour une matrice \`a coefficients entiers (petits) de taille 50.
% k:=50:;A:=matrix(k,k,(i0,j0)->rand(21)-10):;
% pari();
% time(p1:=pari_charpoly(A,0));
% time(p2:=pari_charpoly(A,1));
% !s!<c>
% Pour les matrices a coeff entiers xcas n'utilise pas faddeev ni
% lagrange. Il utilise du Hessenberg et une remontee modulaire
% !s!
% time(p7:=pcar(A,x));
% p3:=pcar(A,x,lagrange);
% !s!<c>
%Pour obtenir le polynome caract\'eristique sous forme d'un symbole, on passe la
%variable x en seconde option:
%!s!
% p4:=pcar(A,x,fadeev);
% p5:=pcar(A,x,pmin);
% p6:=det(A-x*idn(k));
% !s!<c>
%C'est important de mettre x sinon il croit que lagrange
% est le nom de la variable, et non pas l'option.
%!s!
% normal([poly2symb(p1-p2,x),poly2symb(p2,x)-p3,p3-p4,p4-p5,p5-p6,p6-p7]);
\squ Pour une matrice \`a coefficients rationnels petits de taille 30.
% k:=30:;A:=matrix(k,k,(i0,j0)->(rand(21)-10)/(rand(4)^2+(1+rand(3))^2)):;
%% time(pari_charpoly(A,0));//fadeev
%% time(pari_charpoly(A,1));//lagrange
% time(pcar(A,x,lagrange));
% time(det(A-x*idn(k),bareiss));//bizarre, c'est trop rapide?
\qu Quel est le cout en terme d'op\'erations sur le corps de base de cette
m\'ethode?
% !s!<c>
%c'est en O(n^4), en fait n^4/3, alors que Faddeev est en n^4. Mais il y a plus
%de fractions chez lagrange, ce qui peut donner l'avantage a faddeev.
%!s!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\end{document}


