Algorithme de recherche d'un zero d'une fonction

Algorithme de recherche d'un zero d'une fonction

Algorithme de recherche d'un zéro d'une fonction

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 f(x) = 0, 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 f(x) = 0 sont généralement appelés « algorithmes de résolution numérique d’une équation ». 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éaire 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 équations non linéaires.

Les algorithmes de recherche des zéros d’une fonction sont étudiés en analyse numérique.

Sommaire

Algorithmes spécifiques

Dichotomie

La méthode de dichotomie est l'algorithme le plus simple pour trouver des zéros : 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 [a, c] ou [c, b], c = (a + b) / 2 étant le milieu de a et b. L’algorithme repose sur le choix du sous-intervalle de [a, b] 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.

Newton-Raphson

La méthode de Newton, appelée aussi méthode de Newton-Raphson, « linéarise » la fonction f en la valeur approchée courante du zéro. Cela donne la relation récurrente :

 x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}.

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 complexité est quadratique). Elle est importante car qu’elle peut aisément se généraliser à des problèmes en dimensions supérieures.

Sécante

Si la dérivée de la fonction dans la méthode de Newton est remplacée par une différence finie, c'est la méthode de la sécante. Elle utilise la relation récurrente :

x_{n+1} = x_n - \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} f(x_n).

Cette méthode ne requiert pas le calcul d’une dérivée, mais c’est au prix d’une vitesse de convergence lente (de l’ordre de 1,6).

Regula falsi

La méthode de la fausse position, aussi appelée méthode de regula falsi, s’apparente à la méthode de dichotomie. Cependant, elle ne coupe pas l’intervalle en deux parts égales à chaque itération, mais en un point donné par la formule de la méthode de la sécante. Cette méthode hérite de la robustesse de la méthode de dichotomie et de la complexité « super-linéaire » de la méthode de la sécante.

Méthode de Müller

La méthode de la sécante intervient également quand la fonction inconnue f est approchée par interpolation linéaire. Quand une interpolation quadratique est employée à la place, cela donne la méthode de Müller. Elle converge plus rapidement que la méthode sécante. Une particularité de cette méthode est que le terme itéré xn peut devenir complexe.

Interpolation quadratique inverse

L'inconvénient de la méthode de Müller peut être évité par l'interpolation de la bijection réciproque de f ce qui mène à la méthode de l’interpolation quadratique inverse. Encore une fois, la convergence est asymptotiquement plus rapide que la méthode de la sécante, mais elle se comporte souvent mal quand les itérés ne sont pas proches du zéro.

Méthode de Brent

Enfin, la méthode de Brent est une combinaison de la méthode de dichotomie, de la méthode de la sécante et de l’interpolation quadratique inverse. À chaque itération, cette méthode décide de laquelle de ces trois méthodes est susceptible d’approcher au mieux le zéro, et effectue une étape en utilisant cette méthode. Cela donne une méthode robuste et rapide, très populaire et très appréciée.

Autres algorithmes

D’autres algorithmes de recherches de zéros sont :

  • substitutions successives ;
  • méthode de Broyden ;
  • méthode du point fixe : l'équation f(x) = 0 est re-formulée sous la forme x = g(x) où g est choisie de telle sorte que toute suite (xn) donnée par xn + 1 = g(xn) converge vers un zéro de f.

Von Mises

Gradient conjugué

Article principal : Méthode du gradient conjugué.

Recherche des racines d’un polynôme

Une attention particulière a été donné au cas particulier où la fonction f est polynomiale. Bien sûr, les méthodes décrites dans la section précédente peuvent être utilisées. En particulier, il est facile de déterminer la dérivée d’un polynôme, et la méthode de Newton représente un très bon candidat. Mais il est possible de choisir une méthode qui exploite le fait que f est un polynôme.

Une possibilité est de considérer la matrice compagnon associée au polynôme. Sachant que les valeurs propres de cette matrice coïncident avec les racines du polynôme, on peut alors utiliser n’importe quel algorithme de recherche de valeur propre pour trouver des valeurs approchées des racines du polynôme initial.

Une autre possibilité est d’utiliser la méthode de Laguerre, qui est une méthode très compliquée mais qui converge très rapidement. En fait, elle développe une vitesse de convergence cubique pour les racines simples, pulvérisant la vitesse de convergence quadratique de la méthode de Newton.

Si le polynôme a des coefficients rationnels et si on recherche uniquement des racines rationnelles, alors la méthode de Ruffini peut être utilisée.

Dans tous les cas, le problème de recherche de valeurs approchées de racines peut être mal conditionné comme le montrent les polynômes de Wilkinson.

Voir aussi

Lien externe


  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme de recherche d%27un z%C3%A9ro d%27une fonction ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de recherche d'un zero d'une fonction de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Algorithme De Recherche D'un Zéro D'une Fonction — 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 f(x) = 0, pour une fonction donnée f. Ici, x est un nombre réel appelé zéro de f ou lorsque f est… …   Wikipédia en Français

  • Algorithme de recherche d'un zéro d'une fonction — 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 f(x) = 0, pour une fonction donnée f. Ici, x est un nombre réel appelé zéro de f ou lorsque f est… …   Wikipédia en Français

  • Algorithme De Calcul De La Racine N-ième — La racine n ième d un nombre réel positif A, notée , est le réel positif solution de l équation xn = A (Pour tout entier naturel non nul n, il existe n nombres complexes distincts solutions de cette équation si A > 0, mais une seule est… …   Wikipédia en Français

  • Algorithme de calcul de la racine n-ieme — Algorithme de calcul de la racine n ième La racine n ième d un nombre réel positif A, notée , est le réel positif solution de l équation xn = A (Pour tout entier naturel non nul n, il existe n nombres complexes distincts solutions de cette… …   Wikipédia en Français

  • Algorithme de calcul de la racine n-ième — La racine n ième d un nombre réel positif A, notée , est le réel positif solution de l équation xn = A (Pour tout entier naturel non nul n, il existe n nombres complexes distincts solutions de cette équation si A > 0, mais une seule est… …   Wikipédia en Français

  • Algorithme de Babylone — Méthode de Héron En mathématiques, la méthode de Héron ou méthode babylonienne est une méthode efficace d extraction de racine carrée. Elle porte le nom du mathématicien Héron d Alexandrie mais certains calculs antérieurs semblent prouver que la… …   Wikipédia en Français

  • Convergence d'une suite — Une suite de nombres réels est dite convergente lorsqu elle admet un nombre réel comme limite. Cette notion a été généralisée, en topologie : une suite définie sur un espace topologique E converge vers un élément l de E si tout ouvert de E… …   Wikipédia en Français

  • Racine Cubique (Calcul D'une ) — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Racine cubique (calcul d'une ) — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Recherche dichotomique — Dichotomie La dichotomie (« couper en deux » en grec) est, en algorithmique, un processus itératif ou récursif de recherche où, à chaque étape, l espace de recherche est restreint à l une des deux parties. On suppose bien sûr qu il… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”