(pour signaler une erreur monnerat@u-pec.fr)

Algorithmes de recherche de points fixes.

Points fixes

On considére une fonction \(f:I\rightarrow I\). Un point fixe de \(f\) dans \(I\) est un réel \(l\in I\) qui vérifie l'équation : $$f(l)=l$$

On voit que la recherche d'un point fixe peut se ramener à la recherche d'une racine (et réciproquement) car $$f(x)=x \Leftrightarrow f(x)-x=0$$

Un algorithme classique consiste à partir d'un point quelconque \(x_0\in I\), et à générer son orbite sous \(f\), c'est à dire la suite \((x_n)\) définie par la récurrence \(x_{n+1} = f(x_n)\)

On a vu en cours que sous certaines conditions sur \(f\), cette algorithme converge vers un point fixe de \(f\).

Votre travail

On considère la fonction \(f(x)=1-\displaystyle \frac{x^2}{4}\), définie sur \({\mathbb R}_{+}\).

1. 1. Calculez son point fixe, noté \(l\).
   2. Donnez un intervalle \(I\) borné tel que \(l\in I\), et \(f(I)\subset I\).
   3. Montrez que toute suite définie par \(x_0\in I\), et \(x_{n+1} = f(x_n)\) conerverge vers \(l\).
   4. Ecrire un programme qui calcule une valeur approcée de \(l\). Remplir le tableau du tp précédent pour estimer la vitesse convergence de l'algorithme.
      L'erreur (exacte) à chaque itération est \(\epsilon_n = |x_n - l |\). On prendra pour la calculer une valeur approchée de \(\sqrt{2}\) (regardez dans math.h).
   5. Comment vous semble évoluer la valeur de l'erreur en fonction du nombre d'itérations ?
2. On veut comparer cette méthode avec celle de Newton.
   1. Sur quelle fonction \(g\) appliquer Newton pour retrouver le point fixe de \(f\) ?
   2. Faites-le et vérifier que l'algorithme de Newton converge bien vers la même limite.
   3. Quelle méthode (Newton ou point fixe) est la plus rapide ?