Rappels
Pour résoudre l'équation f (x) = 0 lorsque f est suffisamment
régulière, on itère la fonction :
Exemple: l'algorithme de Héron
Cet algorithme, basé sur la méthode de Newton, permet de déterminer des
valeurs approchées de racines d'entiers.
Pour calculer une valeur approchée de
où b > 1, on pose :
Exercice (à faire en TD)
Justifiez la convergence quadratique de la suite un de (1)
vers .
Indication, montrer que :
On rappelle qu'on a programmé au TP2 une fonction iter(f,a,N,epsilon) qui calcule les valeurs successives de la suite un définie par u0 et un + 1 = f (un) et s'arrête lorsque | un + 1 - un| < ou lorsque n > N.
Exercice 1 (à rendre à la fin de la séance)
Déterminez avec la fonction iter pour quelles valeurs de n,
on a
Exercice 2 (à rendre à la fin de la séance)
Appliquez la méthode de Newton pour résoudre x4 - 6 = 0,
On donnera la suite récurrente un correspondante, une valeur initiale,
le résultat de la fonction iter
avec
= 10-10,
et on justifiera rigoureusement que la suite est convergente.
Exercice 3 (à rendre au début de la séance suivante)
Justifier que les deux suites de l'exercice 1 satisfont les hypoyhèses
du théorème du point fixe sur [1, 2] (vous pouvez utiliser un
logiciel de calcul formel pour faire les calculs!).
Donnez alors une majoration de
| un + 1 - | dans les deux
cas pour n tel que
| un + 1 - un| < 10-7
(utilisez la majoration
| un - | où k est la
constante du théorème du point fixe et utilisez
(2) pour la suite de Héron).
Justifiez l'intérêt de la méthode de Newton.
Exercice 4 (à rendre au début de la séance suivante)
Programmez la méthode de Newton pour trouver une racine
d'un polynôme P à coefficients complexes (on écrira une
fonction racine(P,a,N,epsilon)
où P
désigne le polynôme, a la valeur initiale de la suite récurrente,
N le nombre maximal d'itérations et le test d'arrêt du programme
sera
| un + 1 - un| < ).
Vérifiez votre programme
avec le polynôme x4 - 6 et une valeur de départ proche du
.
Testez votre programme avec x4 + 1 et plusieurs valeurs
de départ (essayez d'en trouver une pour chacune des racines
complexes de x4 + 1), expliquez pourquoi
il faut donner une valeur de départ non réelle pour espérer converger
vers une racine de ce polynôme.