\documentclass{article}
\usepackage{titling}
\author{L. \textsc{Gay} d'apr\`es F. \textsc{Lemonnier}}
\include{preambule}
\include{preambuleflo}


\newboxedtheorem{defi}{Définition}{compteur1}
\newboxedtheorem{prop}{Proposition}{compteur2}
\newboxedtheorem{lem}{Lemme}{compteurLEM}
\newboxedtheorem{coro}{Corollaire}{compteur3}
\newboxedtheorem{thm}{Théorème}{}
\newboxedtheorem{ex}{Exemple}{}


\renewenvironment{proof}[1][]{{\underline{\bfseries \proofname #1 :}\\~\\ }}{\hfill $\blacksquare$\\}

\begin{document}
\renewcommand{\proofname}{Preuve}
\begin{textblock*}{3cm}(10mm,0mm) 
\includegraphics[scale=0.15]{images/newton.jpg} 
\end{textblock*} 
\begin{spacing}{2}
\setlength {\shadowsize }{2pt}
\begin{center} \shadowbox{\begin{minipage}{15cm}
\centering     \begin{huge} 
\textsc{Méthode de Newton}\end{huge}
\end{minipage}} \end{center}\end{spacing}
~\\


\underline{Référence :} \textsc{Rouvière} : Petit guide de calcul différentiel, Exercice 49 p. 152\\

Cette méthode permet de trouver des approximations d'un zéro (ou racine) d'une fonction d'une variable réelle à valeurs réelles.\\
Soit $f:[c,d]\rightarrow\mathbb{R}$ une fonction de classe $\mathcal{C}^2$ vérifiant $f(c)<0<f(d)$ et $f'(x)>0$ pour tout $x\in [c,d]$. \\
$f$ admet donc un unique zéro $a$ dans l'intervalle $]c,d[$. \\
On définit $F$ sur $[c,d]$ par \[F(x)=x-\dfrac{f(x)}{f'(x)}\]
On a ainsi $F(a)=a$. Le problème de zéro est ramené à un problème de point fixe.\\
On a $F'(x)=1-\dfrac{f'(x)^2-f(x)f''(x)}{f'(x)^2}$ et donc $F'(a)=0$.\\

\begin{thm}
Pour $x_0 \in [c,d]$, on pose tant qu'on peut $x_{n+1} = F\left(x_n\right)$\\
\begin{enumerate}
\item Il existe un intervalle $J=[a-\alpha,a+\alpha]$ stable par $F$. En prenant $x_0\in J$, la suite définie par $x_{n+1}=F(x_n)$ converge de façon quadratique (d'ordre 2) vers le point fixe $a$.
\item Si, de plus, on suppose que $f$ est convexe, on n'a plus besoin de prendre $x_0$ proche de $a$, comme le montre le résultat suivant:\\
Si $f'' > 0$ sur $[c,d]$ et $x_0>a$, alors la suite $\left(x_n\right)$ est bien définie, $\forall n \in \IN, x_n>a$.\\
      Dans ce cas, on a l'équivalent : $\dst x_{n+1}-a \underset{n \rightarrow \infty}{\sim} \frac{f''(a)}{2f'(a)} \left(x_n-a\right)^2$.
\end{enumerate}
\end{thm}

\begin{center}
\includegraphics[scale=0.20]{images/rouviere.jpg} 
\end{center}
~\\
\checkmark ~Avantages de la méthode: s'il y a convergence, celle-ci est rapide (souvent quadratique), elle nécessite un seul point de départ.\\
\checkmark ~Inconvénients de la méthode: $f$ doit être suffisamment régulière, la convergence n'est pas assurée dans tous les cas, s'il y a plusieurs racines elle ne converge par forcément vers la plus proche du point de départ.\\
~\\
\begin{proof}~
\begin{enumerate}
\item \begin{description}
\item[Étape 1 :]  (question 1) Pour $x \in [c,d]$:
\begin{align*}
F(x)-a
&=x-\dfrac{f(x)}{f'(x)}-a
\\ &= \dfrac{(x-a)f'(x)-f(x)}{f'(x)}
\end{align*}
D'après la formule de Taylor-Lagrange à l'ordre 2: \\
Il existe $z\in]a,x[$ (ou $]x,a[$) tel que: 
$$f(a)=0=f(x)+(a-x)f'(x)+\dfrac{(x-a)^2}{2}f''(z)$$ 
On en déduit :
\[F(x)-a=\dfrac{1}{2}\dfrac{f''(z)}{f'(x)}(x-a)^2 \]
\item[Étape 2 :] (question 2) On pose $C=\dfrac{\max\vert f''\vert}{2\min f'}$. Ce dernier est bien défini car $f''$ et $f'$ sont continues sur le segment $[c,d]$. On obtient $\vert F(x)-a\vert \leqslant C\vert x-a\vert ^2$ pour $x\in[c,d]$.\\
On choisit $\alpha >0$ tel que $J=[a-\alpha,a+\alpha]\subset [c,d]$ et tel que $C\alpha<1$.\\
Alors, si $x \in J$, $\abs{F(x)-a} \leqslant C \abs{x-a}^2 \leqslant C\alpha^2 < \alpha$.\\
Ainsi $F(J) \subset J$ ie $J$ est stable par $F$. \\
En prenant $x_0\in J$ on a, pour tout $n$, $x_n\in J$ et $\vert x_{n+1}-a \vert \leq C\vert x_n -a \vert ^2$.\\
D'où
$$C \abs{x_n-a} \leqslant (C\abs{x_0-a} )^{2^n} \leqslant {\underbrace{(C\alpha)}_{<1} }^{2^n} $$
 donc la convergence est d'ordre 2.
			\end{description}
			
			
			
\item (question 3)\begin{description}
\item[Étape 1 :] Pour $x\in [a,d]$, $f(x)\geq 0$ et $f'>0$.\\
Donc $F(x)=x-\dfrac{f(x)}{f'(x)} \leq x$. \\
D'autre part, $f''>0$ et la preuve de 1., avec la formule de Taylor-Lagrange, montre que $F(x)-a\geq 0$ (toujours pour $x\in [a,d]$).\\ 
Ainsi, l'intervalle $I=[a,d]$ est stable par $F$. \\
De plus, si $x_0\in]a,d]$ la suite $(x_n)_n$ est strictement décroissante. Si $x_0=a$, la suite est stationnaire.\\
Sous les conditions de l'énoncé, la suite est donc décroissante, minorée par $a$, donc converge vers une limite $l$ point fixe de $F$.\\
Donc $f(l)=0$, d'où $l=a$. La convergence vers $a$ est quadratique, comme précédemment.\\
\item[Étape 2 :] Enfin, cette inégalité est essentiellement optimale.\\
      De plus, si $x_0>a$, on a pour tout $n$, $x_n >a$ et, comme dans la preuve précédente :
\[\dfrac{x_{n+1}-a}{(x_n-a)^2}=\dfrac{1}{2}\dfrac{f''(z_n)}{f'(x_n)}\] avec $a< z_n <x_n$.\\
Comme $\dfrac{f''(z_n)}{f'(x_n)}\longrightarrow \dfrac{f''(a)}{f'(a)}$ ($z_n$ est ``coincé" donc converge + continuité de $f'$ et $f''$), on obtient l'équivalent souhaité.
\end{description}
\end{enumerate}
\end{proof}

\begin{ex}
(Rouvière fin de l'exo)Soit $y \in \IR^{+*}$ ; imaginons qu'on veuille estimer $a = \sqrt{y}$. Soit $f : x \mapsto x^2-y$, définie sur un intervalle $[c,d]$, avec $0 < c < d$ et $c^2 < y < d^2$. Pour approcher $a$, on doit itérer la fonction $\dst F(x) = x - \frac{x^2-y}{2x}$.\\
On a alors : $\dst F(x) - a = \frac{(x-a)^2}{2x}$ et $\dst F(x) + a = \frac{(x+a)^2}{2x}$.\\
Donc, en prenant $x_0 \in ]a,d]$ et en posant $x_n = F^n\left(x_0\right)$, on obtient : $\dst \frac{x_n+a}{x_n-a} = \left(\frac{x_0+a}{x_0-a}\right)^{2^n}$.\\
Par conséquent : $\dst 1 + \frac{2a}{x_n-a} = \left(1+\frac{2a}{x_0-a}\right)^{2^n} \geq 1 + \left(\frac{2a}{x_0-a}\right)^{2^n}$.\\
On obtient donc un encadrement de l'erreur : $\dst 0 < x_n-a \leq 2a \left(\frac{x_0-a}{2a}\right)^{2^n}$.
\end{ex}

\begin{ex}[Approximation du nombre d'or] 
(Rouvière pages avant)
Le nombre d'or  $\left(\frac{1+ \sqrt{5}}{2} \right)$ est un point fixe de $F(x)=\sqrt{1+x}$ sur l'intervalle stable $[0,+\infty[$ ainsi que de $G(x)=1+\dfrac{1}{x}$ sur l'intervalle stable $[\sqrt{2},1+\sqrt{2}]$.\\
On a $F'(x)=\frac12 \frac1{\sqrt{1+x}}$ et $G'(x)=-\frac1{x^2}$. \\
On sait pour ces deux fonctions qu'il y a bien convergence car $\vert F'(x)\vert \leq 1/2$ et $\vert G'(x)\vert \leq 1/2$.\\ Seulement, a priori, on sait que la convergence est linéaire mais on ne sait pas plus. (voir \textbf{Théorème} ci-dessous) \\
La méthode de Newton appliquée à $f(x)=x^2-x-1=0$ sur $[c,d]=I=[1,2]$ (qui vérifie bien les hypothèses) offre donc une convergence plus rapide directement.
\end{ex}





\begin{thm}[Méthode du point fixe et convergence]
Soient $F~:~I \rightarrow \R$, de classe $\mathcal{C}^1$ sur un intervalle ouvert $I$, et $a \in I$ un point fixe de $F$. Alors:
\begin{enumerate}[i)]
\item Point fixe attractif. \\
Si $\abs{F'(a)}<1$, il existe un intervalle fermé $J$ centré en $a$, stable par $F$ tel que pour $x_0 \in J$, la suite $x_{n+1}=F(x_n)$ converge vers le point fixe $a$.
\item Sous les conditions de i), et si $F'$ ne s'annule pas sur $J$, si $x_0 \neq a$, alors pour tout $n$, $x_n \neq a$ et 
$$ x_{n+1}-a \underset{n \rightarrow +\infty}{\sim} F'(a)(x_n -a)$$
ie convergence d'ordre 1, convergence linéaire.
\item Point fixe superattractif. \\
Sous les conditions de i), et si $F$ est de classe $\mathcal{C}^2$, si $F'(a)=0$, si $F''$ ne s'annule pas sur $J$ et si $x_0 \neq a$, alors  pour tout $n$, $x_n \neq a$ et 
$$ x_{n+1}-a \underset{n \rightarrow +\infty}{\sim} \frac{F''(a)}{2}(x_n -a)^2$$
ie convergence d'ordre 2, convergence quadratique (différent de la convergence en moyenne quadratique).
\item Point fixe répulsif. \\
(Si $\abs{F'(a)}>1$, il existe un intervalle fermé $J$ centré en $a$, tel que, pour $x_0 \in J$ et $x_0 \neq a$, la suite $x_n$ sorte de $J$.)
\end{enumerate}
\end{thm}

\begin{center}
\includegraphics[scale=0.25]{images/rouviere2.jpg} 
\end{center}

\hrulefill \\
~\\
\underline{Notes:}\\
~\\
\checkmark ~\textbf{A l'oral}, on a énormément le temps. On fait l'interprétation géométrique au début, et on fait le nombre d'Or.\\
\checkmark ~Généralement, cette méthode se fait après dichotomie ou gradient à pas optimal pour avoir déjà une idée de l'intervalle où se situe le zéro.\\
\checkmark ~L'interprétation géométrique de cette méthode est assez facile. En effet, elle donne: 
$$ f(x_n)+f'(x_n)(x_{n+1}-x_n)=0$$
ce qui exprime que $x_{n+1}=F(x_n)$ est l'abscisse de l'intersection avec l'axe O$x$ de la droite $y=f(x_n)+f'(x_n)(x-x_n)$, qui est la tangente au graphe de $f$ au point d'abscisse $x_n$.\\
$\clubsuit$ Isaac \textsc{Newton} (1643 - 1727) -il est donc mort très vieux pour son époque!- est un philosophe, mathématicien, physicien, alchimiste, astronome et théologien anglais. Figure emblématique des sciences, il est surtout reconnu pour avoir fondé la mécanique classique, pour sa théorie de la gravitation universelle et la création, en concurrence avec \textsc{Leibniz}, du calcul infinitésimal, en optique, en théologie et en alchimie . 



\end{document}