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

\usepackage[beamer,utf8x,russe]{preambuleTrm}
%\usepackage{stmaryrd}



\usepackage{iwona}


\mode<presentation>
{
  %\usetheme{Bergen}%Montpellier}
  % or ...Frankfurt, 
  \usetheme[secheader]{Montpellier}%{Madrid}

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
  \usefonttheme{progressbar}
  %\useoutertheme{progressbar}
  %\useinnertheme{progressbar}
  %\progressbaroptions{% titlepage=normal,
  %  imagename=/home/moi/Photos/Maths/prisoner}
}
\makeatletter
\setbeamertemplate{footline}
{
    \leavevmode%
    \hbox{%
        \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,left]{title in head/foot}%
          \includegraphics[width=0.1\textwidth]{logoUNI}
            %\usebeamerfont{title in head/foot}\insertshorttitle
        \end{beamercolorbox}%
 \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
            \usebeamerfont{author in head/foot}\insertshortauthor
        \end{beamercolorbox}%
        \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,right]{date in head/foot}%
            \usebeamerfont{date in head/foot}\insertshortdate{}\hspace*{2em}
            \insertframenumber{} / \inserttotalframenumber\hspace*{2ex} 
        \end{beamercolorbox}}%
        \vskip0pt%
    }
    \makeatother


%\setbeamertemplate{footline}[frame number]
\setbeamertemplate{navigation symbols}{}
%\setbeamertemplate{footline}[text line]{\insertshortauthor\hfill}

%\usepackage{elephantbird}
\newcommand\MyBox[2][XXX]{%
  \fbox{\tabular[b]{C{#1}} #2 \endtabular}}


%\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,shadows,patterns}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}

\usetikzlibrary{intersections}

\hypersetup{pdfpagemode=FullScreen}

\usepackage[detect-all]{siunitx}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

\usepackage{scalefnt}
\setbeamertemplate{theorems}[numbered]

\usepackage[square]{daedale}
\bibliographystyle{cyclope}


\usepackage{algo}

\renewcommand{\algocommentfont}{\tiny\ttfamily\itshape}
\renewcommand{\algokeywordfont}{\small\ttfamily}
\renewcommand{\algotextfont}{\footnotesize\ttfamily}
\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/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/}{/home/moi/PREPA/IPT/2014_15/Poly/}}




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


\newcommand{\triangleup}{\Delta}












\begin{document}


\title[]% (optional, use only with long paper titles)
{Centrale 2015 - Méthodes d'Euler}

\subtitle{Informatique pour tou(te)s - semaines 48 \& 49}

\author[\url{Guillaume.Connan@univ-nantes.fr}] % (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$^{\star}$}% (optional, but mostly needed)

%\logo{\includegraphics[width=0.1\textwidth]{logoUNI}}

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

\date[] % (optional, should be abbreviation of conference name)
{novembre - décembre 2015}
% - 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{<+->}


\AtBeginSubsection[]
{\scriptsize
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\tiny
\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}
%\ThisCenterWallPaper{1}{logoiremBigInv}
 \Large \titlepage 
\thispagestyle{empty}
\end{frame}

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

 
 \end{frame}



% début




\section{Étude de schémas numériques}

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

\end{frame}



\begin{frame}

  \begin{block}{Question II.A.1}
    
  \begin{itemize}
  \item $y''(t)=f(y(t))$
  \item On introduit $z:I\to \bbr,\ z:t↦y'(t)$
  \item  Montrer que  l'équation  peut  se mettre  sous  la  forme d'un  système
    différentiel du premier ordre en $z(t)$ et $y(t)$ noté $(S)$.
  \end{itemize}


  \end{block}

\end{frame}



\begin{frame}
$$
\begin{cases}
y'(t)=z(t)\\
z'(t)=f \bigl( y(t) \bigr)
\end{cases}
$$
\end{frame}



\begin{frame}

  \begin{block}{Question II.A.2}
    
$n > 1, \ J_n=\llbracket 0, n-1 \rrbracket, \ t=\frac{t_{\max}-t_{\min}}{n-1}, \
t_i=t_{\min}+ih$

Montrer que pour tout entier $i\in\llbracket 0, n-2 \rrbracket$


$$y(t_{i+1})=y(t_i)+\int_{t_i}^{t_{i+1}}z(t)\d                           t\qquad
z(t_{i+1})=z(t_i)+\int_{t_i}^{t_{i+1}}f \bigl( y(t) \bigr)\d t$$

\end{block}
\end{frame}


\begin{frame}
$$\int_{t_i}^{t_{i+1}}z(t)\d t=\int_{t_i}^{t_{i+1}}y'(t)\d t=y(t_{i+1})-y(t_i)$$

\pause

$$\int_{t_i}^{t_{i+1}}f \bigl( y(t) \bigr)\d t = \int_{t_i}^{t_{i+1}}z'(t)\d t=z(t_{i+1})-z(t_i)$$
\end{frame}




\subsection{Schéma d'Euler explicite}


\begin{frame}\frametitle{Schéma d'Euler explicite}
  Dans le schéma d’Euler explicite, chaque terme sous le signe intégrale est remplacé par sa valeur prise en la
borne inférieure.

\pause


  \begin{block}{Question II.B.1}
    

Dans ce schéma, montrer que les équations précédentes permettent de définir deux
suites $(y_i)_{i\in J_n}$ et $(z_i)_{i\in J_n}$
où $y_i$ et $z_i$ sont des valeurs approchées de $y(t_i)$ et $z(t_i)$. 

Donner les relations de récurrence permettant de
déterminer les valeurs de $y_i$ et $z_i$ connaissant $y_0$ et $z_0$.
\end{block}

\end{frame}




\begin{frame}
$$\int_{t_i}^{t_{i+1}}z(t_i)\d t=z_ih\qquad  \int_{t_i}^{t_{i+1}}f \bigl( y(t_i)
\bigr)\d t=f(y_i)h$$


\pause


$$y_{i+1}=y_i+z_ih\qquad z_{i+1}=z_i+f(y_i)h$$
\end{frame}


\begin{frame}
\begin{center}
  EULER EXPLICITE $=$ MÉTHODE DES RECTANGLES
\end{center}
\end{frame}




\begin{frame}[fragile]



  \begin{block}{Question II.B.2}
    
  Écrire une fonction \verb+euler+ qui reçoit en argument les paramètres qui vous semblent pertinents et
qui  renvoie deux  listes de  nombres  correspondant aux  valeurs associées  aux
suites $(y_i)_{i\in J_n}$ et $(z_i)_{i\in J_n}$. 

Vous
justifierez le choix des paramètres transmis à la fonction.
\end{block}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def euler(f, y0, z0, h, n) :
    y, z = y0, z0
    ys, zs = [y], [z]
    for i in range(n - 1) :
        fy = f(y)
        y, z  = y + z*h, z + fy*h
        ys.append(y)
        zs.append(z)
    return ys, zs
\end{pythoncode}
\end{frame}



\begin{frame}
Pour illustrer cette méthode, on considère l’équation différentielle $$y''(t)=-ω^2y(t)$$ dans
laquelle $ω$ est un nombre réel.

\pause


  \begin{block}{Question II.B.3.a}
    

Montrer qu’on peut définir une quantité  E, indépendante du temps, vérifiant une
équation de la forme:

$$\frac{1}{2}y'(t)^2+g \bigl( y(t) \bigr) = E$$
\end{block}

\end{frame}



\begin{frame}
$$y''(t)=-ω^2y(t)$$ 

\pause

$$\frac{1}{2}2y'(t)y''(t)=-\frac{1}{2}ω^22y'(t)y(t)$$

\pause

$$\frac{1}{2}y'(t)^2+\frac{ω^2}{2}y(t)^2=E$$ 

\pause

$$E={\rm cte}\qquad g=x↦\frac{ω^2}{2}x^2$$
\end{frame}







\begin{frame}


  \begin{block}{Question II.B.3.b}
    
On  note $E_i$  la valeur  approchée  de $E$  à  l’instant $t_i$  , $i\in  J_n$,
calculée en utilisant les valeurs approchées  de $y(t_i)$ et $z(t_i)$ obtenues à
la question II.B.1. Montrer que $$E_{i+1}-E_i=h^2ω^2E_i$$
\end{block}

\pause

\textit{On fait les calculs et ça marche avec $z_{i+1}=z_i-ω^2y_ih$
}
\end{frame}


\begin{frame}



  \begin{block}{Question II.B.3.c}
    
Qu’aurait donné un schéma numérique qui satisfait à la conservation de 𝐸 ?

\end{block}
\pause

\bigskip
\bigskip

\textit{
Ben...l'énergie se conserve. On devrait avoir $ΔE=0$}

\end{frame}


\begin{frame}

  \begin{block}{Question II.B.3.d}
    

 En portant les valeurs  de $y_i$ et $z_i$ sur l’axe des  abscisses et l’axe des
 ordonnées respectivement, quelle serait l’allure du graphe qui respecte la conservation de $E$ ?

\end{block}
\end{frame}


\begin{frame}
$$\frac{1}{2}y'(t)^2+\frac{ω^2}{2}y(t)^2=E$$

\pause

$$\frac{1}{2}z^2+\frac{ω^2}{2}y^2=E$$

\pause

Ellipse


\end{frame}



\begin{frame}


  \begin{block}{Question II.B.3.e}
    

La mise en \oe uvre de la méthode d’Euler explicite génère le résultat graphique donné figure 1 à gauche. Dans
un  système d’unités  adapté,  les calculs  ont été  menés  en prenant  $y_0=3$,
$z_0=0$, $t_{\min} = 0$, $t_{\max} = 3$, $ω=2π$ et $n=100$



%\begin{figure}
\begin{center}
  \includegraphics[height=0.5\textheight]{figure1}
\end{center}
%\end{figure}

En quoi ce graphe confirme-t-il que le schéma numérique ne conserve pas 𝐸 ? Pouvez-vous justifier son allure ?

\end{block}

\end{frame}






\begin{frame}[fragile]
\begin{pythoncode}
import matplotlib.pyplot as plt

def phase_euler(f, y0, z0, h, n) :
    ys, zs = euler(f, y0, z0, h, n)
    plt.plot(ys, zs)
    plt.savefig("Graph.pdf")  
\end{pythoncode}


\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [46]: phase_euler(lambda x: -(2*pi)**2*x, 3, 0, 3/100,100)  
\end{pythoncode}



%\begin{figure}
\begin{center}
  \includegraphics[height=0.7\textheight]{../Python/Graph}
\end{center}
%\end{figure}



\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
In [46]: phase_euler(lambda x: -(2*pi)**2*x, 3, 0, 3/2**13,2**13)  
\end{pythoncode}



%\begin{figure}
\begin{center}
  \includegraphics[height=0.7\textheight]{../Python/Graph2}
\end{center}
%\end{figure}



\end{frame}

\subsection{Schéma de Verlet}

\begin{frame}[fragile]
  Le  physicien  français Loup  \textsc{Verlet}  a  proposé  en 1967  un  schéma
  numérique d’intégration d’une équation de la 
forme (II.1)  dans lequel, en  notant $f_i=f(y_i)$ et  $f_{i+1}=f(y_{i+1})$, les
relations de récurrence s’écrivent

$$y_{i+1}=y_i+hz_i+\frac{h^2}{2}f_i\qquad z_{i+1}=z_i+\frac{h}{2}(f_i+f_{i+1})$$

\begin{block}{Question II.C.1}
 Écrire une fonction \verb+verlet+ qui reçoit en argument les paramètres qui vous semblent pertinents et qui
renvoie deux  listes de nombres  correspondant aux valeurs associées  aux suites
$(y_i)_{i\in J_n}$ et $(z_i)_{i\in J_n}$. 
\end{block}


\end{frame}





\begin{frame}[fragile]
\begin{pythoncode}
def verlet(f, y0, z0, h, n) :
    y, z = y0, z0
    ys, zs = [y], [z]
    for i in range(n - 1) :
        fy     = f(y)
        y      = y + h*z + 0.5*h**2*fy
        fy_new = f(y)
        z      = z + 0.5*h*(fy + fy_new)
        ys.append(y)
        zs.append(z)
    return ys, zs
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def phase(methode, f, y0, z0, h, n, no) :
    ys, zs = methode(f, y0, z0, h, n)
    plt.plot(ys, zs)
    plt.savefig('Graph' + str(no) + '.pdf')
\end{pythoncode}

\pause

\begin{pythoncode}
In [18]: phase(verlet, lambda x: -(2*pi)**2*x, 3, 0, 3/100, 100, 3)  
\end{pythoncode}

\end{frame}

\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{../Python/Graph3}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}\frametitle{D'où sortent ces formules?}

Verlet \pause / Leapfrog \pause / Point milieu

\begin{figure}[h!]
\caption{Point milieu}
\begin{tikzpicture}[scale=1.0,transform shape]
\def\basic{%
    \draw[very thick, -stealth] (-0.3,0) -- (12,0) node[right] {$t$};% x-axis
    \draw[very thick, -stealth] (0,-0.3) -- (0,3)  node[above] {$f(y(t))$};% y-axis

    \draw [name path=curve, thick, blue] (0.5,2.2) .. controls (1.5,4.4) and (9.6,0.2) .. (9.5,1.5);% curve

    \foreach \x/\Point [count=\xi] in { 1/a, 1.5/b, 2.0/c, 2.5/d, 3.0/e, 5.6/f, 6.5/g, 7.4/h } {%
        \path [name path global=line \xi, red] (\x,0) -- (\x,3);
        \path [name intersections={of=curve and line \xi, by={\Point}}];
    }%

    \foreach \Line/\Name in { 1/a, 2/b, 3/c, 4/d, 5/e, 6/f, 7/g, 8/h} {% 
        \path [name intersections={of=curve and line \Line, by={\Name}}];
    }

    \foreach \point/\label in 
    {a/0 b/1, c/2, d/3, e/4, f/i-0.5, g/i, h/i+0.5} 
            \draw[densely dotted, thick] (\point|-0,0) node[below] {$t_{\label}$} -- (\point);

% Draw the desired lines
    \path[name path=Horizontal Line at g] (g) -| (0,0);
    \path[name intersections={of=Horizontal Line at g and line 6, by={f'}}];
    \draw[ultra thick, orange] (h) |- (g) -| (f');
}
\basic
%\node[above=10pt] at (k) {$\boxed{f(x)}$};
\end{tikzpicture} \end{figure}


  
\end{frame}


\begin{frame}
  $$z_{i+1/2}-z_{i-1/2}=\int_{t_{i-1/2}}^{t_{i+1/2}}f(y(t))\d t= hf_i$$
\end{frame}


\begin{frame}

\begin{figure}[h!]
\caption{Point milieu}
\begin{tikzpicture}[scale=1.0,transform shape]
\def\basic{%
    \draw[very thick, -stealth] (-0.3,0) -- (12,0) node[right] {$t$};% x-axis
    \draw[very thick, -stealth] (0,-0.3) -- (0,3)  node[above] {$z(t)$};% y-axis

    \draw [name path=curve, thick, blue] (0.5,2.2) .. controls (1.5,4.4) and (9.6,0.2) .. (9.5,1.5);% curve

    \foreach \x/\Point [count=\xi] in {1/a, 1.5/b, 2.0/c, 2.5/d, 3.0/e, 5.6/f, 6.5/g, 7.4/h } {%
        \path [name path global=line \xi, red] (\x,0) -- (\x,3);
        \path [name intersections={of=curve and line \xi, by={\Point}}];
    }%

    \foreach \Line/\Name in {1/a, 2/b, 3/c, 4/d, 5/e, 6/f, 7/g, 8/h} {% 
        \path [name intersections={of=curve and line \Line, by={\Name}}];
    }

    \foreach \point/\label in 
        {a/0, b/1, c/2, d/3, e/4, f/i, g/i+0.5, h/i+1} 
            \draw[densely dotted, thick] (\point|-0,0) node[below] {$t_{\label}$} -- (\point);

% Draw the desired lines
    \path[name path=Horizontal Line at g] (g) -| (0,0);
    \path[name intersections={of=Horizontal Line at g and line 6, by={f'}}];
    \draw[ultra thick, orange] (h) |- (g) -| (f');
}
\basic
%\node[above=10pt] at (k) {$\boxed{f(x)}$};
\end{tikzpicture} \end{figure}


  
\end{frame}




\begin{frame}
  $$y_{i+1}-y_i=\int_{t_i}^{t_{i+1}}z(t)\d t= hz_{i+1/2}$$
\end{frame}


\begin{frame}
  
  \begin{eqnarray*}
    z_{i+3/2}&=&z_{i+1/2}+hf_{i+1}\\
           &=&z_{i-1/2}+h(f_i+f_{i+1})\\
  \end{eqnarray*}


\pause

$$
\frac{z_{i+3/2}+{\color{blue}{z_{i+1/2}}}}{2}=\frac{z_{i+3/2}+{\color{blue}{z_{i+1/2}}}}{2} + \frac{h(f_i+f_{i+1})}{2}
$$

\pause

$$
z_{i+1}=z_i+h \frac{f_i+f_{i+1}}{2}
$$
\end{frame}



\begin{frame}
  $$y_{i+1}=y_i+hz_{i+1/2}$$

\pause

$$z_i=\frac{z_{i-1/2}+z_{i+1/2}}{2}\pause \qquad z_{i-1/2}=z_{i+1/2}-hf_i$$

\pause

$$z_{i+1/2}=z_i+h \frac{f_i}{2}$$

\pause

$$y_{i+1}=y_i+h \left(z_i+\frac{hf_i}{2}\right)$$
\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{blue}{\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{blue}{{f[x_1,x_2,x_3,x_4]}}$&\\
$f[x_2]$ & $f[x_2,x_3]$ & $\textcolor{blue}{{f[x_2,x_3,x_4]}}$ & & \\
$f[x_3]$ & $\textcolor{blue}{{f[x_3,x_4]}}$ & & & \\
$\textcolor{blue}{{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{white}{=}& \textcolor{white}{\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{white}{=}& \textcolor{white}{\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{white}{ \underbrace{\textcolor{black}{\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_0(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_1(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(t-\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}




\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 \approx  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, a, b, y0, n):
    y = y0
    h  = ( b - a ) / n
    ys  = [y]
    for k in range( n ):
        y += h * f( y,  a + k*h )
        ys.append(y)
    return ys
\end{pythoncode}


\end{frame}



\section{Algo $\neq$ Programme: approximation de $\pi$}


\begin{frame}[fragile]
  
$$\pi=4      \displaystyle
\displaystyle\int_{0}^{1} \sqrt{1-t^2} \;{\rm d} t$$

\pause

\begin{pythoncode}
from math import sqrt, pi

def f(t):
    return sqrt(1-t*t)
\end{pythoncode}




\end{frame}


\subsection{Méthode des rectangles}



\begin{frame}[fragile]

\begin{pythoncode}
def int_rec_droite(f,a,b,N):
    S = 0
    t = a
    dt = (b-a)/N
    while t < b :
        S += f(t)*dt
        t += dt
    return S
  \end{pythoncode}

\pause

  \begin{pythoncode}
def int_rec_gauche(f,a,b,N):
    S = 0
    t = a
    dt = (b-a)/N
    while t+dt < b :
        S += f(t+dt)*dt
        t += dt
    return S
\end{pythoncode}

\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
>>> 4*int_rec_gauche(f,0,1,100)
3.1204170317790454
>>> 4*int_rec_gauche(f,0,1,10000)
3.1413914777848557
\end{pythoncode}


\pause

\begin{pythoncode}
>>> pi - 4*int_rec_gauche(f,0,1,10000)
0.0002011758049373924  
\end{pythoncode}



\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(8): print(pi - 4*int_rec_gauche(f,0,1,10**k))
... 
3.141592653589793
0.23707432138101003
0.021175621810747725
0.002037186678767622
0.0002011758049373924
2.003710526476965e-05
2.001187481948108e-06
1.9943306694969465e-07
\end{pythoncode}
\end{frame}


\subsection{Méthode des trapèzes}


\begin{frame}[fragile]
\begin{pythoncode}
def int_trap(f,a,b,N):
    S = 0
    t = a
    dt = (b-a)/N
    while t+dt <= b :
        S += (f(t)+f(t+dt))*dt/2
        t += dt
    return S
\end{pythoncode}
\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(8): print(pi-4*int_trap(f,0,1,10**k))
... 
1.1415926535897931
0.03707432436124236
0.003996969006682782
0.00012660703439637544
1.1758915650084134e-06
3.7144431530578004e-08
4.015919596866979e-09
-5.628750798791771e-10
\end{pythoncode}

\pause

Dernier résultat ??

\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
>>> def int_trap(f,a,b,N):
    S=0
    dt=(b-a)/N
    for k in range(N):
        S += (f(a + k*dt) + f(a + (k+1)*dt)) * dt/2
    return S
... ... ... ... ... ... 
>>> for k in range(8): print(pi - 4*int_trap(f,0,1,10**k))
... 
1.1415926535897931
0.037074327341474866
0.001175621810749039
3.7186678768730275e-05
1.1759784679377105e-06
3.718782926043218e-08
1.1759344609174605e-09
3.643840784661734e-11
\end{pythoncode}
\end{frame}



\begin{frame}[fragile]

$$\pi=12 \left( \displaystyle\int_{0}^{\frac{1}{2}} f(t) \;{\rm d}
  t - \frac{\sqrt{3}}{8}\right)$$

\pause

\begin{pythoncode}
>>> for k in range(7): print(pi-12*(int_trap(f,0,1/2,10**k)-sqrt(3)/8))
... 
0.14159265358979312
0.0014430555975519788
0.05206198505358994
0.005197162208523842
1.4433143569192453e-09
1.3836487511298401e-11
5.1961539169198545e-06
\end{pythoncode}

\pause

?????

\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(7): print(pi-12*(int_trap(f,0,1/2,10**k)-sqrt(3)/8))
... 
0.14159265358979223
0.0014430555975519788
1.4433724657703095e-05
1.443375703402694e-07
1.4433609862862795e-09
1.439337538045038e-11
1.1457501614131615e-13
\end{pythoncode}

\end{frame}


\subsection{Méthode de \textsc{Simpson}}


\begin{frame}[fragile]
\begin{pythoncode}
def int_simps(f,a,b,N):
    S = 0
    t = a
    dt = (b-a)/N
    while t+dt <= b:
        S += ( f(t) + 4*f(t + dt/2) + f(t + dt) ) * dt/6
        t += dt
    return S
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(8): print(pi-4*int_simps(f,0,1,10**k))
... 
0.16552491016462367
0.00514558833917933
0.003766184709476761
0.0001192583254159274
1.6234044686314064e-07
5.117280821309578e-09
3.783345636776403e-09
-5.92078830408127e-10
\end{pythoncode}
\end{frame}




\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(8): print(pi - 12*(int_simps(f,0,1/2,10**k)-sqrt(3)/8))
... 
0.0006601149512537319
7.997674877913141e-08
0.0520477428322228
0.005197018063311631
-2.042810365310288e-14
-5.88862292261183e-13
5.1961537730349505e-06
-8.213874025386758e-11
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(8): print(pi - 12*(int_simps(f,0,1/2,10**k)-sqrt(3)/8))
... 
0.0006601149512537319
7.997674877913141e-08
8.021139308311831e-12
5.329070518200751e-15
2.1316282072803006e-14
-3.907985046680551e-14
-3.375077994860476e-14
-5.284661597215745e-13
\end{pythoncode}
\end{frame}



\begin{frame}
  \begin{center}
    Ah oui, j'ai eu un cours sur les flottants
  \end{center}
\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
>>> for k in range(13): print(pi-12*(int_simps(f,0,1/2,2**k)-sqrt(3)/8))
... 
0.0006601149512537319
4.72214266773463e-05
3.0824728671774437e-06
1.9496909775540416e-07
1.222303502856903e-08
7.645306610015723e-10
4.779110440722434e-11
2.9887203822909214e-12
1.8474111129762605e-13
7.993605777301127e-15
-4.440892098500626e-16
-1.3766765505351941e-14
-8.881784197001252e-15
\end{pythoncode}
\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
>>> f(1e-8)
1.0
\end{pythoncode}

\pause

\verb+while+ et \verb+for+

\pause

 \verb|while  t+dt<=b| 

\pause

\begin{pythoncode}
>>> 1 + 0.1 + 0.1 + 0.1 - 0.3 <= 1
False
\end{pythoncode}



\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
print('-'*75)
print('{:22s} | {:22s} | {:22s}'.format('rectangle gauche', 'trapeze', 'simpson'))
print('-'*75)

for k in range(10):
    print("{:1.16e} | {:1.16e} | {:1.16e}".format(\
        pi-12*(int_rec_gauche(f, 0, 1/2, 2**k)-sqrt(3)/8), \
        pi-12*(int_trap(f, 0, 1/2, 2**k)-sqrt(3)/8), \
        pi-12*(int_simps(f, 0, 1/2, 2**k)-sqrt(3)/8)))
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
---------------------------------------------------------------------------
rectangle gauche    | trapeze             | simpson
---------------------------------------------------------------------------
5.4351644223647e-01 | 1.4159265358979e-01 | 6.6011495125373e-04
2.3685514393423e-01 | 3.5893249610888e-02 | 4.7221426677346e-05
1.0948967563440e-01 | 9.0087284727298e-03 | 3.0824728671774e-06
5.2494967553668e-02 | 2.2544939728321e-03 | 1.9496909775540e-07
2.5684006510449e-02 | 5.6376972003269e-04 | 1.2223035028569e-08
1.2701069992491e-02 | 1.4095159728411e-04 | 7.6453066100157e-10
6.3152976703237e-03 | 3.5238472716692e-05 | 4.7791104407224e-11
3.1488392528258e-03 | 8.8096540218352e-06 | 2.9887203822909e-12
1.5722172151479e-03 | 2.2024157457778e-06 | 1.8474111129762e-13
7.8555800377522e-04 | 5.5060407389007e-07 | 7.9936057773011e-15
\end{pythoncode}
\end{frame}

\begin{frame}
  \textit{démonstration mathématique et domination de la machine valent
  mieux qu'observation et utilisation au petit bonheur}



\end{frame}



\subsection{Bye bye $\pi$?}


\begin{frame}[fragile]
\begin{pythoncode}
>>> from decimal import*
# on regle la precision a 30 chiffres
>>> getcontext().prec = 30
# on rentre les nombres entre apostrophes, comme des chaines
>>> deux=Decimal('2')
>>> deux.sqrt()
Decimal('1.41421356237309504880168872421')
>>> getcontext().prec = 50
>>> deux.sqrt()
Decimal('1.4142135623730950488016887242096980785696718753769')
\end{pythoncode}
\end{frame}



\begin{frame}
 James \textsc{Gregory} 1671:

\[{\rm Arctan}(x)=\sum_{k=0}^{+\infty} \frac{(-1)^kx^{2k+1}}{2k+1}\]

\pause

Wilhelm \textsc{Leibniz} 1682: critère spécial des séries alternées:



\[\left|{\rm Arctan}(x)-\sum_{k=0}^n \frac{(-1)^kx^{2k+1}}{2k+1}\right|<\frac{x^{2n+3}}{2n+3}\]

\pause

Valeur  de $n$ telle
que $ \frac{a^{2n+3}}{2n+3} \leqslant 10^{-d}$?

\pause

\[ \left(2+\frac{3}{n}\right)\log  \frac{1}{a}
\geqslant \frac{d}{n}- \frac{\log(2n+3)}{n}\]

\end{frame}

\begin{frame}
  John \textsc{Machin} 1706:


$$4\,\arctan\frac{1}{5}-\arctan\frac{1}{239}=\frac{\pi}{4}$$


\pause

Polynôme de \textsc{Gregory}

$$G_n(X)=\displaystyle\sum_{k=0}^n \frac{(-1)^kX^{2k+1}}{2k+1}$$

\end{frame}

\begin{frame}[fragile]
\begin{pythoncode}
def greg(a,N):
    ad = Decimal('1')/Decimal(str(a))
    nd = ad
    dd = Decimal('1')
    s  = nd/dd
    for k in range(1,N):
        nd *= Decimal('-1')*ad*ad
        dd += Decimal('2')
        s  += nd/dd
    return s
\end{pythoncode}

\pause


\begin{pythoncode}
def pi_machin(d):
    getcontext().prec = d+2
    rap=2*log(5)/log(10)
    N=int(d/rap)+1
    return 4*(4*greg(5,N)-greg(239,N)) 
\end{pythoncode}



\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
>>> PI-pi_machin(1000)
Decimal('-1.5E-1000')
\end{pythoncode}

\pause

\begin{pythoncode}
>>> pi_machin(1000)
Decimal('3.14159265358979323846264338327950288419716939937510582097494459230781640628\
6208998628034825342117067982148086513282306647093844609550582231725359408128481117450\
2841027019385211055596446229489549303819644288109756659334461284756482337867831652712\
0190914564856692346034861045432664821339360726024914127372458700660631558817488152092\
0962829254091715364367892590360011330530548820466521384146951941511609433057270365759\
5919530921861173819326117931051185480744623799627495673518857527248912279381830119491\
2983367336244065664308602139494639522473719070217986094370277053921717629317675238467\
4818467669405132000568127145263560827785771342757789609173637178721468440901224953430\
1465495853710507922796892589235420199561121290219608640344181598136297747713099605187\
0721134999999837297804995105973173281609631859502445945534690830264252230825334468503\
5261931188171010003137838752886587533208381420617177669147303598253490428755468731159\
56286388235378759375195778185778053217122680661300192787661119590921642019915')  
\end{pythoncode}



\end{frame}



\begin{frame}
  Et sinon:


%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{plouffe}
\end{center}
%\end{figure}


\end{frame}

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