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

Algorithmes de recherche de racines d'une fonction.

Dichotomie

Soit une fonction \(f\) continue sur un intervalle \(I=[a,b]\), strictement monotone avec \(f(a)f(b)<0\).

Quel(s) théorème(s) permet(tent) d'affirmer que \(f\) possède une zéro unique dans \(I\) ?

La méthode dichotomique consiste à évaluer \(f\) au milieu de \(I\) en \(c=\frac{a+b}{2}\). Si \(f(c)=0\), c'est fini, sinon \(f(a)f(c)<0\) ou bien \(f(c)f(b)<0\). Dans le premier cas, on pose \(b=c\), et dans le deuxième \(a=c\). On est donc ramené au problème précedent, mais la longueur de \(I\) a été divisée par 2.

Votre travail

1. En notant \(I_n=[a_n,b_n]\) les intervalles engendrés par l'algorithme précédent, démontrer que les suites \((a_n)\) et \((b_n)\) convergent, vers la même limite, racine de \(f\).
2. Récuperez le programme C dichotomie.c. Vous devez implanter la fonction dichotomie. Elle prend en argument \(a\) et \(b\), la fonctions \(f\) (pointeur de fonction) et \(\epsilon\) qui servira dans le test d'arrêt.
3. Testez avec \(f(x)=x^{2}-2\) en choississant un intervalle de départ correct.

Méthode de Newton

On a une fonction \(f\) dérivable sur un intervalle \(I\), qui admet une racine unique \(\alpha \in I\).

Soit \(x_0\in I\) une valeur approchée (grossière) de \(\alpha\). On va utiliser l’approximation affine (la tangente) \(T_{x_0}\) de \(f\) au point \(x_0\).

Son équation est \(T_{x_0}(x)=f(x_0)+(x-x_0)f^{'}(x_0)\). Cette droite coupe l’axe des abscisses en \(x_1\).

Sous certaines conditions, le nombre \(x_1\) peut représenter une meilleure approximation de \(\alpha\) que \(x_0\).

La méthode de Newton consiste à itérer le processus en repartant de \(x_1\) et ainsi de suite.

Votre travail

1. Calculer \(x_1\) en fonction de \(x_0\). \(x_{n+1}\) en fonction de \(x_n\).
2. Récuperer le programme C newton.c. Vous devez implanter la fonction newton. Elle prend en argument le point de départ \(x_0\), les fonctions \(f\) et \(f^{'}\) (pointeurs de fonction) et \(\epsilon\) qui servira dans le test d'arrêt. On arrêtera la boucle dès que \(|f(x_n)|\leq \epsilon\) en considérant que \(x_n\) est une "bonne" approximation de \(\alpha\).
3. Tester avec \(f(x)=x^{2}-2\) en partant de \(x_0 = 2\).

Comparaison des vitesses de convergence

Pour cette partie, on prendra la fonction \(f(x) = x^2-2\). On s'interesse à son zéro positif \(\sqrt{2}\). On prendra, dans les programmes C, le type long double.

1. Ecrire un programme C qui affiche, pour chacune des deux méthodes, le nombre d'itérations nécessaires pour le calcul approché de \(\sqrt{2}\) pour atteindre les précisions

   Précision	Itération Newton	Itération dichotomie
   \(10^{-1}\)
   \(10^{-2}\)
   \(10^{-3}\)
   \(10^{-4}\)
   \(10^{-5}\)
   \(10^{-6}\)
   \(10^{-7}\)
   \(10^{-9}\)
   \(10^{-10}\)
   \(10^{-11}\)
   \(10^{-12}\)
   \(10^{-13}\)
   \(10^{-14}\)

   L'erreur (exacte) à chaque itération est \(\epsilon_n = |x_n -\sqrt{2}|\). On prendra pour la calculer une valeur approchée de \(\sqrt{2}\) (regardez dans math.h).

2. Quelle méthode est la plus rapide ?
3. Comment vous semble évoluer la valeur de l'erreur en fonction du nombre d'itérations pour chacune des deux méthodes ?