Pour télécharger le mémoire du TIPE : cliquez ici

INTRODUCTION :
Nous avons mené ce travail en quatre grandes étapes. Dans un premier temps, nous nous sommes intéressés à la méthode de Newton dans R, puis dans des ensembles de plus en plus "grands", respectivement C et R^n. Ensuite, nous nous sommes attachés à établir une comparaison entre l'algorithme de Newton, des méthodes dérivant de cet algorithme, et d'autres méthodes classiques de calcul de solutions d'équations telles que celles de la sécante, de la bissection (ou dichotomie), du point fixe, ou encore la méthode de Steffensen.
 

- ETUDE -
  • Première étape : dans R
L'algorithme de Newton est basé sur le calcul des termes de la suite :
xn+1=xn-f(xn)/f '(xn)
Nous mettons en évidence d'une part une convergence rapide vers une solution, d'autre part l'importance du choix de la valeur initiale r0 ainsi qu'un comportement chaotique quand l'équation ne possède pas de racines réelles (x^2+1 = 0). C'est d'ailleurs cette dernière équation qui nous a conduit à considérer la méthode dans C.
 
 
  • Deuxième étape : dans C
L'algorithme reste identique. L'intérêt de passer dans le corps complexe est de pouvoir illustrer graphiquement la convergence de la méthode en mettant en évidence différentes zones appelées bassins d'attraction ou bassins de Newton. Ces graphiques permettent ainsi de prendre conscience de la grande sensibilité de la méthode. Nous en avons créé quelques uns pour bien illustrer notre propos :
 
z^8 + 15.z^4-16 :
(z-1).(z-(-1.384609-0.9231.i)).(z-(0.384609+0.9231.i)) :
(z-1).(z-(-1.384609-0.9.i)).(z-(0.384609+0.9231.i)) :
 
  • Troisième étape : dans R^n
Nous nous sommes alors demandé si nous ne pouvions pas aussi considérer R^2, et plus généralement R^n, comme domaine d'application de la méthode de Newton. Ceci est tout à fait possible et l'algorithme reste similaire au précédent. On calcule les différents termes de la suite de vecteurs de R^n définie par rk+1=rk-yk où yk est la solution du système [JF(rk)].yk=F(rk). D'un point de vue purement formel, on retrouve la formule bien connue : rk+1=rk-[JF(rk)]^(-1).F(rk). L'intérêt de passer dans R^n est de pouvoir résoudre des systèmes non linéaires. Ainsi, à titre d'exemple, nous avons calculé dans R^2 l'intersection de deux courbes. Mais là encore, nous mettons en évidence une grande sensibilité qui se traduit par une incertitude (dépendant de la valeur choisie pour r0) quant à la racine visée.
 
  • Quatrième étape : étude comparative
Devant le défaut énoncé ci-dessus, nous avons alors cherché d'autres méthodes d'approximation des racines pour les comparer à celle de Newton. Nous en avons trouvé deux sortes : celles dérivant de la méthode de Newton et celles n'ayant aucun lien avec elle. Celles dérivées de la méthode de Newton consistent soit en un enrichissement de la formule avec des termes en f '' (dans R ou C), soit en une réévaluation de la matrice Jacobienne toutes les p itérations (dans R^n). Les autres méthodes sont les algorithmes classiques de la sécante, de la dichotomie, du point fixe, et la méthode de Steffensen. Généralement ces méthodes se révèlent moins efficaces car, en plus de défauts tels que l'introduction de solutions parasites, elles nécessitent un plus grand nombre d'itérations pour arriver à la même précision que la méthode de Newton.

CONCLUSION : Comme nous avons pu le constater, la méthode de Newton, malgré ses imperfections, reste l’une des plus performantes à nos jours, notamment dans son application à l’extraction de la racine carrée d'un nombre. Elle est utilisée par des logiciels de calcul actuels tels que Maple. Par ailleurs, elle suscite encore des recherches sur la dynamique à l'origine des graphiques que l'on obtient dès que le degré du polynôme est supérieur à 3.

- OUTILS UTILISES -
  • Maple (pour les graphes des exemples dans R^2).
  • Calculateur en ligne de l'Université de Clark (pour les dessins dans C).
  • Calculateur en ligne de l'Université de Laval (pour tester les différentes méthodes  utilisées dans le calcul de la racine carrée de 3).
- SOURCES D'INFORMATION -
  • Divers ouvrages parmi lesquels : "A first course in chaotic dynamical systems" (1992) et "An introduction to chaotic dynamical systems" (1989) de R. Devaney, ainsi que "L’itération de Newton, convergence et chaos" (1984) de C. Masse.
  • Internet, et notamment les sites :