\section{Motivation}
-Bien qu’il puisse être posé simplement (trouver tous les $x$ tel que $P(x) =0$),
-résoudre algébriquement des équations
+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
$
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:
+$\Delta = \frac{4}{27}p^3+ q^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
$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\}.
-$$
+\textrm{ où } j=-\frac12+ i \frac{\sqrt3}2=e^{i\frac{2\pi}3}
+$
+\item sinon, l'équation a 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)}\textrm{ avec } k\in\{0,1,2\}.
+$
\end{itemize}
-Donnée à titre d'exemple, ce travail montre que rapidement on obtient
+%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
\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.
+Ce dernier est négatif d'après l'hypothèse de récurence.
\end{itemize}
A chaque itération, l'intervalle $[a_n,b_n]$ est découpé
\begin{figure}
+\centering{
+\begin{minipage}{0.5\textwidth}
+\vspace{7em}
\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}
+\vspace{5em}
+\end{minipage}
+}
\caption{Représentation graphique de méthodes itératives de construction de racine}\label{fig:graphe1}
\end{figure}
\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;
\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}
+%\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}
+%\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}
\begin{Prop}[Vitesse de convergence]
+Si la suite des itérés obtenus par dichotomie converge,
+alors la convergence est linéaire.
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,
\end{itemize}
+
+\begin{TP}[Comparaison d'approches]
+
+\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}
+
+
+
\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$,
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}]$;
+\item fonction $g_2$ de Ferrari sur $[3;\textrm{3,1}]$.
\end{enumerate}
\end{Exo}
\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}
