Algorithme de recherche d'un zéro d'une fonction
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) réel appelé zéro (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide dans l’écriture des nombres en notation positionnelle.) de f ou lorsque f est polynomiale racine de f.

Lorsque x est un vecteur (En mathématiques, un vecteur est un élément d'un espace vectoriel, ce qui permet d'effectuer des opérations d'addition et de multiplication par un scalaire. Un n-uplet...), les algorithmes pour trouver x tel que f(x) = 0 sont généralement appelés "algorithmes de résolution numérique (Une information numérique (en anglais « digital ») est une information ayant été quantifiée et échantillonnée, par opposition à une information dite...) d’une équation (En mathématiques, une équation est une égalité qui lie différentes quantités, généralement pour poser le problème de leur identité. Résoudre l'équation consiste à...)". Ces algorithmes sont une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent être...) des algorithmes de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la...) 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 équations non linéaires.

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

Algorithmes spécifiques

Dichotomie

L’algorithme le plus simple permettant de trouver des zéros est la méthode de dichotomie : on commence avec deux points a et b qui encadrent un zéro de la fonction, et à chaque itération, on choisit l’un des deux intervalles [a, c] ou [c, b], c = (a + b) / 2 étant le milieu de a et b. L’algorithme choisit toujours le sous-intervalle de [a, b] qui contient un zéro. La méthode de dichotomie garantit la convergence (Le terme de convergence est utilisé dans de nombreux domaines :) vers un zéro lorsque la fonction est continue. Sa progression dans la recherche est plutôt lente (La Lente est une rivière de la Toscane.) puisque sa vitesse (On distingue :) 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 vous commencez trop loin d’un zéro. Cependant, si elle converge, elle est beaucoup plus rapide que la méthode de dichotomie (sa complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en...) est quadratique). La méthode de Newton est importante parce qu’elle peut aisément se généraliser à des problèmes en dimensions (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de révolution.) supérieures.

Sécante

Si nous remplaçons la dérivée (La dérivée d'une fonction est le moyen de déterminer combien cette fonction varie quand la quantité dont elle dépend, son argument, change. Plus...) de la fonction dans la méthode de Newton avec une différence finie, nous obtenons 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).

Ainsi, la méthode de la sécante 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 elle coupe l’intervalle en un point (Graphie) donné par la formule de la méthode de la sécante. La méthode de la fausse position 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.

Muller

La méthode de la sécante intervient également quand on approche la fonction inconnue f 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 (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un élément y tel que x·y = y·x = 1, si 1 désigne...)

Cet inconvénient peut être évité par l'interpolation de la bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans...) réciproque (La réciproque est une relation d'implication.) 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 l'interpolation quadratique inverse se comporte souvent mal quand les itérés ne sont pas proches du zéro.

Brent

Enfin, la méthode de Brent est une combinaison (Une combinaison peut être :) de la méthode de dichotomie, de la méthode de la sécante et de l’interpolation quadratique inverse. À chaque itération, la méthode de Brent 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

  • Successive substitutions
  • méthode de Broyden
  • méthode du point fixe (En mathématiques, pour une application f d’un ensemble E dans lui-même, un élément x de E est un point fixe de f si f(x) = x.)

Von Mises

Gradient conjugué (En mathématiques, le conjugué d'un nombre complexe z est le nombre complexe formé de la même partie réelle que z mais de partie imaginaire opposée.)

La méthode du gradient conjugué

Recherche des racines d’un polynôme (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne serait-ce que...)

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 (En algèbre linéaire, la matrice compagnon du polynôme unitaire) 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 (En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés,...) de valeur propre (En mathématiques, le concept de vecteur propre est une notion algébrique s'appliquant à une application linéaire d'un espace dans lui-même. Il correspond à l'étude des axes privilégiés, selon lesquels...) 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, il faut garder à l’esprit que le problème de recherche de valeurs approchées de racines peut être mal conditionné comme le montrent les polynômes de Wilkinson.

Page générée en 0.105 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique