From: couchot <jf.couchot@gmail.com>
Date: Mon, 9 Sep 2013 07:47:34 +0000 (+0200)
Subject: initialisation
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/commitdiff_plain/f4fb6abd4d0ca7a866d0cba93347244e9797040a

initialisation
---

diff --git a/biblio.bib b/biblio.bib
new file mode 100644
index 0000000..15b905b
--- /dev/null
+++ b/biblio.bib
@@ -0,0 +1,18 @@
+@book{jedrzejewski2005introduction,
+  title={Introduction aux m{\'e}thodes num{\'e}riques},
+  author={Jedrzejewski, F.},
+  isbn={9782287252037},
+  url={http://books.google.fr/books?id=c4wyKythaZwC},
+  year={2005},
+  publisher={Springer}
+}
+
+@book{bastien2003introduction,
+  title={Introduction {\`a} l'analyse num{\'e}rique: Applications sous Matlab},
+  author={Bastien, J. and Martin, J.N.},
+  isbn={9782100066827},
+  series={Sciences sup},
+  url={http://books.google.fr/books?id=SvQzHQAACAAJ},
+  year={2003},
+  publisher={Dunod}
+}
\ No newline at end of file
diff --git a/complexite.tex b/complexite.tex
new file mode 100644
index 0000000..dff2985
--- /dev/null
+++ b/complexite.tex
@@ -0,0 +1,310 @@
+\section{Complexité}
+
+\subsection{Quelques définitions}
+
+Soit $\mathcal{F}$ l'ensemble des fonctions de
+$\N$ dans $\R^*_+$. 
+\begin{Def}[fonctions asymptotiquement dominées]
+Soit $f \in \mathcal{F}$. L'ensemble $\mathcal{O}(f)$ 
+des fonctions \emph{asymptotiquement dominées par} $f$ est défini par
+$$
+\mathcal{O}(f) = 
+\large\{ g \in \mathcal{F} \textrm{ t. q. }
+\exists n_0 \in \N, 
+\exists c \in \R_+,
+\forall n \geq n_0,
+g(n) \leq c f(n)
+\large\}.
+$$
+Ainsi, à partir d'un rang $n_0$, $g(n)$ est majorée par $c f(n)$.
+\end{Def}
+
+\begin{Prop}
+Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
+$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
+alors on a 
+$\mathcal{O}(f) =  
+\mathcal{O}(g)$
+\end{Prop}
+
+
+On confond dans ce qui suit la fonction $n \mapsto f(n)$ avec $f(n)$.
+
+\begin{Exo}
+Que dire de:
+\begin{enumerate}
+\item  $2^{n+1}$  et $\mathcal{O}(2^{n})$?
+\item  $({n+1})!$  et $\mathcal{O}(n!)$?
+\end{enumerate}
+\end{Exo}
+
+\begin{Prop}
+Soit deux réels $\epsilon$ et $c$ vérifiant $0 < \epsilon <  1 < c$. Alors on a 
+
+$
+\mathcal{O}(1) \subset 
+\mathcal{O}(\ln(n)) \subset 
+\mathcal{O}(n^{\epsilon}) \subset 
+\mathcal{O}(n) \subset 
+\mathcal{O}(n \ln(n)) \subset 
+\mathcal{O}(n^c) \subset 
+\mathcal{O}(c^n) \subset 
+\mathcal{O}(n!)
+$
+\end{Prop}
+
+\begin{Def}[fonctions dominant asymptotiquement]
+Soit $f \in \mathcal{F}$. L'ensemble $\Omega(f)$ 
+des fonctions \emph{dominant asymptotiquement} $f$ est défini par
+$$
+\Omega(f) = 
+\large\{ g \in \mathcal{F} \textrm{ t. q. }
+\exists n_0 \in \N, 
+\exists c \in \R_+,
+\forall n \geq n_0,
+g(n) \geq c f(n)
+\large\}.
+$$
+Ainsi, à partir d'un rang $n_0$, $g(n)$ majore $c f(n)$.
+\end{Def}
+
+
+\begin{Prop}
+Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
+$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
+alors on a 
+$\Omega(f) =  
+\Omega(g)$
+\end{Prop}
+
+\begin{Prop}
+Soit deux réels $\epsilon$ et $c$ vérifiant $0 < \epsilon <  1 < c$. Alors on a 
+
+$
+\Omega(1) \supset 
+\Omega(\ln(n)) \supset 
+\Omega(n^{\epsilon}) \supset 
+\Omega(n) \supset 
+\Omega(n \ln(n)) \supset 
+\Omega(n^c) \supset 
+\Omega(c^n) \supset 
+\Omega(n!)
+$
+\end{Prop}
+
+\begin{Def}[fonctions asymptotiquement équivalentes]
+Soit $f \in \mathcal{F}$. L'ensemble $\Theta(f)$ 
+des fonctions \emph{asymptotiquement équivalentes} à  $f$ est défini par
+$$
+\Theta(f) = 
+\large\{ g \in \mathcal{F} \textrm{ t. q. }
+\exists n_0 \in \N, 
+\exists c, c' \in \R_+,
+\forall n \geq n_0,
+c f(n) \leq g(n) \leq c' f(n)
+\large\}.
+$$
+\end{Def}
+
+
+\begin{Prop}
+Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
+$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
+alors on a 
+$f \in \Theta(g)$ et   
+$g \in \Theta(f)$.
+\end{Prop}
+
+\begin{Prop}
+Soit $f$, $f_1$,  et $g$ des fonctions de $\mathcal{F}$. Si 
+$f \in \Theta(g)$ et si $\lim_{n \rightarrow + \infty} \frac{f_1(n)}{g(n)} = 0 $
+alors on a 
+$f  + f_1 \in \Theta(g)$.
+\end{Prop}
+
+
+\subsection{Mesurer la complexité}
+Soit $\mathcal{A}(n)$ un algorithme résolvant un problème sur des données 
+de taille $n$, $n \in \N$. On suppose que l'exécution de $\mathcal{A}$ 
+coûte $T(n)$ étapes informatiques élémentaires ou unités de temps. 
+
+\begin{Def}[Pire des cas]
+L'algorithme $\mathcal{A}(n)$ a une \emph{complexité du pire des cas}
+dans $\mathcal{O}(f(n))$ si $T(n) \in \mathcal{O}(f(n))$.   
+On dit que $\mathcal{A}$ est en $\mathcal{O}(f(n))$.
+\end{Def}
+
+Attention, la majoration proposée doit être la plus fine possible.
+De plus, celle-ci doit être valide au delà d'une valeur $n$ supérieure 
+à un seuil $n_0$. 
+ 
+
+\begin{Def}[Meilleur des cas]
+L'algorithme $\mathcal{A}(n)$ a une \emph{complexité du meilleur des cas}
+dans $\Omega(f(n))$ si $T(n) \in \Omega(f(n))$.   
+On dit que $\mathcal{A}$ est en $\Omega(f(n))$.
+\end{Def}
+
+\begin{Def}[ordre de grandeur d'un temps d'exécution]
+L'algorithme $\mathcal{A}(n)$ a une \emph{complexité} en
+$\Theta(f(n))$ si $T(n) \in \Theta(f(n))$.   
+On dit que $\mathcal{A}$ est en $\Theta(f(n))$.
+\end{Def}
+
+On note que si $T(n) \in \Theta(f(n))$, alors 
+$T(n) \in \mathcal{O}(f(n))$ et $T(n) \in \Omega(f(n))$.
+Lorsque 
+$T(n) \in \Theta(n)$, on dit que l'algorithme est \emph{linéaire en $n$} 
+et lorsque 
+$T(n) \in \Theta(n^2)$, on dit que l'algorithme est \emph{quadratique en $n$}.
+
+\subsection{Exemples d'étude de complexité}
+
+\subsubsection{Un premier algo}
+Soit $p$ une fonction polynôme de degré $n$ définie par 
+$
+p(x) = \sum_{i=0}^n a_i x^i
+$.
+On considère tout d'abord l'algorithme suivant: 
+
+
+
+
+
+\begin{algorithm}[H]
+ \LinesNumbered 
+ \SetAlgoLined
+ \KwData{$n$: degré, $(a_i)_{0 \le i \le n}$: coefficients, $t$: 
+   réel en lequel on évalue}
+ \KwResult{$\textit{val}$: réel tel que $\textit{val}= p(t)$}
+ \nllabel{laff1} $a' = a$ \; 
+ \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} 
+   \nllabel{lafori} $a' = a_i + t \times a'$ \;
+ \nllabel{laforf}}
+ \nllabel{laff2} $\textit{val} = a'$ \;
+ \caption{Évaluation du polynôme $p$ en $t$}
+\end{algorithm}
+
+On calcule les coûts d'exécution des lignes de l'algorithme comme suit:
+\begin{itemize} 
+% \item $\alpha$ désigne le temps d'accès mémoire en lecture écriture;
+% \item $\beta$ désigne le temps d'exécution d'une opération arithmétique ($+$,$-$,$\times$, $/$);
+% \item $\gamma$ désigne le temps d'exécution d'un test.
+\item les lignes \ref{laff1} et \ref{laff2} cumulées coûtent une constante 
+de temps $A$ indépendante de $n$;
+\item la ligne \ref{lafori} nécessite un temps d'exécution 
+  $B$ indépendant de $n$; 
+\item la boucle for (ligne \ref{laford}) nécessite donc un temps $nB$.
+\end{itemize}
+
+Donc $T(n)= A + nB$ et donc $\lim_{n \rightarrow + \infty} \frac{T(n)}{n} = B$.
+Ainsi cet algorithme a une complexité linéaire en $n$.
+
+
+\subsubsection{Un second algo}
+
+On considère l'algorithme suivant:
+
+\begin{algorithm}[H]
+  \LinesNumbered 
+  \SetAlgoLined
+  \KwData{$n$: entier naturel, $(x_i)_{0 \le i \le n}$: abscisses réelles,
+    $(y_i)_{0 \le i \le n}$: ordonnées réelles.}
+ \KwResult{$d$: vecteur de $n+1$ réels}
+ \nllabel{laford2}\For{$i=0$ \KwTo $n$}{
+   \nllabel{lafori2} $d_i' = y_i$ \; 
+   \nllabel{laforf2}}
+ \nllabel{laford2b}\For{$i=1$ \KwTo $n$}{
+   \nllabel{laford2bb}\For{$j=n$ \KwTo $i$}{
+     \nllabel{lafori2bb} $d_j = (d_j - d_{j-1})/(x_j - x_{j-1})$ \;
+     \nllabel{laforf2b}}
+   \nllabel{lafori2b} }
+ \caption{Polynôme  d'approximation d'une fonction}
+\end{algorithm}
+
+
+On calcule les coûts d'exécution des lignes de l'algo comme suit:
+\begin{itemize} 
+\item la boucle for (lignes \ref{laford2}-\ref{laforf2})
+  nécessite un temps $(n+1)A$.
+\item la seconde boucle for (lignes \ref{laford2b}-\ref{lafori2b})
+  nécessite un temps
+$\sum_{i=1}^n B(n-i+1)$ soit encore 
+$B\sum_{i=1}^n (n-i+1)=B\sum_{i=1}^n i= B\frac{n.(n+1)}{2}$
+\end{itemize}
+Ainsi $T(n) = (n+1)A + B\frac{n.(n+1)}{2}$ et donc l'algorithme proposé est 
+quadratique en $n$.
+
+
+\begin{Exo}
+Dans un cadre industriel, on est amené à effectuer un contrôle $(P)$ sur 
+les données. La durée de cette phase est limitée. 
+Il existe deux méthodes $A_1(n)$ et $A_2(n)$ de traitement de $(P)$.
+On a établi que le temps d'exécution $T_1(n)$ de $A_1(n)$ est en 
+$\Theta(n^3)$ et que le temps d'exécution $T_2(n)$ de $A_2(n)$ est en 
+$\Theta(n^2)$.
+\begin{enumerate}
+\item Lors d'une évaluation pratique des deux méthodes, on a 
+  obtenu les mesures suivantes 
+$$\begin{array}{|l|l|l|}
+\hline
+n & T_1(n) & T_2(n) \\
+\hline
+200 & 10400 & 6800 \\
+\hline
+\end{array}.$$
+
+\begin{enumerate}
+\item En déduire quel sera le temps nécessaire au traitement de données 
+  de taille $n'=10^4$.
+\item Même question avec $n'=200\lambda$ où $\lambda$ réel de $[1, +\infty[$.
+\item Déterminer la taille maximale des données que peuvent traiter 
+  $A_1$ et $A_2$ si le temps disponible est $t=10^5$.
+\end{enumerate}
+\item En fait, une étude statistique approfondie des deux algorithmes a permis 
+d'établir que pour $n$ grand, on obtient: $T_1(n) \approx 0,001n^3$ et $T_2(n) \approx 0,19n^2$.
+\begin{enumerate}
+\item Quel est à priori l'algorithme le plus performant au vu de 
+  l'étude effectuée ?
+\item Montrer qu'il existe un seuil $n_0$ en dessous duquel l'algorithme réputé 
+le meilleur est en fait le moins performant. Déterminer cette valeur.
+\item Pourquoi un algorithme performant sur des données de grandes tailles 
+peut-il être lent pour des données de petite taille?
+\end{enumerate}
+\end{enumerate}
+\end{Exo}
+
+\subsection{Classes de complexité de problèmes}
+
+\subsubsection{La classe \emph{P}}
+Les problèmes de cette classe sont ceux qui admettent une solution 
+algorithmique  \emph{déterministe} et en temps \emph{polynomial}:
+lorsque la taille du problème est $n$, le 
+nombre d'étapes de l'algorithme qui le résout reste plus petit 
+qu'une certaine puissance de $n$ et ne contient pas d'indéterminisme.
+La complexité de l'algorithme est alors en $\Theta(n^k)$ pour un certain $k$.
+
+
+
+\subsubsection{La classe  \emph{NP}}
+Les problèmes de cette classe sont ceux qui admettent 
+une solution algorithmique \emph{non déterministe} en temps \emph{polynomial}.
+De façon équivalente, c'est la classe des problèmes pour lesquels 
+si une solution est proposée, on peut vérifier sa validité à l'aide d'un 
+un algorithme en temps polynomial. 
+On a $\emph{P} \subset \emph{NP}$.
+
+\subsubsection{La classe \emph{NP-complet}} 
+Les problèmes de cette classe sont ceux de la classe $\emph{NP}$ 
+tels que tous les problèmes de la classe NP peuvent se réduire à celui-ci. 
+Cela signifie que le problème est au moins aussi difficile
+que tous les autres problèmes de la classe NP.
+
+Le problème du voyageur de commerce (qui consiste à
+trouver le chemin le plus court reliant une série de villes),
+le problème du sac à dos (étant donné un sous-ensemble $S$
+de l’ensemble des entiers naturels et $m$
+un nombre positif, peut-on trouver
+une partie $A$ de $S$ 
+telle que la somme de ses éléments soit égale à l’entier $m$)
+sont des exemples de problèmes NP-complets.
diff --git a/equations.tex b/equations.tex
new file mode 100644
index 0000000..4a76973
--- /dev/null
+++ b/equations.tex
@@ -0,0 +1,444 @@
+\section{Motivation}
+Bien qu’il puisse être posé simplement (trouver tous les $x$ tel que $P(x) =0$),
+résoudre algébriquement des équations
+est un problème difficile.
+Depuis l'antiquité, l’homme a cherché des algorithmes donnant les
+valeurs des racines d'un polynôme 
+en fonction de ses coefficients.
+On connaît une solution pour les polynômes de degré 2. 
+C’est Cardan qui donna
+en 1545 les formules de résolution de certaines équations cubiques de 
+la forme 
+$ 
+x^3 + px+q = 0
+$ avec $p$ et $q$ non nuls. Calculons le discriminant 
+$\Delta = \frac{4}{27}p^3+ p^2$ et discutons de son signe:
+\begin{itemize}
+\item si $\Delta$ est nul, l'équation possède
+  deux solutions réelles, une simple et une double :
+
+$$
+\begin{cases}
+  x_0=2\sqrt[3]{\frac{-q}2}=\frac{3q}p
+  \\
+  x_1=x_2=-\sqrt[3]{\frac{-q}2}=\frac{-3q}{2p}
+\end{cases}
+$$
+
+
+\item Si $\Delta$ est positif, l'équation possède une solution réelle
+  et deux complexes. On pose alors 
+$u = \sqrt[3]{\frac{-q + \sqrt{\Delta}}2}$ et $v = \sqrt[3]{\frac{-q - \sqrt{\Delta}}2}$.
+La seule solution réelle est alors $x_0=u+v$. 
+Il existe également deux solutions complexes conjuguées l'une de l'autre:
+$$
+\begin{cases}
+x_1= j u +\bar{j} v \\ 
+x_2= j^2u +\overline{j^2}\end{cases}
+\qquad\textrm{ où }\qquad j=-\frac12+ i \frac{\sqrt3}2=e^{i\frac{2\pi}3}
+$$
+
+\item si $\Delta$ est négatif,  l'équation possède trois solutions réelles:
+$$
+x_k = 2 \sqrt{\frac{-p}{3}} \cos{\left(\frac13\arccos{\left(\frac{-q}{2}\sqrt{\frac{27}{-p^3}}\right)}+ \frac{2k\pi}{3}\right)}\qquad\mbox{ avec }\qquad k\in\{0,1,2\}.
+$$
+
+
+\end{itemize}
+Donnée à titre d'exemple, ce travail montre que rapidement on obtient 
+des algorithmes compliqués.
+De plus, Abel a montrée en 1824 qu'il n'est pas toujours possible 
+d'exprimer les racines de l'équation générale de
+degré supérieur ou égal à 5 à partir des coefficients du polynôme, des
+quatre opérations  et des racines nièmes...  
+On s'intéresse donc aux méthodes numériques.
+
+
+
+\section{Méthodes classiques}
+On considère pour l'ensemble du chapitre l'équation $f(x)=0$, où 
+$x$ décrit l'intervalle $[a,b]$ de $\R$ et $f$ désigne une fonction 
+définie et continue sur $[a,b]$ et à valeur dans $\R$.
+On suppose de plus la condition $f(a)f(b)\leq 0$ qui garantit 
+l'existence d'(au moins) une solution sur $[a,b]$.
+On présente la méthode par dichotomie et on ferra ensuite des exercices 
+sur d'autres méthodes.
+
+\subsection{Méthode par dichotomie}
+Construisons trois suites $(x_n)_{n \in \N}$,
+$(a_n)_{n \in \N}$ et $(b_n)_{n \in \N}$ définies par:
+\begin{itemize}
+\item $a_0=a$, $b_0=b$ et pour tout $n \in \N$, $x_n = (a_n+b_n)/2$, soit 
+  le milieu de $[a_n,b_n]$;
+\item si $f(a_n)f(x_n)\leq 0$, alors $a_{n+1} =  a_{n}$ et $b_{n+1}=x_n$;
+\item si $f(a_n)f(x_n)> 0$, alors $a_{n+1} =  x_{n}$ et $b_{n+1}=b_n$.
+\end{itemize}
+
+Par récurrence montrons que $f(a_n)f(b_n)\leq 0$ pour tout $n\in \N$.
+C'est vrai au rang 0. Supposons que ce le soit jusqu'au rang $n$.
+Évaluons $f(a_{n+1})f(b_{n+1})$: 
+\begin{itemize}
+\item si $f(a_n)f(x_n)\leq 0$ alors comme $a_{n+1} =  a_{n}$ et $b_{n+1}=x_n$, 
+le résultat est établi, c.-à-d. $f(a_{n+1})f(b_{n+1})\leq 0$;
+\item sinon, $f(a_n)f(x_n)> 0$. Ainsi $f(a_{n+1})f(b_{n+1})$ a le même 
+signe que $f(a_{n+1})f(b_{n+1})f(a_n)f(x_n)$ c.-à-d. le signe de  
+$f(x_{n})f(b_{n})f(a_n)f(x_n)$ soit encore le signe de  $f(a_n)f(b_n)$.
+Ce dernier est positif d'après l'hypothèse de récurence. 
+\end{itemize}
+
+A chaque itération, l'intervalle $[a_n,b_n]$ est découpé 
+en deux. On a donc 
+$$
+\begin{array}{c}
+|
+a_{n+1} -
+b_{n+1} 
+|
+\leq 
+\frac{1}{2}
+|
+a_{n} -
+b_{n} 
+|, 
+\,
+a \le a_n \le x_n \le b_n \le b,
+\,
+a_{n+1} \geq a_n
+\textrm{ et }
+ b_{n+1} \leq b_n
+\end{array}
+$$ 
+
+On obtient alors par récurrence que 
+\begin{equation}\label{eq:met:maj}
+|
+a_{n} -
+b_{n} 
+|
+\leq 
+\frac{1}{2^n}
+|
+a -
+b
+| 
+\end{equation}
+
+La suite $(a_n)$ est croissante, majorée. Elle converge vers une limite 
+$\alpha$ quand $n$ tend vers l'infini. 
+De même, 
+la suite $(b_n)$ est décroissante, minorée. Elle converge vers une limite 
+$\alpha'$ quand $n$ tend vers l'infini.
+D'après l'inégalité précédente, $\alpha = \alpha'$.
+La suite $(x_n)$ est encadrée par $(a_n)$ et $(b_n)$. Elle converge donc aussi  
+vers $\alpha$.
+Enfin, comme $f$ est continue et comme
+$f(a_n)f(b_n)\leq 0$, on a $f(\alpha)f(\alpha)\leq 0$ et donc 
+$f(\alpha)=0$ et donc $\alpha$ est une racine.
+On a donc trouvé une méthode algorithmique simple qui converge vers une 
+des racines.  
+
+Essayons maintenant de déterminer une majoration de l'erreur commise à 
+chaque itération. 
+Tout d'abord, comme $(a_n)$ est croissante et converge vers $\alpha$ on a 
+$a_n \leq \alpha$. De même $\alpha \leq b_n$ et donc
+$a_n \leq \{ \alpha,x_n\} \leq b_n$. 
+Ainsi, d'après l'équation (\ref{eq:met:maj}), on a 
+$$ 
+| x_n - \alpha |
+\leq 
+| a_n - b_n |
+\leq 
+\frac{1}{2^n}
+|
+a -
+b
+|. 
+$$
+
+Ainsi pour un $\epsilon$ donné positif représentant l'amplitude maximale de l'erreur, posons    
+\begin{equation}\label{eq:erreur:epsilon}
+n_0 = \lfloor \dfrac{ \ln(\frac{b-a}{\epsilon})}{\ln(2)} \rfloor + 1 
+\end{equation}
+
+Si $n \geq n_0$, alors 
+$
+2^n \geq 2^{\frac{ \ln(\frac{b-a}{\epsilon})}{\ln(2)}} \geq  
+e^{ \ln(\frac{b-a}{\epsilon})} \geq 
+\frac{b-a}{\epsilon}.
+$
+Ainsi $\frac{1}{2^n}(b-a) \leq {\epsilon}$ et donc
+$ 
+| x_n - \alpha |
+\leq 
+{\epsilon}.
+$
+
+Pour un $\epsilon$ donné, on sait calculer un rang $n_0$ à partir duquel 
+l'erreur avec la limite est inférieure à cet $\epsilon$. 
+
+
+
+\begin{figure}
+\psset{xunit=3cm,yunit=0.8cm}
+\savedata{\mydata}[{{0.0, -1.25}, {0.1, -1.24}, {0.2, -1.21}, {0.3, -1.16}, {0.4, -1.0899999999999999}, {0.5, -1.0}, {0.6, -0.89}, {0.7, -0.76}, {0.8, -0.6099999999999999}, {0.9, -0.43999999999999995}, {1.0, -0.25}, {1.1, -0.039999999999999813}, {1.2, 0.18999999999999995}, {1.3, 0.44000000000000017}, {1.4, 0.7099999999999997}, {1.5, 1.0}, {1.6, 1.3100000000000005}, {1.7, 1.6399999999999997}, {1.8, 1.9900000000000002}, {1.9, 2.36}, {2.0, 2.75}, {2.1, 3.16}, {2.2, 3.5900000000000007}, {2.3, 4.039999999999999}, {2.4, 4.51}}]
+\dataplot[plotstyle=curve,showpoints=true]{\mydata}
+\psline{<->}(0,2)(0,-2)(0,0)(3,0)
+\psline{-}(1.3125,0)(2.2,3.55)
+
+\vspace{2em}
+% \begin{pspicture}(9,9)
+% \psaxes[labels=none,ticks=none]{->}(0,0)(8,8)[$x$,0][$y$,0]
+% \pscurve(1,1)(3,4)(6,6)(8,4)
+% \pscurve[linestyle=symbol,symbolStep=11.6pt,% must be positive 
+%   curveticks,startAngle=60](1,1)(3,4)(6,6)(8,4)
+% \end{pspicture}
+% \begin{pspicture}(8,8)
+% \psaxes[labels=none,ticks=none]{->}(0,0)(8,8)[$x$,0][$y$,0]
+% \pscurve[linestyle=symbol,symbolStep=-20,% must be negative !
+%   curveticks,startAngle=60](1,1)(3,4)(6,6)(8,4)
+% \end{pspicture}
+\caption{Représentation graphique de méthodes itératives de construction de racine}\label{fig:graphe1} 
+\end{figure}
+
+\begin{Exo}
+Soit $f$ une fonction de $\R$ dans $\R$. On suppose 
+que $f$ possède une racine $\alpha$ dans l'intervalle $[a,b]$ et 
+on cherche une valeur approchée de cette racine.
+L'idée commune des méthodes de Lagrange et Newton est d'écrire 
+\begin{equation}
+0 = f(\alpha)= f(x) + (\alpha-x)f'(\zeta), \textrm{ où } \zeta \in [\alpha,x]
+\end{equation}
+On construit de façon itérative une suite $(x_n)_{n \in \N}$ censée converger 
+vers $\alpha$ en remplaçant l'équation précédente par 
+\begin{equation}
+0 = f(x_n) + (x_{n+1}-x_{n})q_n \label{eq:num:class}
+\end{equation}
+où $q_n$ est une approximation de $f'(x_n)$.
+
+Dans cet exercice, on suppose en plus que:
+\begin{itemize}
+\item $f(x_n) \neq 0$ : sinon, la racine est trouvée;
+\item $f$ est injective sur $[a,b]$ (pour tout $x$, $y$ de $[a,b]$, 
+  si $f(x) = f(y) \Rightarrow x = y$);
+\item $q_n$ n'est jamais nul.
+\end{itemize}
+
+\begin{enumerate}
+\item Méthode globale
+\begin{enumerate}
+\item Montrer que l'on a $x_{n+1} \neq x_{n}$.
+\item Montrer que (\ref{eq:num:class}) est équivalente à 
+\begin{equation}
+x_{n+1} = x_{n} - \frac{f(x_n)}{q_n} \label{eq:num:gen}
+\end{equation}
+\item Dans la représentation graphique donnée figure~\ref{fig:graphe1}:
+  \begin{enumerate}
+  \item donner l'équation de la droite tracée;
+  \item montrer que l'abscisse du point d'intersection 
+    de cette droite avec l'axe des abscisses est $x_{n+1}$;
+  \item Construire quelques $x_i$ supplémentaires.
+  \end{enumerate}
+\end{enumerate}
+
+\item Dans la méthode de la corde, $q_n$ est constante et égale à 
+\begin{equation}
+q_{n} = \frac{f(b) - f(a)}{b - a} \label{eq:num:corde}
+\end{equation}
+
+\item Dans la méthode de Lagrange on a 
+\begin{equation}
+q_{n} = \frac{f(x_{n}) - f(x_{n-1})}{x_n - x_{n-1}} \label{eq:num:lagrange}
+\end{equation}
+
+\item Dans la méthode de Newton on a $q_n = f'(x_n)$
+\end{enumerate}
+\end{Exo}
+
+
+
+\section{Convergence des méthodes de Lagrange et Newton}
+
+
+\begin{Prop}
+Soit l'équation $f(x)=0$ et la suite $(x_n)$ des itérés de Newton définie par
+$x_0$ et $\forall n \in N$, $x_{n+1} = x_{n} -\frac{f(x_n)}{f'(x_n)}$.
+Sous les hypothèses suivantes:
+\begin{enumerate}
+\item $f$ de classe $C^2$ sur $[a,b]$,
+\item $f(a)f(b) < 0$,
+\item $ \forall x \in [a,b]$, $f'(x)\neq 0$,
+\item $f''$ de signe constant sur $[a,b]$,
+\item $\frac{|f(a)|}{|f'(a)|} < b-a $ et $\frac{|f(b)|}{|f'(b)|} < b-a $,
+\end{enumerate}
+la suite des itérés de Newton converge pour tout choix de $x_0$ dans $[a,b]$ vers l'unique 
+solution $\alpha$ de cet intervalle.
+\end{Prop}
+
+
+
+ \begin{Def}[Erreur et ordre]
+   Soit $(x_n)$ une suite convergeant vers une valeurs $\alpha$. 
+   On appelle \emph{erreur de rang $n$} le réel $e_n=\alpha-x_n$. On 
+   dit que la convergence est d'ordre $p \in \R^*_+$ si
+   $
+   \lim\limits_{n \to \infty} \dfrac{|e_{n+1}|}{|e_n|^p} = c
+   $, 
+   où $c$ est un réel positif non nul.
+   On remarque que plus l'ordre est élevé, plus la méthode converge vite.
+ \end{Def}
+
+
+\begin{Prop}[Vitesse de convergence]
+Si la suite des itérés de Lagrange converge, alors la convergence est 
+d'ordre $(1+\sqrt{5})/2$.
+Si la suite des itérés de Newton converge, 
+alors la convergence est au moins d'ordre 2.
+\end{Prop}
+
+
+\section{Méthode de point fixe}
+Soit $f$  une application d'un ensemble $E$ dans lui-même.
+On appelle \emph{point fixe} de l'application $f$ tout élément
+$u$ dans $E$ tel que $g(u)=u$.
+On voit que résoudre ce type d'équation
+est un cas particulier des équations numériques 
+$h(u)=g(u)-u=0$. 
+Cependant, on peut les étudier pour les algorithmes spécifiques 
+qui les résolvent. 
+
+\subsection{Exemples de points fixe}
+L'équation $x^4+6x^2-60x+36=0$ dite de Ferrari admet deux racines réelles dans l'intervalle $[0,4]$.
+Pour résoudre numériquement ce problème, on peut transformer l'équation en une équation du point 
+fixe $g_i(x) =x$ avec 
+\begin{itemize}
+\item $g_1(x) = \frac{1}{60}(x^4 + 6x^2 +36)$;
+\item $g_2(x) = - \frac{36}{x^3+6x-60}$;
+\item $g_3(x) = (-6x^2+ 60x -36)^{\frac{1}{4}}$.
+\end{itemize}
+
+
+\subsection{Algorithme du point fixe}
+L'algorithme du point fixe donné ci dessous (Algorithme~\ref{algo:pf}) est 
+une version constructive de la suite $(x_n)$ définie par $x_0$ et pour tout $n \in \N$, 
+$x_{n+1} = g(x_n)$.
+
+\begin{algorithm}[H]
+ \LinesNumbered 
+ \SetAlgoLined
+ \KwData{$x_0$: terme initial, $g$: fonction définissant les itérés} 
+ \KwResult{$n$: nombre d'itérations effectuées, $[x_1, \ldots,x_n]$: vecteurs des itérés}
+ $n = 0$ \; 
+ initialisation du booléen d'\textit{arrêt}\; 
+ \While{non(arrêt)}{
+   $x_{n+1} = g(x_n)$ \;
+   $n = n+1$ \;}
+ \caption{Algorithme du point fixe}\label{algo:pf}
+\end{algorithm}
+
+\subsection{Conditions suffisantes de convergence}
+
+
+\begin{Prop}\label{th:csconv:pf}
+Supposons qu'il existe un intervalle $[a,b]$ de $\R$ sur lequel $g$ vérifie:
+\begin{enumerate}
+\item $g$ est définie sur $[a,b]$ et $g([a,b]) \subset [a,b]$;
+\item $g$ est dérivable sur $[a,b]$ et il existe un réel $k\in[0,1[$ tel que pour 
+tout $x \in [a,b]$ on a $|g'(x)|<k$;
+\end{enumerate}
+alors:
+\begin{enumerate}
+\item $g$ admet un point fixe $l$ dans $[a,b]$;
+\item pour tout $x_0$ de $[a,b]$, la suite $x_n$ converge vers $l$, unique solution dans 
+$[a,b]$.
+\end{enumerate}
+\end{Prop}
+
+
+\subsection{Vitesse de convergence}
+\begin{Prop}[Vitesse de convergence de la méthode du point fixe]
+Sous les hypothèses de la proposition précédente, on peut dire qu'en général
+la convergence de la méthode du point fixe est linéaire.
+\end{Prop}
+
+\begin{Exo}
+Pour chacune des équations suivantes, étudier la convergence de la suite des 
+itérés du point fixe pour un $x_0$ choisi dans l'intervalle proposé.
+\begin{enumerate}
+\item fonction $g_3$ de Ferrari sur $[2;4]$;
+\item fonction $g_2$ de Ferrari sur $[3;\textrm{3,1}]$;
+\end{enumerate}
+\end{Exo}
+
+
+\begin{Exo}
+On verra dans cet exercice que les conditions de la 
+proposition~\ref{th:csconv:pf}  sont suffisantes, pas nécessaires.
+\begin{enumerate}
+\item Quels sont les points fixes de $g(x)=x - x^3$ sur $[-1;1]$?
+\item La fonction $g$ vérifie-t-elle les hypothèses de la proposition~\ref{th:csconv:pf}?
+\item Montrer que pour tout $x_0 \in [-1;1]$, la suite des itérés converge. 
+  On pourra  se restreindre à étudier $x_0$ sur  $[0;1]$ comme 
+  la fonction est paire.
+\item Mêmes questions avec $g(x)=x + x^3$.
+\end{enumerate}
+\end{Exo}
+
+\begin{TP}
+Tout le code suivant est à faire en python.
+\begin{enumerate}
+\item Écrire la fonction 
+\verb+[n,X] = iteration_dichotomie(a,b,m,epsilon,f)+ où
+\begin{itemize}
+\item \verb+a+, \verb+b+ sont les bornes de l'intervalle, \verb+m+
+  est le nombre maximal 
+  d'itérations, \texttt{epsilon} est la précision souhaitée 
+  (voir équation (\ref{eq:erreur:epsilon})) et \verb+f+ la fonction à itérer;
+\item \verb+n+ est le nombre d'itérations réalisées pour que 
+\verb+f(+$\verb+x+_{\verb+n+}$\verb+)+=0 ou que 
+$|\verb+x+_{\verb+n+}- \verb+x+_{\verb+n-1+}| \leq \verb+epsilon+$, \verb+n+ étant inférieur à \verb+m+ et \verb+X+ est 
+  le vecteur contenant les 
+  valeurs $\verb+x+_{\verb+0+},\ldots,\verb+x+_{\verb+n+}$.
+\end{itemize}
+\item Écrire la fonction 
+\verb+[n,X] = iteration_corde(a,b,+$\verb+x+_{\verb+0+}$\verb+,m,epsilon,f)+ où
+\begin{itemize}
+\item $\verb+x+_{\verb+0+}$ est le premier terme de la suite;
+\end{itemize}
+\item Écrire la fonction 
+\verb+[n,X] = iteration_Newton(+$\verb+x+_{\verb+0+}$\verb+,m,epsilon,f)+.
+\end{enumerate}
+\end{TP}
+
+
+\begin{TP}
+L'objectif du TP est de mesurer l'ordre de grandeur de la convergence d'une 
+méthode.
+On suppose que la suite $(x_n)$ converge vers $l$ avec l'ordre $p\geq 1$. 
+On note $e_n= l -x_n$. On a $|e_{n+1}| \approx c |e_n|^p$ et donc 
+$\ln(|e_{n+1}|) \approx p \ln(|e_n|) + \ln(c)$.
+En posant $y = \ln(|e_{n+1}|)$, $x = \ln(|e_n|)$ et $k = \ln(c)$ on a 
+$y = px + k$ soit l'équation d'une droite de pente $p$.
+Pour estimer $p$, on peut donc tracer l'ensemble de points 
+$(\ln(|e_{n}|),\ln(|e_{n+1}|))$, contruire la droite de regression linéaire
+et prendre son coefficient directeur.
+
+\begin{enumerate}
+\item Construire la méthode 
+\verb+p=ordre_convergence(X,l)+ telle que 
+\begin{itemize}
+\item \texttt{X} est le vecteur contenant les valeurs des itérés $\verb+x+_{\verb+0+}$, \ldots, $\verb+x+_{\verb+n+}$ et 
+  \verb+l+ est la limite présumée de la suite;
+\item cette fonction exploite la fonction 
+\verb+scipy.stats.linregress(x, y=None)+;
+\item \verb+p+ est l'ordre de convergence calculé numériquement.
+\end{itemize}
+
+\item Tester les méthodes du TP précédent 
+  (dichotomie, corde, Lagrange, Newton) pour la fonction 
+  $f$ définie par $f(x)=\cos(x)-x$ sur $[0,\pi/2]$.
+  Calculer l'ordre à l'aide de la fonction développée à la première question.
+\item Comparer avec la fonction \verb+scipy.optimize.newton+.
+\end{enumerate}
+\end{TP}
+
+
diff --git a/interpol.tex b/interpol.tex
new file mode 100644
index 0000000..f1f9078
--- /dev/null
+++ b/interpol.tex
@@ -0,0 +1,199 @@
+Soit $f: I \to \R$ une fonction connue seulement en  $n+1$ 
+points $x_0$, $x_1$, \ldots, $x_n$, 
+tous dans $I$. Ce sont par exemples les points 
+en lesquels la fonction $f$ a pu être évaluée.
+Peut-on déterminer un polynôme $p$ de degré au plus égal à $n$ prenant les 
+mêmes valeurs que la fonction $f$ en $x_0$, $x_1$, \ldots, $x_n$.
+Si un tel polynôme $p$ existe, on dit alors que $p$ interpole $f$ aux points 
+(au n{\oe}uds) $x_0$, $x_1$, \ldots, $x_n$.
+
+\section{Formalisation du problème}
+\begin{Def}[Interpolation]
+  On dit qu'un polynôme $p$ de degré $n$ interpole $f$ aux points
+  $x_0$, $x_1$, \ldots, $x_n$ si pour tout $i$, $0 \le i \le n$, on a 
+  $p(x_i) = f(x_i)$.
+\end{Def}
+
+
+
+\begin{Prop}[Unicité du polynome d'interpolation]
+Si $p$ de degré inférieur ou égal à $n$ interpole $f$ en 
+$x_0$, $x_1$, \ldots, $x_n$, alors $p$ est unique.
+\end{Prop}
+
+\begin{Def}[Base de Lagrange]
+  On appelle base de Lagrange associée au support 
+  $\{x_0, x_1, \ldots, x_n\}$ l'ensemble des polynômes $l_i$, 
+  $0 \le i \le n $ définis par 
+  $$
+  l_i = \prod_{
+    \begin{scriptsize}
+    \begin{array}{ll} 
+        j = 0 \\ 
+      j \neq i
+    \end{array}
+  \end{scriptsize}
+}^n
+\dfrac{x - x_j}{x_i - x_j}
+  $$
+\end{Def}
+
+\begin{Prop}[Existence du polynome d'interpolation]
+  Le polynôme $p$ défini par 
+  $p(x) = \sum_{i=0}^n f(x_i)l_i(x)$, où les $l_i$ forment la base de Lagrange,  
+  interpole $f$ 
+  en $x_0$, $x_1$, \ldots, $x_n$.
+  On parle d'\emph{interpolation de Lagrange} dans ce cas.
+\end{Prop}
+
+\begin{Exo}
+Montrer les résultats suivants:
+\begin{enumerate}
+\item Le polynôme de degré 0 qui interpole $f$ en $x_0$ est donné par 
+  $p(x) = f(x_0)$.
+\item Soit $x_0$ et $x_1$ deux réels distincts.
+  Le polynôme de degré inférieur 1 qui interpole $f$ en $x_0$ et $x_1$ 
+  est donné par  $p(x) = f(x_0) + \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)$.
+\end{enumerate}
+\end{Exo}
+
+\section{Détermination efficace du polynôme d'interpolation}
+On peut écrire le polynôme $p$ qui interpole $f$ 
+en $x_0$, $x_1$, \ldots, $x_n$ sous sa forme \og de Newton \fg{} 
+$$
+p(x) = \sum_{i=0}^n d_i \left[  \prod_{j=0}^{i-1} (x - x_j)\right],
+$$
+où les $d_i$ sont à déterminer.
+
+On peut alors démontrer le résultat suivant. 
+
+\begin{Prop}[Construction iterrative selon la forme de Newton]
+Pour tout $k \in \{1, \ldots, n\}$, on a:
+$$p_i(x) = p_{i-1}(x) + d_i  \left[  \prod_{j=0}^{i-1} (x - x_j)\right]$$.
+\end{Prop}
+
+Ainsi pour obtenir $p$ sur $x_0$, $x_1$, \ldots, $x_n$, il suffit:
+\begin{itemize}
+\item de calculer $d_0$, pour définir $p_0$ qui interpole $p$ sur $x_0$,
+\item de calculer $d_1$, pour définir $p_1$  qui interpole $p$ sur $x_0$ 
+  et $x_1$,
+\item \ldots
+\item de calculer $d_n$, pour définir $p_n$  qui interpole $p$ sur 
+  $x_0$, $x_1$, \ldots, $x_n$.
+\end{itemize}
+
+Le coefficient $d_i$ est le coefficient dominant de $p_i$: il dépend 
+de $f$ et de $x_0$, $x_1$, \ldots, $x_i$. On appelle ce nombre la 
+\og différence divisée\fg{} et on le note $d_i = f[x_0, \ldots,x_i]$.
+On admettra la méthode suivante pour calculer la table des différences 
+divisées.
+
+
+\begin{Prop}[Calcul des différences divisées]
+On a:
+\begin{enumerate}
+\item $f[x_i] = f(x_i)$ pour tout $i \in \{0, \ldots, n\}$;
+\item $f[x_i,x_{i+1}, \ldots, x_{i+j}] = 
+  \dfrac{f[x_{i+1}, \ldots, x_{i+j}]- f[x_i,x_{i+1}, \ldots, x_{i+j-1}]}{x_{i+j}-x_{i}}$
+\end{enumerate}
+Ainsi on obtient:
+$$
+\begin{array}{llllll}
+x_0 & \bf{f[x_0]} & \bf{f[x_0,x_1]} & \bf{f[x_0,x_1,x_2]} & \ldots & 
+\bf{f[x_0,x_1,x_2,x_3\ldots,x_n]}\\
+x_1 & f[x_1]      & f[x_1,x_2]         &  \ldots & f[x_1,x_2,x_3,\ldots,x_n] \\
+\ldots \\
+x_{n-1} & f[x_{n-1}] & f[x_{n-1},x_n]\\
+x_n & f[x_n]
+\end{array} 
+$$
+\end{Prop}
+
+
+Les coefficients sur la première ligne fournissent les coefficients 
+de la forme de Newton de $p_n$ relative aux centres 
+$x_0$, \ldots $x_{n-1}$:
+$p_n(x) = 
+f[x_0] + f[x_0,x_1](x-x_0) +  f[x_0,x_1,x_2](x-x_0)(x-x_1) + \ldots
++ f[x_0,\ldots,x_n](x-x_0)(x-x_1)\ldots(x-x_{n-1})
+$
+
+\begin{Exo}
+On donne trois valeurs d'une fonction $f$ définie sur $[1,6]$:
+$f(1) = 1,5709$,  
+$f(4) = 1,5727$ et   
+$f(6) = 1,5751$.  
+\begin{enumerate}
+\item En utilisant les polynômes de Lagrange relatifs au support $\{1,4\}$,
+fournir une valeur approchée de $f(3,5)$ grâce au polynôme d'interpolation 
+de $f$ de degré un.
+\item En utilisant les polynômes de Lagrange relatifs au support $\{1,4,6\}$,
+fournir une valeur approchée de $f(3,5)$ grâce au polynôme d'interpolation 
+de $f$ de degré deux.
+\item Traiter de nouveau ces deux questions en utilisant une forme de Newton.
+\item Comparer ces deux méthodes et conclure.
+\end{enumerate}
+\end{Exo}
+
+
+
+\begin{TP}[Première interpolation]
+\begin{enumerate}
+\item Construire l'algorithme qui:
+\begin{itemize}
+\item prend en entrée $x_0, \ldots,x_n$ et $f(x_0), \ldots, f(x_n)$;
+\item retourne la matrice \verb+diff_div+ de taille $(n+1)\times(n+1)$ telle
+que \verb+diff_div[i][j]+$=f[x_i, \ldots,x_{i+j}]$ pour 
+$i\in\{0,\ldots,n\}$ et $j\in \{0, \ldots, n-i\}$ comme définie
+dans la proposition précédente.
+\end{itemize}
+\item Dans le cadre d'un processus industriel, on a noté le temps d'exécution 
+$T(n)$ d'un algorithme sur des données de taille $n$ dans le tableau suivant:
+$$
+\begin{array}{|l||l|l|l|}
+\hline 
+n & 10 & 25 & 60 \\
+\hline
+T(n) & 2,3 & 8,0 & 24,6 \\
+\hline
+\end{array}
+$$
+\begin{enumerate}
+\item Déterminer le polynôme $p$ d'interpolation de $T$ sur le support
+$\{10,25,60\}$ en utilisant la méthode développée à la première partie.
+\item En déduire le temps $T(n)$ pour un traitement de données de 
+taille $n$, avec $n \in \{15,40,100\}$.
+\item Représenter le tracé de $p$.
+\end{enumerate}
+\end{enumerate}
+\end{TP}
+
+\begin{TP}[Choix du support]
+L'objectif du TP est de montrer que des points régulièrement répartis sur 
+un support contraint peu le polynôme sur les bords de celui-ci.
+Ainsi l'approximation peu s'en trouver dégradée sur les bords.
+
+On se place sur $[a,b]= [-1,1]$ et on considère deux 
+interpolations de $f(x)=e^x$ correspondant à deux choix de supports.
+\begin{enumerate}
+\item Premier choix: Pour tout $i \in \{0,\ldots,8\}$, on construit 
+  $x_i = -1 + 0,25i$.
+\begin{enumerate}
+\item Déterminer le polynôme $p_1$ d'interpolation de $f$ sur 
+  $\{x_0,\ldots,x_8\}$ à l'aide de la méthode développée au TP précédent.
+\item Représenter $p_1$ en faisant apparaître les points d'abscisse $x_0$,\ldots, 
+$x_8$.
+\item Représenter la fonction $e_1(x) = | f(x)-p_1(x) |$  pour tout $x\in[-1,1]$. 
+\end{enumerate}
+\item Second choix: Pour tout $i \in \{0,\ldots,8\}$, on construit 
+  $t_i = \cos(\frac{\pi}{2}\frac{2i+1}{9})$.
+\begin{enumerate}
+\item Déterminer le polynôme $p_2$ d'interpolation de $f$ sur 
+  $\{t_0,\ldots,t_8\}$ à l'aide de la méthode développée au TP précédent.
+\item Représenter $p_2$ en faisant apparaître les points d'abscisse 
+  $t_0$,\ldots, $t_8$.
+\item Représenter la fonction $e_2(x) = | f(x)-p_2(x) |$  pour tout $x\in[-1,1]$. 
+\end{enumerate}
+\item Conclure
+\end{enumerate}
+\end{TP}
diff --git a/main.tex b/main.tex
new file mode 100755
index 0000000..3a8e172
--- /dev/null
+++ b/main.tex
@@ -0,0 +1,152 @@
+\documentclass[a4paper,french,11pt]{report}
+%\usepackage{hyperlatex}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{lmodern}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{stmaryrd}
+\usepackage{amssymb}
+\usepackage{optional}
+\usepackage{framed}
+\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
+\usepackage[dvips]{graphics}
+\usepackage{epsfig}
+\usepackage{epsfig,psfrag}
+\usepackage{subfigure}
+\usepackage{color}
+\usepackage{calc}
+\usepackage{listings}
+\usepackage{url}
+\usepackage{makeidx}
+\usepackage{longtable}
+\usepackage{tabls}
+\usepackage{textcomp}
+%\usepackage{slashbox}
+\usepackage{times}
+\usepackage{gastex}
+\usepackage{multirow}
+\usepackage{algorithm2e}
+\usepackage{pst-plot}
+%\input{format.sty}
+\usepackage[frenchb]{babel}
+\usepackage[a4paper]{geometry}
+\input{symboles.sty}
+
+
+\theoremstyle{plain}
+%\theoremsymbol{\ensuremath{\clubsuit}}
+\theoremseparator{.}
+%\theoremprework{\hrulefill}
+%\theorempostwork{\hrulefill\newline}
+\newtheorem{Exo}{Exercice}[chapter]
+
+
+
+\theoremstyle{plain}
+%\theoremsymbol{\ensuremath{\clubsuit}}
+\theoremseparator{.}
+%\theoremprework{\hrulefill}
+%\theorempostwork{\hrulefill\newline}
+\newtheorem{TP}{Travaux pratiques}[chapter]
+
+
+
+
+\theoremstyle{plain}
+\theoremheaderfont{\normalfont\bfseries\sc}
+\theorembodyfont{\normalfont}
+%\theoremsymbol{\ensuremath{}}
+\theoremprework{\bigskip}
+\theoremseparator{.}
+\newtheorem{Def}{Définition}[chapter]
+
+
+\theoremstyle{plain}
+\theoremheaderfont{\normalfont\bfseries\sc}
+\theorembodyfont{\normalfont}
+%\theoremsymbol{\ensuremath{}}
+\theoremprework{\bigskip}
+\theoremseparator{.}
+\newtheorem{Prop}{Proposition}[chapter]
+
+
+\lstset{% general command to set parameter(s)
+basicstyle=\small,          % print whole listing small
+keywordstyle=\color{black}\bfseries\underbar,
+                                % underlined bold black keywords
+identifierstyle=,           % nothing happens
+commentstyle=\color{white}, % white comments
+stringstyle=\ttfamily,      % typewriter type for strings
+extendedchars = true,
+showstringspaces=false}     % no special string spaces
+
+
+
+\usepackage{hyperref}
+\pdfcompresslevel=9
+\hypersetup{
+     %backref=true,    %permet d'ajouter des liens dans...
+     %pagebackref=true,%...les bibliographies
+     %hyperindex=true, %ajoute des liens dans les index.
+     colorlinks=true, %colorise les liens
+     breaklinks=true, %permet le retour à la ligne dans les liens trop longs
+     urlcolor= blue, %couleur des hyperliens
+     linkcolor= blue, %couleur des liens internes
+     %bookmarks=true, %créé des signets pour Acrobat
+     bookmarksopen=true,            %si les signets Acrobat sont créés,
+                                    %les afficher complÚtement.
+     pdftitle={Cours de mathématiques discrètes}, %informations apparaissant dans
+     pdfauthor={Christophe Guyeux},     %dans les informations du document
+     pdfsubject={Mathématiques discrètes}          %sous Acrobat.
+}
+
+
+
+
+\makeindex
+
+%\renewcommand{\thesubsection}{~~~~\arabic{subsection}}
+%\renewcommand{\theparagraph}{~~~~~~~~\arabic{paragraph}}
+
+
+\begin{document}
+\title{Modélisation et Évaluation des Systèmes Informatiques}
+\author{Christophe {\sc Guyeux} et Jean-Fran\c{c}ois {\sc Couchot} \\
+  \url{guyeux [arobase] univ-fcomte
+    [point] fr}\\
+  \url{couchot [arobase]univ-fcomte
+    [point] fr}}
+
+
+
+%\lstset{language=C}
+\maketitle
+\tableofcontents
+
+\setcounter{secnumdepth}{3}
+
+
+
+
+\chapter{Des erreurs  de problèmes numériques}
+\input{pbnum}
+
+\chapter{Introduction à la complexité}
+\input{complexite}
+
+\chapter{Interpolation polynomiale}
+\input{interpol}
+
+
+
+
+\chapter{Résolution d'équations}
+\input{equations}
+
+\bibliographystyle{alpha}
+\bibliography{biblio}
+\include{Bibliographie}
+
+
+\end{document}
diff --git a/pbnum.tex b/pbnum.tex
new file mode 100644
index 0000000..58b3a0a
--- /dev/null
+++ b/pbnum.tex
@@ -0,0 +1,327 @@
+Ce chapitre s'inspire de~\cite{jedrzejewski2005introduction} et 
+de~\cite{bastien2003introduction}. 
+On y pointe quelques erreurs classiques en calcul numérique.
+
+On peut classer les erreurs en plusieurs groupes:
+\begin{itemize}
+\item les erreurs de calcul en machine: elles sont dues aux arrondis de 
+  calcul pour les nombres flottants, par exemple.
+\item les erreurs de méthode: elles sont dues à l'algorithme utilisé.
+  Par exemple, approximation d'une somme infinie par une somme finie, 
+  d'une limite d'une suite par un terme de grand indice, 
+  d'une intégrale par une somme finie.
+\item les erreurs sur les données (imprécision des mesures physiques, 
+  résultats d'un calcul approché). Ces données ne peuvent pas être modifiées, 
+  mais on peut étudier l'influence de ces erreurs sur le résultat final.
+\end{itemize}
+
+
+
+
+ 
+% \section{Représentation} 
+% \begin{Def}[Nombres en base $\Beta$}
+% Soit $\Beta$ un nombre entierstrictement supérieur à 1. 
+% pour tout entier $n$ supérieur ou égal à 1, 
+% il existe un unique entier $p$ et 
+% des entiers  $d_i$ ($0 \le i \le p$) tous compris entre 0 
+% et $\Beta -1$ avec $d_p \neq 0$ tels que
+% $$ n = \Sum_{i=0}^p d_i \Beta^1.$$
+% Lemembre de droite est la représentation de $n$ en base 
+% $\Beta$
+
+\section{Erreurs de calcul en machine sur les entiers}
+
+
+On donne à la figure~\ref{script:facto:java} les codes java et python 
+permettant d'évaluer la fonction factorielle.
+
+\lstset{language=Java}
+\begin{figure}
+\begin{scriptsize}
+\begin{minipage}{0.68\textwidth}
+\begin{lstlisting}
+ class TestFactorielle{    
+   public static int  factorielle(int n){
+     int r = 1;
+     for (int i=2; i<=n ; i++){
+       r = r * i;}
+     return r;}
+
+   public static void main(String args[]){
+     for (int j=1; j< 36; j++){
+       System.out.println(j+' '+
+                          factorielle(j));
+     }}}
+\end{lstlisting}
+\end{minipage}
+\begin{minipage}{0.30\textwidth}
+\lstset{language=Python}
+\begin{lstlisting}
+def factorielle(n):
+  r=1
+  i=2
+  while i<=n :
+    r=r*i
+    i+=1
+    return r
+
+for j in range(36):
+    print j, factorielle(j)
+\end{lstlisting}
+\end{minipage}
+\end{scriptsize}
+\caption{Factorielle en Java, en Python}\label{script:facto:java}
+\end{figure}
+
+En Java, on a:
+\begin{eqnarray*}
+5!&=& 120\\
+& \vdots&\\
+12! &= & 479001600 \\
+13! &=& 1932053504 \\
+& \vdots&\\
+15! &=& 2004310016\\
+16! &=&2004189184\\
+17! &=&-288522240\\
+ &\vdots&\\
+34! & = & 0 \\
+35! & = & 0 
+\end{eqnarray*}
+
+On remarque que 
+\begin{itemize}
+\item le résultat donné pour 13! est différent de 13 fois le résultat de 12!
+\item le résultat donné pour 16! est plus petit que celui donné pour 15!
+\item le résultat donné pour 17! est négatif
+\item tous les résultats donnés à partir de 34! sont nuls!
+\end{itemize}
+
+Par contre en Python 2.7 on a des résultats cohérents:
+\begin{eqnarray*}
+12! &= &479001600\\
+13! & =& 6227020800\\
+& \vdots & \\
+17! &=& 355687428096000\\
+ & \vdots & \\
+34!&=& 295232799039604140847618609643520000000 \\
+35! & =&10333147966386144929666651337523200000000
+\end{eqnarray*}
+
+Les deux langages travaillent pourtant avec des entiers et ne sont donc pas 
+exposés aux erreurs d'arrondis.
+
+Expliquons l'erreur d'interprétation du langage java. 
+Celui-ci code chaque entier avec 32 bits. 
+Le bit le plus à gauche est celui de signe. Il reste donc 31 bits.
+Cela permet de couvrir tous les entiers de l'intervalle
+$\llbracket -2147483648, 2147483647, \rrbracket$. Le tableau donné à la 
+figure~\ref{table:codage:entiers} donne la correspondance entre 
+certains entiers et le version binaire. 
+
+
+\begin{table}
+\centering{
+\begin{scriptsize}
+$$
+\begin{array}{|r|r|r|r|r|}
+\hline
+-2147483648&-2147483647&\ldots&-2&-1 \\
+
+\hline
+100\ldots000&100\ldots001&\ldots&111\ldots110&111\ldots111\\
+\hline
+\hline
+0&1&2&\ldots&2147483647\\
+\hline
+000\ldots000&000\ldots001&000\ldots010&\ldots&011\ldots111\\
+\hline
+\end{array}
+$$
+\end{scriptsize}}
+\caption{Correspondance décimaux-binaires}\label{table:codage:entiers}
+\end{table}
+
+
+Multiplier par un facteur revient à effectuer des opérations sur les bits.
+Tant que le résultat est inférieur à la valeur maximale des entiers, 
+tout se passe bien. 
+Par contre dès que le résultat est supérieur, l'interpréteur 
+fait n'importe quoi. C'est le cas à partir de 13!.
+De plus lorsqu'on a dépassé les capacités, on peut ateindre 0 sans que cela ait 
+du sens (comme à partir de 34!)
+
+Si le langage python réussit (au moins à partir de 2.7),
+c'est parce qu'il stocke les entiers
+sous 64 bits et les convertit en long si besoin, dont le nombre de bits 
+n'est pas borné. 
+Python 3, dont le type int équivaut au long de la version 2.7 n'a pas un 
+nombre borné de bits pour les entiers. Il ne faillit pas dans ce calcul.
+
+
+\section{Erreurs de calcul en machine sur les flottants}
+
+Un ordinateur  représente chaque nombre réel sur
+un nombre fini de bits. 
+Ceci  ne permet la représentation exacte que d'un petit sous-ensemble des réels.
+La plupart des calculs sur les réels conduisent ainsi à des résultats approchés
+qui résultent de la discrétisation de la représentation.
+
+
+Le tableau~\ref{table:xpl:flottants} donne 
+des exemples de nombres réels et leur représentation 
+par des flottants en java et en python.
+
+\begin{table}
+\centering{
+\begin{scriptsize}
+\begin{tabular}{|l|l|l|l|}
+\hline
+Nombre & Représentation	& Valeur approchée &	Erreur \\
+\hline
+$\frac{1}{7}$	& $0,\overline{142 857}\ldots$	& 0.14285714285714285 &	$7.10^{-18}+\frac{10^{-19}}{7}$ \\
+\hline 
+$\ln 2$	&     0.693147180559945309417232121458\ldots &  0.6931471805599453  & $\approx 10^{-17}$ \\
+\hline 
+$\sqrt{2}$ &  1.414213562373095048801688724209\ldots & 1.4142135623730951 & $ >  10^{-17}$ \\
+\hline 
+$\pi$ &       3.141592653589793238462643383279\ldots& 3.141592653589793& $ >  10^{-17}$ \\
+\hline 
+\end{tabular}
+\end{scriptsize}
+}\caption{Interprétation erronée de nombres réels particuliers}\label{table:xpl:flottants}
+\end{table}
+
+On constate que les deux langages utilisent 64 bits dont 1 pour le signe, 
+53 pour le contenu et 11 pour l'exposant de la puissance de 10. Ils peuvent
+donc mémoriser au plus 17 chiffres significatifs. 
+
+
+
+\section{Adaptation de la méthode pour contourner 
+les approximations }
+
+\begin{Exo}
+Soit l'équation $x^2 +bx +c = 0$ avec $b$ et $c$ strictement positifs.
+On suppose que le discriminant $\Delta$ est strictement positif et proche 
+numériquement de $b^2$.
+\begin{enumerate}
+\item Exprimer les deux racines $x_1$ et $x_2$ ($x_1 < x_2$).
+\item Que dire du signe du numérateur de $x_2$ en théorie? 
+\item En pratique quelle va être sa valeur si l'interpréteur fait des 
+  approximations. 
+\item Cette erreur d'arrondi est-elle effectuée dans le calcul de $x_1$?
+\item Montrer qu'on pourrait calculer la racine $x_2$ avec $x_2= \frac{c}{x_2}$.
+\item Cette nouvelle méthode permet-elle de trouver le signe de $x_2$, et 
+est-elle plus précise?
+\end{enumerate}   
+\end{Exo}
+
+\begin{TP}
+Soit l'équation $x^2+1.5.10^{9}x +1 = 0$. Donner une réponse pratique  
+aux questions précédentes en effectuant les calculs en java.
+\end{TP}
+
+
+
+\section{Erreurs sur les données}
+
+Les données provenant de mesures physiques sont souvent entachées d'erreurs.
+Par exemple, un traceur GPS ne peut avoir une précision inférieure à 8m 
+
+
+\begin{Def}[conditionnement]
+Soit $A$ une matrice inversible. Le  \emph{conditionnement} de $A$, noté 
+$\textit{cond}(A)$ est défini par 
+$$ 
+\textit{cond}(A) = ||A||~||A^{-1}||.
+$$
+Une matrice $A$ est dite bien conditionnée si son conditionnement 
+$\textit{cond}(A)$ est proche de 1.
+\end{Def}
+
+
+
+\begin{TP}
+On considère les matrices 
+$$ A = \left( 
+\begin{array}{llll}
+4 & 1 & 0 & 0 \\
+1 & 4 & 1 & 0 \\
+0 & 1 & 4 & 1 \\
+0 & 0 & 1 & 4 \\
+\end{array}
+\right) ,
+A' = \left( 
+\begin{array}{llll}
+4 & 1 & 0,1 & 0,2 \\
+1,08 & 4,04 & 1 & 0 \\
+0 & 0,98 & 3,89 & 1 \\
+-0,01 & -0,01 & 1 & 3,98 \\
+\end{array}
+\right) , 
+B = \left(
+\begin{array}{l}
+5 \\
+6 \\
+6 \\
+5 \\
+\end{array}
+\right) \textrm{ et } 
+B' = \left(
+\begin{array}{l}
+5,1 \\
+5,9 \\
+6,1 \\
+4,9 \\
+\end{array}
+\right).  
+$$ 
+
+\begin{enumerate}
+\item Que dire de $A$ et $A'$, $B$ et $B'$.
+\item Résoudre à l'aide de numpy le système $AX_1=B$.
+\item Résoudre à l'aide de numpy le système $AX_2=B'$.
+\item Résoudre à l'aide de numpy le système $A'X_3=B$.
+\item Que dire des différents vecteurs $X_1$, $X_2$ et $X_3$?
+\item Calculer le conditionnement de $A$.
+\item Reprendre les questions précédentes avec 
+ 
+$$ A = \left( 
+\begin{array}{llll}
+10 & 7 & 8 & 7 \\
+7 & 5 & 6 & 5 \\
+8 & 6 & 10 & 9 \\
+7 & 5 & 9 & 10 \\
+\end{array}
+\right) ,
+A' = \left( 
+\begin{array}{llll}
+10 & 7 & 8,1 & 7,2 \\
+7,08 & 5,04 & 6 & 5 \\
+8 & 5,98 & 9,98 & 9 \\
+6,99 & 4,99 & 9 & 9,98 \\
+\end{array}
+\right) , 
+B = \left(
+\begin{array}{l}
+32 \\
+23 \\
+33 \\
+31 \\
+\end{array}
+\right) \textrm{ et } 
+B' = \left( 
+\begin{array}{l}
+32,1 \\
+22,9 \\
+33,1 \\
+30,9 \\
+\end{array}
+\right)  
+$$ 
+\item Que peut-on en conclure?
+\end{enumerate}
+
+\end{TP}
+
diff --git a/tps/chap1/ErreurFlottant.class b/tps/chap1/ErreurFlottant.class
new file mode 100644
index 0000000..98870fc
Binary files /dev/null and b/tps/chap1/ErreurFlottant.class differ
diff --git a/tps/chap1/tpFlotant.java b/tps/chap1/tpFlotant.java
new file mode 100644
index 0000000..c1064b5
--- /dev/null
+++ b/tps/chap1/tpFlotant.java
@@ -0,0 +1,20 @@
+
+
+class ErreurFlottant{
+    
+
+    public static void main(String args[]){
+	String nombres[] ={"1/7","Math.log(2)","Math.log10(2)","Math.sqrt(2)","Math.pow(2,1.0/3),Math.pi"};
+	System.out.println("1/7 &"+ 1.0/7+ "&" + (1.0/7 -0.14285714285714285)); 
+	System.out.println("ln(2) &"+ Math.log(2)+ "&" + (Math.log(2)-0.6931471805599453));
+	System.out.println("log(2) &"+ Math.log10(2)+ "&" + (Math.log10(2)-0.3010299956639812)); 			   
+	System.out.println("sqrt(2) &"+ Math.sqrt(2)+ "&" + (Math.sqrt(2)-1.4142135623730951)); 			   
+	System.out.println("3\\/-2 &"+ Math.pow(2,1.0/3)+ "&" + (Math.pow(2,1.0/3)-1.2599210498948732)); 			   
+	System.out.println("pi &"+ Math.PI+ "&" + (Math.PI-3.141592653589793)); 			   
+	
+    }
+}
+                   
+
+
+
diff --git a/tps/chap1/tpFlotant.java~ b/tps/chap1/tpFlotant.java~
new file mode 100644
index 0000000..19371de
--- /dev/null
+++ b/tps/chap1/tpFlotant.java~
@@ -0,0 +1,13 @@
+
+class TestUnSeptieme{
+    
+
+    public static void main(String args[]){
+	System.out.println(1E6*1/(float)7 -1/(float)7);
+	
+    }
+}
+                   
+
+
+
diff --git a/tps/chap1/tpapprox.py b/tps/chap1/tpapprox.py
new file mode 100644
index 0000000..c659d5b
--- /dev/null
+++ b/tps/chap1/tpapprox.py
@@ -0,0 +1,21 @@
+from math import *
+
+
+b= 160
+c= 1 
+delta = 160*160 - 4
+sqdelta = sqrt(delta)
+s_sqd = str(sqdelta)
+
+x1_approx = (-b-float(s_sqd))/2
+x1_exact = (-b-sqdelta)/2
+
+x2_approx = (-b+float(s_sqd))/2
+x2_exact = (-b+sqdelta)/2
+
+x2p_exact = c/x1_exact
+x2p_approx = c/x1_exact
+
+print x1_exact,x1_approx,x2_exact,x2_approx,x2p_exact,x2p_approx
+
+
diff --git a/tps/chap1/tpcond.py b/tps/chap1/tpcond.py
new file mode 100644
index 0000000..286d4c3
--- /dev/null
+++ b/tps/chap1/tpcond.py
@@ -0,0 +1,27 @@
+import numpy as np
+
+A = np.array([[4,1,0,0],[1,4,1,0],[0,1,4,1],[0,0,1,4]])
+Ap = np.array([[4,1,0.1,0.2],[1.08,4.04,1,0],[0,0.98,3.89,1],[-0.1,-0.1,1,3.98]])
+B = np.array([[5],[6],[6],[5]])
+Bp = np.array([[5.1],[5.9],[6.1],[4.9]])
+
+X1 = np.linalg.solve(A,B)
+X2 = np.linalg.solve(A,Bp)
+X3 = np.linalg.solve(Ap,B)
+
+print X1,X2,X3
+print np.linalg.cond(A)
+
+
+A = np.array([[10,7,8,7],[7,5,6,5],[8,6,10,9],[7,5,9,10]])
+Ap = np.array([[10,7,8.1,7.2],[7.08,5.04,6,5],[8,5.98,9.98,9],[6.99,4.99,9,9.98]])
+
+B = np.array([[32],[23],[33],[31]])
+B = np.array([[32.1],[22.9],[33.1],[30.9]])
+
+X1 = np.linalg.solve(A,B)
+X2 = np.linalg.solve(A,Bp)
+X3 = np.linalg.solve(Ap,B)
+
+print X1,X2,X3
+print np.linalg.cond(A)
diff --git a/tps/chap1/tpequa.py b/tps/chap1/tpequa.py
new file mode 100644
index 0000000..a4dbe70
--- /dev/null
+++ b/tps/chap1/tpequa.py
@@ -0,0 +1,19 @@
+from math import * 
+
+
+a = input("valeur de a : ") 
+b = input("valeur de b : ") 
+c = input("valeur de c : ") 
+
+delta = b**2 - 4*a*c
+print "delta :", delta, "b^2 :",b**2
+
+if (delta>= 0) :
+    x1 = float((-b - sqrt(delta)))/(2*a)
+    x2 = float((-b + sqrt(delta)))/(2*a)
+    print "numerateur de x2", -b + sqrt(delta)
+    x2b = 1/float(x1)
+    print "x1 :",x1,", x2 : ",x2,",x2 bis : ", x2b
+
+
+
diff --git a/tps/chap1/tpfacto.java b/tps/chap1/tpfacto.java
new file mode 100644
index 0000000..c93341b
--- /dev/null
+++ b/tps/chap1/tpfacto.java
@@ -0,0 +1,21 @@
+
+class TestFactorielle{
+    
+    public static int  factorielle(int n){
+	int r = 1;
+	for (int i = 2; i <= n ; i ++){
+	    r = r * i;
+	}
+	return r;
+    }
+
+    public static void main(String args[]){
+	for (int j=1; j< 36 ; j++){
+	    System.out.println(""+j+"!="+factorielle(j));
+	}
+    }
+}
+                   
+
+
+
diff --git a/tps/chap1/tpfacto.py b/tps/chap1/tpfacto.py
new file mode 100644
index 0000000..67d27ea
--- /dev/null
+++ b/tps/chap1/tpfacto.py
@@ -0,0 +1,20 @@
+from math import * 
+
+
+def factorielle(n):
+    r = 1
+    i = 2
+    while i <= n :
+        r = r * i
+        i +=1
+    return r
+
+
+for j in range(2,100):
+    k = factorielle(j)
+    #print (str(j) +" "+ str(k) )
+    print (str(j) +" "+ str(k) +" "+ str(type(k))+" "+str(log(k,2)))
+                   
+
+
+
diff --git a/tps/chap2/diff_div.py b/tps/chap2/diff_div.py
new file mode 100644
index 0000000..8ac41e3
--- /dev/null
+++ b/tps/chap2/diff_div.py
@@ -0,0 +1,109 @@
+import matplotlib.pyplot as plt
+import numpy as np
+from math import *
+
+
+def coeffs(X,Y):
+    n = len(X)-1
+    diff_div=[[0 for _ in xrange(n+1)] for _ in xrange(n+1)]
+    for i in xrange(n+1):
+        diff_div[i][0] = Y[i]
+    for j in xrange(1,n+1):
+        for i in xrange(n-j+1):
+            r = float(diff_div[i+1][j-1]-diff_div[i][j-1])/(X[i+j]-X[i])
+            diff_div[i][j] = r
+    print diff_div
+    return diff_div[0]
+
+
+
+
+def prod(list):
+    r = 1
+    for x in list:
+        r *= x
+    return r
+
+
+def construit_et_eval_pol(X,Y,x):
+    d = coeffs(X,Y)
+    n = len(X)-1
+    return sum([d[i]*prod([x - X[j] for j in xrange(i)]) for i in xrange(n+1)])
+
+
+
+def construit_pol(X,Y):
+    d = coeffs(X,Y)
+    n = len(X)-1
+    return lambda x : \
+        sum([d[i]*prod([x - X[j] for j in xrange(i)]) for i in xrange(n+1)])
+
+
+
+
+"""
+
+print "tp 2.1....."
+X = [10,25,60]
+XX= [15,40,100]
+Y = [2.3, 8, 24.6]
+p = construit_pol(X,Y)
+Yp =[p(x) for x in XX]
+Ypp = [construit_et_eval_pol(X,Y,x) for x in XX]
+
+print Yp, Ypp
+
+
+x=np.linspace(10,100,100)
+plt.plot(x,p(x))  
+plt.ylabel('temps d\'execution')
+plt.xlabel("taille des donnees")
+plt.show()
+
+
+
+
+
+print p(15)
+print p(40)
+print p(100)
+
+
+"""
+
+
+
+print "tp 2.2....."
+X1 = [-1+0.25*i for i in xrange(9)]
+Y1 = [e**x for x in X1]
+p1 = construit_pol(X1,Y1)
+
+
+X2 = [cos(pi/2*(float(2*i+1)/9)) for i in xrange(9)]
+Y2 = [e**x for x in X2]
+p2 = construit_pol(X2,Y2)
+
+
+
+e1 = lambda x : abs(p1(x) - e**x)
+e2 = lambda x : abs(p2(x) - e**x)
+
+
+l1 = [e1(-1 + 0.001*i) for i in range(2001)]
+l2 = [e2(-1 + 0.001*i) for i in range(2001)]
+
+average = lambda l : sum(l)/len(l)
+
+print "l1", max(l1), average(l1)
+print "l2", max(l2), average(l2)
+
+
+x=np.linspace(-1,1,1000)
+plt.plot(x,e1(x))  
+plt.plot(x,e2(x))  
+
+plt.ylabel('exp')
+plt.xlabel("x")
+plt.show()
+
+
diff --git a/tps/chap2/diff_div.py~ b/tps/chap2/diff_div.py~
new file mode 100644
index 0000000..41634b1
--- /dev/null
+++ b/tps/chap2/diff_div.py~
@@ -0,0 +1,79 @@
+import matplotlib.pyplot as plt
+import numpy as np
+from math import *
+
+
+def coeffs(X,Y):
+    n = len(X)-1
+    diff_div=[[0 for _ in xrange(n+1)] for _ in xrange(n+1)]
+    for i in xrange(n+1):
+        diff_div[i][0] = Y[i]
+    for j in xrange(1,n+1):
+        for i in xrange(n-j+1):
+            r = float(diff_div[i+1][j-1]-diff_div[i][j-1])/(X[i+j]-X[i])
+            diff_div[i][j] = r
+    print diff_div
+    return diff_div[0]
+
+
+print "TP 2.1 ............"
+
+
+def forloop(list):
+    r = 1
+    for x in list:
+        r *= x
+    return r
+
+
+def construit_pol(X,Y):
+    d = coeffs(X,Y)
+    n = len(X)-1
+    return lambda x : sum([d[i]*forloop([x - X[j] for j in xrange(i)]) for i in xrange(n+1)])
+
+
+"""
+print "tp 2.1....."
+X = [10,25,60]
+Y = [2.3, 8, 24.6]
+p = construit_pol(X,Y)
+Yp =[p(x) for x in X]
+
+print p(15)
+print p(40)
+print p(100)
+
+
+x=np.linspace(10,100,100)
+plt.plot(x,p(x))  
+plt.ylabel('temps d\'execution')
+plt.xlabel("taille des donnees")
+plt.show()
+
+
+
+"""
+
+print "tp 2.2....."
+X1 = [-1+0.25*i for i in xrange(9)]
+Y1 = [e**x for x in X1]
+p1 = construit_pol(X1,Y1)
+
+
+X2 = [cos(pi/2*(float(2*i+1)/9)) for i in xrange(9)]
+Y2 = [e**x for x in X2]
+p2 = construit_pol(X2,Y2)
+
+
+
+e1 = lambda x : abs(p1(x) - e**x)
+e2 = lambda x : abs(p2(x) - e**x)
+x=np.linspace(-1,1,1000)
+
+plt.plot(x,e1(x))  
+plt.plot(x,e2(x))  
+
+plt.ylabel('exp')
+plt.xlabel("x")
+plt.show()
+
diff --git a/tps/chap3/jjm.py b/tps/chap3/jjm.py
new file mode 100644
index 0000000..d5b4e98
--- /dev/null
+++ b/tps/chap3/jjm.py
@@ -0,0 +1,52 @@
+from math import *
+
+def f(x):
+    return cos(x)-x
+
+
+def iteration_lagrange(x0, q0, m, epsilon, f):
+    def maj_test(xn,xnm1):
+        return f(xn)!=0 and abs(xn-xnm1)>epsilon
+
+    n=0
+    test=f(x0)!=0
+    X=[x0]
+    xnm1=x0
+    xn=float(x0-f(x0))/q0
+    qn=q0
+    print(xn,q0)
+    while n<=m and test:
+        qn=float((f(xn)-f(xnm1)))/(xn-xnm1)
+        xnm1=xn
+        xn=xnm1-f(xnm1)/qn
+
+        X+=[xn]
+        test=maj_test(xn,xnm1)
+        n+=1
+    return (n,X)
+
+print(iteration_lagrange(pi/4,1,200,0.0000001,f))
+
+
+def iteration_lagrange(x0, x1, m, epsilon, f):
+    def maj_test(xn,xnm1):
+        return f(xn)!=0 and abs(xn-xnm1)>epsilon
+
+    n=2
+    test=f(x0)!=0
+    X=[x0,x1]
+    xnm1=x0
+    xn=x1
+    while n<=m and test:
+        qn=float((f(xn)-f(xnm1)))/(xn-xnm1)
+        xnm1=xn
+        xn=xnm1-f(xnm1)/qn
+
+        X+=[xn]
+        test=maj_test(xn,xnm1)
+        n+=1
+    return (n,X)
+
+
+
+print(iteration_lagrange(0,pi/4,200,0.0000001,f))
diff --git a/tps/chap3/jjm.py~ b/tps/chap3/jjm.py~
new file mode 100644
index 0000000..da9ef8b
--- /dev/null
+++ b/tps/chap3/jjm.py~
@@ -0,0 +1,23 @@
+def iteration_lagrange(x0, q0, m, epsilon, f):
+    def maj_test(xn,xnm1):
+        return f(xn)!=0 and abs(xn-xnm1)>epsilon
+
+    n=0
+    test=f(x0)!=0
+    X=[x0]
+    xnm1=x0
+    xn=float(x0-f(x0))/q0
+    qn=q0
+    print(xn,q0)
+    while n<=m and test:
+        qn=float((f(xn)-f(xnm1)))/(xn-xnm1)
+        xnm1=xn
+        xn=xnm1-f(xnm1)/qn
+
+        X+=[xn]
+        test=maj_test(xn,xnm1)
+        n+=1
+    return (n,X)
+
+////////////////////////////////////////////////////////////////////////////
+print(iteration_lagrange(pi/4,1,200,0.0000001,f))
diff --git a/tps/chap3/methodes.py b/tps/chap3/methodes.py
new file mode 100644
index 0000000..8ae3b71
--- /dev/null
+++ b/tps/chap3/methodes.py
@@ -0,0 +1,161 @@
+import matplotlib.pyplot as plt
+import numpy as np
+from math import *
+
+
+
+
+
+def f(x):
+    return cos(x)-x
+
+def fp(x):
+    return -sin(x)-1
+
+
+
+
+def  iteration_dichotomie(a,b,m,epsilon,f):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    xnm1 = a 
+    xn= a
+    X=[]
+    n = 1
+    an= a
+    bn=b
+    test = True
+    while n <= m and test:
+        xnm1 = xn
+        xn=float(an+bn)/2
+        test = maj_test(xn,xnm1)
+        X +=[xn]
+        if f(an)*f(xn)<=0 : 
+            bn=xn
+        else :
+            an=xn
+        n +=1
+    return (n,X)
+
+def  iteration_newton(x0,m,epsilon,f,fp):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    n=0;
+    test= f(x0) != 0
+    xn=x0
+    X=[x0]
+    while n < m and test:
+        qn=fp(xn)
+        xnm1=xn
+        xn= xn-f(xn)/qn
+        X += [xn]
+        n=n+1
+        test= maj_test(xn,xnm1)
+
+#f(x) !=0 and n<m  and abs(x-xm1)>epsilon
+    return (n,X)
+
+
+def  iteration_corde(a,b,x0,m,epsilon,f):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    n=0;
+    q=float(f(b)-f(a))/(b-a)
+    test= f(x0) != 0
+    xn=x0
+    X=[x0]
+    while n < m and test:
+        xnm1=xn
+        xn= xn-f(xn)/q
+        X += [xn]
+        n=n+1
+        test= maj_test(xn,xnm1)
+
+#f(x) !=0 and n<m  and abs(x-xm1)>epsilon
+    return (n,X)
+
+"""def  iteration_newton(x0,m,epsilon,f,fp):
+    n=0;
+    delta=float(1)/fp(x0)
+    test= f(x0) != 0
+    x=x0
+    X=[x0]
+    while(test):
+        xm1=x
+        x= x-delta*f(x)
+        delta=float(1)/fp(x)
+        X += [x]
+        n=n+1
+        test= not (f(x)==0 or n>=m  or abs(x-xm1)<=epsilon)
+    return (n,X)
+"""
+
+def  iteration_lagrange(x0,x1,m,epsilon,f):
+    n=0;
+    delta=float(x1-x0)/(f(x1)-f(x0))
+    test= f(x0) != 0
+    x=x1
+    X=[x1]
+    while(test):
+        xm1=x
+        x= x-delta*f(x)
+        delta=float(x-xm1)/(f(x)-f(xm1))
+        X += [x]
+        n=n+1
+        test= not (f(x)==0 or n>=m  or abs(x-xm1)<=epsilon)
+    return (n,X)
+
+def  iteration_muller(x0,x1,x2,m,epsilon,f):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    n=0;
+    test= f(x2) != 0
+    xn=x2
+    xnm1 = x1
+    xnm2 = x0
+    X=[x0,x1]
+    while n < m and test:
+        # calcul des coefs an, bn et cn 
+        an = float(f(xn))/((xn-xnm1)*(xn-xnm2))+float(f(xnm1))/((xnm1-xn)*(xnm1-xnm2))+float(f(xnm2))/((xnm2-xn)*(xnm2-xnm1))
+        bn = -float(f(xn)*(xnm1+xnm2))/((xn-xnm1)*(xn-xnm2))-float(f(xnm1)*(xn+xnm2))/((xnm1-xn)*(xnm1-xnm2))-float(f(xnm2)*(xn+xnm1))/((xnm2-xn)*(xnm2-xnm1))
+        cn = float(f(xn)*xnm1*xnm2)/((xn-xnm1)*(xn-xnm2))+float(f(xnm1)*xn*xnm2)/((xnm1-xn)*(xnm1-xnm2))+float(f(xnm2)*xn*xnm1)/((xnm2-xn)*(xnm2-xnm1))
+
+        dn = bn*bn - 4*an*cn
+        xnp = float(-bn - sqrt(dn))/(2*an)        
+        xnpp = float(-bn + sqrt(dn))/(2*an)        
+        xnp1 = xnp if abs(xnp-xn)<abs(xnpp-xn) else xnpp
+        X += [xn]
+        xnm2 = xnm1
+        xnm1 = xn
+        xn = xnp1
+        test= maj_test(xn,xnm1)
+        n +=1
+#f(x) !=0 and n<m  and abs(x-xm1)>epsilon
+    return (n,X)
+
+
+
+
+def main():
+    print "TP 3.1 ............ dichotomie"
+    print iteration_dichotomie(0,pi/2,200,0.00000001,f)
+
+    
+    print "TP 3.1 ............ corde"
+    print iteration_corde(0,pi/2,0,200,0.00000001,f)
+
+
+    print "TP 3.1 ............ newton"
+    print iteration_newton(0,200,0.00000001,f,fp)
+
+
+    print "TP 3.1 ............ lagrange"
+    print iteration_lagrange(0,pi/2,200,0.00000001,f)
+
+    print "TP 3.1 ............ muller"
+    print iteration_muller(0,pi/4,pi/2,200,0.00000001,f)
+    
+
+if __name__ == '__main__':
+    main()
+
diff --git a/tps/chap3/methodes.pyc b/tps/chap3/methodes.pyc
new file mode 100644
index 0000000..29f025b
Binary files /dev/null and b/tps/chap3/methodes.pyc differ
diff --git a/tps/chap3/methodes.py~ b/tps/chap3/methodes.py~
new file mode 100644
index 0000000..c7080e2
--- /dev/null
+++ b/tps/chap3/methodes.py~
@@ -0,0 +1,128 @@
+import matplotlib.pyplot as plt
+import numpy as np
+from math import *
+
+
+
+
+
+def f(x):
+    return cos(x)-x
+
+def fp(x):
+    return -sin(x)-1
+
+
+
+
+def  iteration_dichotomie(a,b,m,epsilon,f):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    xnm1 = a 
+    xn= a
+    X=[]
+    n = 1
+    an= a
+    bn=b
+    test = True
+    while n <= m and test:
+        xnm1 = xn
+        xn=float(an+bn)/2
+        test = maj_test(xn,xnm1)
+        X +=[xn]
+        if f(an)*f(xn)<=0 : 
+            bn=xn
+        else :
+            an=xn
+        n +=1
+    return (n,X)
+
+def  iteration_newton(x0,m,epsilon,f,fp):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    n=0;
+    test= f(x0) != 0
+    xn=x0
+    X=[x0]
+    while n < m and test:
+        qn=fp(xn)
+        xnm1=xn
+        xn= xn-f(xn)/qn
+        X += [xn]
+        n=n+1
+        test= maj_test(xn,xnm1)
+
+#f(x) !=0 and n<m  and abs(x-xm1)>epsilon
+    return (n,X)
+
+
+def  iteration_corde(a,b,x0,m,epsilon,f):
+    def maj_test(xn,xnm1):
+        return f(xn) != 0 and abs(xnm1-xn) > epsilon  
+    n=0;
+    q=float(f(b)-f(a))/(b-a)
+    test= f(x0) != 0
+    xn=x0
+    X=[x0]
+    while n < m and test:
+        xnm1=xn
+        xn= xn-f(xn)/q
+        X += [xn]
+        n=n+1
+        test= maj_test(xn,xnm1)
+
+#f(x) !=0 and n<m  and abs(x-xm1)>epsilon
+    return (n,X)
+
+"""def  iteration_newton(x0,m,epsilon,f,fp):
+    n=0;
+    delta=float(1)/fp(x0)
+    test= f(x0) != 0
+    x=x0
+    X=[x0]
+    while(test):
+        xm1=x
+        x= x-delta*f(x)
+        delta=float(1)/fp(x)
+        X += [x]
+        n=n+1
+        test= not (f(x)==0 or n>=m  or abs(x-xm1)<=epsilon)
+    return (n,X)
+"""
+
+def  iteration_lagrange(x0,x1,m,epsilon,f):
+    n=0;
+    delta=float(x1-x0)/(f(x1)-f(x0))
+    test= f(x0) != 0
+    x=x1
+    X=[x1]
+    while(test):
+        xm1=x
+        x= x-delta*f(x)
+        delta=float(x-xm1)/(f(x)-f(xm1))
+        X += [x]
+        n=n+1
+        test= not (f(x)==0 or n>=m  or abs(x-xm1)<=epsilon)
+    return (n,X)
+
+
+def main():
+    print "TP 3.1 ............ dichotomie"
+    print iteration_dichotomie(0,pi/2,200,0.00000001,f)
+
+    
+    print "TP 3.1 ............ corde"
+    print iteration_corde(0,pi/2,0,200,0.00000001,f)
+
+
+    print "TP 3.1 ............ newton"
+    print iteration_newton(0,200,0.00000001,f,fp)
+
+
+    print "TP 3.1 ............ lagrange"
+    print iteration_lagrange(0,pi/2,200,0.00000001,f)
+    
+
+if __name__ == '__main__':
+    main()
+
diff --git a/tps/chap3/ordre.py b/tps/chap3/ordre.py
new file mode 100644
index 0000000..95517ff
--- /dev/null
+++ b/tps/chap3/ordre.py
@@ -0,0 +1,38 @@
+import scipy.stats as st
+import numpy as np
+from math import *
+from methodes import *
+
+
+
+
+
+def ordre_convergence(X,l=None) :
+    if l == None :
+        l=X[len(X)-1]
+        e = [abs(x-l) for x in X]
+        pts = [(log(e[j]),log(e[j+1])) for j in range(len(X)-2)]
+    else :
+        e = [abs(x-l) for x in X]
+        pts = [(log(e[j]),log(e[j+1])) for j in range(len(X)-1)]
+    slope, intercept, r_value, p_value, std_err = st.linregress(pts)
+    return slope
+
+
+
+def main():
+
+    print "TP 3.2 ............ ordre convergence corde"
+    print ordre_convergence(iteration_corde(0,pi/2,0,200,0.00000001,f)[1])
+
+
+    print "TP 3.2 ............ ordre convergence newton"
+    print ordre_convergence(iteration_newton(0,200,0.00000001,f,fp)[1])
+
+
+    print "TP 3.1 ............ ordre convergence lagrange"
+    print ordre_convergence(iteration_lagrange(0,pi/2,200,0.00000001,f)[1])
+
+
+if __name__ == '__main__':
+    main()
diff --git a/tps/chap3/texput.log b/tps/chap3/texput.log
new file mode 100644
index 0000000..b31ad14
--- /dev/null
+++ b/tps/chap3/texput.log
@@ -0,0 +1,20 @@
+This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=latex 2012.9.3)  10 OCT 2012 17:05
+entering extended mode
+ %&-line parsing enabled.
+**main.tex
+
+! Emergency stop.
+<*> main.tex
+            
+End of file on the terminal!
+
+ 
+Here is how much of TeX's memory you used:
+ 3 strings out of 495062
+ 105 string characters out of 1182645
+ 45108 words of memory out of 3000000
+ 3282 multiletter control sequences out of 15000+50000
+ 3640 words of font info for 14 fonts, out of 3000000 for 9000
+ 28 hyphenation exceptions out of 8191
+ 0i,0n,0p,1b,6s stack positions out of 5000i,500n,10000p,200000b,50000s
+No pages of output.