X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/blobdiff_plain/f4fb6abd4d0ca7a866d0cba93347244e9797040a..HEAD:/equations.tex?ds=inline diff --git a/equations.tex b/equations.tex index 4a76973..bd10efc 100644 --- a/equations.tex +++ b/equations.tex @@ -1,6 +1,5 @@ \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 @@ -12,18 +11,17 @@ 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: +$\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 @@ -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: -$$ +$ \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 @@ -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)$. -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é @@ -179,24 +177,17 @@ l'erreur avec la limite est inférieure à cet $\epsilon$. \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} @@ -228,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{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; @@ -241,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 à -\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} @@ -289,6 +280,8 @@ solution $\alpha$ de cet intervalle. \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, @@ -317,6 +310,67 @@ fixe $g_i(x) =x$ avec \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$, @@ -365,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]$; -\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} @@ -383,62 +437,5 @@ proposition~\ref{th:csconv:pf} sont suffisantes, pas nécessaires. \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}