%% Last modified: <Analyse_calcul_diff.tex modifié par  Guillaume CONNAN le jeudi 14 mai 2015 à 18h 42min 17s>


\chapterimage{differentiel}
\chaptertext{La notion d'\textit{infiniment petit} a  crée des guerres entre les
  savants pendant deux siècles. Elle n'a été formalisée rigoureusement qu'à la fin du XIX\eme
  siècle.  Cependant,  nous allons  rester  fidèle  au cheminement  de  l'esprit
  humain  et  nous  attacher  à   cette  notion  qui  est  pédagogiquement  plus
  intéressante et se rapproche de l'arithmétique des flottants sur machine Cette
  approche historique  et intuitive du calcul  a été magistralement mise  en \oe
  uvre dans \cite{opac-b1096819}.}

\chapter{Un soupçon de calcul différentiel}


\section{Le calcul infinitésimal}


\subsection{Infiniment petits}

La notion de dérivée est née bien avant celle de limite: dès le XVII\eme \textsc{Fermat}, \textsc{Newton}, \textsc{Leibniz}, Jean \textsc{Bernoulli},
vont développer  le calcul  infinitésimal, avant que \textsc{Bolzano} et \textsc{Weierstra\ss}
ne perfectionnent la notion de limite deux siècles plus tard. 

Mais les approches  des savants du XVII\eme s'adaptent bien  à l'utilisation des
flottants sur machine. 

L'informatique nous incite donc à un retour aux sources historiques.




\begin{remarque}[Analyse non standard et hyperréels]
\ill{Il  est à noter  que dans  les années  1960, un  logicien américain
d'origine allemande (encore un!...), Abraham
\textsc{Robinson},  mit  au  point  l'\textit{analyse non  standard}  en
utilisant les \textit{nombres hyperréels}. 
Il s'agit  de  nos  réels
auxquels on adjoint des nombres \textit{infinitésimaux} qui sont}{robinson}
strictement inférieurs en valeur absolue  à tout nombre réel non nul, et
les   nombres  \textit{infiniment   grands}  dont   les   inverses  sont
infinitésimaux.  Ceci  est fait de  manière très rigoureuse et  permet de
justifier une incroyable intuition que \textsc{Fermat}
avait présenté trois siècles plus tôt.

C'est également assez proche de la définition des flottants selon la norme IEEE 754
\end{remarque}

Pour Jean \textsc{Bernoulli} (1691), \textbf{les infiniment petits sont des quantités
qui  peuvent être  ajoutées à  des quantités  finies sans  changer leurs
valeurs. Les courbes sont des polygones à côtés infiniment courts.} 

Voici  qui s'adapte  à la  notion de  sous-capacité et  au tracé  de courbes  sur
machine.


Voyons  ce que  cela donne  pour les  tangentes à  la  courbe d'équation
$y=x^2$:



%\begin{figure}
\begin{center}
  \includegraphics{limfonc.22}
\end{center}
%\end{figure}


Si $x$ augmente de $\Delta x$, alors $y$ devient $y+\Delta y=(x+\Delta x)^2
=x^2+2x\Delta x+(\Delta x)^2$. Or $y=x^2$.

Pour des valeurs de $\Delta x$ non nulles, cela donne donc:

\[\frac{\Delta y}{\Delta x}= 2x+\Delta x\]


C'est  ici qu'on  a  besoin  de la  notion  intuitive d'infiniment  petits...qui
commence pour nous avec la sous-capacité.


\begin{remarque}
\ill{C'est  Joseph-Louis \textsc{Lagrange}(1736-1813)  ou plutôt  Giuseppe Lodovico
\textsc{Lagrangia},  un  mathématicien  Piémontais d'origine  française,
qui  introduisit  les  termes   et  les  notations  que  nous  utilisons
actuellement:
\begin{quote}
Nous  appellerons  la fonction  $f_x$,  \textit{fonction primitive},  par
rapport aux  fonctions $f'_x$,  $f''_x$, \&c. qui  en dérivent,  et nous
appellerons celles-ci, \textit{fonctions dérivées}, par rapport à celle-là.
\end{quote}
Il a aussi  réfuté la notion d'infiniment  petit et a tenté  de fonder l'analyse
sur les séries de \textsc{Taylor}: nous allons en reparler.
}{lagrange}


\end{remarque}



\subsection{Règles de dérivation}\label{sec::regDeriv}


\subsubsection{Dérivée d'une combinaison linéaire}

Soit  $y(x)=a\cdot u(x)+b\cdot  v(x)$  avec $a$  et  $b$ des  constantes
réelles.
En   posant   comme   précédemment  $y+\Delta(y)=y(x+\Delta   x)$   puis
$u+\Delta(u)=u(x+\Delta   x)$  et   $v+\Delta(v)=v(x+\Delta   x)$,  nous
obtenons $\Delta y=a\cdot \Delta u+b\cdot \Delta v$.
Alors:

\begin{theoreme}[Dérivation d'une combinaison linéaire]
$$y=au+bv     \Longrightarrow     \frac{\mathrm{d}y}{\mathrm{d}x}=a\cdot
\frac{\mathrm{d}u}{\mathrm{d}x}+b\cdot    \frac{\mathrm{d}v}{\mathrm{d}x}
\text{ ou bien } y'=a\cdot u'+b\cdot v'$$
\end{theoreme}


\subsection{Dérivée d'un produit}

\begin{recherche}
  Essayez  de prouver  de  même  une règle  de  dérivation d'un  produit
  $y=u\cdot v$.
\end{recherche}



\begin{theoreme}[Dérivation d'un produit]
$$y=u\cdot v \Longrightarrow \hspace{20em}$$
\end{theoreme}


\subsubsection{Dérivée d'un quotient}


Nous  allons d'abord  établir  un résultat  préliminaire.  Pour $x$  \og
petit\fg{} on \og sent\fg{} que $\frac{1}{1-x}\approx 1$.

Par exemple $\frac{1}{1-10^{-5}}\approx 1,0000100001=1+10^{-5}+10^{-10}$.


Essayons d'être plus précis sur l'approximation. Posons
$$\frac{1}{1-x}=1+\delta$$

et essayons  de déterminer  ce $\delta$ sachant  qu'on peut  le négliger
devant $x$.

Multiplions chaque membre de l'équation par $1-x$. On obtient:


$$1=1-x+\delta(1-x)$$

c'est-à-dire, après simplifications:

$$\delta=x+\delta x$$


Ainsi, comme $\delta x$ est négligeable devant $x$, on peut considérer que
$\delta\approx x$ donc:

$$\frac{1}{1-x}\approx 1+x$$

\begin{remarque}[Série géométrique]
\ill{En 1593, François \textsc{Viète} établit avec une méthode similaire
que, pour tout réel $x$ tel que
$|x|<1$, on a:
$$\frac{1}{1-x}=1+x+x^2+x^3+x^4+x^5+\cdots$$}{Viete}
\end{remarque}



\begin{recherche}
  Vous  pouvez  maintenant  essayer  d'établir une  formule  donnant  la
  dérivée d'un quotient $y=\frac{u}{v}$.

\end{recherche}


\begin{theoreme}[Dérivation d'un quotient]
$$y=\frac{u}{v} \Longrightarrow \hspace{20em}$$
\end{theoreme}



\subsubsection{Fonctions composées}


Soit trois fonctions $f$, $g$ et $h$ telles que $h=f\circ g$.
Ainsi, $h(x)=f \bigl( g(x) \bigr)$.

Posons $g(x+\Delta x)=z+\Delta z$ et $h(x+\Delta x)=y+\Delta y$. 

Alors $y+\Delta y=f \bigl( g(x+\Delta x) \bigr)=f(z+\Delta z)$.
Or    $\frac{\Delta   y}{\Delta   x}=\frac{\Delta    y}{\Delta   z}\cdot
\frac{\Delta z}{\Delta x}$. On obtient donc:


\begin{theoreme}[Dérivation de fonctions composées]
$$\frac{{\rm d}   y}{{\rm d}   x}=\frac{{\rm d}    y}{{\rm d}   z}\cdot
\frac{{\rm  d}  z}{{\rm   d}  x}  \text{  ou  }   h'(x)=f'  \bigl(  g(x)
\bigr)\cdot g'(x)$$
\end{theoreme}


Par  exemple, si $h(x)=\left(3x-5\right)^2$,  alors $y=h(x)=f  \bigl( g(x)
\bigr)$ avec $z=g(x)=3x-5$ et  $f(z)=z^2$. On en déduit que
$h'(x)=\frac{{\rm d}    y}{{\rm d}   z}\cdot
\frac{{\rm d} z}{{\rm d} x}=2z\cdot 3=6(3x-5)$.



\section{Comment calculer un logarithme sur machine..au XVII\eme
  siècle?}


\subsection{Calcul d'une approximation d'une racine carrée par la méthode de \textsc{Héron}}\label{sec::heron}



Le mathématicien \textsc{Héron} d'Alexandrie n'avait pas attendu \textsc{Newton} et le
calcul différentiel  pour trouver  une méthode permettant  de déterminer
une approximation de la racine carrée d'un nombre entier positif puisqu'il a
vécu seize siècles avant Sir Isaac.


Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
$\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
(pourquoi~?) et vice-versa.

La    moyenne   arithmétique    de   ces    deux    approximations   est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
approximation que les deux précédentes.

On  peut  montrer c'est  une  approximation  par  excès (en  développant
$\left(x_n-\sqrt{a}\right)^2$ par exemple).

\begin{haskellcode}
heron a x n 
  | n == 0    = x
  | otherwise = heron a ((x + a / x) / 2) (n - 1) 
\end{haskellcode}

Le résultat est assez bluffant:

\begin{haskellcode}
*Main> heron 2 1 5
1.414213562373095
*Main> sqrt 2
1.4142135623730951
\end{haskellcode}


Il  y a  cependant des  discussions au  sujet de  l'exactitude des  calculs dans
$\bbv$: nous en reparlerons dans un prochain chapitre quand nous saurons diviser
deux flottants :-)

\subsection{Calcul d'une approximation de log 2 par la méthode de \textsc{Briggs}}
\label{sec::briggs}

\setindent{-0.75cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.65cm]{stifel}
%\caption{\foreignlanguage{russian}{Николай Петрович Брусенцов}(1925 -)}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.2cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Michael \textsc{Stifel} s'est intéressé dès 1544 aux fonctions vérifiant
$\ell(x\cdot  y)=\ell(x)+\ell(y)$  afin de  simplifier  les calculs  des
astronomes et des navigateurs.  Cependant, cela nécessite de disposer de
tables  \textit{logarithmiques} ($\lambda  o \gamma  o  \varsigma$: mot,
relation,  $\alpha  \rho \iota  \theta  \mu  o  \varsigma$: nombre;  les
logarithmes  sont donc  des  relations entre  les  nombres avant  d'être
l'anagramme d'algorithmes...).

Nous allons nous occuper comme Henry \textsc{Briggs} du logarithme de base
10.

Sachant que $\log_{10}(10)=1$ et  que $\log_{10} \left(a^p\right) =p\cdot \log_{10}(a)$
pour        tout         rationnel        $p$,       on en déduit  alors   que     $\log_{10}
\left(\sqrt{10}\right)=\frac{1}{2}$,                                $\log_{10}
\left(\sqrt{\sqrt{10}}\right)=\frac{1}{4}$, etc.

Nous  pouvons  utiliser  l'algorithme   de  \textsc{Horner}  pour  calculer  les
approximations des racines successives de 10 et on obtient le tableau suivant:



\begin{center}
             \begin{tabular}{lccccc}
	     \hline
             Nombres & 10,0000 & 3,1623 & 1,7783 & 1,3335 & 1,0000\\
             Logarithmes & 1 & 0,5 & 0,25 & 0,125 & 0\\
             \hline
             \end{tabular}
             \end{center}
Le problème, c'est que connaître  le logarithme de 3,1623 n'est pas très
intéressant. On aimerait plutôt connaître ceux des entiers de 1 à 10.

C'est ici  qu'intervient l'anglais  Henry \textsc{Briggs} qui  publia en
1617   ses   premières   tables   de  logarithmes   décimaux   contenant
$\numprint{1000}$ valeurs avec quatorze décimales.

Voyons comment il a procédé pour le calcul de $\log(2)$.

Il a commencé par obtenir des valeurs approchées des nombres suivant:

\begin{center}
\begin{tabular}{cc}
  $\sqrt{10}=10^{\frac{1}{2}}$ & $\sqrt{2}=2^{\frac{1}{2}}$\\
$\sqrt{\sqrt{10}}=10^{\frac{1}{2^2}}$ & $\sqrt{\sqrt{2}}=2^{\frac{1}{2^2}}$\\
$\sqrt{\sqrt{\sqrt{10}}}=10^{\frac{1}{2^3}}$ & $\sqrt{\sqrt{\sqrt{2}}}=2^{\frac{1}{2^3}}$\\
$\vdots$ & $\vdots$\\
$\sqrt{\sqrt{\cdots         \sqrt{10}}}=10^{\frac{1}{2^{54}}}$         &
$\sqrt{\sqrt{\cdots \sqrt{2}}}=2^{\frac{1}{2^{54}}}$\\
\end{tabular}
\end{center}

Il a finalement abouti à:


\[
10^{\frac{1}{2^{54}}}\approx
\underbrace{\numprint{1,00000000000000012781914932003235}}_{1+a} \]

\[ 2^{\frac{1}{2^{54}}}\approx \underbrace{\numprint{1,00000000000000003847739796558310}}_{1+b}
\]


Or  on cherche à  déterminer $x=\log(2)$  mais $x=\log(2)\Leftrightarrow
10^x=2$.

D'après les calculs de \textsc{Briggs}:

\[
1+b=2^{\frac{1}{2^{54}}}=\left(10^x\right)^{\frac{1}{2^{54}}}=(1+a)^x
\]

Un  résultat  classique  que  nous   allons  très  bientôt  étudier  montre  que
$(1+a)^x\approx 1+ax$ pour $a$ assez 
proche de zéro et $x>0$. On en déduit que
$1+b\approx 1+ax$ et donc que:

\[
\log(2)=x\approx
\frac{b}{a}=\frac{\numprint{3847739796558310}}{\numprint{12781914932003235}}
\]

\begin{haskellcode}
*Main>  3847739796558310 / 12781914932003235
0.30102999566398114
\end{haskellcode}

Ainsi, $\log(2)\approx \numprint{0,30102999566398114}$.


Cela  nous permet  alors d'avoir  également  $\log(4)=2\times\log(2)$ et
$\log(8)=3\times\log(2)$ mais aussi $\log(5)=\log(10)-\log(2)$.

Il  nous faudrait  donc  obtenir  de même  $\log(3)$  et $\log(7)$  pour
compléter    notre   collection    car    $\log(6)=\log(3)+\log(2)$   et
$\log(9)=2\cdot\log(3)$.

On  peut donc  à titre  d'exercice  calculer ces  deux logarithmes  pour
obtenir:

\[
\log(3)\approx \numprint{0,47712125471966244} \quad \log(7)\approx \numprint{0.8450980400142567}
\]


La   route   est   longue   jusqu'aux   $\numprint{1000}$   logarithmes   de
\textsc{Briggs}\citep{roegel:inria-00543939}:


  \begin{center}
    \includegraphics[height=6cm]{briggs}
  \end{center}

On  peut  retrouver  ces  résultats  sur Sage  qui  permet  de  travailler  très
simplement avec MPFR:

\sagec

\begin{pythoncode}
# Travail commode avec la bibliothèque MPFR de C  via sage
# On ouvre dans emacs un fichier d'extension sage qui met emacs en mode sage
# La syntaxe de programmation est celle de Python
#
 
# On travaille sur 128 bits (on donne la précision = taille de la mantisse)
RN = RealField(113)
 
# Algorithme de Héron pour calculer ?..
def racine(a,x,n):
    if n == 0:
        return RN(x)
    else:
        return racine(RN(a), ??? * RN(0.5), n - 1)
 
# quid ?
def racine_n(a,n):
    if n == 0:
        return RN(a)
    else:
        return racine_n(racine(RN(a),1.0,10), n - 1)
 
# Calcul de log 2
a = ???
b = ???
 
logDeux = RealField(53)(b / a) # résultat projeté sur 64 bits
diffLog = logDeux - (log(2.))/ log(10.) # On compare avec le log 2 de sage
 
# Calcul de log 3 et log 7 ? Généralisation ? log 0 ?  log (-10) ?
\end{pythoncode}

Alors:

\begin{pythoncode}
sage: logDeux
0.301029995663981182
sage: diffLog
5.55111512312578e-17
\end{pythoncode}

\haskell


\subsection{Polynômes interpolateurs}


\subsubsection{Qu'est-ce qu'un polynôme?}

Les  polynômes en  informatique  sont  un outil  très  puissant  et très  utile,
notamment en  théorie de l'information  (détection et correction  d'erreur). Les
entiers en précision  infinie sont considérés comme des  polynômes. Les exemples
abondent mais il s'agit d'une vision discrète  de la notion: un polynôme est une
liste  finie  de  nombres  et  on munit  l'ensemble  des  polynômes  d'opérations
spécifiques.



Nous allons ici étudier plutôt les fonctions polynomiales, i.e. les fonctions de
la forme:

$$p~:~x\mapsto p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots + a_0$$

où les $a_i$ sont des constantes arbitraires  qui seront pour nous des nombres à
virgule flottante. Si $a_n$ est non nul, on dira que la fonction polynôme est de
degré $n$.

Cette fonction correspond au polynôme:
 $$P=[a_n,a_{n-1},...,a_0]$$


Dans  $\bbf_2$  nous verrons  que  la  distinction  entre polynôme  et  fonction
polynomiale est très  importante. Dans $\bbr$ ou $\bbv$, c'est  moins grave mais
bon...


L'intérêt? Il  s'agit de  fonctions très rapidement  évaluables sur  machine car
faisant  intervenir   uniquement  des  additions   et  des
multiplications.


\subsubsection{Problème d'interpolation}

On  connaît   quelques  valeurs   du  logarithme  donnée   par  la   méthode  de
\textsc{Briggs}.  Cependant, cette  méthode  est très  fastidieuse: il  faudrait
trouver une autre idée pour calculer les valeurs intermédiaires.

Par exemple, on connaît pour l'instant  des approximations des logarithmes de 1,
2, 3 et 4. Comment faire pour déterminer des approximations de tous les nombres entre 1
et 4 avec un pas de 0,25?

Nous allons chercher un polynôme de degré  3 qui passe par ces quatre points. On
cherche donc $a$, $b$, $c$ et $d$ tels que:

$$
\left\{ \begin{array}{l}
p(x)=a+bx+cx^2+dx^3\\
\mathtt{map}\ p\ [1,2,3,4] = \mathtt{map}\ \log\ [1,2,3,4]
\end{array}
\right.
$$


C'est un simple  système linéaire de 4 équations à  quatre inconnues. Cependant,
les équations ont  une forme très spéciale. Voyons une  première éthode proposée
par \textsc{Newton} en 1676.



\subsubsection{Interpolation de \textsc{Newton}}\label{sec::interpolNewton}

Notons $[y_1,y_2,y_3,y_4]= \mathtt{map}\ \log\ [1,2,3,4]$.


\begin{figure}[h!]
  \begin{center}
    \includegraphics[height=7cm]{newton_diff}
    \caption{Problème  d'interpolation   dans  \textit{Methodus  Differentialis}
      publié par \textsc{Newton} en 1676}
    \label{fig:newton_diff}
  \end{center}
\end{figure}

Appliquons l'algorithme  de Gau\ss{}  à ce  système même si  le génie  allemand ne
naîtra qu'un siècle plus tard:

\begin{center}
\begin{tabular}{|l|l|}
  \hline
$x=1$ & $p(x)=a+b+c+d=y_1$\\
$x=2$ & $p(x)=a+2b+4c+8d=y_2$\\
$x=3$ & $p(x)=a+3b+9c+27d=y_3$\\
$x=4$ & $p(x)=a+4b+16c+64d=y_4$\\
\hline
\end{tabular}
\end{center}

En soustrayant les lignes deux par deux, on fait disparaître $a$:

\begin{center}
\begin{tabular}{|l|}
  \hline
 $y_2-y_1=b+3c+7d=\Delta y_1$\\
$y_3-y_2=b+5c+19d=\Delta y_2$\\
$y_4-y_3=b+7c+37d=\Delta y_3$\\
\hline
\end{tabular}
\end{center}

En soustrayant les lignes deux par deux, on fait disparaître $b$:

\begin{center}
\begin{tabular}{|l|}
  \hline
 $\Delta y_2-\Delta y_1=2c+12d=\Delta^2 y_1$\\
 $\Delta y_3-\Delta y_2=2c+18d=\Delta^2 y_2$\\
\hline
\end{tabular}
\end{center}

En soustrayant les lignes deux par deux, on fait disparaître $c$:


$\Delta^2 y_2-\Delta^2 y_1=6d=\Delta^3 y_1$

ce qui donne:

  $d=\frac{1}{6}\Delta^3 y_1$


  $c=\frac{1}{2}\Delta^2
y_1-\Delta^3y_1$


 $b=\Delta y_1-\frac{3}{2}\Delta^2
y_1+3\Delta^3y_1-\frac{7}{6}\Delta^3 y_1=\Delta y_1-\frac{3}{2}\Delta^2y_1+\frac{11}{6}\Delta^3 y_1$


$a=y_1-\Delta y_1+\frac{3}{2}\Delta^2y_1-\frac{11}{6}\Delta^3 y_1-\frac{1}{2}\Delta^2
y_1+\Delta^3y_1-\frac{1}{6}\Delta^3 y_1=y_1-\Delta y_1+\Delta^2 y_1-\Delta^3 y_1$



Finalement:

\[
P(x)=y_1+(x-1)\Delta y_1+\frac{1}{2}(x-1)(x-2)\Delta^2 y_1+\frac{1}{6}(x-1)(x-2)(x-3)\Delta^3 y_1
\]


\textsc{Newton} avait l'habitude de  réunir les résultats dans un schéma
de cette forme:

\begin{center}
\begin{tabular}{cccc}
$\mathbf{y_1}$ &                      &                       &                         \\
               &$\mathbf{\Delta y_1}$ &                       &                         \\
$y_2$          &                      &$\mathbf{\Delta^2 y_1}$&                         \\
               &$\Delta y_2$          &                       & $\mathbf{\Delta^3 y_1}$ \\
$y_3$          &                      &$\Delta^2 y_2$         &                         \\
               &$\Delta y_3$          &                       &                         \\
$y_4$          &                      &                       &                         \\
\end{tabular}
\end{center}


avec $\Delta y_i=y_{i+1}-y_i$, $\Delta^2y_i=\Delta y_{i+1}-\Delta y_i$ et $\Delta^3y_i=\Delta^2 y_{i+1}-\Delta^2 y_i$.




On peut généraliser à des abscisses successives de 1 à $n$:

\begin{theoreme}[Interpolation  de   \textsc{Newton}  passant  par   les  points
  $(1,y_1)$, $(2,y_2)$,..., $(n,y_n)$]\label{th::newton}
\[
p(x)=y_1+(x-1)\Delta y_1+\frac{1}{2!}(x-1)(x-2)\Delta^2 y_1+\cdots+\frac{1}{(n-1)!}(x-1)\cdots(x-(n-1))\Delta^{n-1} y_1
\]
\end{theoreme}

voire à d'autres valeurs d'entiers successifs:

\begin{theoreme}[Interpolation  de   \textsc{Newton}  passant  par   les  points
  $(α,y_1)$, $(α+1,y_2)$,..., $(α+n-1,y_n)$]\label{th::newton_gen}
\[
p(x)=y_1+(x-α)\Delta y_1+\frac{1}{2!}(x-α)(x-α-1)\Delta^2 y_1+\cdots+\frac{1}{(n-1)!}(x-α)\cdots(x-α-(n-2))\Delta^{n-1} y_1
\]
\end{theoreme}


On peut généraliser à des suites quelconques d'abscisses mais c'est un peu plus compliqué.



\section{Polynômes et erreurs}\label{sec::horner}


Nous  allons  étudier à  l'\vref{ex::horner}  un  moyen d'évaluer  une  fonction
polynomiale en un nombre particulier.

Cependant, nous allons  être à nouveau confrontés au problème  des erreurs suite
au calcul sur les nombres à virgule flottante.

Considérons par exemple la fonction $x\mapsto (x-2)^9$ au voisinage de 2.

Une petite illustration vaut mieux qu'un long discours...Avec le code suivant:

\begin{haskellcode}
comparePoly = 
  plot X11  [ 
    Data2D [Title "Schéma Horner", Color Blue, Style Lines] [] [(x, exHorn x) | x <-  [1.94, 1.940125 .. 2.06]],
    Function2D [Title "Forme factorisée", Color Green] [Range 1.94 2.06, Step 0.000125] (\x -> exFac x)
    ]
\end{haskellcode}


On obtient:


%\begin{figure}
\begin{center}
  \includegraphics{plot_horner}
\end{center}
%\end{figure}


Bon, évidemment, on est allé chercher  l'exemple qui fâche. Ailleurs, les choses
marchent bien mieux.

Il existe un algorithme  de Horner compensé comme il en existe  un pour la somme
mais c'est un peu  plus compliqué. Les curieux pourront se  référer à un article
de Philippe \textsc{Langlois} et Nicolas \textsc{Louvet} \citep{lalo08}.

\begin{NB}
\illt{Comme nous  ne sommes  qu'en premier cycle,  nous mettrons de  côté à  partir de
maintenant ces problèmes d'erreur dans les évaluations.

Il faudra tout  de même retenir que ces problèmes  existent et sont omniprésents
dans la  machine: est-ce que  mon joueur  est sous le  feu de l'ennemi?  Je dois
savoir si,  en 3D, il  est à gauche  ou à droite d'une  zone ce qui  revient sur
machine  à calculer  un déterminant  dépendant de  3 paramètres,  bref évaluer  un
polynôme de  trois variables. Si  je me trompe dans  mes calculs, quand  je suis
prêt de la zone frontière, mon joueur peut  mourir dans d'atroces souffrances
(sur mon écran seulement, bien sûr).}{call_duty}{0.6}{0.4}

\end{NB}


\section{Série de \textsc{Taylor}}

\subsection{Dérivées d'ordre supérieur}


Nous avons eu  une approche intuitive de la dérivation  jusqu'à maintenant. Elle
nous suffira la plupart du temps. Cependant  il ne faut pas oublier qu'un manque
de rigueur dans l'étude de ces notions peut entraîner de graves erreurs.

Nous rappelons donc  quelques définitions qui nous servirons  à mieux comprendre
certains problèmes.

\begin{definition}[Dérivabilité]
Soit $f$ une fonction numérique définie sur un intervalle I de $\bbr$.

Soit $a\in I$. On dit que $f$  est dérivable en $a$ si, et seulement si,
le rapport:

$$\tau_a(h)=\frac{f(a+h)-f(a)}{h}$$
admet une limite finie lorsque $a$ tend vers 0.

Dans ce cas on note $f'(a)$ cette limite.

\end{definition}


Rappelons que $f'(a)$ est aussi  le coefficient directeur de la tangente
à la courbe représentative de $f$ au point d'abscisse $a$.

\begin{definition}[D\'{e}riv\'{e}e $k^{\grave{e}me}$]

Si $f^{\prime }$ est d\'{e}rivable sur $I$ on note $f^{\prime \prime }$ ou $%
f^{(2)}$ la d\'{e}riv\'{e}e de $f^{\prime }$ et on l'appelle la d\'{e}riv%
\'{e}e seconde de $f.$ De m\^{e}me si $f^{\prime \prime }$ est d\'{e}rivable
sur $I,$ $f^{\prime \prime \prime }$ ou $f^{(3)},$ la d\'{e}riv\'{e}e de $%
f^{\prime \prime },$ est la d\'{e}riv\'{e}e troisi\`{e}me de $f.$ Plus g\'{e}%
n\'{e}ralement on note $f^{(k)}$ la d\'{e}riv\'{e}e $k^{i\grave{e}me}$ de $f$
avec la convention $f^{(0)}=f,$ $f^{(k+1)}=\left( f^{(k)}\right) ^{\prime }.$

\end{definition}


\begin{definition}[Fonctions de classe $\mathcal{C}^{n},$ de classe $\mathcal{C}%
^{\infty }$]

On dit que $f$ est de classe $\mathcal{C}^{n},$ $n\in \mathbb{N},$ sur $I$
ssi $f$ est $n$ fois d\'{e}rivable et ses $n$ d\'{e}riv\'{e}es sont
continues sur $I.$ On remarquera que si $f^{(n+1)}$ existe sur $I$ alors $f$
est de classe $\mathcal{C}^{n}$ sur $I$ qui s'\'{e}crit $f\in \mathcal{C}%
^{n}(I).$ On dit que $f$ est de classe $\mathcal{C}^{\infty }$ sur $I$ pour
exprimer que $f$ est ind\'{e}finiment d\'{e}rivable et, a fortiori, que
toutes ses d\'{e}riv\'{e}es sont continues.

\end{definition}



\subsection{Relations de domination}


\begin{quote}
  {\it Brooks's Law [prov.]

\og Adding manpower to a late software project makes it later\fg{} -- a result
of  the fact that  the expected  advantage from  splitting work  among N
programmers is $O(N)$, but the complexity and
communications cost associated with  coordinating and then merging their
work is $O(N^2)$}
\begin{flushright}
  in \og The New Hacker's Dictionnary\fg{}\\
\href{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}
\end{flushright}
\end{quote}

Les notations  de \textsc{Landau}(1877-1938) ont  en fait été  crées par
Paul 
\textsc{Bachmann}(1837-1920) en 1894, mais bon, ce sont tous deux des 
mathématiciens allemands.

Par exemple, si l'on considère l'expression: $$f(n)=n+1+\frac{1}{n}+\frac{75}{n^2}-\frac{765}{n^3}+\frac{\cos(12)}{n^{37}}-\frac{\sqrt{\numprint{765481}}}{n^{412}}$$


Quand  $n$  est  \og  grand\fg{}, disons  $\numprint{10000}$,  alors  on
obtient:

$$f(\numprint{10000})=\numprint{10000}+1+0,0001+0,00000000075-0,0000000000000765+\text{
  peanuts}$$

Tous les  termes après  $n$ comptent  pour du beurre  quand $n$  est \og
grand\fg{}: on a expérimenté ceci sur machine avec la notion de \textit{sous-capacité}.



 Donnons une définition pour plus de clarté:

\begin{definition}[\og Grand O\fg{}]
Soit $f$ et $g$ deux fonctions  de $\bbn$ dans $\bbr$. On dit que $f$
est un \og grand O\fg{} de $g$ et on note $f=O(g)$ ou $f(n)=O(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $$|f(n)|\leqslant
C|g(n)|$$ pour tout $n\in \bbn$.
\end{definition}



Dans  l'exemple précédent,  $\frac{1}{n} \leqslant  \frac{1}{1}\times 1$
pour tout entier $n$ supérieur à 1
donc $\frac{1}{n}=O(1)$.

De   même,  $\frac{75}{n^2}   \leqslant  \frac{75}{1^2}\times   1$  donc
$\frac{75}{n^2}=O(1)$ mais on peut dire mieux:
 $\frac{75}{n^2}\leqslant  \frac{75}{1}\times\frac{1}{n}$  et  ainsi  on
 prouve que $\frac{75}{n^2}=O \left(\frac{1}{n}\right)$.

En fait, un grand  O de $g$ est une fonction qui  est au maximum majorée
par un multiple de $g$.

Point  de vue  algorithmique, cela  nous donne  un renseignement  sur la
complexité au pire.

Pour  le   tri  fusion,  on  obtient  pour   $n>1$:  $$K(n)\leqslant  4nc
\left(\lfloor                        \log_2(n)\rfloor+1\right)\leqslant
4nc\log_2(n)\left(1+\frac{1}{\log_2(n)}\right) \leqslant 8cn\log_2(n)$$

On en déduit que $K(n)=O(n\log_2(n))$: la complexité est au pire en
$n\log_2(n)$,  c'est ce  qui nous  importe. Le  rôle des  constantes est
accessoire  car  chercher trop  de  précisions  serait illusoire:  l'\og
oubli\fg{}  de ces constantes  correspond en  fait au  différences entre
langages, processeurs, etc.

On peut  cependant faire  mieux avec le  tri fusion  car on a  aussi une
minoration.

C'est le moment d'introduire une nouvelle définition:

\begin{definition}[\og Grand Oméga\fg{}]
  Soit $f$ et $g$ deux fonctions  de $\bbr$ dans lui-même. On dit que $f$
est un \og grand Oméga\fg{} de $g$ et on note $f=\Omega(g)$ ou $f(n)=\Omega(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $$|f(n)|\geqslant
C|g(n)|$$ pour tout $n\in \bbn^*$.
\end{definition}

\begin{remarque}
Comme   $\Omega$  est   une  lettre   grecque,  on   peut,   par  esprit
d'unification, parler de \og grand omicron\fg{} au lieu de \og grand O\fg{}...
\end{remarque}

\begin{remarque}
   $f=\Omega(g)\Longleftrightarrow g=O(f)$...
\end{remarque}


On    montre    donc    facilement    pour    le    tri    fusion    que
$K(n)=\Omega(n\log_2(n))$     grâce     à    l'inégalité     $2cn\lfloor
\log_2(n)\rfloor \leqslant K(n)$.


Ainsi   on  a   dans  ce   cas  en   même  temps   $f=O(n\log_2(n))$  et
$f=\Omega(n\log_2(n))$:  c'est  encore  plus  précis et  nous  incite  à
introduire une nouvelle définition:

\begin{definition}[\og Grand Théta\fg{}]
$$f=\Theta(g)\Longleftrightarrow
\begin{cases}
  f=O(g)\\ f=\Omega(g)
\end{cases}
$$
\end{definition}

Le coût de l'algorithme se trouve donc coincé entre deux valeurs de même
ordre.  On peut  ainsi  dire que  la  complexité du  tri  fusion est  en
$n\log_2(n)$ ce qui  est \textit{souvent} mieux que le tri  par insertion dont la
complexité \textit{au  pire} est  en $n^2$. Mais  attention! \textit{Au  pire} ne
signifie pas \textit{toujours}:  si la liste est déjà  triée, le tri par
insertion est plus économique.


Voici maintenant une petite table pour illustrer les différentes classes
de complexité rencontrées habituellement:

\begin{center}
             \begin{tabularx}{\linewidth}{Y{3}}
	     \whline
             \backslashbox{coût}{$n$}&100&$\numprint{1000}$&$10^6$&$10^9$\\
             \whline
             $\log_2(n)$&$\approx7$&$\approx10$&$\approx 20$&$\approx 30$\\
             \hline
             $n\log_2(n)$&$\approx 665$&$\approx \numprint{10000}$&$\approx  2\cdot  10^{7}$&$\approx 3\cdot 10^{10}$\\
             \hline
             $n^2$&$10^4$&$10^6$&$10^{12}$&$10^{18}$\\
             \hline
             $n^3$&$10^6$&$10^9$&$10^{18}$&$10^{27}$\\
             \hline
             $2^n$&$\approx 10^{30}$&$>10^{300}$&$>10^{10^5}$&$>10^{10^8}$\\
             \whline
             \end{tabularx}
             \end{center}

Gardez en tête que l'âge de l'Univers est environ de $10^{18}$ secondes...


Il existe  également deux autres \og comparateurs\fg{}  que l'on utilise
peu  en algorithmique  mais qui  peuvent s'avérer  utiles  dans d'autres
domaines.

\begin{definition}[\og Petit o\fg{}]
$f=o(g)$ si, et seulement  si, pour toute constante positive $\varepsilon$,
il existe un entier $n_0$ tel 
que, pour tout $n \geqslant n_0$, $$\left|f(n)\right| \leqslant \varepsilon\left|g(n)\right|$$
\end{definition}


On dit alors souvent que $f$ est \textit{négligeable} devant $g$.


Contrairement au  grand O, la majoration  doit se faire  quelque soit la
constante $\varepsilon$ et non pas seulement pour une constante arbitraire.

\begin{definition}[Fonctions équivalentes]
  $f(n)\sim g(n)\Longleftrightarrow f(n)=g(n)+o \left(g(n)\right)$
\end{definition}

Voici  quelques   propriétés  fort   utiles  que  nous   démontrerons  à
l'occasion:

\begin{proprietes}[Manipulation des O]
  \begin{itemize}
  \item $O(f)+O(g)=O(f+g)$;
\item $f=O(f)$;
\item $k\cdot O(f)=O(f)$ si $k$ est une constante;
\item $O \left(O(f)\right)=O(f)$;
\item $O(f)\cdot O(g)=O(f\cdot g)$;
\item $O(f\cdot g)=f\cdot O(g)$.
  \end{itemize}
\end{proprietes}

Par exemple, $2n^3+3n^2+5n=O(n^3)+O(n^3)+O(n^3)=O(n^3)$.




\setindent{-0.75cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3.65cm]{taylor}
  \caption{Brook \textsc{Taylor}\\ (1685-1731)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.8cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


\subsection{Polynôme de \textsc{Taylor}}

Brook \textsc{Taylor} fut un savant anglais  qui reprit les travaux de ses aînés
\textsc{Newton},     \textsc{Leibniz},     Jacques     \textsc{Bernoulli}     et
\textsc{Gregory}.

Musicien,  philosophe, peintre,  il est  surtout célèbre  pour les  formules qui
portent son  nom. Il les obtint  en étudiant le problème  de \textsc{Kepler} qui
concerne le calcul de certaines anomalies dans la révolution des planètes.


Son  but  est  encore  une  fois  d'obtenir  une  interpolation  d'une  fonction
compliquée à l'aide d'un polynôme simple.

Il obtient le résultat suivant:

 
\begin{theoreme}[Polynôme de \textsc{Taylor}]
Soit I un  intervalle, soit $f$ une  fonction de Ιvers $\bbr$  de classe $\CR^n$
avec  $n\in\bbn$   et  soit  $a$  un   élément  de  I.  Il   existe  alors  un
\textit{unique} polynôme  $T_{n,a}$ de degré au  plus $n$ dont les  dérivées jusqu'à
l'ordre $n$ coïncident en $a$ avec celles de $f$.
De plus:

$$
T_{n,a}(x) = f(a) + (x-a)f'(a) + \frac{(x-a)^2}{2!}
f''(a)+\frac{(x-a)^3}{3!}f^{(3)}(a)+\cdots +\frac{(x-a)^n}{n!}f^{(n)}(a)
$$
  
\end{theoreme}

Nous admettrons l'unicité  mais \textit{vous vérifierez}
tout de même que pour tout entier $0 \leqslant k \leqslant n$, $$T_{n,a}^{(k)}(a)=f^{(k)}(a)$$



Par exemple, la fonction exponentielle admet comme polynôme de \textsc{Taylor} à
l'ordre 2 en 0:
\begin{eqnarray*}
  \label{eq:1}
  T_{n,0}(x)&=&\exp(0)+(x-0)\exp'(0)+\frac{(x-0)^2}{2!}\exp''(0)\\
        &=&1+x+\frac{x^2}{2}
\end{eqnarray*}



Le  problème  principal  de  sa   formule  est  d'estimer  l'erreur  commise  en
considérant $T_{n,a}$ à la place de $f$:

$$
f(x)       =  T_{n,a}(x)   +R_{n,a}(x)
$$


Voilà pourquoi  on retrouve  son nom  associé à trois  formules qui  donnent une
meilleure idée  de ce reste (\textit{quelle  erreur commet-on?}) et qui  ont été
établies par trois de ses collègues.


Nous ne ferons pas les preuves qui sont assez techniques.

Nous  admettrons   également  que   le  polynôme  de   \textsc{Taylor}  approche
\textit{mieux}\footnote{Ce qui signifie  que $\left|f(x)-T_{n,a}(x)\right| \leqslant
  \left|f(x)-P(x)\right|$ pour tout polynôme P de degré au plus $n$.} $f$
au voisinage de $a$ que tous les autres polynômes de degré au plus $n$.
\subsection{Formule de \textsc{Taylor-Lagrange}}

\begin{theoreme}
 Si $f$ est de classe $\mathcal{C}^{n}$ sur $\left[ a,x%
\right] $ et si $f^{(n+1)}$ existe sur $\left] a,x\right[ $ alors il existe
au moins un r\'{e}el $c\in \left] a,x\right[ $ tel que : 
\begin{equation*}
f(x)=T_{n,a}(x)+\frac{%
\left( x-a\right) ^{n+1}}{(n+1)!}f^{(n+1)}(c)
\end{equation*}%
On dit que l'on a \'{e}crit la formule de Taylor Lagrange \`{a} l'ordre $n.$
\end{theoreme}

Il est souvent pratique de  réécrire cette formule en posant $x=a+h$. Le
nombre $c$ appartient  donc à l'intervalle $]a,a+h[$. Il  existe donc un
réel $\theta\in]0,1[$ tel que:

$$f(a+h)=\sum\limits_{k=0}^{n}\frac{h^{k}}{k!}f^{(k)}(a)+\frac{h^{n+1}}{(n+1)!}%
f^{(n+1)}(a+\theta h)$$


\subsection{Formule de Taylor-Mac Laurin}

Dans la formule de Taylor-Lagrange on remplace  $a$ par $0.$
On obtient : 

\begin{theoreme}
$$f(x)=\sum\limits_{k=0}^{n}\frac{x^{k}}{k!}f^{(k)}(0)+\frac{x^{n+1}}{(n+1)!}%
f^{(n+1)}(\theta x)$$
\end{theoreme}



\subsection{Formule de Taylor avec reste int\'{e}gral}


Si $f$ est de classe $\mathcal{C}^{n+1}$ sur $I$ contenant $a$:

\begin{theoreme}
$$\forall x\in I,f(x)=T_{n,a}(x)+\int\limits_{a}^{x}\frac{\left( x-t\right) ^{n}}{n!}f^{(n+1)}(t)dt$$
\end{theoreme}


\subsection{Formule de Taylor-Young.}

Si $f$ est de classe $\mathcal{C}^{n}$ sur un intervalle $I$ contenant $a$
alors : 


\begin{theoreme}
$$\forall x\in I,f(x)=T_{n,a}(x)+o\left( (x-a)^{n}\right)$$
\end{theoreme}



\section{D\'{e}veloppements limit\'{e}s}


\subsection{Voisinage}

$a\in \mathbb{R},$ nous appellerons voisinage de $a$ toute partie de $%
\mathbb{R}$ contenant un intervalle ouvert contenant $a.$ L'intervalle $%
\left] a-\alpha ,a+\alpha \right[ ,$ avec $\alpha \in \mathbb{R}^{+\ast },$
est un voisinage de $a,$ nous le noterons $\mathcal{V}_{a}$ et $\mathcal{V}%
_{a}-\left\{ a\right\} $ sera not\'{e} $\mathcal{V}_{a}^{\ast }.$ Un
voisinage \`{a} droite de $a$ est un intervalle du type $\left] a,a+\alpha %
\right[ $ et $\left] a-\alpha ,a\right[ $ est un voisinage \`{a} gauche de $%
a.$ Dans ce qui suit nous ne distinguerons pas ces types de voisinages, en
cons\'{e}quence $\mathcal{V}_{a}^{\ast }$ pourra tout aussi bien aussi d\'{e}%
signer un voisinage \`{a} droite ou \`{a} gauche, lors des applications, le
contexte permettra de les distinguer. Un voisinage de $+\infty $ est un
voisinage du type $\left[ A,+\infty \right[ $ avec $A$ r\'{e}el positif
aussi grand que l'on veut que nous pourrons noter $\mathcal{V}_{+\infty
}^{\ast }$. Notez que $\left] -\infty ;-A\right] $ est un voisinage de $-\infty .$


\subsection{Définition}


\begin{definition}
   On dit que $f,$ d\'{e}finie sur $\mathcal{V}_{a},$ admet un
d\'{e}veloppement limit\'{e} d'ordre $n\in \mathbb{N}$ au voisinage de $a$
(on \'{e}crit en abr\'{e}g\'{e}: \og $f$ admet un $DL_{n}V(a)$\fg{}) s'il existe
un polyn\^{o}me $P_{n}\in \mathbb{R}_{n}\left[ X\right] $ (ensemble des polyn%
\^{o}mes de degr\'{e} inf\'{e}rieur ou \'{e}gal \`{a} $n)$ et une fonction $%
\varepsilon $ v\'{e}rifiant : 
\begin{equation*}
\left\{ 
\begin{array}{c}
\forall x\in \mathcal{V}_{a},f(x)=P_{n}(x-a)+(x-a)^{n}\varepsilon (x) \\ 
\varepsilon (a)=0 \\ 
\underset{x\rightarrow a}{\lim }\varepsilon (x)=0%
\end{array}%
\right.
\end{equation*}


c'est-à-dire $f(x)=P_n(x-a)+o \Bigl( (x-a)^n \Bigr)$.

\end{definition}
Il faut bien remarquer que:

$$
q > p \limp (x-a)^q \underset{a}{=}o \Bigl( (x-a)^p \Bigr)
$$

Plus la puissance $p$ est grande, plus $(x-a)^p$ est petit.


Nous n'irons  pas très loin  dans l'étude  des développements limités  mais elle
nous permettra  d'avoir des approximations polynomiales  de nombreuses fonctions
ce  qui  nous  permettra  de  comprendre de  nombreuses  méthodes  employées  en
informatique.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% EXERCICES
%
%%%%%


\vfill

\eject













\modeexercice

\section{EXERCICES}

%
\begin{exercice}[Formule de dérivation]
En  utilisant les  résultats de  la section  \vref{sec::regDeriv}, démontrez  la
formule de  dérivation de $x\mapsto  x^n$ et  $x\mapsto 1/x^n$ pour  tout entier
positif $n$.
\end{exercice}



%
\begin{exercice}[Méthode de \textsc{Briggs}]
Inspirez-vous  de  la méthode  présentée  à  la section~\vref{sec::briggs}  pour
calculer une approximation de $\log(3)$ et $\log(7)$.
\end{exercice}


%
\begin{exercice}[Interpolation de \textsc{Newton}(1): le gag]
Déterminez le polynôme  de \textsc{Newton} passant par les  points (1,1), (2,8),
(3,27) et (4,64).  
\end{exercice}




%
\begin{exercice}[Interpolation de \textsc{Newton}(2)]
Déterminez le polynôme de \textsc{Newton} passant par les points (1,5), (2,2), (3,5), (4,2) et (5,2).  
\end{exercice}

%
% \begin{exercice}[Interpolation du logarithme]
% Déterminez le polynôme interpolateur de \textsc{Newton} qui passe par les points
% $(1,\log 1)$, $(2,\log 2)$, $(3,\log 3)$ et $(4,\log 4)$.

% En  utilisant l'algorithme  de  Horner, déduisez-en  les  valeurs du  logarithme
% décimal des nombres de 1 à 4 avec un pas de 0,5.
  
% \end{exercice}



\begin{exercice}
Écrivez la formule du théorème \vref{th::newton_gen} sans ... mais avec $\sum$ et $\prod$  
\end{exercice}


%
\begin{exercice}[Calculs des coefficients des polynômes de \textsc{Newton}]
  Reprenez les calculs effectués dans la section~\vref{sec::interpolNewton} mais
  avec $n$ points d'abscisses 0 à $n-1$.
\end{exercice}



%
\begin{exercice}[Polynôme de \textsc{Newton}: le programme]

Nous voudrions programmer  l'interpolation du logarithme décimal  sur [1,4] pour
obtenir un tracé tel que celui-ci:


%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{plot_log_newton}
\end{center}
%\end{figure}


obtenu en utilisant la bibliothèque \texttt{Easyplot} (\mintinline{haskell}{import Graphics.EasyPlot}):


\begin{haskellcode}
compareTrace f a b pas = 
  plot X11 
   -- ou bien (PDF ("plot_" ++ nomf ++ "_newton.pdf")) pour un export PDF 
  [
    Data2D [Title "Méthode de Newton", Color Red] [] [(x, interpol liste x) | x <-  [a, (a + pas) .. b]],
    Data2D [Title "La vraie fonction",Color Blue] [] [(x, f              x) | x <-  [a, (a + pas) .. b]]
  ]
  where liste = map f [a .. b]
\end{haskellcode}


On pourra créer 5 \textit{one liners}:

\begin{haskellcode}
-- Calcule la liste des différences 2 à 2 d'une liste de nbs [1,3,6] -> [2,3]
reduitL :: Num a => [a] -> [a]
reduitL liste = zipWith ????
 
-- Renvoie la liste des listes de différences : le triangle de Newton 
reduit :: (Eq a, Num a) => [a] -> [[a]]
reduit liste = takeWhile ????
 
-- Renvoie la tête du triangle de Newton
diffNewton :: Num a => [a] -> [a]
diffNewton liste = map ????
 
--  Renvoie la liste des évaluations des (x-x0)(x-x0-1).../n! du théorème 2.6 accumulées dans une liste
baseNewton :: (Enum a, Fractional a) => a -> a -> a -> [a]
baseNewton x0 x n = scanl (\ acc k -> ???? ) 1 [1 .. n]
 
-- renvoie l'évaluation du poly de Newton en x en partant de x0 avec une liste de valeurs
-- l'incrément des abscisses est 1 
interpol :: (Enum a, Eq a, Fractional a) => [a] -> a -> a -> a
interpol liste x0 x = ????
\end{haskellcode}


\begin{enumerate}
\item Commencez par créer une fonction \lstinline+reduitL :: Num a => [a] -> [a]+
 qui renvoie la liste des écarts entre les éléments d'une liste donnée:

  \begin{haskellcode}
*Main> reduitL [1,2,5,7,12]
[1,3,2,5]
  \end{haskellcode}

\item Déterminez ensuite une fonction \lstinline+reduit :: Num a => [a] -> [[a]]+ 
  qui la liste des différentes listes des écarts à partir d'une liste donnée:

  \begin{haskellcode}
*Main> reduit [5,2,5,2,2]
[[-3,3,-3,0],[6,-6,3],[-12,9],[21]]
  \end{haskellcode}


\item Déterminez une fonction \lstinline+diffNewton ::  Num a => [a] -> [a]+ qui
  renvoie la  liste des $Δ^iy_1$  du \og triangle\fg{} de  \textsc{Newton} (ceux
  en gras...):

  \begin{haskellcode}
*Main> diffNewton [5,2,5,2,2]
[5,-3,6,-12,21]
  \end{haskellcode}

\item   La   formule   du    théorème~\vref{th::newton}   laisse   entrevoir   un
  \texttt{zipWith}. Nous disposons  déjà de la liste des $Δ^i$.  Il nous reste à
  construire la \textit{base} des polynômes de \textsc{Newton} \lstinline+baseNewton :: (Enum a, Eq a, Fractional a) => a -> a -> [a]+::


\begin{haskellcode}
baseNewton :: (Enum a, Fractional a) => a -> a -> a -> [a]
baseNewton x0 x n = scanl (\ acc k -> ??????? ) 1 [1 .. n]
\end{haskellcode}


Il n'y a plus  qu'à zipper et additionner (bref faire un  produit scalaire : une
liste est un vecteur...) pour créer une fonction \lstinline+interpol :: (Enum a, Eq a, Fractional a) => [a] -> a -> a -> a+:

\begin{haskellcode}
*Main> interpol [1,8,27,64] 1 1.5
3.375
\end{haskellcode}

\item Reprendre toutes les fonctions précédentes pour être compatible avec le théorème\vref{th::newton_gen}.
Par exemple:


\begin{haskellcode}
*Main> compareTrace  log10  44 47 0.125
\end{haskellcode}


%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{plot_log44_newton}
\end{center}
%\end{figure}

\end{enumerate}


  
\end{exercice}

%
\begin{exercice}[Algorithme de Horner]\label{ex::horner}
  


\ill{La  méthode que nous  allons voir  porte le  nom du  britannique William
George  \textsc{Horner} (1786  - 1837)  mais  en fait  elle fut  publiée
presque  10  ans  auparavant  par  un  horloger  londonien,  Theophilius
\textsc{Holdred} et simultanément par l'italien Paolo \textsc{Ruffini} (1765 - 1822)
mais fut déjà utilisée par  \textsc{Newton} 150 ans auparavant et par le
chinois \textsc{Zhu  Shije} cinq siècles  plus tôt (vers 1300)  et avant
lui  par le Persan  \textsc{Sharaf al-Din  al-Muzaffar ibn  Muhammad ibn
al-Muzaffar al-Tusi} vers (1100) et avant lui par le
Chinois \textsc{Liu  Hui} (vers 200)  révisant un des  résultats présent
dans \textit{Les Neuf
Chapitres sur l'art mathématique} publié avant la naissance de JC...


Soit $P$ un  polynôme. Il s'agit de  calculer l'évaluation de $P$  en une valeur
particulière.



Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications (vérifiez-le!).}{Ruffini}



On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}


Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions.

 En fait il y a au maximum $2\times$degré
de P opérations (voire moins avec les zéros).


Que pensez-vous de ce \textit{one liner}?

\begin{haskellcode}
horner p x = foldl (\ pol coeff -> coeff + x * pol) 0 p
\end{haskellcode}


Notez de plus qu'une machine disposant de  la FMA effectue ce calcul encore plus
exactement.

\begin{haskellcode}
*Main> horner [3,-2,7,2,5,-3] 1
12
\end{haskellcode}


Écrivez un programme similaire en C.


Reproduisez le graphe de la section~\vref{sec::horner}.

\end{exercice}



\vfill

\eject


%


\begin{exercice}[Méthode d'\textsc{Euler}]
  On ne  dispose que de  la dérivée d'une  fonction: peut-on tracer  malgré cela
  l'allure de sa courbe représentative?

On  créera une  fonction  Haskell permettant  par exemple  de  tracer la  courbe
représentative de  la fonction dont la  dérivée est la fonction  $x\mapsto x$ et
qui s'annule pour $x=1$.

Généralisez votre  fonction Haskell  pour faire  de même  avec une  fonction qui
vérifie une équation différentielle $$y'=f(x,y)$$

On commencera par créer la liste des  points \lstinline+listeEuler f x y pas n+
qui renvoie la liste des coordonnées des points de la courbe approchée.

On l'utilisera ensuite dans la fonction:

\begin{haskellcode}
euler f x0 y0 xf n = 
  let pas = (xf - x0) / n in
    plot X11  ( 
    Data2D [Title "Méthode d'Euler", Color Blue, Style Lines] [] (listeEuler f x0 y0 pas n) 
    )
\end{haskellcode}

On obtient par exemple avec:

\begin{haskellcode}
*Main> euler (\x y -> y) 0 1 2 (2**10)
\end{haskellcode}

la courbe suivante:


%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{eulerExpo.pdf}
\end{center}
%\end{figure}



Essayez  d'étendre au  cas  des équations  différentielles d'ordre  2  : $y''  =
f(x,y,y')$.

Par exemple:


\begin{haskellcode}
*AnalyseNumerique> euler2 (\ x y y' -> - y) 0 0 1 10 (2**10)
\end{haskellcode}

donne:


%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{eulerExpoDeux.pdf}
\end{center}
%\end{figure}


\end{exercice}





\begin{exercice}[Construction de l'exponentielle]

  \paragraph*{Une équation différentielle}



\textit{L'équation différentielle} $f'=k\,f$ se retrouve dans de
nombreux problèmes : désintégration des noyaux des atomes d'un
corps radioactif, datation au carbone 14, évolution d'une
population où la croissance est proportionnelle au nombre
d'habitants, etc. Le problème est de trouver une fonction la
satisfaisant.

Par exemple, certains phénomènes en mécanique conduisent à étudier
l'équation différentielle $f''=-f$. Nous connaissons au moins deux
fonctions la satisfaisant : cosinus et sinus.



\paragraph*{Construction approchée du graphe d'une solution par la
méthode d'Euler}




Soit $f$ une fonction dérivable sur $\bbr$ vérifiant $f(0)=1$ et,
pour tout  $x$, $f'(x)=f(x)$.  Utilisez la méthode  d'Euler pour  déterminer une
représentation graphique de $f$ sur $[0,2]$.



\paragraph*{Analyse: étude des propriétés mathématiques d'une
solution}


Soit $f$ une fonction dérivable sur $\bbr$ vérifiant $f(0)=1$
et, pour tout $x$, $f'(x)=k\,f(x)$, avec $k\neq 0$.

\begin{enumerate}

\item Montrez que $f'(0)=k$.

\item Soit $y$ un réel fixé et $g_y$ la fonction définie par
$g_y(x)=f(x+y)f(-x)$

\begin{enumerate}

\item Montrez que $g_y$ est dérivable sur $\bbr$ et calculez
$g'_y(x)$.

\item Calculez $g_y(0)$ et déduisez-en que pour tous $x$ et $y$
réels,
$f(x+y)\,f(-x)=f(y)\qquad \mg{(1)}$

\end{enumerate}

\item Montrez alors successivement que:

\begin{enumerate}

\item pour tout réel $x$, $f(x)f(-x)=1$

\item $f$ ne s'annule pas sur $\bbr$

\item pour tous réels $x$ et $y$, $f(x+y)=f(x)\,f(y)$.

\end{enumerate}

\end{enumerate}


\paragraph*{Unicité de la fonction solution}

Peut-on trouver une autre  fonction, $φ$,  distincte de $f$,
et vérifiant les mêmes propriétés que $f$, à savoir~: $φ$  est
une fonction dérivable sur $\bbr$,  vérifiant $φ(0)=1$ et, pour
tout $x$, $φ'(x)=k\,φ(x)$, avec $k\neq 0$?

\medskip

Comme $f$ ne s'annule pas sur $\bbr$, on peut définir la
fonction $ψ=φ/f$.

Vérifiez que $ψ$ est dérivable sur $\bbr$, calculez sa dérivée.
Que peut-on en déduire pour $ψ$? Montrez alors que $f=φ$.


\paragraph*{Synthèse}

Nous avons cherché des solutions au problème:

\begin{quote}
{\itshape
$f$ une fonction dérivable sur $\bbr$ vérifiant $f(0)=1$ et,
pour tout $x$, $f'(x)=k\,f(x)$, avec $k\neq 0$.
}

\end{quote}


Nous avons montré que, \textit{si une telle fonction existe} (ce
que nous prouverons dans un prochain chapitre), alors elle est
unique et elle  vérifie nécessairement la relation
$f(x+y)=f(x)\,f(y) \qquad (2)$.

Il reste à vérifier que, réciproquement, une fonction dérivable,
non nulle, vérifiant la relation (2)  est nécessairement telle que
$f(0)=1$ et vérifie pour tout réel $x$ $f'(x)=kf(x)$, avec $k$ un
réel non nul.

\bigskip

Cette vérification n'est pas anodine et conclut notre raisonnement
d'\textit{analyse-synthèse}.
%Par exemple, on cherche un plombier
%pouvant se glisser dans les canalisations d'une maison pour la
%réparer.
%
%Analyse : nécessairement, cet homme devra mesurer 1 cm de haut,
%avoir des branchies pour respirer sous l'eau, être nyctalope.
%Synthèse :


\begin{enumerate}

\item Montrez que $f$ ne s'annule pas et que $f$ est à valeurs
strictement positives.

\item Montrez que, comme $f$ n'est pas la fonction nulle, alors
$f(0)=1$ en utilisant la relation (2).

\item Soit $a$ un réel fixé. On définit la fonction $φ~:~x\mapsto
f(x+a)$ et la fonction $ψ~:~x\mapsto f(x)\times f(a)$.

Montrez que $f'(x+a)=f(a)\times f'(x)$, puis que, pour tout réel
$a$, $f'(a)=k\,f(a)$, où $k$ est un réel que vous déterminerez.

\end{enumerate}


\end{exercice}




%



\begin{exercice}





\illg{clouseau}{La loi de Newton sur le refroidissement dit que la vitesse de refroidissement d'un objet est
proportionnelle à l'écart de température entre l'objet et le milieu ambiant.\\
L'inspecteur \textsc{Clouseau} arrive sur les lieux d'un meurtre à 9h00. Il commence par prendre la
température de la victime~:~30\degre C. Une heure plus tard, la température du corps est tombée à
29\degre C. Sachant que la température normale du corps d'une personne vivante en bonne santé est de
37\degre C, que la victime était syldave, qu'elle  aimait  les films de gladiateurs et se trouvait
dans une pièce maintenue à 0\degre C, estimez l'heure du décès de la victime et la couleur de ses yeux.}{0.15}{0.8}

On pourra avoir une idée graphique avec:

\begin{haskellcode}
*Main> euler (\ x y -> k * y ) 10 29 2 100 where k = ...
\end{haskellcode}
\end{exercice}



\begin{exercice}




\illt{Dans la forêt syldave, des détritus naturels (~feuilles, branches, animaux morts, cadavres
d'espions, etc.) tombent sur le sol et s'y décomposent. La quantité $Q(t)$ exprimée en $g\cdot m^{-2}$ de
détritus jonchant le sol varie avec le temps $t$. On suppose que de nouveaux détritus tombent au sol
à un taux constant de $200\,g\cdot m^{-2}$ par année et que les détritus accumulés au sol se décomposent
au taux de $50\%$ de la quantité de détritus jonchant le sol.
\begin{enumerate}
\item On note $f(t)=Q(t)-200$. Déterminez une équation différentielle vérifiée par $f$.
\item En déduire l'expression générale de $Q(t)$.
\item Exprimer $Q(t)$ sachant qu'au temps $t=0$, on comptait $50\,g\cdot~m^{-2}$
\end{enumerate}}{paysageSyldave}{0.65}{0.32}


\end{exercice}



%


\begin{exercice}





  \illg{gateway}{
Si  vous allez  vous promener  dans la  ville de  Saint-Louis  dans le
  Missouri aux
  États-Unis, vous  pourrez y admirer  la célèbre \textit{Gateway  Arch to
  the   West}   conçue  en   1947   par   l'architecte  finlandais   Ero
  \textsc{Saarinen}   et   l'ingénieur   Hannskarl  \textsc{Bandel}   et
  dont la construction s'acheva en 1965.  Cette
  arche a la forme d'une \textit{chaînette} pondérée
  d'équation  $$y=212-21\ch(0,033x)$$  où $x$  et  $y$  sont mesurés  en
  mètres  et  rend  hommage  aux  pionniers  partis  à  la  conquête  de
  l'Ouest.\\
Pouvez-vous déterminer  la hauteur de  l'arche et la distance  entre les
deux pieds~?
On rappelle que $\ch x = \frac{\E^x+\E^{-x}}{2}$.}{0.3}{0.65}

\end{exercice}

%

\begin{exercice}




 L'équation   de   la
 hauteur $h$ par rapport au  sol d'un fil électrique suspendu entre deux
 poteaux       s'obtient       en       résolvant       l'\textit{équation
 différentielle}:

    \illt{ \[h''(x)=k \sqrt{1+\left(h'(x)\right)^2}\]
où $k$
 est un paramètre qui dépend de la  densité et de la tension du fil et $x$
est mesuré en  mètres horizontalement à partir d'une  origine située sur
le sol en-dessous du point où la hauteur du fil est la plus faible.

\begin{enumerate}
\item  Vérifiez que  $h~:~x\mapsto  \frac{1}{k}\ch(kx)$ satisfait  cette
      équation différentielle.
\item Quelle  est la hauteur  minimale du fil  si le paramètre  $k$ vaut
      $0,05$~?
\item Quelle  est la  hauteur des poteaux  (de même hauteur)  s'ils sont
      distants de 30~m et que le paramètre $k$ vaut 0,05~?
\end{enumerate}}{cable}{0.65}{0.33}
\end{exercice}




%
\begin{exercice}[DL]
\'{E}crire la formule de Taylor-Mac Laurin et la formule de Taylor-Young 
\`{a} l'ordre $n$  pour les fonctions suivantes et  dans un voisinage de
0:

\begin{multicols}{3}

\begin{enumerate}
\item $f(x)=\text{e}^{x}$

\item $f(x)=\dfrac{1}{1+x}$

\item $f(x)=\dfrac{1}{1-x}$

\item $f(x)=\ln (1+x)$

\item $f(x)=\sin \left( x\right) $

\item $f(x)=\sqrt{1+x},$ $n=4$
\end{enumerate}

\end{multicols}

\end{exercice}


%
\begin{exercice}[DL]
Donner un $DL_{3}(0)$ pour les fonctions suivantes :
\begin{multicols}{4}
\begin{enumerate}
\item $f_{1}(x)=\ln (1+x)$
\item $g(x)=f_{1}(x^{2})$

\item $f_{2}(x)=\text{e}^{x}$

\item $h(x)=f_{2}(-2x)$

\item $f_{3}(x)=f_{1}(x)f_{2}(x)$

\item $f_{4}(x)=f_{1}(x)+f_{2}(x)$
\end{enumerate}
\end{multicols}
\end{exercice}


%

\begin{exercice}[Fonctions homographiques]
  
Une  fonction  homographique est  une  fonction  de  la forme  $x\mapsto
\dfrac{ax+b}{cx+d}$ avec $a$, $b$, $c$ et $d$ des réels.


Notons $g$ la fonction homographique correspondant au cas $a=0$, $b=d=1$
et $c=-1$.

Quel est l'ensemble de définition de $g$~? 

Calculez $g^{(1)}(x)$,  $g^{(2)}(x)$, $g^{(3)}(x$  et plus
généralement $g^{(n)}(x)$.

Écrivez le plus simplement possible $T_{5,0}(g)(x)$.




Sur un  même graphique, donnez  l'allure des courbes  représentatives de
$g$ et de $T_{5,0}(g)$ avec Haskell.



\medskip


Soit $h(x)=\dfrac{5-3x}{1-x}$. Montrez  qu'il existe deux réels $\alpha$
et $\beta$ tels que $h(x)=\alpha+\dfrac{\beta}{1-x}$.

Déduisez-en $T_{5,0}(h)(x)$ pour $x$ appartenant à un bon intervalle.

\end{exercice}











%

\begin{exercice}[Question ouverte...]
  Les polynômes  de \textsc{Newton}  et de  \textsc{Taylor} se  ressemblent non?
  Dans quelle mesure?
\end{exercice}












%
\begin{exercice}[Courbes de \textsc{Bézier}]

\ill{Dans  les  années 60,  les  ingénieurs  Pierre  \textsc{Bézier} et  Paul
\textsc{De  Casteljau}   travaillant  respectivement  chez   Renault  et
Citroën, réfléchissent  au moyen de  définir de manière la  plus concise
possible la forme d'une carrosserie.

Le  principe  a été  énoncé  par  \textsc{Bézier}  mais l'algorithme  de
construction  par  son  collègue  de  la marque  aux  chevrons  qui  n'a
d'ailleurs été dévoilé  que bien plus tard, la  loi du secret industriel
ayant primé sur le développement scientifique...


Pour la  petite histoire Pierre \textsc{Bézier}  (diplômé de
l'\textsc{Ensam}  et  de \textsc{Supélec}) fut  à  l'origine des  premières
machines à commandes  numériques et de la \textsc{Cao}  ce qui n'empêcha
pas sa  direction de le mettre  à l'écart: il se  consacra alors presque
exclusivement aux
mathématiques  et à  la  modélisation  des surfaces  et  obtint même  un
doctorat en 1977.}{pierre_bezier}

 Paul
\textsc{De Casteljau} était lui un mathématicien d'origine, ancien élève
de la  Rue d'\textsc{Ulm}, qui a  un temps été  employé par l'industrie automobile. 


Aujourd'hui, les courbes de \textsc{Bézier} sont très utilisées en informatique.

Une Courbe de \textsc{Bézier} est une courbe paramétrique aux extrémités imposées
avec des points de contrôle qui définissent les tangentes à cette courbe
à des instants donnés.


\textbf{Algorithme de Casteljau}



Soit $t$ un  paramètre de l'intervalle $[0,1]$ et  $P_1$, $P_2$ et $P_3$
les trois points de contrôle. 

On    construit     le    point    $M_1$     barycentre    du    système
$\left\{(P_1,1-t),(P_2,t)\right\}$    et   $M_2$   celui    du   système
$\left\{(P_2,1-t),(P_3,t)\right\}$. 

On   construit   ensuite   le   point   $M$,   barycentre   du   système
$\left\{(M_1,1-t),(M_2,t)\right\}$.

Exprimez M comme barycentre des trois points $P_1$, $P_2$ et $P_3$.

Faites la construction à la main avec $t=1/3$ par exemple puis utilisez Haskell.



Nous allons assimiler les points $M_1$, $M_2$ et $M$ à des courbes paramétrées. 

Ainsi  $M_1(t)=(1-t)P_1+tP_2$, $M_2(t)=(1-t)P_2+tP_3$ puis

$$M(t)=(1-t)M_1(t)+tM_2(t)=(1-t)^2P_1+2t(1-t)P_2+t^2P_3$$

Vérifiez que $M'(t)=2(M_2(t)-M_1(t))$. Comment l'interpréter~?

\medskip

\textbf{Avec 4 points de contrôle}


Faites une étude similaire (\og à la main\fg{}) avec 4 points de contrôle.

On pourra  utiliser une représentation similaire aux arbres de probabilité.



Créez une  fonction
\verb+bezier3+ qui trace la courbe de \textsc{Bezier} de degré 3 passant par une
liste de 4 points de contrôle.

On pourra créer un type synonyme \lstinline+type Point = (Float,Float)+ et utiliser EasyPlot:

\begin{haskellcode}
type Point = (Float,Float)

infixr 4 @* -- produit externe
(@*) :: Float -> Point -> Point
(@*) k p = 

infixr 2 @+ -- somme de points
(@+) :: Point -> Point -> Point
(@+) p1 p2 = 

infixr 2 @- -- différence de points
(@-) :: Point -> Point -> Point 
(@-) p1 p2 = 

bezier3 :: [Point] -> [Graph2D Float Float]
bezier3 [p0,p1,p2,p3] =
    let m = \ t -> ... in
             [ 
    Data2D [Title "Bezier 3", Color Blue, Style Lines] [] [m t | t <-  [0, 0.01 .. 1]],
    Data2D [Title "Départ",  Color Green, Style Lines] [] [p0,p1],
    Data2D [Title "Arrivée", Color Red  , Style Lines] [] [p2,p3]
             ]
bezier3 _      = ...
\end{haskellcode}


Par exemple:

\begin{haskellcode}
*Main> plot X11 $ bezier3 [(0,0),(-1,1),(-1,0),(0,-3)]
\end{haskellcode}


donne:



%\begin{figure}
\begin{center}
  \includegraphics{bezier3}
\end{center}
%\end{figure}



Quel est le rôle des différents  points de contrôle?

\medskip


\textbf{Courbe de \textsc{Bézier} du 3\up{e}  degré avec un nombre quelconque de
  points de contrôle}


Il est   pratique  de travailler avec  des polynômes de  degré trois
pour avoir droit à des points d'inflexion.


Augmenter  le  nombre  de  points  de contrôle  implique  a  priori  une
augmentation du degré de la fonction polynomiale.

Pour remédier à  ce problème, on découpe une  liste quelconque en liste
de listes de 4 points. 

Cependant, cela  est insuffisant pour obtenir un  raccordement de classe
$\CR^1$  (pourquoi~? pourquoi est-ce  important d'avoir  un raccordement
de classe $\CR^1$~?)


Pour assurer la  continuité tout court, il faut que  le premier point d'un
paquet soit le dernier du paquet précédent.

Le dernier \og vecteur  vitesse\fg{} de la liste $[P_1,P_2,P_3,P_4]$ est
$\ve{P_3P_4}$. Il  faut donc que ce  soit le premier  vecteur vitesse du
paquet suivant pour assurer la continuité de la dérivée.

Appelons provisoirement le paquet suivant $[P_1',P_2',P_3',P_4']$. On a 
d'une part $P_1'=P_4$
et           d'autre          part          $\ve{P_3P_4}=\ve{P_1'P_2'}$,
i.e. $P_2'=P_4+\ve{P_3P_4}$.

On a donc $P_3'=P_5$ et $P_4'=P_6$.


Connaissant  \verb+bezier3+,  construire  une fonction qui  trace  une
courbe de \textsc{Bézier} cubique avec un nombre quelconque de points de contrôle
(on prendra un nombre pair de points pour se simplifier la vie).

Testez avec:

\begin{haskellcode}
plot X11 [(1, 1), (2, 3), (5, 5), (6, 2), (7, 7), (10, 5), (10, 2), (8, 0), (4, 0), (5, 1)]
\end{haskellcode}
  


%\begin{figure}
\begin{center}
  \includegraphics{essaiBez}
\end{center}
%\end{figure}

On pourra, par exemple, construire quelques fonctions intermédiaires:

\begin{haskellcode}
beziaux :: [Point] -> [Point]
-- Rajoute les points pour que la courbe soit de classe C1
beziaux (p1:p2:p3:p4:xs) =
    ...
beziaux _                = []

bezierP :: [Point] -> [Graph2D Float Float]
-- Colle les bouts de bezier3
bezierP []     = []
bezierP listeP = ...
    
bezier :: TerminalType -> [Point] -> IO Bool
-- crée le graphique avec le type de terminal en option (X11, PDF, ...)
bezier option listeP = plot option (bezierP $ beziaux listeP)
\end{haskellcode}


C'était il y a peu  la Saint-Valentin alors
dessinez un c\oe ur....



%\begin{figure}
\begin{center}
  \includegraphics[height=7cm,width=7cm]{coeur}
\end{center}
%\end{figure}



\medskip

\textbf{B-splines uniformes}

Tout ceci est  très beau mais il  y a un hic: en changeant  un point de
contrôle, on modifie grandement la figure.




On considère $m$ n\oe uds $t_0,t_1n,\cdots,t_m$ de l'intervalle $[0,1]$.




Introduisons une nouvelle fonction~:

$$\mathbf{S}(t)= \sum_{i=0}^{m-n-1} \mathbf{P}_{i} b_{i,n}(t) \mbox{ , } t \in [0,1]$$


 les $P_i$ étant les points de contrôle et les fonctions $b_{j,n}$ étant
 définies récursivement par 

$$  b_{j,0}(t)  =  \left\{\begin{matrix}  1  &  \text{si}  \quad  t_j
    \leqslant t < t_{j+1} \\ 0 & \text{sinon} \end{matrix} \right.$$

et pour $n\geqslant  1$

$$    b_{j,n}(t) = \frac{t - t_j}{t_{j+n} - t_j} b_{j,n-1}(t) + \frac{t_{j+n+1} - t}{t_{j+n+1} - t_{j+1}} b_{j+1,n-1}(t). $$

On ne  considérera par  la suite que  des n\oe  uds équidistants~:~ainsi
on aura $t_k=\frac{k}{m}$.

On  parle  de B-splines  uniformes  et  on  peut simplifier  la  formule
précédente en remarquant également des invariances par translation.


À l'aide des formules précédentes, on  peut prouver que dans le cas de 4
points de contrôle on obtient:

$$S(t)=\frac{1}{6}\Big((1-t)^3P_0+(3t^3-6t^2+4)P_1+(-3t^3+3t^2+3t+1)P_2+t^3P_3\Big)$$


Calculez $S(0)$, $S(1)$ puis $S'(0)$ et $S'(1)$:~que peut-on en conclure~?

Reprenez l'étude faite avec les courbes de \textsc{Bézier} 



\begin{haskellcode}
*Main> plot X11 $ bspline3 [(0,0),(-1,1),(-1,0),(0,-3)]
\end{haskellcode}



%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{bspline3}
\end{center}
%\end{figure}


Obtiendrez-vous un plus joli c\oe ur?


%\begin{figure}
\begin{center}
  \includegraphics[width=8cm,height=8cm]{coeurSpline}
\end{center}
%\end{figure}



\end{exercice}


%1
\begin{exercice}[2 points]
  Déterminez  la dérivée  de  la fonction  $x\mapsto \sqrt{\Bigl(\sqrt{\bigl(  \sqrt{(\sqrt
  {x})}\bigr)}\Bigr)}$.  Vous donnerez  l'expression  finale sous  la  forme la  plus
  simple possible.
\end{exercice}


%2
\begin{exercice}[6 points]
Déterminez, en détaillant vos calculs, les polynômes de \textsc{Taylor} à l'ordre 4 au voisinage de 0 de:
\begin{multicols}{3}
\begin{enumerate}
\item $f_1(x)=\ln(1-x)$
\item $f_2(x)=\exp(-x)$
\item $f_3(x)=\cos(2x)$
\end{enumerate}
\end{multicols}
\end{exercice}


\modenormal
%%% Local Variables: 
%%% TeX-master: "PolyAnalyse14"
%%% End: 
