+\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}
+
+
