« Méthode de Newton » : différence entre les versions

Sous sa forme moderne, l'algorithme peut être présenté brièvement comme suit : à chaque itération, la fonction dont on cherche un zéro est linéarisée en l'itéré (ou point) courant et l'itéré suivant est pris égal au zéro de la fonction linéarisée. Cette description sommaire indique qu'au moins deux conditions sont requises pour la bonne marche de l'algorithme : la fonction doit être [[Différentielle|différentiable]]dérivable aux points visités (pour pouvoir y linéariser la fonction) et les dérivées ne doivent pas s'y annuler (pour que la fonction linéarisée ait un zéro) ; s'ajoute à ces conditions la contrainte forte de devoir prendre le premier itéré ''assez proche'' d'un zéro ''régulier'' de la fonction (i.e., en lequel la dérivée de la fonction ne s'annule pas), pour que la convergence du processus soit assurée.

L'intérêt principal de l'algorithme de Newton est sa [[Vitesse de convergence des suites#Convergence q-quadratique|convergence quadratique]] locale. En termes imagés mais peu précis, cela signifie que le nombre de [[Chiffre significatif|chiffres significatifs]] corrects des itérés double à chaque itération, ''asymptotiquement''. Comme le nombre de chiffres significatifs représentables par un ordinateur est d’environ 15 [[système décimal|chiffres décimaux]] (sur un ordinateur qui respecte la norme [[IEEE_754|IEEE-754]]), on peut simplifier grossièrement les propriétés de convergence de l'algorithme de Newton en disant que, soit il converge en moins de 10 itérations, soit il diverge. En effet, si l'itéré initial n'est pas pris suffisamment proche d'un zéro, la suite des itérés générée par l'algorithme a un comportement erratique, dont la convergence éventuelle ne peut être que le fruit du hasard (un des itérés est ''par chance'' proche d'un zéro).

L'importance de l'algorithme a incité les numériciens à étendre son application et à proposer des remèdes à ses défauts. Par exemple, l'algorithme permet également de trouver un zéro d'une [[fonction de plusieurs variables]] à valeurs vectorielles, voire définie entre [[espace vectoriel|espaces vectoriels]] de dimension infinie ; la méthode conduit d'ailleurs à des résultats d'existence de zéro (utilisés dans certaines preuves du [[théorème des fonctions implicites]], les théorèmes de [[Leonid Kantorovitch|Kantorovitch]]). On peut aussi l'utiliser lorsque la fonction est différentiable dans un sens plus faible (fonction différentiable par morceaux, [[Fonction B-différentiable|B-différentiable]], [[Fonction semi-lisse|semi-lisse]], obliquement différentiable, ''etc''), ainsi que pour résoudre des systèmes d'inégalité non linéaire, des problèmes d'[[inclusion fonctionnelle]], d'équations différentielles ou aux dérivées partielles, d’[[inéquation variationnelle|inéquations variationnelles]], de [[complémentarité]], ''etc''. On a également mis au point des ''techniques de globalisation'' de l'algorithme, lesquelles ont pour but de forcer la convergence des suites générées à partir d'un itéré initial arbitraire (non nécessairement proche d'un zéro), comme la [[algorithme à directions de descente|recherche linéaire]] et les [[algorithme à régions de confiance|régions de confiance]] agissant sur une fonction de mérite (souvent la fonction de moindres-carrés). Dans les versions dites ''inexactes'' ou ''tronquées'', on ne résout le système linéaire à chaque itération que de manière approchée. Enfin, la famille des [[Méthode de Quasi-Newton|algorithmes de quasi-Newton]] propose des techniques permettant de se passer du calcul de la dérivée de la fonction. Toutes ces améliorations ne permettent toutefois pas d'assurer que l'algorithme trouvera un zéro existant, quel que soit l'itéré initial.

Cette méthode fut l'objet de publications antérieures. En [[1685 en science|1685]], [[John Wallis]] en publia une première description<ref>{{MathWorld|nom_url=WallissConstant|titre=Wallis's Constant}}.</ref> dans ''A Treatise of Algebra both Historical and Practical''. En [[1690 en science|1690]], [[Joseph Raphson]] en publia une description simplifiée dans ''Analysis aequationum universalis''. Raphson considérait la méthode de Newton toujours comme une méthode purement algébrique et restreignait aussi son usage aux seuls polynômes. Toutefois, il mit en évidence le calcul récursif des approximations successives d'un zéro d'un polynôme au lieu de considérer comme Newton une [[suite de polynômes]].

Il se peut que la récurrence doive se terminer, si à l'étape {{mvar|k}}, {{mvar|x_k}} n'appartient pas au [[Ensemble de définition|domaine de définition]] ou si la dérivée {{math|''f {{'}}''(''x{{ind|k}}'')}} est nulle ; dans ces cas, la méthode échoue.

Pour illustrer la méthode, recherchons le nombre positif {{mvar|<math>x}}</math> vérifiant {{<math|>\cos(''x'') {{=}} ''x''{{^3}}}}</math>.
Reformulons la question pour introduire une fonction devant s'annuler :
on recherche le zéro positif (la racine) de {{<math|''>f''(''x'') {{=}} \cos(''x'') – ''-x''{{^3}}}}</math>.
La dérivation donne {{<math|''> f {{'}}''(''x'') {{=}} –sin-\sin(''x'') –- 3''x''{{3x^2}}}} </math>.

Comme {{math|cos(''x'') < 1}} <math>\cos(x)\leqslant 1</math> pour tout {{formule|''<math>x''}}</math> et {{formule|''<math>x''{{^3}}>1}}</math> pour {{formule|''<math>x''>1}}, nous savons que notre zéro se situe entre 0 et 1. Nous essayons une valeur de départ de {{</math|''x''{{ind|0}} {{=}} 0>,5}}.

x_1 & = & x_0 - \frac{f(x_0)}{f'(x_0)}
& = & 0,5 - \frac{\cos(0,5) - 0,5^3}{{}-\sin(0,5) - 3 \times 0,5^2}
& \simeq & 1{,}112\,141\,637\,1097\,2 \\

x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)}
& & \vdotscdots & \simeq & 0{,}909\,672\,693\,736\,8 \\

x_3 & & \vdotscdots & & \vdotscdots & \simeq & 0{,}866\,263\,818\,209208\,8 \\

x_4 & & \vdotscdots & & \vdotscdots & \simeq & 0{,}865\,477\,135\,298\,2 \\

x_5 & & \vdotscdots & & \vdotscdots & \simeq & 0{,}865\,474\,033\,111110\,9 \\

x_6 & & \vdotscdots & & \vdotscdots & \simeq & 0{,}865\,474\,033\,101\,6 \\

x_7 & & \vdotscdots & & \vdotscdots & \simeq & 0{,}865\,474\,033\,102101\,6

Les 7 premiers13 chiffres significatifs affichés de cettel'approximation valeur<math>x_7</math> coïncident avec les 713 premiers chiffres du vrai zéro exact.

Pour un intervalle compact {{mvar|I}} contenant {{mvar|x}} et {{mvar|a}} et inclus dans le domaine de définition de {{mvar|f}}, on pose : {{math|''m''{{ind|1}} {{=}} min{{ind|''x'' ∈ ''I''}} {{!}}''f {{'}}''(''x'') {{!}}}} ainsi que {{math|''M''{{ind|2}} {{=}} max{{ind|''x'' ∈ ''I''}} {{!}}''f {{''}}''(''x'') {{!}}}}. Alors, pour tout {{math|''x'' ∈ ''I''}} :

On peut déterminer une intersection des [[Graphe d'une fonction|graphes]] de deux fonctions réelles dérivables {{mvar|f}} et {{mvar|g}}, c'est-à-dire un point {{mvar|x}} tel que {{formule|''f''(''x'') {{=}} ''g''(''x'')}}, en appliquant la méthode de Newton à la fonction {{formule||§=''f'' – ''g''}}.

Il arrive parfois que la dérivée (ou la matrice jacobienne pour un système d'équations à plusieurs variables) de la fonction {{mvar|f}} soit coûteuse à calculer. La dérivée peut alors être approximéeapprochée au moyen de [[différences finies]]. Par exemple, en approchant la dérivée {{math|''f {{'}}''(''x{{ind|k}}'')}} par

Lorsque la fonction dont on cherche une racine est non-différentiable, mais seulement [[fonction semi-lisse|semi-lisse]], unla algorithmeméthode analoguede estNewton encorene possible.génère Unpas étatnécessairement une suite {{math|{''x{{ind|k}}''} }} convergente, même si les itérés sont des points de ldifférentiabilité de {{mvar|f}}, arbitrairement proches d'artun zéro de {{mvar|F}}. Un contre-exemple est donné par IzmailovKummer et Solodov(1988<ref>{{en}} AB. F. Izmailov, M. V. SolodovKummer (20141988). ''Newton-TypeNewton’s Methodsmethod for Optimization andnondifferentiable Variational Problemsfunctions''. SpringerIn Series{{ouvrage|lang=en|auteur1=J. inGuddat|auteur2=B. OperationsBank|auteur3=H. ResearchHollatz|auteur4=P. andKall|auteur5=D. FinancialKlatte|auteur6=B. EngineeringKummer|auteur7=K. SpringerLommatzsch|auteur8=L. Tammer|auteur9=M. Vlach|auteur10=K. Zimmerman|titre=Advances in Mathematical Optimization|pages=114–125|éditeur=Akademie-Verlag|lieu=Berlin}}.</ref>).

* {{en}} J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, [[Claudia Sagastizábal|C. Sagastizábal]] (2006), ''Numerical Optimization - Theoretical and Practical Aspects'' {{détail des éditions|Référence:Optimisation (Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006)}}.

{{Palette|Méthodes de résolution|Analyse Numérique|Optimisation}}