Méthode de Newton

En analyse numérique , la méthode de Newton , également connue sous le nom de méthode Newton – Raphson , du nom d' Isaac Newton et Joseph Raphson , est un algorithme de recherche de racines qui produit successivement de meilleures approximations des racines (ou zéros) d'une fonction à valeur réelle . La version la plus basique commence par une fonction à une seule variable f définie pour une variable réelle x , la dérivée de la fonction f ′ et une estimation initiale x 0 pour une racine de f . Si la fonction satisfait suffisamment d'hypothèses et que l'estimation initiale est proche, alors

est une meilleure approximation de la racine que x 0 . Géométriquement, ( x 1 , 0) est l'intersection de l' axe x et de la tangente du graphique de f en ( x 0 , f  ( x 0 )) : autrement dit, la supposition améliorée est la racine unique de l' approximation linéaire au point initial. Le processus est répété comme

jusqu'à ce qu'une valeur suffisamment précise soit atteinte. Cet algorithme est le premier de la classe des méthodes de Householder , succédé par la méthode de Halley . La méthode peut également être étendue à des fonctions complexes et à des systèmes d'équations .

Illustration of Newton's method
La fonction f est représentée en bleu et la ligne tangente est en rouge. On voit que x n + 1 est une meilleure approximation que x n pour la racine x de la fonction f .

L'idée est de commencer par une estimation initiale qui est raisonnablement proche de la vraie racine, puis d'approximer la fonction par sa ligne tangente en utilisant le calcul , et enfin de calculer l' interception x de cette ligne tangente par algèbre élémentaire . Cette x -interception sera généralement une meilleure approximation de la racine de la fonction d'origine que la première estimation, et la méthode peut être itérée .

Plus formellement, supposons que f  : ( a , b ) → ℝ est une fonction différentiable définie sur l' intervalle ( a , b ) avec des valeurs dans les nombres réels   , et nous avons une approximation courante x n . Ensuite, nous pouvons dériver la formule pour une meilleure approximation, x n + 1 en se référant au diagramme de droite. L'équation de la tangente à la courbe y = f  ( x ) en x = x n est

f ′ désigne la dérivée . L' interception x de cette ligne (la valeur de x qui fait y = 0 ) est prise comme approximation suivante, x n + 1 , à la racine, de sorte que l'équation de la ligne tangente est satisfaite lorsque:

La résolution de x n + 1 donne

Nous commençons le processus avec une valeur initiale arbitraire x 0 . (Plus le zéro est proche, mieux c'est. Mais, en l'absence de toute intuition sur l'endroit où le zéro pourrait se trouver, une méthode "deviner et vérifier" pourrait réduire les possibilités à un intervalle raisonnablement petit en faisant appel au théorème de la valeur intermédiaire .) La méthode convergera généralement, à condition que cette estimation initiale soit suffisamment proche du zéro inconnu, et que f ′ ( x 0 ) ≠ 0 . De plus, pour un zéro de multiplicité  1, la convergence est au moins quadratique (voir taux de convergence ) au voisinage du zéro, ce qui signifie intuitivement que le nombre de chiffres corrects double à peu près à chaque pas. Plus de détails peuvent être trouvés dans la section d'analyse ci - dessous.

Les méthodes de Householder sont similaires mais ont un ordre supérieur pour une convergence encore plus rapide. Cependant, les calculs supplémentaires requis pour chaque étape peuvent ralentir les performances globales par rapport à la méthode de Newton, en particulier si f ou ses dérivées sont coûteuses en calcul.

Le nom «méthode de Newton» est dérivé de la description par Isaac Newton d'un cas particulier de la méthode dans De analysi per aequationes numero terminorum infinitas (écrit en 1669, publié en 1711 par William Jones ) et dans De metodis fluxionum et serierum infinitarum ( écrit en 1671, traduit et publié sous le titre Méthode de Fluxions en 1736 par John Colson ). Cependant, sa méthode diffère considérablement de la méthode moderne donnée ci-dessus. Newton a appliqué la méthode uniquement aux polynômes, en commençant par une estimation de racine initiale et en extrayant une séquence de corrections d'erreurs. Il a utilisé chaque correction pour réécrire le polynôme en termes d'erreur restante, puis a résolu une nouvelle correction en négligeant les termes de plus haut degré. Il n'a pas explicitement lié la méthode aux dérivés ni présenté une formule générale. Newton a appliqué cette méthode à des problèmes numériques et algébriques, produisant des séries de Taylor dans ce dernier cas.

Newton a peut-être dérivé sa méthode d'une méthode similaire mais moins précise de Vieta . L'essence de la méthode de Vieta se trouve dans les travaux du mathématicien persan Sharaf al-Din al-Tusi , tandis que son successeur Jamshīd al-Kāshī a utilisé une forme de la méthode de Newton pour résoudre x P - N = 0 pour trouver les racines de N ( Ypma 1995). Un cas particulier de la méthode de Newton pour calculer les racines carrées était connu depuis l'Antiquité et est souvent appelé la méthode babylonienne .

La méthode de Newton a été utilisée par le mathématicien japonais du XVIIe siècle Seki Kōwa pour résoudre des équations à variable unique, bien que le lien avec le calcul fût absent. [1]

La méthode de Newton a été publiée pour la première fois en 1685 dans A Treatise of Algebra both Historical and Practical par John Wallis . [2] En 1690, Joseph Raphson a publié une description simplifiée dans Analysis aequationum universalis . [3] Raphson a également appliqué la méthode uniquement aux polynômes, mais il a évité le processus de réécriture fastidieux de Newton en extrayant chaque correction successive du polynôme original. Cela lui a permis de dériver une expression itérative réutilisable pour chaque problème. Enfin, en 1740, Thomas Simpson a décrit la méthode de Newton comme une méthode itérative pour résoudre des équations non linéaires générales en utilisant le calcul, donnant essentiellement la description ci-dessus. Dans la même publication, Simpson donne également la généralisation aux systèmes de deux équations et note que la méthode de Newton peut être utilisée pour résoudre des problèmes d'optimisation en mettant le gradient à zéro.

Arthur Cayley en 1879 dans le problème imaginaire de Newton – Fourier fut le premier à remarquer les difficultés de généralisation de la méthode de Newton à des racines complexes de polynômes avec un degré supérieur à 2 et des valeurs initiales complexes. Cela a ouvert la voie à l'étude de la théorie des itérations des fonctions rationnelles.

La méthode de Newton est une technique puissante - en général la convergence est quadratique: à mesure que la méthode converge vers la racine, la différence entre la racine et l'approximation est mise au carré (le nombre de chiffres précis double à peu près) à chaque étape. Cependant, il y a quelques difficultés avec la méthode.

Difficulté à calculer la dérivée d'une fonction

La méthode de Newton exige que la dérivée puisse être calculée directement. Une expression analytique du dérivé peut ne pas être facilement accessible ou être coûteuse à évaluer. Dans ces situations, il peut être approprié d'approximer la dérivée en utilisant la pente d'une droite passant par deux points proches de la fonction. L'utilisation de cette approximation aboutirait à quelque chose comme la méthode sécante dont la convergence est plus lente que celle de la méthode de Newton.

Échec de la convergence de la méthode vers la racine

Il est important de revoir la preuve de la convergence quadratique de la méthode de Newton avant de l'implémenter. Plus précisément, il convient de revoir les hypothèses formulées dans la preuve. Pour les situations où la méthode ne parvient pas à converger , c'est parce que les hypothèses formulées dans cette preuve ne sont pas satisfaites.

Dépasser

Si la première dérivée ne se comporte pas bien au voisinage d'une racine particulière, la méthode peut dépasser et diverger de cette racine. Un exemple de fonction à une racine, pour laquelle le dérivé ne se comporte pas bien au voisinage de la racine, est

pour lequel la racine sera dépassée et la séquence de x divergera. Pour a =1/2, la racine sera toujours dépassée, mais la séquence oscillera entre deux valeurs. Pour1/2< a <1 , la racine sera toujours dépassée mais la séquence convergera, et pour un ≥ 1 la racine ne sera pas dépassée du tout.

Dans certains cas, la méthode de Newton peut être stabilisée en utilisant une sur-relaxation successive , ou la vitesse de convergence peut être augmentée en utilisant la même méthode.

Point stationnaire

Si un point stationnaire de la fonction est rencontré, la dérivée est zéro et la méthode se terminera en raison de la division par zéro .

Mauvaise estimation initiale

Une erreur importante dans l'estimation initiale peut contribuer à la non-convergence de l'algorithme. Pour surmonter ce problème, on peut souvent linéariser la fonction qui est optimisée en utilisant le calcul, les logs, les différentiels ou même en utilisant des algorithmes évolutifs, comme le tunneling stochastique . Les bonnes estimations initiales sont proches de l'estimation finale des paramètres optimaux au niveau mondial. Dans la régression non linéaire, la somme des erreurs quadratiques (SSE) n'est «proche de» parabolique que dans la région des estimations finales des paramètres. Les estimations initiales trouvées ici permettront à la méthode de Newton – Raphson de converger rapidement. C'est seulement ici que la matrice de Hesse de l'ESS est positive et que la première dérivée de l'ESS est proche de zéro.

Atténuation de la non-convergence

Dans une implémentation robuste de la méthode de Newton, il est courant de placer des limites sur le nombre d'itérations, de lier la solution à un intervalle connu pour contenir la racine et de combiner la méthode avec une méthode de recherche de racine plus robuste.

Convergence lente pour les racines de multiplicité supérieure à 1

Si la racine recherchée a une multiplicité supérieure à un, le taux de convergence est simplement linéaire (erreurs réduites d'un facteur constant à chaque étape) à moins que des mesures spéciales ne soient prises. Lorsqu'il y a deux racines ou plus proches l'une de l'autre, plusieurs itérations peuvent être nécessaires avant que les itérations ne se rapprochent suffisamment de l'une d'elles pour que la convergence quadratique soit apparente. Cependant, si la multiplicitéde la racine est connue, l'algorithme modifié suivant préserve le taux de convergence quadratique: [4]

Cela équivaut à utiliser une sur-relaxation successive . Par contre, si la multiplicité m de la racine n'est pas connue, il est possible d'estimer après avoir effectué une ou deux itérations, puis utilisez cette valeur pour augmenter le taux de convergence.

Si la multiplicité m de la racine est finie alors g ( x ) = f ( x ) / f ′ ( x ) aura une racine au même endroit avec la multiplicité 1. L'application de la méthode de Newton pour trouver la racine de g ( x ) récupère convergence quadratique dans de nombreux cas, bien qu'elle implique généralement la dérivée seconde de f ( x ) . Dans un cas particulièrement simple, si f ( x ) = x m alors g ( x ) = x / m et la méthode de Newton trouve la racine en une seule itération avec

Supposons que la fonction f a un zéro en α , c'est-à-dire f  ( α ) = 0 , et f est différentiable dans un voisinage de α .

Si f est continûment différentiable et sa dérivée est différente de zéro à  α , alors il existe un voisinage de α tel que pour toutes les valeurs de départ x 0 dans ce voisinage, la séquence { x n } sera convergent à α . [5]

Si la fonction est continuellement différentiable et que sa dérivée n'est pas 0 en α et qu'elle a une dérivée seconde en α, alors la convergence est quadratique ou plus rapide. Si la dérivée seconde n'est pas 0 en α, alors la convergence est simplement quadratique. Si la troisième dérivée existe et est bornée dans un voisinage de α , alors:

Si la dérivée est 0 en α , alors la convergence n'est généralement que linéaire. Plus précisément, si f est continuellement différentiable deux fois, f ′ ( α ) = 0 et f ″ ( α ) ≠ 0 , alors il existe un voisinage de α tel que, pour toutes les valeurs de départ x 0 dans ce voisinage, la séquence d'itérations converge linéairement, avec un taux 1/2 [6] Alternativement, si f ′ ( α ) = 0 et f ′ ( x ) ≠ 0 pour xα , x  dans un voisinage U de α , α étant un zéro de multiplicité r , et si fC r ( U ) , alors il existe un voisinage de α tel que, pour toutes les valeurs de départ x 0 dans ce voisinage, la suite d'itérations converge linéairement.

Cependant, même la convergence linéaire n'est pas garantie dans les situations pathologiques.

En pratique, ces résultats sont locaux et le voisinage de convergence n'est pas connu à l'avance. Mais il y a aussi quelques résultats sur la convergence globale: par exemple, étant donné un voisinage droit U + de α , si f est deux fois dérivable dans U + et si f ′ ≠ 0 , f · f ″ > 0 dans U + , alors, pour chaque x 0 dans U + la séquence x k décroît de façon monotone jusqu'à α .

Preuve de la convergence quadratique pour la méthode itérative de Newton

Selon le théorème de Taylor , toute fonction f  ( x ) qui a une dérivée seconde continue peut être représentée par un développement autour d'un point proche d'une racine de f  ( x ) . Supposons que cette racine soit α . Alors le développement de f  ( α ) autour de x n est:

où la forme de Lagrange du reste de l'expansion de la série Taylor est

ξ n est entre x n et α .

Puisque α est la racine, ( 1 ) devient:

Diviser l'équation ( 2 ) par f ′ ( x n ) et réorganiser donne

En se rappelant que x n + 1 est défini par

on trouve que

C'est-à-dire,

Prendre la valeur absolue des deux côtés donne

L'équation ( 6 ) montre que le taux de convergence est au moins quadratique si les conditions suivantes sont satisfaites:

  1. f ′ ( x ) ≠ 0 ; pour tout xI , où I est l'intervalle [ α - r , α + r ] pour certains r ≥ | α - x 0 | ;
  2. f ″ ( x ) est continue, pour tout xI ;
  3. x 0 est suffisamment proche de la racine α .

Le terme suffisamment proche dans ce contexte signifie ce qui suit:

  1. L'approximation de Taylor est suffisamment précise pour que nous puissions ignorer les termes d'ordre supérieur;
  2. pour certains C <∞ ;
  3. pour n , n ≥ 0 et C satisfaisant la condition b.

Enfin, ( 6 ) peut être exprimé de la manière suivante:

M est le supremum du coefficient variable de ε n 2 sur l'intervalle I défini à la condition 1, soit:

Le point initial x 0 doit être choisi de telle sorte que les conditions 1 à 3 soient satisfaites, où la troisième condition exige que M | ε 0 | <1 .

Bassins d'attraction

Les sous-ensembles disjoints des bassins d'attraction - les régions de la droite numérique réelle telles que dans chaque région, l'itération à partir de n'importe quel point mène à une racine particulière - peuvent être infinies en nombre et arbitrairement petites. Par exemple, [7] pour la fonction f  ( x ) = x 3 - 2 x 2 - 11 x + 12 = ( x - 4) ( x - 1) ( x + 3) , les conditions initiales suivantes sont dans des bassins successifs d'attraction:

La convergence de la méthode de Newton n'est garantie que si certaines conditions sont remplies. Si les hypothèses faites dans la preuve de la convergence quadratique sont satisfaites, la méthode convergera. Pour les sous-sections suivantes, l'échec de la convergence de la méthode indique que les hypothèses formulées dans la preuve n'ont pas été satisfaites.

Mauvais points de départ

Dans certains cas, les conditions de la fonction nécessaires à la convergence sont satisfaites, mais le point choisi comme point initial n'est pas dans l'intervalle où la méthode converge. Cela peut arriver, par exemple, si la fonction dont la racine est recherchée s'approche de zéro asymptotiquement lorsque x va vers ou −∞ . Dans de tels cas, une méthode différente, telle que la bissection , doit être utilisée pour obtenir une meilleure estimation du zéro à utiliser comme point initial.

Le point d'itération est stationnaire

Considérez la fonction:

Il a un maximum à x = 0 et des solutions de f  ( x ) = 0 à x = ± 1 . Si nous commençons à itérer à partir du point stationnaire x 0 = 0 (où la dérivée est zéro), x 1 sera indéfini, car la tangente à (0,1) est parallèle à l' axe des x :

Le même problème se produit si, au lieu du point de départ, un point d'itération est stationnaire. Même si la dérivée est petite mais non nulle, la prochaine itération sera une approximation bien pire.

Le point de départ entre dans un cycle

Les droites tangentes de x 3 - 2 x + 2 à 0 et 1 coupent l' axe x à 1 et 0 respectivement, illustrant pourquoi la méthode de Newton oscille entre ces valeurs pour certains points de départ.

Pour certaines fonctions, certains points de départ peuvent entrer dans un cycle infini, empêchant la convergence. Laisser

et prenez 0 comme point de départ. La première itération produit 1 et la deuxième itération retourne à 0 afin que la séquence alterne entre les deux sans converger vers une racine. En fait, ce 2-cycle est stable: il existe des voisinages autour de 0 et autour de 1 à partir desquels tous les points itèrent asymptotiquement vers le 2-cycle (et donc pas vers la racine de la fonction). En général, le comportement de la séquence peut être très complexe (voir fractale de Newton ). La vraie solution de cette équation est−1.769 292 35 ….

Problèmes dérivés

Si la fonction n'est pas continuellement différentiable dans un voisinage de la racine, alors il est possible que la méthode de Newton diverge et échoue toujours, à moins que la solution ne soit devinée du premier coup.

Le dérivé n'existe pas à la racine

Un exemple simple de fonction où la méthode de Newton diverge consiste à essayer de trouver la racine cubique de zéro. La racine cubique est continue et infiniment différentiable, sauf pour x = 0 , où sa dérivée n'est pas définie:

Pour tout point d'itération x n , le prochain point d'itération sera:

L'algorithme dépasse la solution et atterrit de l'autre côté de l' axe y , plus loin qu'il ne l'était initialement; l'application de la méthode de Newton double en fait les distances de la solution à chaque itération.

En fait, les itérations divergent à l'infini pour tout f  ( x ) = | x | α , où 0 < α < 1/2. Dans le cas limite de α = 1/2(racine carrée), les itérations alterneront indéfiniment entre les points x 0 et - x 0 , donc elles ne convergent pas non plus dans ce cas.

Dérivé discontinu

Si la dérivée n'est pas continue à la racine, alors la convergence peut ne pas se produire dans n'importe quel voisinage de la racine. Considérez la fonction

Son dérivé est:

Dans n'importe quel voisinage de la racine, cette dérivée continue de changer de signe lorsque x s'approche de 0 à partir de la droite (ou de la gauche) tandis que f  ( x ) ≥ x - x 2 > 0 pour 0 < x <1 .

Donc f  ( x )/f ′ ( x ) est illimité près de la racine, et la méthode de Newton divergera presque partout dans n'importe quel voisinage de celle-ci, même si:

  • la fonction est différentiable (et donc continue) partout;
  • le dérivé à la racine est différent de zéro;
  • f est infiniment différentiable sauf à la racine; et
  • le dérivé est borné dans un voisinage de la racine (contrairement à f  ( x )/f ′ ( x )).

Convergence non quadratique

Dans certains cas, les itérations convergent mais ne convergent pas aussi rapidement que promis. Dans ces cas, les méthodes plus simples convergent aussi rapidement que la méthode de Newton.

Dérivé zéro

Si la première dérivée est nulle à la racine, alors la convergence ne sera pas quadratique. Laisser

alors f ′ ( x ) = 2 x et par conséquent

La convergence n'est donc pas quadratique, même si la fonction est infiniment différentiable partout.

Des problèmes similaires se produisent même lorsque la racine est seulement "presque" double. Par exemple, laissez

Ensuite, les premières itérations commençant à x 0 = 1 sont

x 0 = 1
x 1 = 0,500 250 376
x 2 = 0.251 062 828
x 3 = 0,127 507 934
x 4 = 0,067 671 976
x 5 = 0,041 224 176
x 6 = 0,032 741 218
x 7 = 0,031 642 362

il faut six itérations pour atteindre un point où la convergence semble quadratique.

Pas de dérivé secondaire

S'il n'y a pas de deuxième dérivée à la racine, alors la convergence peut ne pas être quadratique. Laisser

Puis

Et

sauf lorsque x = 0 où il n'est pas défini. Étant donné x n ,

qui a environ 4/3fois plus de bits de précision que x n . C'est moins que les 2 fois plus qui seraient nécessaires pour la convergence quadratique. La convergence de la méthode de Newton (dans ce cas) n'est donc pas quadratique, même si: la fonction est continuellement différentiable partout; la dérivée n'est pas nulle à la racine; et f est infiniment différentiable sauf à la racine désirée.

Fonctions complexes

Bassins d'attraction pour x 5 - 1 = 0 ; plus sombre signifie plus d'itérations à converger.

Lorsqu'il s'agit de fonctions complexes , la méthode de Newton peut être directement appliquée pour trouver leurs zéros. [8] Chaque zéro a un bassin d'attraction dans le plan complexe, l'ensemble de toutes les valeurs de départ qui font converger la méthode vers ce zéro particulier. Ces ensembles peuvent être mappés comme dans l'image montrée. Pour de nombreuses fonctions complexes, les limites des bassins d'attraction sont des fractales .

Dans certains cas, il y a des régions du plan complexe qui ne sont dans aucun de ces bassins d'attraction, ce qui signifie que les itérations ne convergent pas. Par exemple, [9] si l'on utilise une condition initiale réelle pour rechercher une racine de x 2 + 1 , toutes les itérations suivantes seront des nombres réels et donc les itérations ne peuvent pas converger vers l'une ou l'autre racine, puisque les deux racines ne sont pas réelles. Dans ce cas, presque toutes les conditions initiales réelles conduisent à un comportement chaotique , tandis que certaines conditions initiales itèrent soit à l'infini, soit à la répétition de cycles de toute longueur finie.

Curt McMullen a montré que pour tout algorithme purement itératif possible similaire à la méthode de Newton, l'algorithme diverge sur certaines régions ouvertes du plan complexe lorsqu'il est appliqué à un polynôme de degré 4 ou supérieur. Cependant, McMullen a donné un algorithme généralement convergent pour les polynômes de degré 3. [10]

Méthode du troisième ordre de Chebyshev

Itération Nash – Moser

Systèmes d'équations non linéaires

k variables, k fonctions

On peut aussi utiliser la méthode de Newton pour résoudre des systèmes de k équations (non linéaires), ce qui revient à trouver les zéros de fonctions continuellement différentiables F  : ℝ k → ℝ k . Dans la formulation donnée ci-dessus, il faut alors laisser multiplier par l'inverse de la matrice jacobienne k × k J F ( x n ) au lieu de diviser par f ′ ( x n ) :

Plutôt que de calculer l'inverse de la matrice jacobienne, on peut gagner du temps et augmenter la stabilité numérique en résolvant le système d'équations linéaires

pour l'inconnu x n + 1 - x n .

k variables, m équations, avec m > k

La variante k- dimensionnelle de la méthode de Newton peut également être utilisée pour résoudre des systèmes de plus de k équations (non linéaires) si l'algorithme utilise l' inverse généralisé de la matrice jacobienne non carrée J + = ( J T J ) −1 J T au lieu de l'inverse de J. Si le système non linéaire n'a pas de solution, la méthode tente de trouver une solution au sens des moindres carrés non linéaires . Voir Algorithme de Gauss – Newton pour plus d'informations.

Equations non linéaires dans un espace de Banach

Une autre généralisation est la méthode de Newton pour trouver une racine d'un F fonctionnel défini dans un espace de Banach . Dans ce cas, la formulation est

F ′ ( X n ) est la dérivée de Fréchet calculée en X n . Il faut que la dérivée de Fréchet soit inversible bornée à chaque X n pour que la méthode soit applicable. Une condition d'existence et de convergence vers une racine est donnée par le théorème de Newton-Kantorovich . [11]

Équations non linéaires sur des nombres p -adiques

Dans l' analyse p -adique, la méthode standard pour montrer une équation polynomiale dans une variable a une racine p -adique est le lemme de Hensel , qui utilise la récursivité de la méthode de Newton sur les nombres p -adiques. En raison du comportement plus stable de l'addition et de la multiplication dans les nombres p -adiques par rapport aux nombres réels (en particulier, la boule unitaire dans les p -adics est un anneau), la convergence dans le lemme de Hensel peut être garantie sous des hypothèses beaucoup plus simples que dans la méthode classique de Newton sur la ligne réelle.

Méthode de Newton – Fourier

La méthode de Newton-Fourier est l' extension de Joseph Fourier de la méthode de Newton pour fournir des limites sur l'erreur absolue de l'approximation de la racine, tout en fournissant une convergence quadratique.

Supposons que f  ( x ) soit deux fois continuellement différentiable sur [ a , b ] et que f contienne une racine dans cet intervalle. Supposons que f ′ ( x ), f ″ (x) ≠ 0 sur cet intervalle (c'est le cas par exemple si f  ( a ) <0 , f  ( b )> 0 , et f ′ ( x )> 0 , et f ″ ( x )> 0 sur cet intervalle). Cela garantit qu'il existe une racine unique sur cet intervalle, appelez-la α . S'il est concave vers le bas au lieu de concave vers le haut, remplacez f  ( x ) par - f  ( x ) car ils ont les mêmes racines.

Soit x 0 = b l'extrémité droite de l'intervalle et soit z 0 = a l'extrémité gauche de l'intervalle. Étant donné x n , définissez

qui est juste la méthode de Newton comme avant. Puis définissez

où le dénominateur est f ′ ( x n ) et non f ′ ( z n ) . Les itérations x n seront strictement décroissantes jusqu'à la racine tandis que les itérations z n augmenteront strictement jusqu'à la racine. Aussi,

de sorte que la distance entre x n et z n diminue quadratiquement.

Méthodes Quasi-Newton

Lorsque le jacobien est indisponible ou trop coûteux à calculer à chaque itération, une méthode quasi-Newton peut être utilisée.

q-analogique

La méthode de Newton peut être généralisée avec le q-analogue de la dérivée habituelle. [12]

Modifications des méthodes de Newton

Procédure de Maehly

Une équation non linéaire a plusieurs solutions en général. Mais si la valeur initiale n'est pas appropriée, la méthode de Newton peut ne pas converger vers la solution souhaitée ou peut converger vers la même solution trouvée précédemment. Quand on a déjà trouvé N solutions de, alors la racine suivante peut être trouvée en appliquant la méthode de Newton à l'équation suivante: [13] [14]

Cette méthode est appliquée pour obtenir des zéros de la fonction de Bessel du second type. [15]

Méthode Newton modifiée de Hirano

La méthode de Newton modifiée de Hirano est une modification conservant la convergence de la méthode de Newton et évitant l'instabilité. [16] Il est développé pour résoudre des polynômes complexes.

Intervalle méthode de Newton

La combinaison de la méthode de Newton avec l' arithmétique des intervalles est très utile dans certains contextes. Cela fournit un critère d'arrêt plus fiable que les critères habituels (qui sont une petite valeur de la fonction ou une petite variation de la variable entre des itérations consécutives). En outre, cela peut détecter des cas où la méthode de Newton converge théoriquement mais diverge numériquement en raison d'une précision en virgule flottante insuffisante (c'est généralement le cas pour les polynômes de grand degré, où un très petit changement de la variable peut changer radicalement la valeur de la fonction ; voir le polynôme de Wilkinson ). [17] [18]

Considérer , où est un intervalle réel, et supposons que nous ayons une extension d'intervalle de , ce qui signifie que prend comme entrée un intervalle et sort un intervalle tel que:

Nous supposons également que , donc en particulier a au plus une racine dans . Nous définissons ensuite l'opérateur de Newton intervalle par:

. Notez que l'hypothèse sur implique que est bien défini et est un intervalle (voir l' arithmétique des intervalles pour plus de détails sur les opérations d'intervalle). Cela conduit naturellement à la séquence suivante:

Le théorème de la valeur moyenne garantit que s'il existe une racine de dans , alors c'est aussi dans . De plus, l'hypothèse sur s'assure que est au plus la moitié de la taille de lorsque est le milieu de , donc cette séquence converge vers , où est la racine de dans .

Si contient strictement , l'utilisation de la division d'intervalle étendue produit une union de deux intervalles pour  ; les racines multiples sont donc automatiquement séparées et délimitées.

Problèmes de minimisation et de maximisation

La méthode de Newton peut être utilisée pour trouver un minimum ou un maximum d'une fonction . La dérivée est zéro à un minimum ou à un maximum, donc les minima et maxima locaux peuvent être trouvés en appliquant la méthode de Newton à la dérivée. L'itération devient:

Inverses multiplicatifs des nombres et des séries de puissance

Une application importante est la division Newton – Raphson , qui permet de trouver rapidement l' inverse d'un nombre a , en utilisant uniquement la multiplication et la soustraction, c'est-à-dire le nombre x tel que1/X= a . Nous pouvons reformuler cela en trouvant le zéro de f ( x ) = 1/X- un . On a f ′ ( x ) = - 1/x 2.

L'itération de Newton est

Par conséquent, l'itération de Newton n'a besoin que de deux multiplications et d'une soustraction.

Cette méthode est également très efficace pour calculer l'inverse multiplicatif d'une série de puissance .

Résolution d'équations transcendantales

De nombreuses équations transcendantales peuvent être résolues en utilisant la méthode de Newton. Compte tenu de l'équation

avec g ( x ) et / ou h ( x ) une fonction transcendantale , on écrit

Les valeurs de x qui résolvent l'équation d'origine sont alors les racines de f  ( x ) , qui peuvent être trouvées via la méthode de Newton.

Obtention de zéros de fonctions spéciales

La méthode de Newton est appliquée au rapport des fonctions de Bessel afin d'obtenir sa racine. [19]

Vérification numérique des solutions d'équations non linéaires

Une vérification numérique des solutions d'équations non linéaires a été établie en utilisant la méthode de Newton plusieurs fois et en formant un ensemble de solutions candidates. [20] [21]

Modélisation CFD

Une procédure itérative de Newton-Raphson a été utilisée afin d'imposer une condition aux limites de Dirichlet stable dans la CFD , comme stratégie assez générale pour modéliser la distribution du courant et du potentiel pour les piles de cellules électrochimiques. [22]

Racine carrée

Considérons le problème de trouver la racine carrée d'un nombre a , c'est-à-dire le nombre positif x tel que x 2 = a . La méthode de Newton est l'une des nombreuses méthodes de calcul des racines carrées . Nous pouvons reformuler cela en trouvant le zéro de f ( x ) = x 2 - a . On a f ′ ( x ) = 2 x .

Par exemple, pour trouver la racine carrée de 612 avec une estimation initiale x 0 = 10 , la séquence donnée par la méthode de Newton est:

où les chiffres corrects sont soulignés. Avec seulement quelques itérations, on peut obtenir une solution précise à plusieurs décimales.

Réorganiser la formule comme suit donne la méthode babylonienne de recherche des racines carrées :

c'est-à-dire la moyenne arithmétique de la supposition, x n etune/x n.

Solution de cos ( x ) = x 3

Considérons le problème de trouver le nombre positif x avec cos ( x ) = x 3 . Nous pouvons reformuler cela en trouvant le zéro de f ( x ) = cos ( x ) - x 3 . On a f ′ ( x ) = −sin ( x ) - 3 x 2 . Puisque cos ( x ) ≤ 1 pour tout x et x 3 > 1 pour x > 1 , nous savons que notre solution est comprise entre 0 et 1.

Par exemple, avec une estimation initiale x 0 = 0,5 , la séquence donnée par la méthode de Newton est (notez qu'une valeur de départ de 0 conduira à un résultat indéfini, montrant l'importance d'utiliser un point de départ proche de la solution):

Les chiffres corrects sont soulignés dans l'exemple ci-dessus. En particulier, x 6 est correct à 12 décimales. On voit que le nombre de chiffres corrects après la virgule décimale passe de 2 (pour x 3 ) à 5 et 10, illustrant la convergence quadratique.

Ce qui suit est un exemple d'implémentation de la méthode de Newton dans le langage de programmation Julia pour trouver une racine d'une fonction fqui a un dérivé fprime.

La supposition initiale sera x 0 = 1 et la fonction sera f ( x ) = x 2 - 2 de sorte que f ′ ( x ) = 2 x .

Chaque nouvelle itération de la méthode de Newton sera désignée par x1. Nous vérifierons lors du calcul si le dénominateur ( yprime) devient trop petit (plus petit que epsilon), ce qui serait le cas si f ′ ( x n ) ≈ 0 , sinon une grande quantité d'erreur pourrait être introduite.

x0  =  1  # La première estimation f ( x )  =  x ^ 2  -  2  # La fonction dont nous essayons de trouver la racine fprime ( x )  =  2 x  # La dérivée de la fonction tolérance  =  1e-7  # La précision à 7 chiffres est souhaité epsilon  =  1e-14  # Ne pas diviser par un nombre plus petit que ce maxIterations  =  20  # Ne pas permettre aux itérations de se poursuivre indéfiniment solutionFound  =  false  # N'ont pas encore convergé vers une solutionpour  i  =  1 : maxIterations  y  =  f ( x0 )  yprime  =  fprime ( x0 ) if  abs ( yprime )  <  epsilon  # Stop si le dénominateur est trop petit  break  end global  x1  =  x0  -  y / yprime  # Faire le calcul de Newton si  abs ( x1  -  x0 )  <=  tolérance  # Arrêter lorsque le résultat est dans la tolérance désirée  globale  solutionFound  =  vraie  pause  fin global  x0  =  x1  # Mettre à jour x0 pour redémarrer le processus finif  solutionFound  println ( "Solution:" ,  x1 )  # x1 est une solution dans la tolérance et le nombre maximum d'itérations else  println ( "N'a pas convergé" )  # La méthode de Newton n'a pas convergé fin

  • Processus delta-carré d'Aitken
  • Méthode de bisection
  • Méthode d'Euler
  • Racine carrée inverse rapide
  • Notation de Fisher
  • Descente graduelle
  • Racine carrée entière
  • Théorème de Kantorovich
  • La méthode de Laguerre
  • Méthodes de calcul des racines carrées
  • Méthode d'optimisation de Newton
  • Extrapolation de Richardson
  • Algorithme de recherche de racine
  • Méthode sécante
  • La méthode de Steffensen
  • Méthode du sous-gradient

  1. ^ "Chapitre 2. Seki Takakazu" . Mathématiques japonaises à l'époque d'Edo . Bibliothèque nationale de la Diète . Récupéré le 24 février 2019 .
  2. ^ Wallis, John (1685). Un traité d'algèbre, à la fois historique et pratique . Oxford: Richard Davis. doi : 10.3931 / e-rara-8842 .
  3. ^ Raphson, Joseph (1697). Analyse Æequationum Universalis (en latin) (2e éd.). Londres: Thomas Bradyll. doi : 10.3931 / e-rara-13516 .
  4. ^ "Méthodes de Newton accélérées et modifiées" . Archivé de l'original le 24 mai 2019 . Récupéré le 4 mars 2016 .
  5. ^ Ryaben'kii, Victor S .; Tsynkov, Semyon V. (2006), Une introduction théorique à l'analyse numérique , CRC Press, p. 243, ISBN 9781584886075.
  6. ^ Süli et Mayers 2003 , exercice 1.6
  7. ^ Dence, Thomas (novembre 1997). "Cubiques, chaos et méthode de Newton". Gazette mathématique . 81 (492): 403–408. doi : 10.2307 / 3619617 . JSTOR  3619617 .
  8. ^ Henrici, Peter (1974). "Analyse Complexe Appliquée et Computationnelle". 1 . Citer le journal nécessite |journal=( aide )
  9. ^ Strang, Gilbert (janvier 1991). "Une recherche chaotique pour i ". The College Mathematics Journal . 22 : 3–12. doi : 10.2307 / 2686733 . JSTOR  2686733 .
  10. ^ McMullen, Curt (1987). "Familles de cartes rationnelles et algorithmes itératifs de recherche de racines" (PDF) . Annales des mathématiques . Deuxième série. 125 (3): 467–493. doi : 10.2307 / 1971408 . JSTOR  1971408 .
  11. ^ Yamamoto, Tetsuro (2001). "Développements historiques dans l'analyse de convergence pour les méthodes de Newton et de Newton". Dans Brezinski, C .; Wuytack, L. (éd.). Analyse numérique: développements historiques au 20e siècle . Hollande du Nord. 241-263. ISBN 0-444-50617-9.
  12. ^ Rajkovic, Stankovic et Marinkovic 2002[ citation courte incomplète ]
  13. ^ Appuyez sur et al. 1992[ citation courte incomplète ]
  14. ^ Stoer et Bulirsch 1980[ citation courte incomplète ]
  15. ^ Zhang et Jin 1996[ citation courte incomplète ]
  16. ^ Murota, Kazuo (1982). "Convergence globale d'une itération de Newton modifiée pour les équations algébriques". SIAM J. Numer. Anal . 19 (4): 793–799. doi : 10.1137 / 0719055 .
  17. ^ Moore, RE (1979). Méthodes et applications de l'analyse par intervalles (Vol. 2). Siam.
  18. ^ Hansen, E. (1978). Formes d'intervalle de la méthode Newtons. Computing , 20 (2), 153–163.
  19. ^ Gil, Segura et Temme (2007) [ citation courte incomplète ]
  20. ^ Kahan  ( 1968 ) [ citation courte incomplète ]
  21. ^ Krawczyk (1969)[ citation courte incomplète ] [ citation courte incomplète ]
  22. ^ Colli, AN; Girault, HH (juin 2017). "Stratégie compacte et générale pour résoudre la distribution de courant et de potentiel dans les cellules électrochimiques composées d'électrodes monopolaires et bipolaires massives". Journal de la société électrochimique . 164 (11): E3465 à E3472. doi : 10.1149 / 2.0471711jes . hdl : 11336/68067 .

  • Gil, A .; Segura, J .; Temme, NM (2007). Méthodes numériques pour les fonctions spéciales . Société de mathématiques industrielles et appliquées. ISBN 978-0-89871-634-4.
  • Süli, Endre ; Mayers, David (2003). Une introduction à l'analyse numérique . La presse de l'Universite de Cambridge. ISBN 0-521-00794-1.

  • Kendall E. Atkinson, Une introduction à l'analyse numérique , (1989) John Wiley & Sons, Inc, ISBN  0-471-62489-6
  • Tjalling J. Ypma, Développement historique de la méthode Newton – Raphson, SIAM Review 37 (4), 531–551, 1995. doi : 10.1137 / 1037125 .
  • Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimisation numérique: aspects théoriques et pratiques . Universitext (Deuxième édition révisée de la traduction française de 1997). Berlin: Springer-Verlag. pp. xiv + 490. doi : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. MR  2265882 .
  • P. Deuflhard, Méthodes de Newton pour les problèmes non linéaires. Invariance affine et algorithmes adaptatifs. Série Springer en mathématiques computationnelles, vol. 35. Springer, Berlin, 2004. ISBN  3-540-21099-7 .
  • CT Kelley, Solving Nonlinear Equations with Newton's Method , no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN  0-89871-546-6 .
  • JM Ortega, WC Rheinboldt, Solution itérative d'équations non linéaires dans plusieurs variables. Classics in Applied Mathematics, SIAM, 2000. ISBN  0-89871-461-3 .
  • Appuyez sur WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Chapitre 9. Recherche de racine et ensembles non linéaires d'échantillonnage d'importance d'équations" . Recettes numériques: l'art de l'informatique scientifique (3e éd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.. Voir en particulier les sections 9.4 , 9.6 et 9.7 .
  • Avriel, Mordecai (1976). Programmation non linéaire: analyse et méthodes . Prentice Hall. pp. 216-221. ISBN 0-13-623603-0.

  • "Méthode de Newton" , Encyclopédie des mathématiques , EMS Press , 2001 [1994]
  • Weisstein, Eric W. "Méthode de Newton" . MathWorld .
  • Méthode de Newton, Citizendium.
  • Mathews, J., Les méthodes de Newton accélérées et modifiées, Notes de cours.
  • Wu, X., Racines des équations, Notes de cours.