Suites récurrentes

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

Exercice 2 (à rendre à la fin de la 2ème séance de TP)
Écrire une fonction debut prenant en argument u₀, la fonction f et un entier n et renvoyant la liste {u₀, u₁,..., u_n}. Utilisez la fonction debut pour calculer les 50 premiers termes de la suite u₀ = 0, u_{n + 1} = $\sqrt{2+u_n}$. Que constatez-vous lorsque vous prenez u0:=0 et u0:=0.0 comme valeurs initiales? Pourquoi cette différence? Quels sont les avantages et inconvénients d'utiliser une valeur initiale exacte ou approchée?

Le programme précédent donne une idée de la convergence de la suite, mais ne donne aucune information quantitative sur la vitesse de convergence. Au lieu de renvoyer un nombre fixé de termes de la suite, on va effectuer 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 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.

Exercice 3 (à rendre à la fin de la 2ème séance de TP)
Écrire une fonction iter prenant en argument la fonction f, la valeur de $\varepsilon$ et de N qui s'arrête si l'une des conditions est satisfaite : | u_{n + 1} - u_n| < $\varepsilon$ ou le nombre d'itérations dépasse N. Dans le premier cas la fonction renverra la valeur de u_{n + 1}, dans le second cas une séquence composée de u_N et de N.

On suppose que la fonction f satisfait aux hypothèses du théorème du point fixe (on notera k < 1 la constante de ce théorème), déterminer en fonction de k et u_{n + 1} un encadrement de la limite l de la suite u_n.

Exercice 4 (à rendre au début de la 3ème séance de TP)
Vérifier les hypothèses du théorème du point fixe pour f (x) = 3 cos(x/3) sur [0, 1]. Déterminer une valeur approchée de la limite de u_{n + 1} à 10^-3 près en utilisant la fonction iter précédente.

Déterminer une fraction rationnelle f à coefficients entiers

f (x) = $${\frac{ax+b}{cx+d}}$$

ayant comme point fixe $\sqrt{11}$ et un intervalle I contenant $\sqrt{11}$ sur lequel les hypothèses du théoréme du point fixe sont satisfaites. En utilisant la fonction iter, trouver un encadrement de $\sqrt{11}$ à 10^-2 près par une fraction d'entiers. En quoi ce type de suite récurrente est-il intéressant?