La méthode de Newton et son histoire

23 janvier 2012

Lycée Marcel Pagnol

André BONNET

A.P.M.E.P. Université de Provence IREM

Newton (1643 – 1727) – La méthode des fluxions et des suites infinies - 1736

L’exemplaire personnel de Newton de Philosophiae Naturalis Principia Mathematica

annoté par lui-même (édition de 1687)

Un bref aperçu de la théorie des fluxions

• Soit un carré de coté 𝑥, on note 𝑦 son aire, de sorte que 𝑦 = 𝑥2 .

• Si, à un instant, la fluxion de 𝑥 est 𝑥 𝑜 quelle est la valeur de 𝑦 𝑜 ?

• La réponse peut être donnée, soit par le calcul, soit par un raisonnement géométrique à partir de la figure ci-contre.

• Du point de vue géométrique, 𝑦 est la somme de l’aire du carré de côtés 𝑥𝑜, du double de l’aire du rectangle de côtés 𝑥𝑜et 𝑥 𝑜𝑡 et du petit carré de côté 𝑥 𝑜𝑡 .

• Conclusion : 𝑦 = 𝑥𝑜

2 + 2𝑥𝑜𝑥 𝑜𝑡 + 𝑥 𝑜𝑡2

• Dont on déduit :

𝑦−𝑦𝑜

𝑡 = 2 𝑥𝑜𝑥 𝑜+ 𝑥 𝑜

2𝑡

• Puis 𝑦 𝑜 = 2 𝑥𝑜𝑥 𝑜

Les équations algébriques : formules de résolution exactes et méthodes numériques.

Les équations pour lesquelles on connait une formule donnant la (ou les) solution(s) sont peu nombreuses. Ce sont des équations algébriques du type 𝑓 𝑥 = 0 où 𝑓 𝑥 est une fonction polynôme.

• premier degré : 𝑎 𝑥 − 𝑏 = 0 , solution : 𝑏

𝑎

• second degré : 𝑎 𝑥2 + 𝑏 𝑥 + 𝑐 = 0

si ∆ = 𝑏2 − 4 𝑎 𝑐 > 0 solutions : −𝑏± ∆

2 𝑎

si ∆ = 𝑏2 − 4 𝑎 𝑐 = 0 solution : − 𝑏

2 𝑎

• troisième degré : 𝑥3 + 𝑝 𝑥 + 𝑞 = 0 méthode de Cardan (publiée en 1545)

si ∆ = 4 𝑝3 + 27 𝑞2 ≥ 0 solution : −𝑞− ∆/27

2

3

+−𝑞+ ∆/27

2

3

• quatrième degré : 𝑥4 = 𝑝 𝑥2 + 𝑞 𝑥 + 𝑟 méthode de Ferrari (1540) résolution par la méthode de Cardan d’une équation de degré 3 et utilisation des radicaux carrés.

La méthode de Newton fournit une valeur approchée, avec une très grande précision, d’une équation du type 𝑓 𝑥 = 0.

Les équations algébriques et leur résolution exacte. Niels Abel (1802-1829) et Evariste Galois (1811-1822) :

la fin d’un rêve!

Principe de la méthode de Newton

Principe de la méthode de Newton

Principe de la méthode de Newton

La méthode de Newton sur un exemple

Détermination de l’abscisse 𝑥1 du point d’intersection de l’axe 𝑂𝑥 et de la tangente en 𝑀0 à la courbe.

• On suppose que 𝑓 est définie, dérivable, monotone (croissante) sur 𝑎, 𝑏 et vérifiant la condition : 𝑓 𝑎 𝑓 𝑏 < 0.

On note 𝛼 l’unique solution ( sur 𝑎, 𝑏 ) de l’équation 𝑓 𝑥 = 0.

• Equation de la tangente 𝑇0 en 𝑀0 = 𝑥0 , 𝑓(𝑥0) :

𝑦 = 𝑓′ 𝑥0 𝑥 − 𝑥0 + 𝑓(𝑥0)

• Abscisse du point d’intersection de 𝑇1 et de l’axe 𝑂𝑥 :

𝑥1 = 𝑥0 −𝑓(𝑥0)

𝑓′(𝑥0)

sous réserve que 𝑓′(𝑥0) soit non nul.

• Dans l’exemple proposé, si on prend 𝑎 = 1 et 𝑏 = 5 , les conditions ci-dessus sont satisfaites et on constate que 𝑥1 ∈ [𝛼, 𝑥0] .

Détermination de 𝛼 comme limite d’une suite.

• En traçant la tangente 𝑇1 en 𝑀1 , on peut déterminer une nouvelle valeur approchée de 𝛼, la valeur 𝑥2 abscisse du point d’intersection de 𝑇1 et de l’axe 𝑂𝑥 .

• Sous réserve que la dérivée ne soit pas nulle on a :

𝑥2 = 𝑥1 −𝑓(𝑥1)

𝑓′(𝑥1)

• En itérant le procédé, on obtient une suite 𝑢𝑛 𝑛∈ℕ définie par :

𝑢0 = 𝑥0 et 𝑢𝑛+1 = 𝑢𝑛 −𝑓(𝑢𝑛)

𝑓′(𝑢𝑛)

• On peut démontrer que la suite 𝑢𝑛 𝑛∈ℕ est convergente et que : lim

𝑛→∞𝑢𝑛 = 𝛼 .

Deux algorithmes pour calculer une valeur approchée de 𝛼

𝜀 ← 10−8

𝑢 ← 𝑢0

𝑣 ← 𝑢0 −𝑓(𝑢0)

𝑓′(𝑢0)

𝑡𝑎𝑛𝑡 𝑞𝑢𝑒 𝑣 − 𝑢 > 𝜀 𝑓𝑎𝑖𝑟𝑒 ∶

𝑢 ← 𝑣

𝑣 ← 𝑢 −𝑓 𝑢

𝑓′ 𝑢

𝑎𝑓𝑓𝑖𝑐ℎ𝑒𝑟 𝑣

Condition de sortie de boucle : 𝑣 − 𝑢 ≤ 𝜀

𝜀 ← 10−8

𝑢 ← 𝑢0

𝑡𝑎𝑛𝑡 𝑞𝑢𝑒 𝑓 𝑢 − 𝜀 ∗ 𝑓 𝑢 + 𝜀 > 0 𝑓𝑎𝑖𝑟𝑒 ∶

𝑢 ← 𝑢 −𝑓 𝑢

𝑓′ 𝑢

𝑎𝑓𝑓𝑖𝑐ℎ𝑒𝑟 𝑢

Condition de sortie de boucle : 𝑢 − 𝛼 ≤ 𝜀

Test de l’algorithme sur l’équation : 𝑥3 − 2 𝑥 − 5 = 0 avec 𝑥0 = 3.

• Le programme Maple

f:= x-> x^3-2*x-5;

df:= x-> 3*x^2-2;

eps:= 10^(-9);

u:= 3.;

while f(u-eps)*f(u+eps)> eps do

u:= u - f(u)/df(u);

od;

f(u-eps);

f(u);

• Les résultats :

• A noter la convergence extrêmement rapide.

:= f x x3 2 x 5

:= df x 3 x2 2

:= eps1

100000000

:= u 3.

:= u 2.360000000

:= u 2.127196780

:= u 2.095136037

:= u 2.094551674

:= u 2.094551482

-.6 10-8

.5 10-8

La méthode de Newton telle qu’elle est exposée dans : "The method of fluxions, and infinite series" - parue en 1736

Traduction en français par M. de Buffon, intendant du jardin du Roy, parue en 1740

"Des empêchements fréquents produits (par des lettres d’opposants pleines d’objections) me dissuadèrent absolument de toute publication, car je risquais alors de perdre ma tranquillité, chose absolument essentielle pour moi ".

La correspondance de Newton et Barrow, juin 1669

Dès 1669, Newton fait connaître, dans sa correspondance à Barrow et à Collins, la méthode de résolution des équations affectées.

Ces derniers communiquent les résultats de Newton à Brownker, Oldembourg, qui les envoient à plusieurs autres géomètres : Slusius, Gregori, Bertet, Borelli, Vernon, Strode, …

La correspondance de Newton et Barrow, juin 1669

On constate ici, que Newton a mis au point sa méthode, au plus tard, au cours de l’année 1665.

La méthode de Newton exposée sur un exemple : l’équation 𝑦3 − 2 𝑦 − 5 = 0

Dans le texte de Newton : Dans la traduction de Buffon :

Les calculs faits par Newton

La détermination de 𝑝 et 𝑞 :

Les calculs présentés par Newton pour déterminer 𝑝 et 𝑞 sont très clairs. Par contre le calcul de 𝑟 est moins lisible. La valeur de 𝑞 prise par Newton pour le calcul de 𝑟 est

𝑞 = −0,054 alors qu’il devrait prendre − 0,061

11,23 , soit

𝑞 = − , 00543188

Programmes Maple pour déterminer 𝑟 :

> q:=-0.0054:

collect((q+r)^3,r);

collect(6,3*(q+r)^2,r);

collect(11,23*(q+r);

> 0.061-0.060642+0.0001837-.0000001;

11.23-0.068+0.0000;

Résultats : 𝒓 = − 𝟎,𝟎𝟎𝟎𝟓𝟒𝟏𝟔

𝟏𝟏,𝟏𝟔𝟐

et 𝒚 = 2,09455148

.061

r3 .0162 r2 .00008748 r .157464 10-6

6.3 r2 .06804 r .000183708

11.23 r .060642

.0005416

11.162

La contribution de Raphson (1648 – 1712)

• Newton calcule le complément à rajouter à la valeur approchée de 𝛼 déjà trouvée. Cela l’oblige à résoudre un problème du troisième degré différent à chaque fois.

• Raphson (1648 – 1712) présentera en 1690, dans

Analysis aequationum universalis une nouvelle méthode de résolution approchée des équations du troisième degré.

• Les équations qu’il traite sont de la forme :

𝑥3 − 𝑏 𝑥 = 𝑐 et il appliquera sa méthode à l’équation traitée par Newton.

• Pour cet exemple, il part de la valeur approchée

𝑔 = 2 et calcule le complément 𝑥 à rajouté à 𝑔 (pour obtenir une meilleure valeur approchée de 𝛼) par la formule suivante :

𝑥 = 5+2 𝑔−𝑔3

3 𝑔2−2 (𝑏 = 2 et 𝑐 = 5)

Il obtient ainsi la valeur

𝑔 + 𝑥 = 𝑔 + 5+2 𝑔−𝑔3

3 𝑔2−2

plus proche de 𝛼, qu’il utilise à nouveau etc ...

Les calculs de Raphson vérifiés par Maple

• 𝑥 =5+2 𝑔−𝑔3

3 𝑔2−2

est le complément à ajouter à 𝑔 pour obtenir la nouvelle valeur approchée de 𝛼.

Cette nouvelle valeur est : 𝑔 + 𝑥

c’est-à-dire :

𝑔 −𝑔3 − 2 𝑔 − 5

3 𝑔2 − 2

• Or l’équation de Newton est : 𝑦3 − 2 𝑦 − 5 = 0

donc 𝑔3 − 2 𝑔 − 5 est la valeur du premier membre pour 𝑦 = 𝑔 et

3 𝑔2 − 2 est la valeur de sa dérivée.

• On reconnait la fonction :

𝜙 𝑥 = 𝑥 − 𝑓(𝑥)

𝑓′(𝑥)

> phi:=x->(5+2*x-x^3)/(3*x^2-2);

g:=2.;

x:=phi(g);

g:=g+x;

x:=phi(g);

g:=g+x;

x:=phi(g);

g:=g+x;

:= x 5 2 x x3

3 x2 2

:= x .1000000000

:= g 2.100000000

:= x -.005431878896

:= g 2.094568121

:= x -.00001663930087

:= g 2.094551482

:= g 2.

La contribution de Simpson (1710-1761)

• Dans son "Essays on Several Curious and Useful Subjects in Speculative and Mix’d Mathematicks, Illustred by a Variety of Examples" publié à Londres en 1740, Simpson décrit "A new Method for solution of equations in Numbers" dans lequel il ne fait aucune référence à ses prédécesseurs, mais qui fait appel à la théorie des fluxions :

• Il montre en outre, sur l’exemple suivant :

1 − 𝑥 + 1 − 2 𝑥2 + 1 − 3𝑥3 − 2 = 0

que sa méthode s’applique aux équations non polynomiales.

Etude de la convergence vers α, tel que 𝑓 α = 0

• On exige de 𝑓 les propriétés suivantes :

- 𝑓 est deux fois dérivable sur un intervalle 𝐼 = [𝑎, 𝑏]

- 𝑓′ ne s′annule pas sur 𝐼 = [𝑎, 𝑏]

- 𝑓′′ garde un signe constant sur 𝐼 = [𝑎, 𝑏].

• On note 𝑢𝑛 𝑛∈ℕ la suite définie par :

𝑢0 = 𝑥0 et 𝑢𝑛+1 = 𝑢𝑛 −𝑓(𝑢𝑛)

𝑓′(𝑢𝑛)

• La suite 𝑢𝑛 𝑛∈ℕ est obtenue par itération de la fonction Φ définie par :

Φ 𝑥 = 𝑥 − 𝑓(𝑥)

𝑓′(𝑥)

• On peut alors montrer que :

– Si 𝑓′ et 𝑓′′ sont de signe contraire, en choisissant 𝑢𝑜 = 𝑎 les éléments de la suite 𝑢𝑛 sont dans l’intervalle [𝑎, α], la suite 𝑢𝑛 𝑛єℕ est croissante et a pour limite α.

– Si 𝑓′ et 𝑓′′ sont de même signe, en choisissant 𝑢𝑜 = 𝑏 les éléments de la suite 𝑢𝑛 sont dans l’intervalle [α, 𝑏], la suite 𝑢𝑛 𝑛єℕ est décroissante et a pour limite α.

Les quatre cas de figures

Etude de la rapidité de convergence

• On pose :

𝐾 = max𝑥∈𝐼

𝑓(𝑥) , 𝜇 = min𝑥∈𝐼

𝑓′(𝑥) , 𝑀 = max𝑥∈𝐼

𝑓′′(𝑥)

• On peut démontrer la relation suivante :

𝑢𝑛+1 − 𝛼 ≤ 𝐾 𝑀

𝜇𝑢𝑛 − 𝛼 2

• Dans l’exemple traité par Newton,

𝑎 = 2 ; 𝑏 = 3 ; 𝐾 = 0,061 ; 𝑀 = 12,6 et 𝜇 = 10

ce qui donne : 𝐾 𝑀

𝜇= 0.077

donc : 𝑢𝑛+1 − 𝛼 ≤ 0.077 𝑢𝑛 − 𝛼 2

• On en déduit que, avec 𝑢1 = 2,1 les erreurs dues à la méthode sont : 𝑢1 − 𝛼 < 0.1

𝑢2 − 𝛼 < 0.077 × 0.1 2 = 0.00077 𝑢3 − 𝛼 < 0.077 × 0.077 × 0.1 2 2 = 4.7 10−8

Le calcul des inverses par la méthode de Newton dans certains processeurs

• Le principe est le suivant :

chercher l’inverse de 𝑎 > 0 revient à résoudre l’équation 𝑓 𝑥 = 0

avec 𝑓 𝑥 =1

𝑥− 𝑎 .

• Si on applique la méthode de Newton, la fonction d’itération est :

Φ 𝑥 = 𝑥 −𝑓 𝑥

𝑓′ 𝑥= 𝑥 (2 − 𝑎 𝑥) .

La méthode de Newton appliquée au calcul de l’inverse

• On peut représenter Φ et les premiers termes de la suite 𝑢0 = 𝑥0, 𝑢1, 𝑢2 … sur la même figure.

• Sur cette figure, on voit que l’itération de Newton converge, à condition de prendre

comme valeur initiale 𝑢0 ∈ ]0,2

𝑎[. Donc,

on est devant le paradoxe suivant : "pour être sûr d’avoir une bonne initialisation

dans le calcul de 1

𝑎 , il faut avoir une idée

de 2

𝑎 ".

• Heureusement, les nombres à traiter sont donnés en virgule flottante; c'est-à-dire sous la forme 𝑚.𝐵𝑒 (avec par exemple 𝐵 = 10 comme base de la numération),

𝑚 ∈ [1

𝐵, 1[ et 𝑒 entier donc

2

𝑚∈]2 , 2𝐵]

et on peut prendre 𝑢0 = 1 .

Exemple d’un calcul par ordinateur

• Pour calculer le quotient

𝑄 = 0.42 107 / 0.37 10−11

il faut d’abord déterminer l’inverse de 0.37.

• En procédant par la méthode de Newton et en utilisant le logiciel Maple pour faire les calculs, on obtient les résultats ci-contre.

• On peut voir que ce calcul est très rapide et n’utilise que des multiplications en virgule flottante.

• Le résultat obtenu avec une calculatrice

est 1

0,37= 2,702702703

Leibniz (1646 – 1716) - Acta Eruditorium - 1691

Après plus de trois siècles, les noms de Newton et Leibniz sont encore présents dans :

La formule du binôme (de Newton)

𝑎 + 𝑏 𝑛 = 𝑛𝑘

𝑎𝑘𝑏𝑛−𝑘𝑛𝑘=0

La résolution numérique des équations (par la méthode de Newton).

La dérivation itérée d’une somme (formule de Leibniz)

𝑓 + 𝑔 (𝑛) = 𝑛𝑘

𝑓(𝑘)𝑔(𝑛−𝑘)𝑛𝑘=0

La méthode de Héron pour calculer une racine carrée

Héron d’Alexandrie (premier siècle après J.-C. - début du IIe siècle)

Le point de vue géométrique Le calcul de 𝑢𝑛

• En prenant pour 𝑢1 la moyenne

arithmétique de 𝑢𝑜 et de 𝑎

𝑢𝑜 on otient :

𝑢1 =1

2𝑢𝑜 +

𝑎

𝑢𝑜

• Plus généralement :

𝑢𝑛+1 =1

2𝑢𝑛 +

𝑎

𝑢𝑛

• Lien avec Newton-Raphson-Simpson :

si 𝑓 𝑥 = 𝑥2 − 𝑎

𝑢𝑛+1 = 𝑢𝑛 − 𝑓 𝑢𝑛

𝑓′ 𝑢𝑛

= 𝑢𝑛 - 𝑢𝑛

2 − 𝑎

2 𝑢𝑛

Le calcul de la racine de 2, chez les babyloniens

La tablette babylonienne YBC-7289 Découverte en 1912 en Irak sur les ruines de Babylone, propriété de l’Université de Yale, taille 8 cm, datation entre : – 1900 et – 1600.

• Sur le coté = 30 = 𝑐

• Sur la diagonale :

= 1 24 51 10 = 𝑎

= 42 25 35 = 𝑏

• Converti en numération décimale :

𝑎 = 1 +24

60+

51

60×60+

10

60×60×60

=30547

21600 ~ 1,4142129

or 2 = 1,414213562

• Les nombres 𝑎, 𝑏 et 𝑐 sont liés par la relation : 𝑏 = 𝑎 × 𝑐 .

• Le nombre 𝑏 est la mesure de la diagonale du carré de coté 𝑐 .

L’équation de Kepler (1571-1630)

Les lois de Kepler (1605 et 1618)

• Toute planète a une orbite elliptique dont le soleil est un foyer.

• Le mouvement de la planète sur son orbite s’effectue suivant la loi des aires.

• La relation entre la période T et le demi-grand axe 𝑎 de l’ellipse est :

𝑎3

𝑇2 = 𝑐𝑡𝑒

• Si 𝑒 désigne l’excentricité de l’ellipse et 𝑢 l’anomalie excentrique, c’est-à-dire l’angle 𝐴𝑂𝑃 , la position de la planète au temps 𝑡 , est donnée par la valeur de 𝑢 satisfaisant :

𝑢 − 𝑒 sin 𝑢 =2 𝜋

𝑇𝑡 − 𝑡𝑜

c’est l’équation de Kepler.

S = soleil , P = planète, A = périhélie, A’ = aphélie

La trajectoire d’un projectile selon Tartaglia (1499 - 1557) dans une édition de 1606

La correspondance entre Newton et Leibniz, 1676