%\makeindex
\documentclass{article}
\usepackage[T1]{fontenc}
\newcommand{\norme}[1]{ \left\| {#1} \right\| }
\newcommand{\tr}{\mbox{tr\,}}
\usepackage{amssymb}
\begin{document}
\begin{center}
{\Large MIAS2 TP2\\M\'ethodes it\'eratives}
\end{center}
Il s'agit d'illustrer des m\'ethodes de point fixe, en particulier la
m\'ethode de Newton.
Ces m\'ethodes permettent par exemple de r\'esoudre une \'equation
en cherchant la limite d'une suite r\'ecurrente.
On supposera que la suite $u_n$ est donn\'ee par la relation
de r\'ecurrence $u_0=a ,\ \ u_{n+1}=f(u_n)$.

Ces m\'ethodes num\'eriques peuvent aussi \^etre programm\'ees 
sur des calculatrices qui ne font pas de calcul formel.

\section{L'algorithme} \label{sec:algo}
Il faut tout d'abord traduire le programme
ci-dessous pour votre logiciel de calcul formel. Ce programme
affiche la valeur de $u_i$ si $|u_i-u_{i-1}|<eps$ ou 
''non trouve'' si $i>n$, puis d\'efinir la fonction \`a it\'erer.
\begin{verbatim}
fonction iter(f,a,n,eps)
local b,i
i:=1
repeter
  b:=a 
  a:=f(a) 
  i:=i+1
jusqua (i>n) ou (abs(b-a)<eps)
si (i>n) alors 
  afficher "non trouve" 
sinon 
  afficher a, i 
fsi
ffonction\end{verbatim}
Les param\`etres de la fonction ci-dessus sont :\\
{\tt a} qui rep\'esente  $u_0$\\
{\tt n} qui rep\'esente le nombre maximum d'it\'erations\\
{\tt eps} qui est l'\'ecart tol\'er\'e entre deux $u_i$ cons\'ecutifs.\\
En cours de programme, {\tt i} est l'indice,  {\tt b} repr\'esente 
$u_{i-1}$ et  {\tt a} repr\'esente $u_i$.

{\sc Attention :} trouver $u_i$ tel que $|u_i-u_{i-1}|<eps$ ne prouve pas  
la convergence de la suite $u_n$ (ex $u_n=\Sigma_{i=1}^n \frac{1}{i}$).
Dans certains cas, on peut montrer la convergence de la suite et
déterminer une majoration de $|u_n-l|$ en fonction de $|u_{n+1}-u_n|$
(par exemple lorsqu'on peut appliquer le théorème du point fixe)

La section \ref{sec:Erable} donne la traduction pour la HP49. 
La traduction pour d'autres calculatrices est laiss\'ee
en exercice au lecteur.

\section{Calculatrices} \label{sec:suite}
{\sc Attention} sur les calculatrices TI et Casio, on ne peut pas utiliser des 
param\`etres qui soient des fonctions.
On suppose alors que la fonction \`a it\'erer 
s'appelle $f$.
\subsection{Casio}
Touche {\tt MENU}, choisir {\tt RECUR}. Dans le bandeau, on peut 
s\'electionner avec {\tt TYPE} si on \'etudie une suite r\'ecurrente
\`a un ou deux termes. Indiquez ensuite les valeurs initiales
avec le menu {\tt RANG} du bandeau. Affichez la table des valeurs
num\'eriques de la suite, puis tracez le graphe. Si la suite
r\'ecurrente est \`a un terme, le bandeau de {\tt TABL} comporte
l'option {\tt WEB}.

\subsection{TI}
Touche {\tt MODE}, puis choisir {\tt SEQUENCE} ou {\tt Seq}
en face de {\tt GRAPH}.
Valider ce choix par {\tt ENTER}.
Ensuite ouvrir le menu {\tt Y= } et entrer la suite r\'ecurrente.
Dans le menu Axes ({\tt F7} sur la TI92) choisir {\tt WEB}. Pour
tracer l'escargot, taper sur $\diamondsuit $ {\tt GRAPH}.

\subsection{HP49} \label{sec:Erable}
Il n'existe pas d'instruction préprogrammée pour étudier les suites
récurrentes.
Pour ex\'ecuter plusieurs fois de suite une seule it\'eration :\\
En mode \verb|algebrique|\\
- on tape la valeur initiale\\
- on tape par exemple {\tt COS(ANS(1))/2 ENTER}\\
- puis   {\tt ENTER} effectue \`a nouveau la m\^eme commande donc effectue une it\'eration.\\
On peut aussi bien s\^ur d\'efinir  une fonction de la fa\c{c}on suivante :\\
On tape  \verb|DEF(F(X)=COS(X)/2)|\\
on \'ecrira alors {\tt F(ANS(1)) ENTER etc}\\

On peut \'egalement \'ecrire un programme, pour simplifier on va
supposer que la fonction \`a it\'erer est stock\'ee dans la
variable F et la tol\'erance dans la variable \verb|EPS|.
On saisit la valeur de \verb|EPS|, par exemple:\\
\verb|0.0001 STO> EPS| (\verb|STO>| s'obtient en appuyant sur la touche 
\verb|STO>|).\\
et on tape le programme suivant (pour saisir le s\'eparateur d'instruction
\verb|;| tapez simultan\'ement sur le {\tt shift-rouge} et la 
touche \verb|SPC|)
\begin{verbatim}
<< -> X N                 @ 2 arguments: u_0, nb max d'iterations
  << 0. -> I              @ variable locale compteur d'iteration
     << 
       DO
         STO+(1.,'I') ;   @ incremente le compteur d'iteration
         F(X) STO> X  ;   @ u_{i+1}=f(u_i)
       UNTIL
         ABS(F(X)-X)<EPS OR N<I  @ test d'arret
       END ;
       IF N<I THEN "Non trouve" ELSE ->TAG(X,I) END
     >>
   >>
>> -> ITER
\end{verbatim}
Pour ex\'ecuter le programme, tapez par exemple:
\verb|ITER(0.,30.)|\\
o\`u 0. est la valeur initiale de la suite et 30. est le nombre
maximal d'iterations sur la pile. Le programme renvoie $u_i$
ou affiche un message en cas de non succ\`es (plus de 30 it\'erations).\\
Voici aussi la version \verb|RPN|\footnote{Pour passer du mode alg\'ebrique 
au mode RPN et inversement, taper sur les touches {\tt MODE}, {\tt +/-}
et {\tt ENTER}} de ce programme qui est plus rapide 
et s'ex\'ecute aussi sur les HP48 (saisir le texte suivant puis entrez
les deux arguments $u_0$ et $n$ maximal puis tapez \verb|ITER|)
\begin{verbatim}
<<                       @ X N
   0. -> N I
   << 
     DO                  @ X
       1. 'I' STO+       @ X (incremente le compteur I)
       DUP F             @ X F(X)
       SWAP OVER -       @ F(X) X-F(X)
     UNTIL
       ABS EPS <         @ F(X) ?
       I N > OR
     END
     IF 
       I N > 
     THEN 
       "Non trouve" MSGBOX
     END
   >>                   @ F(X)
>> 'ITER' STO
\end{verbatim}
%\subsection{Sur TI89/92.} \label{sec:ti}
%\begin{verbatim}
%
%\end{verbatim}
\section{Avec MuPAD ou maple} \label{sec:mupad}
Pour d\'efinir la m\^eme fonction, on taperait :\\
\verb| f:= x -> cos(x)/2 |\\
Pour calculer plusieurs it\'erations, initialiser \verb|a| avec une 
valeur num\'erique, par exemple \verb|a:=0.0|, puis taper :\\
\verb|a:=f(a);|\\
puis~:
\begin{itemize}
\item (mupad sous emacs) tapez sur la fl\`eche vers le haut et \verb|ENTER|.
\item (xmaple) rééxécutez la commande (cliquez sur la ligne et \verb|ENTER|).
\end{itemize}
On peut aussi programmer plusieurs itérations avec un test d'arr\^et, 
c'est le travail demand\'e au premier exercice. 
On peut d\'efinir le nombre de chiffres significatifs avec mupad (menu 
\verb|MuPAD|, environnement puis \verb|DIGITS|) et maple (changer la
valeur de \verb|Digits|).

\section{Compl\'ement de cours}
\subsection{Th\'eor\`eme du point fixe} \label{sec:ptfixe}
Soit $f$ est une application continue de $I$ dans $I$ ($I$ d\'esigne un 
intervalle ferm\'e de $\mathbb{R}$).
Si $f$ est contractante 
($\exists k < 1,\ \forall x,\ y \in I \times I,\ |f(x)-f(y)| \leq k|x-y|$) 
alors $f$ admet un point fixe 
unique $a$ et la suite des it\'er\'ees ($u_0 \in I \ u_{n+1}=f(u_n)$) 
converge vers $a$.\\
Exemples~:
$f(x)=\cos(x)$ est contractante sur [0,1],\\ 
$\hspace*{1.8cm} f(x)=\tan(x)$ n'est pas contractante sur $[\frac{\pi}{2},\ \frac{3\pi}{2}]$ \\
Si $f$ est contractante de rapport $k$ alors on a~:
\[ |u_{n+1}-l| \leq \frac{k}{1-k} |u_{n+1}-u_n| \]

\subsection{M\'ethode de Newton}
Pour r\'esoudre l'\'equation $f(x)=0$, on it\`ere la fonction :
$\displaystyle g(x)=x-\frac{f(x)}{f'(x)}$.\\
Puisque $\displaystyle g'(x)=\frac{f(x).f''(x)}{f'(x)^2}$, 
si $a$ est un z\'ero de $f$, on a :\\
$g(a)=a$, $g'(a)=0$ et la suite des it\'er\'ees de $g$ ($u_n=g(u_{n-1})$) converge de fa\c{c}on quadratique ($|u_n-a| \leq k|u_{n-1}-a|^2$).

Cette méthode
nécessite de partir d'un point assez proche de la racine.

\subsection{Algorithme de H\'eron}
Cet algorithme, bas\'e sur la m\'ethode de Newton, permet de d\'eterminer des 
valeurs approch\'ees de racines d'entiers.\\
Exemple~: calcul de $\sqrt{b}$ ($b$ d\'esigne un r\'eel positif).\\
On pose :\\
$u_1=a$ ($a$ d\'esigne un r\'eel positif proche de $\sqrt{b}$)\\
$\displaystyle u_n=\frac{1}{2}(u_{n-1}+\frac{b}{u_{n-1}})$.\\

\subsection{Acc\'el\'eration de convergence: proc\'ed\'e d'Aitken}
Soit $S_n$ une suite convergente vers $S$, on note :\\ 
$\Delta S_n=S_{n+1 }-S_{n}$ et $\Delta ^2 S_n= \Delta S_{n+1}-\Delta S_n =S_{n+2 }-2S_{n+1}+S_{n}$.\\ 
On pose alors :\\
\[ S'_n= S_n -\frac{(\Delta S_n)^2}{\Delta ^2 S_n} \]
La suite $S'_n$ converge en g\'en\'eral plus vite que $S_n$, on peut montrer
que c'est le cas si $(S_{n+1}-S)/(S_n-S)$ converge vers une limite 
$\rho \in ]-1,1[$.

\section{Exercices} \label{sec:ex}
\begin{enumerate}
\item (à rendre lors de la 1ère séance de ce TP)\\
\'Ecrire un programme \verb|MuPAD|, \verb|maple| ou \verb|xcas|
impl\'ementant l'algorithme pr\'esent\'e en section~\ref{sec:algo}
\item (à rendre lors de la 1ère séance de ce TP)\\
Il s'agit de r\'esoudre $\cosh(x)/2=x$ sur $[0,1]$
en utilisant le th\'eor\`eme du point fixe, cf. la section \ref{sec:ptfixe}.
En utilisant un logiciel ou une calculatrice,
donnez une valeur de $n$ pour laquelle $|u_{n+1}-u_n|\leq 10^{-3}$
et en déduire un encadrement de $x$.
\item (à rendre au début du 3ème TP)\\
Résoudre $\cosh(x)=5x$ pour $x>0$
Indication: si la fonction de votre \'equation n'est pas contractante, cherchez
une \'equation \'equivalente dont la fonction est contractante (indication:
si $|f'|>1$ que peut-on dire de $|f^{-1}\,'|$ o\`u $f^{-1}$ d\'esigne
la fonction r\'eciproque de $f$?).
\item (à rendre lors de la 2ème séance de ce TP)\\
Donner une valeur de $\sqrt{5}$ \`a $10^{-5}$ pr\`es en utilisant 
l'algorithme de H\'eron. Comparez avec l'it\'eration de  
$f(x)=\frac{5x+5}{x+5}$. Justifiez dans les deux cas l'encadrement
(on pourra utiliser une méthode analogue à celle du 2ème exercice)
\item (à rendre au début du 3ème TP)\\
Rechercher par la m\'ethode de Newton une racine de $x^3+x+1$. 
\item (à rendre au début du 3ème TP)\\
On suppose que la suite $u_n$ est donn\'ee par la relation
de r\'ecurrence~:
\[ u_0=a ,\quad u_{n+1}=u_n^2+u_n-2\]
On pose $f(x)=x^2+x-2$.
\begin{itemize}
\item
D\'eterminer les points fixes $l_1$ et $l_2$ ($l_1<l_2$) de $f$ et calculer 
$f'$ en ces points.\\
Faire le graphe de $f$ en pr\'ecisant la tangente aux points fixes. \\
Montrer que si $u_0>l_2$ la suite $(u_n)$ est croissante et divergente.\\
Montrer que si  $-\frac{9}{4}<u_0<l_2$ la suite $(u_n)$ est born\'ee.\\
Montrer que quelque soit $u_0$ la suite $(u_n)$ n'est jamais convergente.\\
Comment faites-vous  pour savoir si $u_{2n}$ converge ? (d\'etailler) \\
\item
On suppose  $-\frac{9}{4}<u_0<l_2$, montrer que $(u_n)$ poss\'ede des suites 
extraites convergentes.\\
On veut trouver les limites de ces suites extraites :\\
Voici un programme MuPAD qui affiche pour chaque $u_0$ les valeurs de
$u_{101}$ \`a $u_{200}$ (pour maple, remplacer \verb|end_for| par \verb|od|
et \verb|return| par \verb|RETURN|)
\begin{verbatim}
u:=proc(u0)
  local l;
  begin
    l:=[];
    for j from 1 to 100 do
      u0:=f(u0);
    end_for;
    for j from 1 to 100 do
      u0:=f(u0);
      l:=[op(l),u0];
    end_for;
  return (l);
end_proc;
\end{verbatim}
Faire un programme qui affiche pour chaque $u_0$ les valeurs de $u_{2n}$  de
 $n=101$ \`a $n=200$ et faire un programme qui affiche pour chaque $u_0$ les 
valeurs de $u_{3n}$  de $n=101$ \`a $n=200$.
\item
Chercher les points fixes de $fofof$
(en maple on peut utiliser \verb|fsolve| et en {\tt MuPAD }
{\tt numeric::polyroots(p(x));} pour avoir les valeurs approch\'ees 
des racines d'un polyn\^ome {\tt p(x)}). \\
Essayer diff\'erentes valeurs de $u_0$ (par exemple $u_0=0$, $u_0=-2.25$,\\ 
$u_0=0.8$, $u_0=0.801$, $u_0=0.802$ etc...). Qu'observez-vous ?
\item
Montrer que si $0.802 \leq u_0 \leq 0.843 $, $u_{3n}$ est convergente.
\end{itemize}
\item  (facultatif) \\
Reprendre en utilisant le  proc\'ed\'e d'acc\'el\'eration de convergence 
d'Aitken la r\'esolution de $\cosh(x)/2=x$ sur $[0,1]$ et 
de $\cosh(x)=5x$ pour $x>0$.\\
R\'esoudre par ce proc\'ed\'e l'\'equation :\\
$10\cos(x)=x$ sur $ [0,\ 10]$
\item Suites extraites (facultatif) \\
\'Ecrire un programme donnant $k$ termes d'une
sous-suite de la suite $u_n=\sin(n)$, dont tous les \'el\'ements sont
dans l'intervalle $[0.98,1]$.

\end{enumerate}
\end{document}

En mode \verb|RPN|\\
%l'interface la plus efficace est le mode \verb|RPN|.
 Tapez sur
la touche \verb|MODE| puis sur la touche \verb|+/-| pour passer en mode \verb|RPN| puis sur
\verb|ENTER|.
On peut d\'efinir une fonction de la fa\c{c}on suivante :\\
On tape  \verb|'F(X)=COS(X)/2'|\\
puis on appuie sur le {\tt shift-bleu} et la touche \verb|DEF| pour d\'efinir \verb|F|.\\
Appuyez ensuite sur la touche \verb|VAR| : \verb|F| se trouve dans la 
bandeau (la derni\`ere ligne de l'\'ecran) et  correspond
\`a la touche \verb|F1|.\\
Placez la valeur initiale sur la pile puis tapez  la touche \verb|F1| correspondant
\`a l'intitul\'e \verb|F| du menu du bandeau. 
Ceci ex\'ecute une it\'eration. Il suffit d'appuyer
plusieurs fois de suite sur \verb|F| du menu du bandeau pour it\'erer plusieurs fois.