4.9 : Méthode de Newton
- Décrivez les étapes de la méthode de Newton.
- Expliquez ce que signifie un processus itératif.
- Reconnaissez quand la méthode de Newton ne fonctionne pas.
- Appliquez des processus itératifs à différentes situations.
Dans de nombreux domaines des mathématiques pures et appliquées, nous souhaitons trouver des solutions à une équation de la forme. Cependant,f(x)=0. pour la plupart des fonctions, il est difficile, voire impossible, de calculer leurs zéros de manière explicite. Dans cette section, nous examinons une technique qui fournit un moyen très efficace d'approximer les zéros des fonctions. Cette technique utilise des approximations de lignes tangentes et est à l'origine de la méthode souvent utilisée par les calculateurs et les ordinateurs pour trouver des zéros.
Décrire la méthode de Newton
Considérez la tâche de trouver les solutions def(x)=0. Sif est le polynôme du premier degréf(x)=ax+b, alors la solution def(x)=0 est donnée par la formulex=−ba. Sif est le polynôme du second degréf(x)=ax2+bx+c, les solutions def(x)=0 peuvent être trouvées en utilisant la formule quadratique. Cependant, pour les polynômes de degré 3 ou plus, ilf devient plus compliqué de trouver les racines de. Bien qu'il existe des formules pour les polynômes du troisième et du quatrième degré, elles sont assez compliquées. De plus, si f est un polynôme de degré 5 ou plus, on sait que de telles formules n'existent pas. Par exemple, considérez la fonction
f(x)=x5+8x4+4x3−2x−7.
Il n'existe aucune formule permettant de trouver les solutions à des difficultésf(x)=0. similaires pour les fonctions non polynomiales. Par exemple, considérez la tâche de trouver des solutions àtan(x)−x=0. Aucune formule simple n'existe pour les solutions de cette équation. Dans de tels cas, nous pouvons utiliser la méthode de Newton pour approximer les racines.
La méthode de Newton utilise l'idée suivante pour approximer les solutions def(x)=0. En esquissant un graphique def, nous pouvons estimer une racine def(x)=0. Appelons cela une estimationx0. Nous dessinons ensuite la tangente àf atx0. Sif′(x0)≠0, cette tangente coupe l'xaxe -à un moment donné(x1,0). Passons maintenantx1 à la prochaine approximation de la racine réelle. En général,x1 est plus proche quex0 d'une racine réelle. Ensuite, nous dessinons la tangente àf atx1. Sif′(x1)≠0, cette tangente croise également l'xaxe -, produisant une autre approximation,x2. Nous continuons ainsi, en dérivant une liste d'approximations :x0,x1,x2,…. Généralement, les nombresx0,x1,x2,… se rapprochent rapidement d'une racine réellex∗, comme le montre la figure suivante.
![Cette fonction f (x) est dessinée avec les points (x0, f (x0)), (x1, f (x1)) et (x2, f (x2)) marqués sur la fonction. À partir de (x0, f (x0)), une tangente est tracée et elle heurte l'axe x en x1. À partir de (x0, f (x0)), une tangente est tracée et elle heurte l'axe x en x2. Si une tangente était tracée à partir de (x2, f (x2)), il semblerait qu'elle serait très proche de x*, qui est la racine réelle. Chaque ligne tangente tracée dans cet ordre semble se rapprocher de plus en plus de x*.](https://math.libretexts.org/@api/deki/files/2532/CNX_Calc_Figure_04_09_001.jpeg)
Voyons maintenant comment calculer les approximations.x0,x1,x2,…. Six0 est notre première approximation, l'approximationx1 est définie en laissant(x1,0) être l'xintersection de la tangente àf atx0. L'équation de cette tangente est donnée par
y=f(x0)+f′(x0)(x−x0).
Par conséquent,x1 doit satisfaire
f(x0)+f′(x0)(x1−x0)=0.
En résolvant cette équation pourx1, nous concluons que
x1=x0−f(x0)f′(x0).
De même, le point(x2,0) est l'xintersection de la tangente àf atx1. Par conséquent,x2 satisfait à l'équation
x2=x1−f(x1)f′(x1).
En général, pourn>0,xn satisfaire
xn=xn−1−f(xn−1)f′(xn−1).
Ensuite, nous verrons comment utiliser cette technique pour approximer la racine du polynôme.f(x)=x3−3x+1.
Utilisez la méthode de Newton pour approximer une racine def(x)=x3−3x+1 dans l'intervalle[1,2]. Laissex0=2 et trouvex1,x2,x3,x4, etx5.
Solution
Sur la figure4.9.2, nous voyons qu'ilf y a une racine sur l'intervalle[1,2]. x0=2Cela semble donc être une première approximation raisonnable. Pour trouver l'approximation suivante, nous utilisons l'équation \ ref {Newton}. Puisquef(x)=x3−3x+1, le dérivé estf′(x)=3x2−3. En utilisant l'équation \ ref {Newton} avecn=1 (et une calculatrice qui affiche des10 chiffres), nous obtenons
x1=x0−f(x0)f′(x0)=2−f(2)f′(2)=2−39≈1.666666667.
Pour trouver l'approximation suivantex2, nous utilisons l'équation \ ref {Newton} avecn=2 et la valeur dex1 stockée sur la calculatrice. Nous constatons que
x2=x1−f(x1)f′(x1)≈1.548611111.
En continuant ainsi, nous obtenons les résultats suivants :
- x1≈1.666666667
- x2≈1.548611111
- x3≈1.532390162
- x4≈1.532088989
- x5≈1.532088886
- x6≈1.532088886.
Nous notons que nous avons obtenu la même valeur pourx5 etx6. Par conséquent, toute application ultérieure de la méthode de Newton donnera très probablement la même valeur pourxn.
![La fonction f (x) = x3 — 3x + 1 est dessinée. Ses racines se situent entre −2 et −1, entre 0 et 1 et entre 1 et 2.](https://math.libretexts.org/@api/deki/files/12416/4.9.1.png)
x0=0Utilisons la méthode de Newton pour approximer la racine de l'f(x)=x3−3x+1intervalle[0,1] en calculantx1 etx2.
- Allusion
-
Utilisez l'équation \ ref {Newton}.
- Réponse
-
x1≈0.33333333
x2≈0.347222222
La méthode de Newton peut également être utilisée pour approximer les racines carrées. Nous montrons ici comment approximer√2. Cette méthode peut être modifiée pour approximer la racine carrée de tout nombre positif.
Utilisez la méthode de Newton pour obtenir une approximation√2 (Figure4.9.3). Laissezf(x)=x2−2x0=2, laissez et calculezx1,x2,x3,x4,x5. (Nous remarquonsf(x)=x2−2 que puisque la valeur initiale est nulle√2,x0=2 il est raisonnable de faire un choix approximatif√2).
![La fonction y = x2 — 2 est dessinée. Une ligne pointillée provient de x0 = 2, et une tangente est tracée vers le bas à partir de là. Il touche x1 = 1,5, ce qui est proche de x* = la racine carrée de 2.](https://math.libretexts.org/@api/deki/files/12417/4.9.2.png)
Solution
Pourf(x)=x2−2,f′(x)=2x. From Equation \ ref {Newton}, nous savons que
\ [\ begin {align*} x_n&=x_ {n−1} − \ frac {f (x_ {n−1})} {f' (x_ {n−1})} \ \ [4 points]
&=x_ {n−1} − \ frac {x^2_ {n−1} −2} {2x_ {n−1}} \ \ [4pt]
&= \ frac {1} {2} x_ {n−1} + \ frac {1} {x_ {n−1}} \ \ [4 points]
&= \ frac {1} {2} \ gauche (x_ {n−1} + \ frac {2} {x_ {n−1}} \ droite). \ end {align*} \ nonumber \]
Par conséquent,
x1=12(x0+2x0)=12(2+22)=1.5
x2=12(x1+2x1)=12(1.5+21.5)≈1.416666667.
En continuant ainsi, nous constatons que
x1=1.5
x2≈1.416666667
x3≈1.414215686
x4≈1.414213562
x5≈1.414213562.
Comme nous avons obtenu la même valeur pourx4 etx5, il est peu probable que cette valeurxn change lors d'une application ultérieure de la méthode de Newton. Nous concluons que√2≈1.414213562.
Utilisez la méthode de Newton pour approximer√3 en laissantf(x)=x2−3 etx0=3. Trouvezx1 etx2.
- Allusion
-
Pourf(x)=x2−3, l'équation \ ref {Newton} se réduit àxn=xn−12+32xn−1.
- Réponse
-
x1=2
x2=1.75
Lorsque vous utilisez la méthode de Newton, chaque approximation après l'estimation initiale est définie en fonction de l'approximation précédente en utilisant la même formule. En particulier, en définissant la fonctionF(x)=x−[f(x)f′(x)], nous pouvons réécrire l'équation \ ref {Newton} sous la formexn=F(xn−1). Ce type de processus, dans lequel chacunxn est défini en termes dexn−1 répétition de la même fonction, est un exemple de processus itératif. Nous examinerons prochainement d'autres processus itératifs. Tout d'abord, examinons les raisons pour lesquelles la méthode de Newton pourrait ne pas trouver de racine.
Les échecs de la méthode de Newton
En général, la méthode de Newton est utilisée pour trouver des racines assez rapidement. Cependant, les choses peuvent mal tourner. Parmi les raisons pour lesquelles la méthode de Newton peut échouer, citons les suivantes :
- À l'une des approximationsxn, la dérivéef′ est nulle àxn, maisf(xn)≠0. Par conséquent, la tangente def atxn n'intersecte pas l'xaxe. Nous ne pouvons donc pas poursuivre le processus itératif.
- Les approximationsx0,x1,x2,… peuvent s'approcher d'une racine différente. Si la fonctionf possède plusieurs racines, il est possible que nos approximations ne se rapprochent pas de celle que nous recherchons, mais s'approchent d'une racine différente (voir Figure4.9.4). Cet événement se produit le plus souvent lorsque nous ne choisissons pas l'approximation suffisammentx0 proche de la racine souhaitée.
- Les approximations peuvent ne pas s'approcher complètement d'une racine. Dans Exemple4.9.3, nous fournissons un exemple de fonction et une estimation initiale dex0 telle sorte que les approximations successives ne s'approchent jamais d'une racine car les approximations successives continuent d'alterner entre deux valeurs.
![Une fonction est dessinée avec deux racines, étiquetées racine recherchée et racine trouvée. Un point x0 est choisi de telle sorte que lorsque la tangente de x0 est prise, même s'il est plus proche de la racine recherchée, la tangente pointe vers la racine trouvée.](https://math.libretexts.org/@api/deki/files/2535/CNX_Calc_Figure_04_09_004.jpeg)
Réfléchissez à la fonctionf(x)=x3−2x+2. Laissezx0=0. Montrez que la séquencex1,x2,… ne parvient pas à s'approcher de la racine def.
Solution
Carf(x)=x3−2x+2, le dérivé estf′(x)=3x2−2 .Par conséquent,
x1=x0−f(x0)f′(x0)=0−f(0)f′(0)=−2−2=1.
À l'étape suivante,
x2=x1−f(x1)f′(x1)=1−f(1)f′(1)=1−11=0.
Par conséquent, les nombresx0,x1,x2,… continuent de rebondir entre les deux01 et ne se rapprochent jamais de la racine,f dont la racine se trouve au-dessus de l'intervalle[−2,−1] (Figure4.9.5). Heureusement, si nous choisissons une approximation initialex0 plus proche de la racine réelle, nous pouvons éviter cette situation.
![La fonction f (x) = x3 — 2x + 2 est dessinée, dont la racine est comprise entre −2 et −1. La tangente de x = 0 va à x = 1, et la tangente de x = 1 va à x = 0.](https://math.libretexts.org/@api/deki/files/12418/4.9.3.png)
Pourf(x)=x3−2x+2, louerx0=−1.5 et trouverx1 etx2.
- Allusion
-
Utilisez l'équation \ ref {Newton}.
- Réponse
-
x1≈−1.842105263
x2≈−1.772826920
Dans l'exemple4.9.3, nous voyons que la méthode de Newton ne fonctionne pas toujours. Cependant, lorsqu'elle fonctionne, la séquence d'approximations se rapproche très rapidement de la racine. Des discussions sur la rapidité avec laquelle la séquence d'approximations s'approche d'une racine trouvée à l'aide de la méthode de Newton sont incluses dans des textes sur l'analyse numérique.
Autres processus itératifs
Comme mentionné précédemment, la méthode de Newton est un type de processus itératif. Nous examinons maintenant un exemple d'un autre type de processus itératif.
Prenons l'exemple d'une fonctionF et d'un numéro initialx0. Définissez les nombres suivants à l'xnaide de la formulexn=F(xn−1). Ce processus est un processus itératif qui crée une liste de nombres.x0,x1,x2,…,xn,…. Cette liste de nombres peut s'approcher d'un nombre fini aux∗n fur et à mesure qu'elle s'agrandit, ou non. Dans Exemple4.9.4, nous voyons un exemple de fonctionF et une estimation initiale dex0 telle sorte que la liste de nombres résultante se rapproche d'une valeur finie.
LaisseF(x)=12x+4 et laissex0=0. Pour tousn≥1, laissezxn=F(xn−1). Trouvez les valeursx1,x2,x3,x4,x5. Faites une conjecture sur ce qu'il advient de cette liste de nombresx1,x2,x3,…,xn,… en tant quen→∞. Si la liste de nombres sex1,x2,x3,… rapproche d'un nombre finix∗x∗=F(x∗), alorsx∗ satisfait etx∗ est appelée point fixe deF.
Solution
Six0=0, alors
- x1=12(0)+4=4
- x2=12(4)+4=6
- x3=12(6)+4=7
- x4=12(7)+4=7.5
- x5=12(7.5)+4=7.75
- x6=12(7.75)+4=7.875
- x7=12(7.875)+4=7.9375
- x8=12(7.9375)+4=7.96875
- x9=12(7.96875)+4=7.984375.
À partir de cette liste, nous supposons que les valeurs sexn rapprochent8.
La figure4.9.6 fournit un argument graphique indiquant que les valeurs se rapprochent8 den→∞. En commençant par le point(x0,x0), nous tracons une ligne verticale jusqu'au point(x0,F(x0)). Le prochain numéro de notre liste estx1=F(x0). Nous utilisonsx1 pour calculerx2. Par conséquent, nous dessinons une ligne horizontale reliant(x0,x1)(x1,x1) le point de la ligney=x, puis une ligne verticale reliant(x1,x1) le point(x1,F(x1)). La sortieF(x1) devientx2. En continuant ainsi, nous pourrions créer un nombre infini de segments de ligne. Ces segments de ligne sont piégés entre les lignesF(x)=x2+4 ety=x. Les segments de droite se rapprochent du point d'intersection de ces deux lignes, qui se produit lorsquex=F(x). En résolvant l'équation,x=x2+4, nous concluons qu'ils se croisentx=8. Par conséquent, nos preuves graphiques sont en accord avec nos preuves numériques selon lesquelles la liste des nombres sex0,x1,x2,… rapprochex∗=8 den→∞.
![La fonction F (x) = (1/2) x + 4 est représentée graphiquement avec y = x. À partir de x0, qui semble être à l'origine, une ligne est tracée vers la fonction F (x) à x1 = F (x0). Ensuite, une ligne est tracée vers la droite jusqu'à la ligne y = x, point auquel une ligne est tracée jusqu'à x2 = F (x1). Ensuite, une ligne est tracée vers la droite jusqu'à la ligne y = x, point auquel une ligne est tracée jusqu'à x3 = F (x2). La poursuite de ce processus convergerait vers le point d'intersection des deux lignes à x* = 8.](https://math.libretexts.org/@api/deki/files/12419/4.9.4.png)
Réfléchissez à la fonctionF(x)=13x+6. Laissex0=0 et laissexn=F(xn−1)n≥2. Trouvex1,x2,x3,x4,x5. Faites une conjecture sur ce qu'il advient de la liste des nombresx1,x2,x3,…xn,… en tant quen→∞.
- Allusion
-
Considérez le point où les lignesy=x sey=F(x) croisent.
- Réponse
-
x1=6,x2=8,x3=263,x4=809,x5=24227;x∗=9
Les processus itératifs peuvent donner lieu à des comportements très intéressants. Dans cette section, nous avons vu plusieurs exemples de processus itératifs qui convergent vers un point fixe. Nous avons également vu dans4.9.3 Example que le processus itératif rebondissait entre deux valeurs. Nous appelons ce type de comportement un double cycle. Les processus itératifs peuvent converger en cycles avec différentes périodicités, tels que 2 cycles, 4 cycles (où le processus itératif répète une séquence de quatre valeurs), 8 cycles, etc.
Certains processus itératifs engendrent ce que les mathématiciens appellent le chaos. Dans ce cas, le processus itératif passe d'une valeur à l'autre de manière apparemment aléatoire et ne converge jamais ni ne s'installe dans un cycle. Bien que l'exploration complète du chaos dépasse le cadre de ce texte, nous examinons dans ce projet l'une des principales propriétés d'un processus itératif chaotique : la dépendance sensible aux conditions initiales. Cette propriété fait référence au concept selon lequel de petites modifications des conditions initiales peuvent générer un comportement radicalement différent dans le processus itératif.
L'exemple de chaos le plus connu est probablement l'ensemble de Mandelbrot (voir Figure4.9.7), nommé d'après Benoit Mandelbrot (1924-2010), qui a étudié ses propriétés et contribué à vulgariser le domaine de la théorie du chaos. L'ensemble de Mandelbrot est généralement généré par ordinateur et présente des détails fascinants sur l'agrandissement, y compris l'autoréplication de l'ensemble. Plusieurs versions colorisées de l'ensemble ont été présentées dans des musées et peuvent être consultées en ligne et dans des livres populaires sur le sujet.
![Une fractale très complexe et d'apparence organique.](https://math.libretexts.org/@api/deki/files/2538/CNX_Calc_Figure_04_09_007.jpeg)
Dans ce projet, nous utilisons la carte logistique
f(x)=rx(1−x)
oùx∈[0,1] etr>0
comme fonction de notre processus itératif. La carte logistique est une fonction d'une simplicité trompeuse ; mais, selon la valeur der, le processus itératif qui en résulte présente un comportement très intéressant. Cela peut mener à des points fixes, à des cycles et même au chaos.
Pour visualiser le comportement à long terme du processus itératif associé à la carte logistique, nous utiliserons un outil appelé diagramme en toile d'araignée. Comme nous l'avons fait pour le processus itératif que nous avons examiné plus tôt dans cette section, nous tracons d'abord une ligne verticale d'un point(x0,0) à un point(x0,f(x0))=(x0,x1). Nous tracons ensuite une ligne horizontale entre ce point et le point(x1,f(x1))=(x1,x2),(x1,x1), puis une ligne verticale jusqu'à ce que le comportement à long terme du système devienne évident et nous poursuivons le processus. La figure4.9.8 montre le comportement à long terme de la carte logistique lorsquer=3.55 etx0=0.2. (Les premières100 itérations ne sont pas tracées.) Le comportement à long terme de ce processus itératif est un8 cycle.
![Dans le premier quadrant, f (x) = 3,55x (1 — x) est représenté graphiquement comme y = x. À partir d'un point sur l'axe des x, une ligne est tracée jusqu'à la ligne y = x, à quel point elle devient horizontale et continue jusqu'à toucher le bord extérieur de f (x), où elle redevient verticale jusqu'à atteindre la ligne y = x. le processus se poursuit plusieurs fois et crée une série intéressante de boîtes.](https://math.libretexts.org/@api/deki/files/12420/4.9.5.png)
- Laissezr=0.5 et choisissezx0=0.2. À la main ou à l'aide d'un ordinateur, calculez les premières10 valeurs de la séquence. La séquence semble-t-elle converger ? Dans l'affirmative, à quelle valeur ? Cela entraîne-t-il un cycle ? Si c'est le cas, quel type de cycle (par exemple,2 −cycle,4 −cycle.) ?
- Que se passe-t-il quandr=2 ?
- Pourr=3.2 etr=3.5, calculez les premières valeurs de100 séquence. Générez un diagramme en toile d'araignée pour chaque processus itératif. (Plusieurs applets gratuits sont disponibles en ligne pour générer des diagrammes en toile d'araignée pour la carte logistique.) Quel est le comportement à long terme dans chacun de ces cas ?
- Maintenant,r=4. calculons les premières valeurs de100 séquence et générez un diagramme en toile d'araignée. Quel est le comportement à long terme dans ce cas ?
- Répétez le processus pourr=4, mais laissezx0=0.201. Comment ce comportement se compare-t-il au comportement dex0=0.2 ?
Concepts clés
- La méthode de Newton se rapproche des racines def(x)=0 en commençant par une approximation initialex0, puis utilise des lignes tangentes au graphe def pour créer une séquence d'approximationsx1,x2,x3,….
- En général, la méthode de Newton est une méthode efficace pour trouver une racine particulière. Dans certains cas, la méthode de Newton ne fonctionne pas parce que la liste des nombresx0,x1,x2,… ne s'approche pas d'une valeur finie ou s'approche d'une valeur autre que la racine recherchée.
- Tout processus dans lequel une liste de nombresx0,x1,x2,… est générée en définissant un nombre initialx0 et en définissant les nombres suivants par l'équationxn=F(xn−1) d'une fonctionF est un processus itératif. La méthode de Newton est un exemple de processus itératif, où la fonctionF(x)=x−[f(x)f′(x)] d'une fonction donnéef.
Lexique
- processus itératif
- processus dans lequel une liste de nombresx0,x1,x2,x3… est générée en commençant par un nombrex0 et en définissantxn=F(xn−1) pourn≥1
- La méthode de Newton
- méthode d'approximation des racines def(x)=0; l'utilisation d'une estimation initialex0 ; chaque approximation suivante est définie par l'équationxn=xn−1−f(xn−1)f′(xn−1)