[cours-mesi.git] / equations.tex

\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}
\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{5em}
\end{minipage}
}
\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}