%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8x]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}

\ifpdf \DeclareGraphicsRule{*}{mps}{*}{} \fi

\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}



\usepackage[detect-all]{siunitx}
\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}


\usepackage{media9}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]




\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\uparrow}
\newcommand\xor{\oplus}

\newcommand\foncpart{\rightarrow\!\!\!\!\!\!\shortmid}
\newcommand\fonctot{\rightarrow}
\newcommand\injpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid}
\newcommand\injtot{\rightarrowtail}
\newcommand\surjpart{\twoheadrightarrow\!\!\!\!\!\!\!\shortmid}
\newcommand\surjtot{\twoheadrightarrow}
\newcommand\bijpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid\!\!\!\!\twoheadrightarrow}
\newcommand\bijtot{\rightarrowtail\!\!\!\!\!\!\!\!\!\twoheadrightarrow}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/INFO2/Images/FaceDB/}{/home/moi/IUT/Figures/}{/home/moi/IUT/INFO1/PolyInfo1/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}}


\setcounter{tocdepth}{2} %\setcounter{page}{0}


\renewcommand\FancyVerbFormatLine[1]{\color{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{beamercolorthemeelephantbird}

\newcommand{\triangleup}{\Delta}









\newcolumntype{C}[1]{>{\centering}b{\widthof{#1}}}
\newcommand\MyBox[2][XXX]{%
  \fbox{\tabular[b]{C{#1}} #2 \endtabular}}














\begin{document}


\title[] % (optional, use only with long paper titles)
{Résoudre une équa diff avec la MÉTHODE D'EULER!!}

\subtitle{Informatique pour tou(te)s - Semaines 5 \& 6}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{Lycée Clemenceau - MP/MP* }% (optional, but mostly needed)

%\logo{\includegraphics[scale=0.15]{logo_iut}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \today{} à \now}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

% \AtBeginSubsubsection[]
% {
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\scriptsize
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}



\section{Approximation polynomiale}


\subsection{Inter(extra)polation}

\begin{frame}
  On connaît les valeurs d'une fonction $f$  en des points $x_i$ et on cherche à
  en déduire une approximation polynomiale $P$ de $f$ sur $[a,b]$. 

\pause

Interpolation

\pause

Extrapolation

\pause


Intégration 

\pause


Équations différentielles

\end{frame}


\subsection{Lagrange, Waring, Gau\ss, Newton}

\begin{frame}
\begin{multicols}{2}
    \begin{figure}
      \includegraphics[width=2.7cm]{Waring}
      \caption{ Edward \textsc{Waring}\\(1736 - 1798)}
    \end{figure}

\pause

    1779: \textit{Problems Concerning Interpolations}

    \pause
    

    \begin{figure}
      \includegraphics[width=2.7cm]{lagrange}
      \caption{ Giuseppe Lodovico \textsc{de Lagrangia}\\(1736 - 1813)}
    \end{figure}

\pause

    1795: \textit{Leçons Élémentaires sur les Mathématiques Données a l'École Normale
    }
  \end{multicols}

\end{frame}
  
\begin{frame}
  On travaillera dans cette section avec des polynômes de $\bbr_n[X]$, une
  fonction numérique réelle  $f$ définie sur un intervalle  $[a,b]$ et une
  famille $\bigl\{x_0,x_1,...,x_n\bigr\}$ de $n+1$ points distincts de $[a,b]$.
\end{frame}


\begin{frame}
  \begin{theorem}
  Il existe un polynôme $P_n$ de $\bbr_n[X]$ et un seul tel que:
$$\forall               i\in               \bigl\{0,1,...,n\bigr\}\qquad
\widetilde{P_n}(x_i)=f(x_i)$$

Ce polynôme s'écrit:

$$P_n(X)=\displaystyle\sum_{i=0}^{n}f(x_i)\LR_i(X)$$

avec:

$$\LR_i(X)=\displaystyle\prod_{j=0,j\neq i}^{n}\frac{X-x_j}{x_i-x_j}$$
\end{theorem}
\end{frame}



\begin{frame}
   $$Q(X) = \prod_{j=0}^n(X-x_j)$$


 \pause 

$$Q'(X)=\sum_{i=0}^n\prod_{j=0,j\neq i}^{n}(X-x_j)$$


\pause 

$$Q'(x_i)=\prod_{j=0,j\neq i}^{n}(x_i-x_j)$$

\pause

$$\LR_i(X)=\frac{Q(X)}{Q'(x_i)(X-x_i)}$$


\end{frame}



\begin{frame}
  Choix de la base:

  \begin{itemize}
  \item base canonique: matrice de Vandermonde 
  \item base des polynômes de Lagrange: matrice diagonale
  \item base des différences divisées: 1, $X-x_0$, $(X-x_0)(X-x_1)$,...,$(X-x_0)(X-x_1)\cdots (X-x_{n-1})$
  \end{itemize}
\end{frame}



\begin{frame}
  


D'un point de vue algorithmique,  que se passe-t-il lorsqu'on rajoute un
point pour améliorer l'interpolation?


\end{frame}




\subsection{Newton / Différences divisées}

\begin{frame}
  

$$f[x_0,x_2,...,x_{k}]=\frac{f[x_1,...,x_{k}]-f[x_0,...,x_{k-1}]}{x_{k}-x_0}$$

\pause


\begin{center}
\begin{tabular}{cccc}
$\bm{f[x_0]}$ & $\bm{f[x_0,x_1]}$   & $\bm{f[x_0,x_1,x_2]}$   &  $\bm{f[x_0,x_1,x_2,x_3]}$                       \\
$f[x_1]$          &$f[x_1,x_2]$                      &$f[x_1,x_2,x_0]$ &                         \\
$f[x_2]$          & $f[x_2,x_3]$                     &        &                         \\
$f[x_3]$          &                      &                       &                         \\
\end{tabular}
\end{center}

\pause

Coefficients du polynôme interpolateur dans la base des différences divisées:


$$
P_n(t)=f[x_0]+\sum_{k=1}^nf[x_0,...,x_k](t-x_0)(t-x_1)\cdots(t-x_{k-1})
$$



\end{frame}


\begin{frame}
  


D'un point de vue algorithmique,  que se passe-t-il lorsqu'on rajoute un
point pour améliorer l'interpolation?

\pause


\begin{center}
\begin{tabular}{ccccc}
$\bm{f[x_0]}$ & $\bm{f[x_0,x_1]}$   & $\bm{f[x_0,x_1,x_2]}$   &  $\bm{f[x_0,x_1,x_2,x_3]}$ & $\textcolor{black}{\bm{f[x_0,x_1,x_2,x_3,x_4]}}$                       \\
$f[x_1]$ & $f[x_1,x_2]$ &$f[x_1,x_2,x_0]$ & $\textcolor{black}{{f[x_1,x_2,x_3,x_4]}}$ & \\
$f[x_2]$ & $f[x_2,x_3]$ & $\textcolor{black}{{f[x_2,x_3,x_4]}}$ & & \\
$f[x_3]$ & $\textcolor{black}{{f[x_3,x_4]}}$ & & & \\
$\textcolor{black}{{f[x_4]}}$ &&&&\\
\end{tabular}
\end{center}


\end{frame}


\begin{frame}
  


D'un point de vue algorithmique,  que se passe-t-il lorsqu'on rajoute un
point pour améliorer l'interpolation?




\begin{center}
\begin{tabular}{ccccc}
$\bm{f[x_0]}$ & $\bm{f[x_0,x_1]}$ & $\bm{f[x_0,x_1,x_2]}$ & $\bm{f[x_0,x_1,x_2,x_3]}$ & $\textcolor{yellow}{\bm{f[x_0,x_1,x_2,x_3,x_4]}}$ \\
$f[x_1]$ & $f[x_1,x_2]$ & $f[x_1,x_2,x_0]$ & $\textcolor{yellow}{{f[x_1,x_2,x_3,x_4]}}$&\\
$f[x_2]$ & $f[x_2,x_3]$ & $\textcolor{yellow}{{f[x_2,x_3,x_4]}}$ & & \\
$f[x_3]$ & $\textcolor{yellow}{{f[x_3,x_4]}}$ & & & \\
$\textcolor{yellow}{{f[x_4]}}$ &&&&\\
\end{tabular}
\end{center}


\end{frame}



\subsection{Cherchez l'erreur}

\begin{frame}
Soit  $P_n$  un  polynôme
interpolateur  en  $x_0$, $x_2$,...,$x_n$  points  distincts de  $[a,b]$
d'une fonction $f$ définie sur $[a,b]$.

\pause


Soit    $t\in[a,b]$    distinct    des    $x_i$    (sinon...).    Posons
$e_n(t)=P_n(t)-f(t)$  et  $P_{n+1}$  le  polynôme  qui  interpole  $f$  en
$x_0$,...,$x_n$, $t$.


\pause

$$P_{n+1}(t)=f(t)=P_n(t)+f[x_0,x_2,...,x_n,t]\prod_{i=0}^n(t-x_i)$$


\pause

$$e_n(t)=-f[x_0,x_2,...,x_n,t]\prod_{i=0}^n(t-x_i)$$


\pause

Une $n$\eme formule de \textsc{Cauchy} montre que si $f$ est de classe
$\CR^{n+1}$ sur $[a,b]$, il existe $\xi_t\in]a,b[$ tel que:

$$e_n(t)=-\frac{f^{(n+1)}(\xi_t)}{(n+1)!}\prod_{i=0}^n(t-x_i)\quad
\text{soit}\quad \left|e_n(t)\right|\leqslant \underset{\xi\in]a,b[}{\text{max}}\left|\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(t-x_i)\right|$$


\end{frame}


\subsection{Choix des points}

\begin{frame}
  $$|e_n(t)| \leqslant \frac{1}{(n+1)!}\Bigl\|\prod_{i=0}^n(t-x_i)\Bigr\|_\infty\Bigl\|f^{(n+1)}\Bigr\|_\infty$$

\pause

$$\left\|\prod_{i=0}^n(t-x_i)\right\|_\infty$$

\pause

Ce n'est qu'un début...

\end{frame}


\subsection{Instabilité}

\begin{frame}
  Juste pour  information...On appele $n\eme$ constante  de \textsc{Lebesgue} le
  réel $$\Lambda_n=\underset{t\in[a,b]}{\text{max}}\sum_{i=0}^n|\LR_i(t)|$$

Alors

\begin{theorem}
  Soit $f$ une fonction continue sur $[a,b]$.

$$\|e_n\|_\infty                                                       \leqslant
(1+\Lambda_n)\underset{ Q\in\bbr[X]}{\text{min}}\|f-\widetilde{Q}\|_\infty$$



\end{theorem}




\end{frame}



\section{Méthodes de Newton-Cotes}


\begin{frame}
  
$$\displaystyle\int_{a}^{b}f(t) \d t=
\displaystyle\sum_{i=1}^{n}w_{i}f(x_i)+E_n(f)$$

\pause les $w_i$ sont les \textit{poids}, \pause les $x_i$ sont les pivots, \pause
$E_n(f)$ l'erreur commise.




\end{frame}


\begin{frame}
  
  \begin{eqnarray*}
    \int_a^bf(t)\d t \approx \int_a^bP_n(t)\d t &\textcolor{black}{=}& \textcolor{black}{\int_a^b\sum_{i=0}^nf(x_i)\LR_i(t)\d t}\\
                                             &\textcolor{black}{=}& \textcolor{black}{\sum_{i=0}^n\underbrace{\left(\int_a^b\LR_i(t)\d t\right)}_{w_i}f(x_i)}
  \end{eqnarray*}

\end{frame}



\begin{frame}
  
  \begin{eqnarray*}
    \int_a^bf(t)\d t \approx \int_a^bP_n(t)\d t &=& \int_a^b\sum_{i=0}^nf(x_i)\LR_i(t)\d t\\
                                             &\textcolor{black}{=}& \textcolor{black}{\sum_{i=0}^n\underbrace{\left(\int_a^b\LR_i(t)\d t\right)}_{w_i}f(x_i)}
  \end{eqnarray*}

\end{frame}



\begin{frame}
  
  \begin{eqnarray*}
    \int_a^bf(t)\d t \approx \int_a^bP_n(t)\d t&=& \int_a^b\sum_{i=0}^nf(x_i)\LR_i(t)\d t\\
    &=& \sum_{i=0}^n\textcolor{black}{ \underbrace{\textcolor{white}{\left(\int_a^b\LR_i(t)\d t\right)}}_{w_i}}f(x_i)
  \end{eqnarray*}

\end{frame}


\begin{frame}
  
  \begin{eqnarray*}
    \int_a^bf(t)\d t \approx \int_a^bP_n(t)\d t&=& \int_a^b\sum_{i=0}^nf(x_i)\LR_i(t)\d t\\
                                              &=& \sum_{i=0}^n\underbrace{\left(\int_a^b\LR_i(t)\d t\right)}_{w_i}f(x_i)
  \end{eqnarray*}




\end{frame}

\begin{frame}
  Dans la base des différences divisées:


$$                            \int_a^bf(t)\d                            t\approx
\int_a^bf[x_0]+\sum_{k=1}^n\int_a^bf[x_0,...,x_k](t-x_0)(t-x_1)\cdots(t-x_{k-1})\d t$$


\end{frame}


\begin{frame}
  On notera:

  \begin{itemize}
    \item $\IR(f)      =       \displaystyle\int_a^bf(t)\d      t$
    \item $\IR_n(f)=\displaystyle\sum_{i=0}^nw_if(x_i)$ 
    \item  $E_n(f)=\IR(f) - \IR_n(f)$

 \end{itemize}
\end{frame}

\begin{frame}
  




\begin{definition}
  Une méthode de quadrature est \textbf{exacte}  sur un ensemble A si pour toute
  fonction $f$ de A:

$$E_n(f)=0$$
\end{definition}


\pause

\begin{definition}
Une méthode  de quadrature est  d'\textbf{ordre} $m$ si elle  est exacte pour  tout $x^k$
avec $k\in \bigl\{0...m\bigr\}$ mais n'est pas exacte pour $x^{m+1}$.
 \end{definition}




\end{frame}


\subsection{Newton-Cotes d'ordre 0}

\begin{frame}
$$x_0=a\qquad OU \qquad x_0=b$$

\pause



  $$\IR(f)=f(a)\int_a^b\LR_0(t)\d t \qquad OU \qquad f(b)\int_a^b\LR_0(t)\d t$$


\pause


$$\LR_0(t)=1$$


\pause

\begin{theorem}[Formule des rectangles]
  $$\int_a^bf(t)\d t\approx (b-a)f(a) \qquad OU \qquad (b-a)f(b)$$
\end{theorem}


\pause


Si $f$ est $\CR^1$, il existe $\xi \in ]a,b[$  tel que

$$R_0(f)=\pm \frac{(b-a)^2}{2}f'(\xi)$$

\pause

Démonstration?




%% $F(x) = \int_0^xf(t)\d t$. $F(b)=F(a)+F'(a)(b-a)+\frac{F''(\xi)}{2}(b-a)^2$

\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
def rect( f, a, b, n ):
    s = 0
    h = ( b - a ) / n
    for k in range( n ):
        s += h * f( a + k*h )
    return s
\end{pythoncode}
\end{frame}

\begin{frame}
  Cette méthode est-elle bien d'ordre 0?

\pause


$$\int_a^b1\d t=(b-a)=f(a)(b-a)$$

\pause

$$\int_a^bt\d t=\frac{b^2-a^2}{2}\neq f(a)(b-a)$$
\end{frame}



\subsection{Newton-Cotes d'ordre 1}

\begin{frame}

$$x_0=a\qquad x_1=b$$

\pause

  $$\IR(f)=f(a)\int_a^b\LR_0(t)\d t+f(b)\int_a^b\LR_1(t)\d t$$


\pause


$$\LR_0(t)=\frac{t-b}{a-b}\qquad \LR_1(t)=\frac{t-a}{b-a}$$

\pause

Calculez....


\pause

\begin{theorem}[Formule des trapèzes]
  $$\int_a^bf(t)\d t\approx \frac{b-a}{2}\bigl( f(a)+f(b) \bigr)$$
\end{theorem}

\end{frame}

\begin{frame}


Si $f$ est $\CR^2$, il existe $\xi \in ]a,b[$ tel que:


$$|R_1(f)|=\frac{(b-a)^3}{12}|f''(\xi)|$$


\pause

Ipp de $\displaystyle\int_a^b  \left(x-\frac{a+b}{2}\right)f'(t)\d t$ + théorème
de la moyenne.


\pause 

\bigspace

Ordre 1?

\end{frame}


\begin{frame}
  \begin{exercice}
    Méthode du point milieu: quel est son ordre?
  \end{exercice}
\end{frame}


\subsection{Newton-Cotes d'ordre 2}


\begin{frame}
  $$x_0=a, \quad x_1=\frac{a+b}{2}, \quad x_2=b$$

\pause


Pour changer, allons dans la base des différences divisées:

$$P_2(t)=f[x_0]+f[x_0,x_1](t-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)$$

\pause

Calculez...


\pause


\begin{theorem}[Formule de Simpson]
  $$\int_a^bf(t)\d t\approx \frac{b-a}{6}\Bigl( f(a)+4f\left(\frac{a+}{2}\right) + f(b) \Bigr)$$
\end{theorem}

\end{frame}

\begin{frame}


ordre?

\pause

$$|R_2(f)|=\frac{(b-a)^5}{2880}|f^{(4)}(\xi)|$$

\end{frame}



\begin{frame}
  Méthode de Romberg: en TD
\end{frame}

\section{L'A et l'$\Omega$ de l'ingénieur: la méthode d'Euler... :-) }



\begin{frame}
  $$y'(x) = f(y(x),x)$$

\pause

$$\int_{x_n}^{x_{n+1}}y'(x)\d x  \pause =  y'(x_n) \times  (x_{n+1}-x_n)\pause =
f(y_n,x_n) \times (x_{n+1} - x_n)\pause = h\times f(y_n,x_n)$$


\end{frame}

\begin{frame}[fragile]

\begin{pythoncode}
def rect(f, a, b, n):
    s = 0
    h = ( b - a ) / n
    for k in range( n ):
        s += h * f( a + k*h )
    return s
\end{pythoncode}

\pause


\begin{pythoncode}
def euler_exp(f, x0, xn, y0, n):
    yk = y0
    h  = ( xn - x0 ) / n
    Y  = [y0]
    for k in range( n ):
        yk = yk + h * f( yk,  x0 + k*h )
        Y += [yk]
    return Y
\end{pythoncode}


\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
def euler_exp(f, x0, xn, y0, n):
    h  = ( xn - x0 ) / float( n )
    Y  = [ y0 for k in range( n + 1 ) ]
    X  = [ x0 + k*h for k in range( n + 1 ) ]
    for k in range(1, n + 1 ):
        Y[k] = Y[k - 1] +  h * f( Y[k - 1], X[k] )
    return X,Y
\end{pythoncode}


  
\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
  def trace_euler_exp(f, x0, xn, y0, n):
    X, Y = euler_exp(f, x0, xn, y0, n)
    plt.plot( X, Y )
    plt.show()
\end{pythoncode}

\pause

\begin{pythoncode}
  In [1]: trace_euler_exp( lambda y, x : y, 0, 2, 1, 2**5 )
\end{pythoncode}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{expopy}
\end{center}
%\end{figure}



  
\end{frame}


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