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'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.

Algorithmes spécifiques

Dichotomie

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 $[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. 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.

Newton-Raphson

La méthode de Newton, appelée aussi méthode de Newton-Raphson, suppose que $f$ est de classe C¹. 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 :

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 vitesse de convergence est quadratique). 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, 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})

.

Cette méthode ne requiert pas le calcul d’une dérivée, mais c’est au prix d’une vitesse de convergence plus lente que celle de Newton (de l’ordre de 1,618). Cependant, comme elle ne nécessite qu'une évaluation de fonction par itération, elle se révèle en général plus rapide que la méthode de Newton. Sa généralisation en dimension supérieure à 1 est la méthode de Broyden (en).

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 Muller

La méthode de la sécante évalue la racine de la fonction $f$ en l'approximant par interpolation linéaire. La méthode de Muller évalue la racine par interpolation quadratique à l'aide des trois derniers points calculés. Elle converge plus rapidement que la méthode de la sécante (ordre de convergence de 1,84). Elle nécessite l'évaluation d'une racine carrée à chaque itération. Une particularité de cette méthode est que le terme itéré $x n$ 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

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.

Gradient conjugué

Article détaillé : Méthode du gradient conjugué.

Autres algorithmes

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

méthode du point fixe : l'équation $f (x) = 0$ est reformulée sous la forme $x = g (x)$ où $g$ est choisie de telle sorte que toute suite $(x n)$ donnée par $x n +1 = g (x n)$ converge vers un zéro de $f$ .

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Recherche des racines d’un polynôme

Une attention particulière a été donnée au cas particulier où $f$ est une fonction 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 est 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, par exemple la méthode de la puissance itérée.

Une autre possibilité est d’utiliser la méthode de Laguerre, qui sous certaines conditions converge à coup sûr vers l'une des racines (convergence globale). Sa vitesse de convergence est cubique pour les racines simples.

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 WilkinsonPolynôme de Wilkinson.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Root-finding algorithm » (voir la liste des auteurs).

Voir aussi

Articles connexes

Liens externes

Portail de l'analyse

v · m Méthodes de résolution d'équations
Équations polynomiales	Équation du premier degré Équation du second degré Équation cubique Méthode de Cardan Substitution de Viète Méthode de Lagrange Méthode de Tschirnhaus Méthode de Bézout Équation quartique Méthode de Lagrange Méthode de Ferrari Méthode de Descartes Équation quintique Méthode d'Hermite
Recherche d'un zéro	Méthode de dichotomie Méthode de Householder Méthode de Newton Méthode de Halley Méthode de Bernoulli Méthode de la sécante Méthode de Muller Méthode de Brent Méthode de Chandrupatla Méthode de la fausse position Méthode de Héron Méthode de Laguerre Méthode quasi-Newton Méthode du cercle de séparation

v · m Analyse numérique
Recherche de zéro	Méthode de Josephy-Newton Méthode de la sécante Méthode de Newton Point fixe
Transformations de matrice	Matrice de Hessenberg Décomposition LU Factorisation de Cholesky
Résolutions de systèmes	Méthode de Gauss-Seidel Méthode de surrelaxation successive (SOR) Méthode de Jacobi Décomposition QR Décomposition LU
Intégration numérique	Méthode du point médian Méthode des trapèzes Méthode de Simpson Méthodes de quadrature de Gauss Formule de Newton-Cotes Méthode de Romberg Méthode de Monte-Carlo
Équations différentielles	Méthode d'Euler (et semi-implicite) Méthode de Heun Méthodes de Runge-Kutta Intégration de Verlet Leapfrog Méthode linéaire à pas multiples (Adams-Bashforth, backward differentiation formula (en))
Interpolation numérique	Spline Interpolation polynomiale Interpolation lagrangienne Interpolation d'Hermite Suite de polynômes orthogonaux