
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath,amsfonts,amssymb,a4,epsfig}
\usepackage{times}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\begin{document}
{\Large \noindent Mat249 \hfill TP2: Suites récurrentes \hfill 2008/9 }

\vspace{8mm}

{\em On souhaite étudier des suites récurrentes $(u_n)$ définies par
  $u_{n+1}=f(u_n)$ et $u_0$, où $f$ est une fonction de $\R$
  dans $\R$, par exemple $f(x)=\sqrt{2+x}$.}

{\bf Exercice 1} 
\begin{enumerate}
\item 
  En utilisant le tableur de Xcas (menu Edit->Ajouter->tableur), représenter
  les premiers termes de la suite
  $u_{n+1}=\sqrt{2+u_n}$ avec $u_0=0.1$ ou $u_0=1/10$ (menu Math->suite
  récurrente du tableur).
\item Calculer ensuite en mode exact et approché
  les 10 premiers termes de la suite~:
  vous pouvez définir la cellule
  \verb|A1| par \verb|=sqrt(2+A0)|, puis cliquer sur \verb|A1|,
  puis appuyer en bas \`a droite de la cellule \verb|A1| lorsque
  le curseur souris change de forme
  et relâcher à la fin de la zone
  où vous voulez copier la formule définissant \verb|A1|.
\item
  Quels sont les avantages 
  et inconvénients d'utiliser une valeur initiale exacte ou
  approchée?
\end{enumerate}


\vspace{8mm}

{\em La feuille de calcul précédente donne une idée de la convergence
de la suite, mais ne donne aucune information quantitative
sur la vitesse de convergence. Au lieu de calculer un nombre fixé
de termes de la suite, on va écrire un programme
avec un test d'arrêt selon la
valeur $|u_{n+1}-u_n|$ comparé à un nombre positif (petit)
$\varepsilon$ fixé à l'avance. Pour éviter que le programme ne boucle
indéfiniment lorsque la suite ne converge pas (ou converge
trop lentement pour la machine), on fixe aussi un nombre maximal
d'itération $N$.}

{\bf Exercice 2} \\
Écrire un programme \verb|iter| prenant en argument
la fonction $f$, la valeur de $u_0$, de $N$ et de $\varepsilon$, et
qui s'arrête dès que l'une des conditions suivantes est satisfaite~:
\begin{itemize}
\item $|u_{n+1}-u_n|<\varepsilon$ 
\item le nombre d'itérations dépasse $N$.
\end{itemize}
Dans le premier cas le programme renverra la valeur de $u_{n+1}$, dans
le second cas une séquence composée de $u_N$ et de $N$.\\
Tester votre programme avec $f(x)=\sqrt{2+x}$ et $f(x)=x^2$.


\vspace{8mm}

{\em On suppose que la fonction $f$ satisfait aux hypothèses du
  théorème du point fixe.  On notera $k<1$ la constante de contractance.
  % et $l := \lim u_n$ la limite $l$ de la suite $(u_n)$.
  On peut alors trouver un encadrement de la limite $l$ 
  de la suite $(u_n)$ en fonction de $u_n$, $u_{n-1}$ et $k$.}

{\bf Exercice 3} \\
Écrire un programme \verb|iter_k| prenant en argument
la fonction $f$, la valeur de $u_0$, le nombre maximal d'it\'erations $N$,
la constante $k$ et l'écart toléré $\epsilon$, 
et qui s'arrête dès que $| u_n - l | \le \epsilon$ ou $n>N$.

Vérifier les hypothèses du théorème du point fixe pour $f(x)=2\cos(x/3)$ 
sur $[0,2]$ et expliciter une constante de contractance $k$.
Déterminer une valeur approchée de la limite de $(u_{n})$
à $10^{-3}$ près en utilisant la fonction \verb|iter_k|.
% (ou la fonction \verb|iter| de l'exercice précédent).



\vspace{8mm}

{\em La convergence de ces suites est en général {\em linéaire},
  le nombre de décimales exactes augmente de la même valeur
  à chaque itération. Par contre lorsqu'on est prêt d'une racine,
  la méthode de Newton permet en gros de multiplier par deux le nombre
  de décimales à chaque itération.}

{\bf Exercice 4}
\begin{enumerate}
\item Donner une suite itérative obtenue par la méthode de Newton
convergeant vers $\sqrt{3}$. 
\item Montrer que la fonction $f \colon \R_+ \to \R_+$ définie par 
  \[ f(x)=\frac{3x+3}{x+3} \]
  admet $\sqrt{3}$ pour point fixe.  Trouver un intervalle $I$ 
  contenant $\sqrt{3}$ sur lequel les hypothèses du théorème du point fixe 
  sont satisfaites et expliciter une constante de contractance $k$.
\item Comparer au tableur la vitesse de convergence des 10 premiers
  termes des deux suites (calculez les avec par exemple
  100 chiffres significatifs et faites les différence entre 2 termes
  successifs).
\item Cr\'eez un programme \verb|iter_n|
similaire \`a \verb|iter_k| mais appliquable \`a la m\'ethode
de Newton, i.e. prenant en argument
la fonction $f$ telle que $f(r)=0$, 
$u_0$, $N$, $\epsilon$ et une valeur inferieure \`a  $|f'(r)|$
(la fonction d\'eriv\'ee de $f$ se d\'efinit par
\verb|function_diff(f)|).
\item En utilisant la fonction \verb|iter|, trouver un encadrement de 
  $\sqrt{3}$ à $10^{-6}$ près par les deux méthodes (on pourra
  prendre une valeur initiale approchée puis entière exacte pour avoir
  une valeur numérique approchée puis une fraction).
  Combien d'itérations sont nécessaires?
\end{enumerate}


\vspace{8mm}

{\em Dans certains cas, la fonction $f$ n'est pas contractante, mais
  on peut réécrire l'équation à résoudre sous une autre
  forme avec une fonction contractante, par exemple en utilisant
  une fonction réciproque.}

{\bf Exercice 5}\\
Donner un encadrement à $10^{-6}$ près d'une racine
de l'équation $\tan(x)=x$ sur l'intervalle $]3\pi/2,5\pi/2[$ en
utilisant une méthode de point fixe.

\end{document}

