j

[cours-mesi.git] / equations.tex

diff --git a/equations.tex b/equations.tex
index 8fec68db40a8ac876ab93fea2ccb036f3a07bb59..bd10efcfa0140d3c94c7a1bb7b546b1c622068d3 100644 (file)
--- a/equations.tex
+++ b/equations.tex
@@ -1,6 +1,5 @@
 \section{Motivation}
 \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 
 est un problème difficile.
 Depuis l'antiquité, l’homme a cherché des algorithmes donnant les
 valeurs des racines d'un polynôme 


@@ -12,18 +11,17 @@ la forme
 $ 
 x^3 + px+q = 0
 $ avec $p$ et $q$ non nuls. Calculons le discriminant 
 $ 
 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{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}
 \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
 
 
 \item Si $\Delta$ est positif, l'équation possède une solution réelle


@@ -31,21 +29,21 @@ $$
 $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:
 $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}
 \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}
 
 \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
 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


@@ -83,7 +81,7 @@ 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)$.
 \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é 
 \end{itemize}
 
 A chaque itération, l'intervalle $[a_n,b_n]$ est découpé 


@@ -221,9 +219,9 @@ Dans cet exercice, on suppose en plus que:
 \begin{enumerate}
 \item Montrer que l'on a $x_{n+1} \neq x_{n}$.
 \item Montrer que (\ref{eq:num:class}) est équivalente à 
 \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}
 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 Dans la représentation graphique donnée figure~\ref{fig:graphe1}:
   \begin{enumerate}
   \item donner l'équation de la droite tracée;


@@ -234,14 +232,14 @@ x_{n+1} = x_{n} - \frac{f(x_n)}{q_n} \label{eq:num:gen}
 \end{enumerate}
 
 \item Dans la méthode de la corde, $q_n$ est constante et égale à 
 \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 
 
 \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}
 
 \item Dans la méthode de Newton on a $q_n = f'(x_n)$
 \end{enumerate}


@@ -282,6 +280,8 @@ solution $\alpha$ de cet intervalle.
 
 
 \begin{Prop}[Vitesse de convergence]
 
 
 \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, 
 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, 


@@ -310,6 +310,67 @@ fixe $g_i(x) =x$ avec
 \end{itemize}
 
 
 \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$, 
 \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$, 


@@ -358,7 +419,7 @@ 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]$;
 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}
 


@@ -376,62 +437,5 @@ proposition~\ref{th:csconv:pf}  sont suffisantes, pas nécessaires.
 \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}