--- /dev/null
+@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
--- /dev/null
+\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.
--- /dev/null
+\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}
+
+
--- /dev/null
+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}
--- /dev/null
+\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}
--- /dev/null
+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}
+
--- /dev/null
+
+
+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));
+
+ }
+}
+
+
+
+
--- /dev/null
+
+class TestUnSeptieme{
+
+
+ public static void main(String args[]){
+ System.out.println(1E6*1/(float)7 -1/(float)7);
+
+ }
+}
+
+
+
+
--- /dev/null
+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
+
+
--- /dev/null
+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)
--- /dev/null
+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
+
+
+
--- /dev/null
+
+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));
+ }
+ }
+}
+
+
+
+
--- /dev/null
+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)))
+
+
+
+
--- /dev/null
+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()
+
+
--- /dev/null
+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()
+
--- /dev/null
+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))
--- /dev/null
+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))
--- /dev/null
+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()
+
--- /dev/null
+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()
+
--- /dev/null
+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()
--- /dev/null
+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.
