%\makeindex
\documentclass{article}
\usepackage[pdftex]{hyperref}
\newcommand{\norme}[1]{ \left\| {#1} \right\| }
\newcommand{\tr}{\mbox{tr\,}}
\usepackage{amssymb}
\begin{document}
\begin{center}
{\Large 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}
Il faut tout d'abord  \'ecrire le programme
ci-dessous qui 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.\\
{\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}$).
\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$.

La section \ref{sec:Erable} donne la traduction pour l'\'emulateur
de HP49. La traduction pour {\tt sa} calculatrice est laiss\'ee
en exercice au lecteur.
\section{Application Sequence des calculatrices} \label{sec:suite}
{\sc Attention} sur les calculatrices on ne peut pas utiliser des param\`etres qui
soient des fonctions. On suppose donc 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{HP40}
On peut se servir de l'aplet {\tt Sequence} (touche {\tt APLET} puis on met 
{\tt Sequence} en surbrillance, puis on appuie sur {\tt ENTER}).\\
Il suffit alors de d\'efinir la suite $u_n$ en donnant la valeur de $u_1$
et de $u_2$, puis  la relation de r\'ecurrence $u_n=f(u_{n-1})$ ou 
$u_n=f(u_{n-1},u_{n-2})$.\\
La touche {\tt NUM} donne le tableau des diff\'erentes valeurs de $u_n$.\\
La touche {\tt PLOT} donne ''l'escargot'' si on a r\'egl\'e le {\tt SETUP} du
 {\tt PLOT} en choisissant {\tt cobweb}.
\section{Programmation sur emu49} \label{sec:Erable}
Pour ex\'ecuter plusieurs fois de suite une seule it\'eration,
l'interface la plus efficace est le mode \verb|RPN|. Tapez sur
la touche \verb|MODE| puis sur la touche \verb|+/-| 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 pour it\'erer plusieurs fois.

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|.
Revenez en mode alg\'ebrique en tapant sur les touches \verb|MODE|, \verb|+/-|
et \verb|ENTER|. puis saisissez la valeur de \verb|EPS|, par exemple:\\
\verb|0.0001 STO> EPS| (\verb|STO>| s'obtient en appuyant sur la touche 
\verb|STO>|).\\
et tapez le texte 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| 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} \label{sec:mupad}
Pour d\'efinir la m\^eme fonction, on taperait :\\
\verb| f:= ( x -> (cos(x)/2) )|\\
{\sc Attention} aux parenth\`eses, la priorit\'e de l'op\'erateur \verb|->|
n'est pas celle qu'on pense.\\
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 tapez sur la fl\`eche vers le haut et \verb|ENTER|.
On peut aussi programmer avec un test d'arr\^et. Ouvrez un fichier
(menu \verb|Files| puis \verb|Open File|, nommez-le \verb|iter.mu|)
et tapez :
\begin{verbatim}
iteration:=proc(f,x,maxiter,epsilon)
// f est la fonction, x la valeur initiale, 
//  maxiter le nombre maximal d'iterations, epsilon la tolerance
local i,oldx;
begin
 i:=0;
 x:=float(x);
 epsilon:=float(epsilon);
 repeat
  oldx:=x;
  x:=f(x);
  i:=i+1;
 until ( (abs(x-oldx)<epsilon) or (i>maxiter) ) end_repeat;
 if (i>maxiter) then x,maxiter else x end_if ;
end_proc;
\end{verbatim}
{\sc Attention} il ne faut rien taper apr\`es {\tt end\_proc;} (ni espace, ni enter).\\ 
Revenez dans le buffer \verb|*MuPAD*| et taper \verb|read("iter.mu");|\\
Ne pas oublier d'utiliser des valeurs num\'eriques pour $x$, par  exemple :\\
\verb|iteration(cos,0.2,50,1e-3)|).
On peut d\'efinir le nombre de chiffres significatifs (menu \verb|MuPAD|,
environnement puis \verb|DIGITS|).
\section{Compl\'ement de cours}
\subsection{M\'ethode de Horner}
Soit le polyn\^ome $P(X)=\Sigma _{i=0}^{n} a_iX^i$.\\
Etant donn\'e $c$, on cherche le polyn\^ome 
$Q(X)=\Sigma _{i=1}^{n} b_iX^{i-1}$ v\'erifiant :\\
$P(X)=(X-c)Q(X)+b_0$\\
On a donc :\\
$b_n=a_n$\\
$b_i=a_i+c. b_{i+1}$ ($i=n-1 .. 0$)\\
$b_0=P(c)=a_0+c. b_1$\\
On remarquera que le calcul de $b_0=P(c)$ n\'ecessite seulement le calcul
 de $b_{n-1}$...$b_0$ soit $n$ additions et $n$ multiplications.\\
Voici l'algorithme du calcul des $b_i$ :\\
on suppose qu'en entr\'ee on donne P sous la forme de la liste $\{a_0,...,a_n\}$ et\\
qu'en sortie on repr\'esente le polyn\^ome 
$Q(X)=\Sigma _{i=1}^{n} b_iX^{i-1}$ par la liste $ \{b_1,...,b_n\}$ 
Attention ! si $m=$ la longueur de la liste repr\'esentant $P$ on a :\\
 $P[1]=a_n,\ P[2]=a_{n-1},\ ...,\ P[m]=a_1$
\begin{verbatim}
fonction horner(P,c)
local m,b,Q
m:=dim(P)
b:=P[1]
Q:={b}
pour i de  2 a m-1 faire
  b:=P[i]+c*b
  Q:=append(Q,b) 
fpour
b:=P[m]+c*b
retourne Q,b
ffonction
\end{verbatim}
Remarques :
En MuPAD les listes s'\'ecrivent avec des crochets (exemple Q:=[b];)\\
{\tt HORNER} est implant\'e sur la HP49G les param\`etres sont par exemple P[X]
et $c$.\\
Exemple  : ${\tt HORNER(X^4+2.X^3+X,1)=\{X^3+3.X^2+3.X+4,1,4}\}$ \\
la liste r\'esultat est : \{Q[X],c,P[c]\}. 
\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}]$  
\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$)
\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{itemize}
\item 
R\'esolution de $\cos(x)=x$ sur $[0,1]$, de $\tan(x)=x$ sur $]\pi/2,3\pi/2[$
en utilisant le th\'eor\`eme du point fixe, cf. la section \ref{sec:ptfixe}.
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 
Recherche de valeur approch\'ee de $\sqrt{2}$\\
Vous cherchez une \'equation dont cette valeur est racine et appliquez
une m\'ethode de point fixe (par exemple $f(x)=\frac{2x+2}{x+2}$ admet $\sqrt{2}$ comme point fixe).\\
Donner une valeur de $\sqrt{2}$ \`a $10^{-5}$ pr\`es en utilisant l'algorithme de H\'eron. Comparez avec l'it\'eration de  $f(x)=\frac{2x+2}{x+2}$.
\item
Recherche d'une valeur approch\'ee de $\sqrt[3]{3}$ en utilisant la
m\'ethode de Newton.
\item 
Recherche de racines d'un polyn\^ome par la m\'ethode de Newton.\\
Exemple, racines de $x^4+1$. \\
  il faut partir d'une valeur initiale complexe 
(prendre une valeur non imaginaire pure).
\item Recherche de toutes les racines d'un polyn\^ome par \'elimination
d'une racine (m\'ethode de Horner).\\
Exemple, factorisation de $x^5+x+1$.\\
Pour \'eliminer les erreurs
d'arrondi on applique une it\'eration de Newton sur une estimation
de racine avec le polyn\^ome originel : \\
On se rapproche des racines en utilisant un pr\'efacteur ($\lambda=0.9$ par
exemple) dans la m\'ethode de Newton :
\[ x_{n+1}=x_{n}-\lambda \frac{f(x_n)}{f'(x_n)} \]
puis on prend comme valeur de $u_0$ l'estimation pr\'ec\'edente et  
on utilise la m\'ethode de Newton.
\item  Reprendre en utilisant le  proc\'ed\'e d'acc\'el\'eration de convergence d'Aitken la r\'esolution de $\cos(x)=x$ sur $[0,1]$ et  de $\tan(x)=x$ sur $]\pi/2,3\pi/2[$.\\
R\'esoudre par ce proc\'ed\'e l'\'equation :\\
$10\cos(x)=x$ sur $ [0,\ 10]$
\end{itemize}
\end{document}

        















