%  En préambule,  les  sources metapost.  Si  vous lancez  latex  sur ce  fichier,  il vous  placera
% automatiquement le fichier .mp dans le répertoire courant. 


\begin{filecontents*}{newton.mp}

verbatimtex
%&latex
\documentclass{article}
\usepackage{itek}
\usepackage[utf8]{preambule}
\usepackage[scaled]{helvet} % With " scaled " option
\usepackage{eulervm} %
\begin{document}
etex


input newcourbes;
input couleur;
%input geometriesyr16;
%input TEX;

 
beginfig( 1)


%%%%%%%%%%%%%%%%%%%%%%%
vardef fx(expr t)=
t
enddef;

vardef fy(expr t)=
                          (t-1)**2    % c'est la seule ligne à changer
enddef;
%%%%%%%%%%%%%%%%%%%%%
repere(0,0,-.5,4,-2,5,3cm,1cm);
r_axes;
%r_origine;
%r_unites;
%r_labelxy;
%quad_xy(0.2,bleu_ciel);
%quadu_xy(0.1*bleu_ciel);
%grad_x(1,1,0.4white);
%grad_y(1,1,0.4white);

draw f_courbe(fx,fy,-.5,4,100)withpen pencircle scaled 1.5bp withcolor blue;
draw f_tangente(fx,fy,2,0.05);

dotlabel.top( btex  etex, r_p(2,1) );
dotlabel.top( btex  etex, r_p(2,0) );
dotlabel.top( btex  etex, r_p(1.5,0) );
dotlabel.top( btex  etex, r_p(1,0) );
draw r_segment(2,1,2,0) dashed evenly;

drawarrow r_p(1.5,-1.5)--r_p(1.5,-0.2) withcolor .7white;

drawarrow r_p(2,-1)--r_p(2,-0.1) withcolor .7white;

drawarrow r_p(.5,1)--r_p(1,0.1) withcolor .7white;

label.bot(btex $x_1$ etex,r_p(1.5,-1.5) )withcolor .7white;
label.bot(btex $x_0$ etex,r_p(2,-1) )withcolor .7white;
label.top(btex Le zéro cherché  etex,r_p(.5,1) )withcolor .7white;
r_fin;
endfig;



end
 

\end{filecontents*}


\documentclass[10pt,landscape,svgnames]{article}
\usepackage{etex}
\usepackage[width=240mm,height=173mm]{geometry}
\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage[kpfonts,utf8,biblio]{preambule}


\usepackage{filecontents}
 \usepackage{wasysym,marvosym,keystroke}
\definecolor{0.95white}{rgb}{0.95,0.95,0.95}


% pour algorithm
\incmargin{1em}
\dontprintsemicolon
%\SetCommentSty{\small\sffamily}


\graphicspath{{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Figures/figuresTS/}}

\entete{TD \includegraphics[height=0.4cm]{maple.eps} Maple n°4}{Programmation}{PCSI 2 - Lycée Clemenceau}%g,d,b


%%% Environnement des réponses du logiciel
\DefineVerbatimEnvironment{boxedverbatim}{Verbatim}{fontsize=\small,formatcom=\color{blue},fontshape=it,gobble=2,frame=single,framesep=4mm,label=\textit{\small \textcolor{black}{Réponse du logiciel}},xleftmargin=10pt,rulecolor=\color{black}}




\newcommand\Com[1]{%
\shorthandoff{;:}\textcolor{red}{{ \ttfamily #1}}}


%%% Com avec syntaxe
\newcommand\Comsi[2]{%
\shorthandoff{;:}\textcolor{red}{{ \ttfamily #1}}(\textcolor{red}{\texttt{#2}})}





%%%%%%  Commande personnelle ou bout de code

\renewcommand{\code}[1]{\textcolor{red}{\texttt{#1}}}




\lstset{numbers=none,language=Maple,xleftmargin=10pt,%
keywordstyle=\color{red}\bfseries,basicstyle=\ttfamily\color{black},commentstyle=\normalfont\small\itshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{green!20},showstringspaces=false,stringstyle=\slshape,captionpos=b}








\begin{document}
\setlength{\parindent}{0pt}
\thispagestyle{empty}



%%%%%% TITRE{vide}{intitule chapitre : lecon, chapitre ...}{debut titre}{fin titre}{titre toc}{dessin}
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\setcounter{NumLecon}{3}
         \TITRE{}{TD  \includegraphics[height=0.7cm]{maple.eps}}{Méthodes numériques}{ de résolutions d'équations}{Méthodes numériques de résolutions d'équations}{Isaac.eps}
        


\begin{multicols}{2}


\begin{Abstract}
Vous savez résoudre de  manière formelle quelques types d'équations mais
quid de $x^7-17x^6+12x^3-7x^2+18x-37=0$~?

Nous  allons étudier  dans  ce chapitre  deux  méthodes numériques  pour
obtenir des valeurs approchées de  solutions d'équations de type le plus
quelconque possible.
\end{Abstract}



\section{Dichotomie}



\subsection{Description}

On veut résoudre une équation du type $f(x)=0$ sur un intervalle I avec 
 $f$ une fonction continue, strictement monotone et qui change
de signe sur un intervalle $[a,b]$ inclus dans I.

On sait qu'il existe une solution unique $\alpha$ à notre équation sur $[a,b]$.

Soit $m$ le centre de l'intervalle. Trois cas se rencontrent~:


\begin{itemize}
\item si $f(m)=0$ alors la vie est belle~;
\item  si $f(m)$  a  le  même signe  que  $f(a)$ alors  $\alpha\in[m,b]$
  (pourquoi~?)~;
\item si $f(m)$  a  le  même signe  que  $f(b)$ alors  $\alpha\in[a,m]$
  (pourquoi~?)~;
\end{itemize}


On  itère  ce  mécanisme   jusqu'à  obtenir  un  intervalle  d'amplitude
correspondant à la précision demandée sur $\alpha$~:~pourquoi cela suffit-il~?


On parle  de \emph{dichotomie} du grec  $\delta \iota \chi o  \tau o \mu
\iota \alpha$ qui signifie \emph{division en deux parties égales.}
 
\subsection{Algorithme impératif}

Le principe est donc le suivant~:


\begin{algorithm}[H]
\caption{dichotomie}
\Entree{\;
une fonction $f$\;
un intervalle $[a,b]$\;
une précision $p$
}\;
\Ini{
aa\aff $a$\;
bb\aff $b$\;
compteur\aff 0\tcp{on compte le nombre d'itérations}
}\;
\Deb{
\Tq{bb-aa$\se$ $p$}{
\eSi{le signe de $f((aa+bb)/2)$ est le même que le signe de $f($bb)}
    {bb\aff(aa+bb)/2}
    {aa\aff (aa+bb)/2}\;
k\aff k+1\;
}
\Retour{L'approximation de la solution et le nombre d'itérations}
 } 
\end{algorithm}

\subsection{Procédure MAPLE}


Il ne reste plus qu'à traduire ceci en MAPLE en créant une procédure \texttt{dicho:=proc(f,a,b,p)}...  Il faudra faire
attention à la commande  \texttt{evalf}~:~si la précision est inférieure
à $10^{-10}$, il peut y avoir des erreurs si on n'y prend pas garde...


Testez sur des équations et des précisions diverses. 

Par exemple quel problème résout \verb+dicho(x^2-2,1,2,30)+~?

\subsection{Version récursive}


Écrivez un algorithme récursif traduisant la dichotomie.

\section{Méthode de \textsc{Newton-Raphson}}


\subsection{Historique}


La méthode de  résolution des équations numériques que  nous allons voir
aujourd'hui a  été initiée par  Isaac \textsc{Newton} vers 1669  sur des
exmples  numériques mais la  formulation est  fastidieuse. Dix  ans plus
tard, Joseph \textsc{Raphson} met en évidence une formule de récurrence. Un
siècle  plus tard, \textsc{Mouraille}  et \textsc{Lagrange}  étudient la
convergence  des approximations successives  en fonction  des conditions
initiales  par  une  approche  géométrique.  Cinquante  ans  plus  tard,
\textsc{Fourier}  et  \textsc{Cauchy}  s'occupe  de la  rapidité  de  la
convergence. 


\subsection{Principe}

\textsc{Newton} présenta sa méthode en traitant l'équation $x^3-2x-5=0$.

Soit $f$ la fonction $x\mapsto x^3-2x-5$. 
Tracez son graphe à l'aide de MAPLE.

Il coupe l'axe des abscisses pour une valeur comprise entre 2 et 3.

On assimile la courbe à sa tangente au point d'abscisse 2.

Celle-ci a pour équation $y=(x-2)\times f'(2)+f(2)=10(x-2)-1$

Posons $x=2+\e$ alors $f(2+\e)=0\ssi \e^3+6\e^2+10\e-1=0$.

Si on  assimile la courbe à sa  tangente en 2, alors  $\e$ vérifie aussi
$0=10(2+\e-2)-1$ c'est-à-dire $\e=0,1$.

En fait, assimiler la courbe à sa tangente, c'est négliger les termes en
$\e$ d'ordre supérieur à 1 (ici $\e^3+6\e^2$).

Un approximation de la solution est donc 2,1.

On recommence ensuite  en partant de 2,1 au lieu de  2 puis on reprendra
la nouvelle valeur trouvée comme valeur de départ, etc.



% \subsection{Illustration graphique}

% L'exemple précédent correspond au graphe suivant.

  
% \begin{center}
%   \includegraphics[angle=270,width=.6\linewidth]{newtonmaple01.eps}  
%   \end{center}
  
 \subsection{La formule de récurrence}


On sent  la procédure  algorithmique poindre son  nez. Pour finir  de la
mettre  en évidence,  nous allons  formaliser la  méthode  précédente en
introduisant la suite des approximation successives.  


\begin{itemize}


\item On part d'un nombre  quelconque $x_0$~;
 \item \`a partir de $x_0$, on calcule un nouveau nombre $x_1$ de la
mani\`ere suivante (voir figure )~: on trace la tangente au graphe
de $f$ au point d'abscisse $x_0$, et on d\'etermine le point
d'intersection de cette tangente avec l'axe des abscisses. On
appelle $x_1$ l'abscisse de ce point d'intersection~;
\item et on recommence~: on calcule un nouveau
nombre $x_2$ en appliquant le proc\'ed\'e d\'ecrit au point 2 o\`u
l'on remplace $x_0$ par $x_1$~;
\item etc.
\end{itemize}


\begin{center}
  \includegraphics[width=.9\linewidth]{newton.1}
\end{center}




\`A partir de cette description graphique de
la m\'ethode de Newton, trouver la formule, notée (1), donnant $x_1$ en
fonction de $x_0$, puis $x_{n+1}$ en fonction de $x_n$.\\
Quelles hypoth\`eses doit-on faire sur $f$ et les $x_n$ pour que la
formule ait un sens~?\\

Nous n'irons pas  plus loin pour l'instant concernant  la convergence de
ces suites. Traitons l'exemple de \textsc{Newton}.


\subsection{Étude de la suite associée à l'équation $\text{x}^{\text{3}}\text{-2x-5=0}$.}


On   veut   résoudre  l'équation   $x^3-2x-5=0$   par   la  méthode   de
\textsc{Newton-Raphson} appelée  aussi méthode  de la tangente.  On note
$f$ la fonction $x\mapsto x^3-2x-5$.


\begin{enumerate}
\item  Montrez  rapidement  que  l'équation $f(x)=0$  admet  une  unique
  solution $\alpha$ sur $\bbr$. Montrez que $2<\alpha<3$.

\item Déterminez la fonction  $\f$ telle que $x_{n+1}=\f(x_n)$, la suite
  $(x_n)$ étant celle décrite au paragraphe précédent en prenant $x_0=3$.
\item Étudiez  le sens de  variation de la  fonction $\f$ puis  celui de
  $\f'$ et déduisez-en que $[\alpha,3]$  est stable par $\f$ et que $\f$
  est strictement croissante sur $[\alpha,3]$.
\item Que pouvez-vous en déduire sur la convergence de la suite $x_n$~?
\end{enumerate}


\subsection{Test d'arrêt}


Afin  de  construire  un  algorithme  donnant  une  approximation  d'une
solution    d'une    équation    numérique    par    la    méthode    de
\textsc{Newton-Raphson},   il  faudrait   déterminer  un   test  d'arrêt
c'est-à-dire savoir à partir de quel rang $n$ $|x_n-\alpha|$ restera 
inférieur à une valeur donnée.

Il suffit  de remarquer que  $f(x_n)=f(x_n)-f(\alpha)$. Nous supposerons
$f$ de classe $\CR^2$ sur un \og bon\fg{} voisinage I de $\alpha$ (ce
critère nous échappe encore à notre niveau).  Alors $f$ est en
particulier dérivable en $\alpha$ donc

$$f(x_n)=f(x_n)-f(\alpha)\sim f'(\alpha)\times(x_n-\alpha)$$

C'est-à-dire, puisque $f'(\alpha)$ est supposé non nul~:

$$x_n-\alpha\sim \frac{f(x_n)}{f'(\alpha)}$$

Or  $f$ étant de  classe $\CR^2$,  on a  $f'$ continue  et non  nulle en
$\alpha$ donc $f'(\alpha)\sim f'(x_n)$.

Finalement



$$x_n-\alpha\sim \frac{f(x_n)}{f'(x_n)}=x_n-x_{n+1}$$


Nous choisirons donc comme test d'arrêt $\left|\frac{f(x_n)}{f'(x_n)}\right|<p$
 avec $p$ la précision choisie.

Il ne reste plus qu'à écrire l'algorithme.

\subsection{Algorithme impératif}


D'abord l'algorithme~:



\begin{algorithm}[H]
\caption{\textsc{Newton-Raphson}}
\Entree{\;
fonction $f$\;
 précision $p$\;
premier terme $a0$\;
nombre maximum d'itération \tcp{Pour éviter de \og planter\fg{} MAPLE si
  on tombe sur un cas pathologique\;}
}\;
\Ini{
$fp$\aff dérivée de $f$\;
compteur\aff 0 \tcp{le compteur d'itérations}\;
$un$\aff $u0-\frac{f(u0)}{fp(u0)}$\;

}\;
\Deb{
\Tq{$\left|\frac{f(xn)}{fp(xn)}\right|$   est   plus   grand  que   la
  précision $p$ et que $k<N$}{
\Si{$fp(un)=0$}{On sort  de la  boucle avant de  diviser par zéro  et on
  explique pourquoi}
$un$\aff $un-\frac{f(un)}{fp(un)}$\;
compteur\aff compteur+1\;

}
 }

\Retour{L'approximation et la valeur du compteur} 
\end{algorithm}

\subsection{Procédure MAPLE}


Ici encore il faudra faire attention à l'utilisation de \texttt{evalf}.



Comparez ensuite avec les résultats trouvés avec la dichotomie.



\subsection{Version récursive}


Écrivez un algorithme récursif traduisant la dichotomie.



Regardez également ce qui  se passe avec l'équation $(x-1)^4=0$~:~quelle
précaution  supplémentaire  faut-il prendre~?  (La  preuve nous  échappe
encore à notre niveau).




\section{Recherche d'une racine carrée}

\subsection{\textsc{Héron} et \textsc{Newton}}


\textsc{Héron}  d'Alexandrie n'avait pas  attendu \textsc{Newton}  et le
calcul différentiel  pour trouver  une méthode permettant  de déterminer
une approximation  de la racine  carrée d'un nombre positif  puisqu'il a
vécu seize siècles avant Sir Isaac.


Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
$\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
(pourquoi~?) et vice-versa.

La    moyenne   arithmétique    de   ces    deux    approximations   est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
approximation que les deux précédentes.


Montrez  que cette  méthode  est un  cas  particulier de  la méthode  de
\textsc{Newton-Raphson} appliquée à une équation particulière.


\subsection{Influence de la première approximation}


Notons  $\e_n$ l'erreur  relative après  $n$ itérations  par  la méthode
précédente.


Alors         $\e_n=\frac{x_n-\sqrt{a}}{\sqrt{a}}$        et        donc
$x_n=\frac{1+\e_n}{\sqrt{a}}$.                                         Or
$x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$. 


Montrez qu'alors $$\e_{n+1}=\frac{\e_n^2}{2(1+\e_n)}$$

Si  on  est  trop loin  de  la  solution  au  départ, $\e_n$  n'est  pas
négligeable devant 1 et alors $\e_{n+1}$ est de l'ordre de $\e_n/2$.

Sinon, $\e_{n+1}$ est de l'ordre de $(\e_n)^2/2$.

Ainsi, si on  est loin de la solution, la convergence  est lente au départ
(puisqu'elle est linéaire)  puis elle devient d'ordre 2  (on dit qu'elle
est quadratique).



\subsection{Comment les calculatrices divisent-elles~?}


Pour  diviser $b$  par $a$,  les calculatrices  commencent  par calculer
$1/a$ en appliquant la méthode de \textsc{Newton}. Comment font-elles~?

Montrez que l'erreur relative vérifie cette fois $\e_{n+1}=\e_n^2=(1-ax_n)^2$.

Y a-t-il des valeurs de $x_0$ qui font diverger la suite $(x_n)$~?


Observez avec MAPLE ce qui se passe pour $a=10^{-10}=x_0$ et représentez
l'erreur relative en fonction du rang $n$.
\end{multicols}

\vfill

\nocite{*}
\bibliography{newt}

\end{document}