\documentclass[10pt,twoside]{article}
\usepackage[width=170mm,height=240mm]{geometry}
\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{preambule-utf8}
\usepackage{etex}

\usepackage[boldsans]{ccfonts}
\usepackage{beton,euler}
\usepackage{luximono}

\usepackage{bbding,filecontents}
 \usepackage{wasysym,marvosym,keystroke}
\definecolor{0.95white}{rgb}{0.95,0.95,0.95}


% pour algorithm
\incmargin{1em}
\dontprintsemicolon
%\SetCommentSty{\small\sffamily}


\graphicspath{{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}}

\entete{TD Maple n°7}{Approximations polynomiales}{PCSI 2 - Lycée Clemenceau}%g,d,b

 \usepackage{index}
  \makeindex
 \renewindex{default}{idx}{ind}{Index des commandes vues aujourd'hui}

\newcommand{\indexkeywordsmaple }[1]{\index[default]{maple@\textbf{\large Commandes}!#1@\textcolor{red}{\texttt{#1}}|textbf}}

\newcommand{\indn }[1]{\index[default]{maple@{\large
      Notions }!#1@ #1}}

\newcommand{\indt }[1]{#1\index[default]{maple@{\large
      Touches }!#1@ #1}}


%%% Environnement des réponses du logiciel
\DefineVerbatimEnvironment{boxedverbatim}{Verbatim}{fontsize=\small,formatcom=\color{blue},fontshape=it,gobble=2,frame=single,framesep=4mm,label=\textit{\small \textcolor{black}{Réponse du logiciel}},xleftmargin=10pt,rulecolor=\color{black}}




\newcommand\Com[1]{%
\shorthandoff{;:}\textcolor{red}{{ \ttfamily #1}}\index[default]{maple@\textbf{\large Commandes}!#1@\textcolor{red}{\texttt{#1}}|textbf}}


%%% Com avec syntaxe
\newcommand\Comsi[2]{%
\shorthandoff{;:}\textcolor{red}{{ \ttfamily #1}}(\textcolor{red}{\texttt{#2}})\index[default]{maple@\textbf{\large Commandes}!#1@\textcolor{red}{\texttt{#1}}|textbf}}





%%%%%%  Commande personnelle ou bout de code

\renewcommand{\code}[1]{\textcolor{red}{\bfseries \texttt{#1}}}





\newcommand{\MAPLE}{\lstset{numbers=none,language=Maple,xleftmargin=10pt,%
keywordstyle =\color{red}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{red},commentstyle=\normalfont\scriptsize\itshape,
    backgroundcolor=\color{0.95white},index=[2][keywords],indexstyle=[2]\indexkeywordsmaple,breaklines=true}
}


% %%% Environnement des réponses du logiciel
% \DefineVerbatimEnvironment{boxedverbatim}{Verbatim}{fontsize=\small,formatcom=\color{blue},fontshape=it,gobble=2,frame=single,framesep=4mm,label=\textit{\small \textcolor{black}{Réponse du logiciel}},xleftmargin=10pt,rulecolor=\color{black}}



% %\newlength{\moitie}
% \newlength{\longmot}
% \newenvironment{BoxedVerbatim}[1][(\linewidth)/2-1em]{%
%   \setlength{\margegauche}{#1}
% \setlength{\moitie}{(\widthof{\texttt{Réponse du logiciel}})/2}%
% \setlength{\longmot}{\widthof{\texttt{Réponse du logiciel}}} 
%  \par
%   \begin{lrbox}{\dangerbox}
%     \begin{minipage}{\linewidth-2\marge-2\pslinewidth}
%       \par\vspace*{\margehaut}  %\fontfamily{ccm}\selectfont
% }
% {%
%     \end{minipage}%
%   \end{lrbox}
%   % Affiche le texte dans un cadre en couleur.
%   \rput[tl](0,0){%
%     \psframebox[framesep=\marge,linewidth=.5\pslinewidth]{%
%       \usebox{\dangerbox}%
%     }%
%   }%
%  %  Efface le trait juste ce qu'il faut
%   \rput(\marge,0){%
%     \rput(\margegauche,0){%
%       \psline[linewidth=2\pslinewidth,linecolor=white](-\moitie,0)(\moitie,0)
%     }
%   }
% \rput(\marge,0){\rput(\margegauche,0){{\ttfamily \itshape \small Réponse du logiciel}}}
%   % Réserve la place verticale pour la suite
%  \par
%   \setlength{\marge}{\ht\dangerbox+\dp\dangerbox+2\marge+\extraline}
%   \vspace{\marge}
% }




%biblio

% \usepackage[super,idem=strict,ibidem=name]{jurabib}
% \usepackage{url}
% \bibliographystyle{jurabib}



\begin{document}
\setlength{\parindent}{0pt}
\thispagestyle{empty}



%%%%%% TITRE{vide}{intitule chapitre : lecon, chapitre ...}{debut titre}{fin titre}{titre toc}{dessin}
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%% TITREs{vide}{intitule chapitre : lecon, chapitre ...}{debut titre}{fin titre}{titre toc}
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\setcounter{NumLecon}{6}

\TITREs{}{TD  \includegraphics[height=0.8cm]{maple.eps}
}{Approximations
  polynomiales}{}{Approximations polynomiales}
        

\MAPLE

%\begin{multicols}{2}





\section{Développements limités}

\subsection{Formule de Taylor-Young}


Allez, je ne  vous fais pas l'offense de  vous la rappeler...Nous allons
créer une procédure  MAPLE qui donnera la partie  polynomiale d'un DL en
utilisant cette formule~:



\begin{algorithm}[H]
  \caption{Partie polynomiale d'un DL}
\Entree{une expression f(x) et un ordre n}\;
\Ini{\;
Der\aff f (sous forme de fonction !)\;
Pol\aff 0\;
}\;
\Deb{
\Pour{k allant de 0 à n}{
Pol\aff Pol+Der(0)$\times \frac{x^k}{k!}$\;
Der\aff fonction dérivée de Der
}
 } 
\Retour{{\rm Pol}}
\end{algorithm}

Yaka écrire une procédure \code{DL:=proc(f,n)} en MAPLE...


\begin{figure}[!h]
  \begin{Remarque}[syntaxe MAPLE]
  MAPLE a une commande pour ça.
Il suffit d'utiliser \code{taylor(expression,var=point,ordre(en option))}
L'ordre par défaut est 6. Attention~! MAPLE utilise des O et non des o.

Pour les développements asymptotiques, on utilise plutôt~:
\code{asympt(expression, variable)}

    \end{Remarque}
  \end{figure}

Utiliser la procédure \code{DL} pour avoir un ordre de grandeur de l'approximation
pour différentes fonctions et différentes valeurs de $x$.

Par exemple~:

\code{evalf(unapply(DL(ln(1+x),5),x)(0.001)-ln(1+0.001),20)}

\code{evalf(unapply(DL(ln(1+x),5),x)(1.1)-ln(1+1.1))}


Essayez plutôt de présenter les résultats dans un tableau avec plusieurs
valeurs de $x$ en colonnes et plusieurs fonctions en lignes.

\subsection{Visualisation de l'approximation locale par une fonction polynôme}

Créez une procédure \code{graph:=proc(f,xmax,ymax,p)} dans laquelle vous construirez une séquence de \code{plot(DL(f,i))} pour i variant de 1 à p et vous ajouterez la représentation graphique de f avec une couleur différente.

\sm

Pour visualiser de manière dynamique l'approximation, on utilisera \code{display} de la bibliothèque \code{plots} avec l'option \code{insequence=true} qui permet d'animer le graphique. Pour cela, il faut cliquer  sur le graphique : des icônes apparaissent.
Par exemple, regardez et commentez ce que donne~:

\begin{lstlisting}
  graph(x->cos(x),15,1,50);
  graph(x->ln(1+x),3,3,50);
\end{lstlisting}



\section{Polynôme d'interpolation de Lagrange}

\subsection{À quoi ça sert~?}

D'un point de vue abstrait, on pourrait se contenter de dire que si on ne connaît que quelques points
de la courbe représentative  d'une fonction inconnue, on cherche à approcher  cette fonction par une
fonction polynomiale  passant par  ces points.  Intuitivement, on peut  penser que  plus on  aura de
points de contrôles, meilleures sera l'approximation  mais les mathématiques vont venir une nouvelle
fois contredire notre intuition.

D'un point  de vue  plus concret, on  voudrait reconstituer  un organe humain  à partir  de quelques
mesures  prises en  imagerie médicale  ou reconstituer  une couche  géologique à  partir  de mesures
sismiques~:~on est alors amené  à reconstituer une formes à partir de nuages  de points, en 3D cette
fois.

Ces problèmes sont le  quotidien de l'ingénieur. Nous nous contenterons bien  sûr ici d'un survol de
quelques méthodes très simples dans des cas théoriques eux aussi assez triviaux.


\subsection{Cas général}

On considère $n$ points de coordonnées $(x_1,y_1)\dots(x_n,y_n)$
On veut trouver un polynôme P tel que $P(x_i)=y_i$ pour tout $i\in [\![1\pv n]\!]$. 

Une petite activité mathématique consiste à prouver que l'unique polynôme de degré $n-1$, solution du problème, est
défini par 

\[ P(x)=\sum_{k=1}^ny_k \LR_k(x)\quad \text{avec} \quad\LR_k(x)=\frac{\ds\prod_{i=1, i\neq
k}^{i=n}(x-x_i)}{\ds\prod_{i=1, i\neq k}^{i=n}(x_k-x_i)}\]

 Déterminez une procédure \code{Lagrange:=proc(X,Y,x)} où X est la liste des abscisses, Y celle
  des ordonnées et $x$ la variable. 



Le problème, c'est ce $i\neq k$. Il faut donc user d'astuce... 

On construit un polynôme intermédiaire~:~ $L\leftarrow \ds\prod_{i=1}^n(x-x_i)$

On enlève le terme en trop en divisant par $(x-x_k)$~:~$L\leftarrow L/(x-x_k)$


 Pour cela on utilise
la commande \Comsi{quo}{poly1,poly2,variable} qui calcule le quotient de deux polynômes.


On divise par la même chose mais en substituant $x$ par $x_k$~:~$L\leftarrow L/subs(x=x_k,L)$

Vous ferez bon usage des fonctions MAPLE suivantes : 


\begin{itemize}
\item \Comsi{product}{expression(k),k=debut..fin};
\item \Comsi{subs}{ancien=nouveau,Liste};
\item \Comsi{expand}{Polynome};
\item \Comsi{sort}{Polynome}.
\end{itemize}



Ça aura cette forme~:

\begin{lstlisting}
Lagrange:=proc(X,Y,t)
 local k,L,P,Produit;
 P:=0:
 Produit:=product(t-X[i],i=1..nops(X));   
 for k to nops(X) do
   .
   . 
   .  
 od:
 sort(expand(P));
 end:
\end{lstlisting}


Par exemple avec~:

\begin{lstlisting}
  Lagrange([1,2,3,4,5],[7,-8,9,-10,11],x)
\end{lstlisting}

on obtient :

\begin{figure}
  \begin{BoxedVerbatim}
    $\mathtt{6x^{4}-\dfrac{214}{3}x^{3}+294x^{2}-\dfrac{1463}{3}x+266}$
 \end{BoxedVerbatim}
\end{figure}


Vérifiez que $P(1)=7$, $P(2)=-8$, etc.


\subsection{Application à l'approximation polynomiale d'une fonction}

Déterminez une  procédure \code{LagrangeFonc:=proc(f,X,t)}  où $f$ est  une fonction de  $\bbr$ dans
$\bbr$ et qui renvoie le polynôme d'interpolation de Lagrange associé aux points de coordonnées 
$\left(x_1,f(x_1)\right),\dots \left(x_n,f(x_n)\right)$.

Il suffit d'utiliser astucieusement la procédure précédente.

Voyez ce que ça donne par exemple avec 

\begin{lstlisting}
  LagrangeFonction(t->1/(1+t^2),[1,2,3,4,5],x)
\end{lstlisting}



\subsection{Visualisation}
On veut à présent visualiser l'approximation du graphe d'une fonction par des polynômes de Lagrange
successifs en augmentant les points de contrôle.

On va par exemple prendre une subdivision régulière de l'intervalle et on augmentera le nombre de
points de contrôles pour observer si l'approximation s'en trouve améliorée.

Construisez une animation de l'approximation de la fonction
$x\mapsto \frac{1}{1+x^2}$  sur $[-5\pv 5]$ avec  comme séries successives d'abscisses  de points de
contrôle des subdivisions régulières de l'intervalle $[-5\pv 5]$. 

Faites de même pour $x\mapsto ln(1+x)$ en adaptant les intervalles. 

\medskip

On a bien sûr envie de généraliser. Comme je suis gentil, voici une solution


\begin{lstlisting}
 LagrangeGraphe:=proc(g,n,a,b,ymin,ymax)
 local i,s,p;
 s:=seq(plots[display](plot(LagrangeFonction(g,[a+(b-a)*i/p$i=0..p],t),t=a..b),
        plot(g(t),t=a..b,color=blue)),p=1..n):
 plots[display](s,insequence=true,view=[a..b,ymin..ymax]);
 end:
\end{lstlisting}

%$

Ce qui donne 

\begin{lstlisting}
 LagrangeGraphe(t->1/(1+t^2),40,-5,5,t,-0.2,1.2);
 LagrangeGraphe(t->ln(1+t),20,0,5,t,-2,3);
\end{lstlisting}


Bref, ce  n'est pas aussi  magique qu'il n'y paraissait  : plus on  augmente le nombre de  points de
contrôle, plus les \og effets de bord\fg deviennent gênants. 

Vous prouverez peut-être un jour que si $f$ est définie sur un intervalle I, si la suite des dérivées successives de $f$ est uniforméméent
bornée et  si l'on fait tendre le  nombre de points de  contrôle vers $+\infty$, alors  la suite des
interpolateurs de Lagrange de $f$ converge  \emph{uniformément} vers $f$ sur tout segment $[a\pv b]$
inclus dans I lorsque $n$ tend vers  $+\infty$. Vous comprendrez l'an prochain toute l'importance du
mot \emph{uniformément}  qui permet d'éviter ces désagréables  \og effets de bord\fg.  Ça n'a malgré
tout que peu  d'intérêt car ces conditions sont  trop restrictives et de toute façon,  la formule de
Taylor-Lagrange nous donne ce qu'il faut pour de telles fonctions.

\subsection{Polynômes de Tchebychev}

Il existe néanmoins  un résultat positif pour les  fonctions de classe $\CR^1$ sur $[-1\pv  1]$ : il
suffit de prendre pour  abscisses des points de contrôle les racines  des polynômes de Tchebychev et
alors la convergence est uniforme. 

Oui, mais qu'est-ce qu'un polynôme de Tchebychev~? 




               \begin{figure}[!h]
                 \begin{Idee}{Polynôme de Tchebychev}
                   
On définit les polynômes de Tchebychev d'ordre $n$ par \[ T_n(x)=\cos \big(n\Arccos(x)\big)\]

En fait, ce sont les polynômes qui vérifient $T_n(\cos(t))=\cos(nt)$. 

On peut les déterminer à la main ou utiliser \Comsi{orthopoly[T]}{(n,x)} qui donne $T_n(x)$. 

                   \end{Idee}
                 \end{figure}




Observez par exemple~:

\begin{lstlisting}
T(5,x);
S:=solve(T(5,x)=0,x);
evalf(S);
\end{lstlisting}





Étudiez alors quelques exemples (les fonctions doivent être définies sur $[-1\pv 1]$) mais avec comme abscisses les racines des polynômes de
Tchebychev pour différentes valeurs de $n$. Qu'observez-vous~? 
On construira une procédure \code{LagrangeTcheb:=proc(g,n,ymin,ymax)}


\begin{lstlisting}
LagrangeTcheb:=proc(g,n,ymin,ymax)
 local i,s,p;
 s:=seq( plots[display]( 
    plot ( LagrangeFonction(g,[evalf(solve(T(p,x)=0,x))],t),t=-1..1),
    plot(g(t),t=-1..1,color=blue)),
    p=1..n):
 plots[display](s,insequence=true,view=[-1..1,ymin..ymax]);
 end:
\end{lstlisting}

Il y a bien sûr des approximations plus intéressantes 

\begin{itemize}
\item  par les  polynômes de Bernstein définis par
$B_n(x)=\ds\sum_{k=0}^n\Co{k}{n}f   \left(\frac{k}{n}\right)x^k(1-x)^{n-k}$   pour   des   fonctions
continues sur un segment

\item par des polynômes trigonométriques dans des cas encore plus généraux
comme vous le verrez en étudiant les séries de Fourier l'an prochain.

\end{itemize}




%\end{multicols}





\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
