Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de recherche d'un zéro d'une fonction
Résumé
Un algorithme de recherche d'un zéro d’une fonction est une méthode numérique ou un algorithme de recherche d’une valeur approchée d’un x vérifiant , pour une fonction donnée f. Ici, x est un nombre réel appelé zéro de f ou lorsque f est polynomiale, racine de f.
Lorsque x est un vecteur, les algorithmes pour trouver x tel que sont généralement appelés « algorithmes de résolution numérique d'un système d'équations ». Ces algorithmes sont une généralisation des algorithmes de recherche d’un zéro d’une fonction et peuvent s’appliquer à des équations linéaires ou non linéaires. Certains algorithmes de recherche des zéros (comme la méthode de Newton) peuvent être généralisés à la résolution numérique des systèmes d'équations non linéaires.
Les algorithmes de recherche des zéros d’une fonction sont étudiés en analyse numérique.
La méthode de dichotomie est l'algorithme le plus simple pour trouver des zéros d'une fonction continue : commencer avec deux points a et b qui encadrent un zéro de la fonction, et à chaque itération, choisir l’un des deux intervalles ou , étant le milieu de a et b. L’algorithme repose sur le choix du sous-intervalle de qui contient un zéro. Dans la plupart des cas, la méthode de dichotomie garantit la convergence vers un zéro lorsque la fonction est continue. Sa progression dans la recherche est plutôt lente, puisque sa vitesse de convergence est linéaire. Une des particularités de cet algorithme est qu'il est possible de connaître à l'avance le nombre d'itérations nécessaires pour déterminer la racine de l'équation avec la précision souhaitée.
La méthode de Newton, appelée aussi méthode de Newton-Raphson, suppose que f est de classe C1. On « linéarise » la fonction f en la valeur approchée courante du zéro, en utilisant la dérivée de la fonction. Cela donne la relation de récurrence :
La méthode de Newton peut ne pas converger si la valeur initiale est trop loin d’un zéro. Cependant, si elle converge, elle est beaucoup plus rapide que la méthode de dichotomie (sa vitesse de convergence est quadratique).
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.