Des articles

3.8 : Méthode de Newton - Mathématiques


Dans de nombreux domaines des mathématiques pures et appliquées, nous sommes intéressés à trouver des solutions à une équation de la forme (f(x)=0.) Pour la plupart des fonctions, cependant, il est difficile, voire impossible, de calculer leurs zéros explicitement. Dans cette section, nous examinons une technique qui fournit un moyen très efficace d'approximer le zéros de fonctions. Cette technique utilise des approximations de lignes tangentes et est à l'origine de la méthode souvent utilisée par les calculatrices et les ordinateurs pour trouver des zéros.

Décrire la méthode de Newton

Considérons la tâche de trouver les solutions de (f(x)=0.) Si (f) est le polynôme du premier degré (f(x)=ax+b), alors la solution de ( f(x)=0) est donné par la formule (x=−frac{b}{a}). Si (f) est le polynôme du second degré (f(x)=ax^2+bx+c), les solutions de (f(x)=0) peuvent être trouvées en utilisant la formule quadratique . Cependant, pour les polynômes de degré 3 ou plus, trouver les racines de (f) devient plus compliqué. Bien qu'il existe des formules pour les polynômes des troisième et quatrième degrés, elles sont assez compliquées. De plus, si f est un polynôme de degré 5 ou plus, on sait qu'il n'existe pas de telles formules. Par exemple, considérons la fonction

[f(x)=x^5+8x^4+4x^3−2x−7.]

Il n'existe aucune formule permettant de trouver les solutions de (f(x)=0.) Des difficultés similaires existent pour les fonctions non polynomiales. Par exemple, considérons la tâche de trouver des solutions de (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 de (f(x)=0.) En esquissant un graphe de (f), on peut estimer une racine de (f(x)=0). Appelons cette estimation (x_0). Nous traçons ensuite la ligne tangente à (f) en (x_0). Si (f′(x0)≠0), cette ligne tangente coupe l'axe (x) en un point ((x1,0)). Soit maintenant (x_1) la prochaine approximation de la racine réelle. Typiquement, (x_1) est plus proche que (x_0) d'une racine réelle. Ensuite, nous traçons la ligne tangente à (f) en (x_1). Si (f′(x1)≠0), cette ligne tangente coupe également l'axe (x), produisant une autre approximation, (x_2). On continue ainsi, en dérivant une liste d'approximations : (x_0,x_1,x_2,….) Typiquement, les nombres (x_0,x_1,x_2,…) s'approchent rapidement d'une racine réelle (x*) , comme le montre la figure suivante.

Voyons maintenant comment calculer les approximations (x_0,x_1,x_2,….) Si (x_0) est notre première approximation, l'approximation (x_1) est définie en laissant ((x_1,0) ) être l'ordonnée à l'origine (x) de la ligne tangente à (f) en (x_0). L'équation de cette tangente est donnée par

[y=f(x_0)+f′(x_0)(x−x_0).]

Par conséquent, (x_1) doit satisfaire

[f(x_0)+f′(x_0)(x_1−x_0)=0.]

En résolvant cette équation pour (x_1), nous concluons que

[x_1=x_0−frac{f(x0)}{f'(x0)}.]

De même, le point ((x_2,0)) est l'intersection (x) de la ligne tangente à (f) en (x_1). Par conséquent, (x_2) satisfait l'équation

[x_2=x_1−frac{f(x1)}{f'(x1)}.]

En général, pour (n>0,x_n) satisfait

[x_n=x_{n−1}−frac{f(x_{n−1})}{f'(x_{n−1})}.]

Ensuite, nous voyons comment utiliser cette technique pour approximer la racine du polynôme (f(x)=x^3−3x+1.)

Exemple (PageIndex{1}) : Recherche d'une racine d'un polynôme

Utilisez la méthode de Newton pour approximer une racine de (f(x)=x^3−3x+1) dans l'intervalle ([1,2]). Soit (x_0=2) et trouve (x_1,x_2,x_3,x_4), et (x_5).

Solution

D'après la figure, nous voyons que (f) a une racine sur l'intervalle ((1,2)). Par conséquent, (x_0=2) semble être une première approximation raisonnable. Pour trouver l'approximation suivante, nous utilisons l'équation. Puisque (f(x)=x^3−3x+1), la dérivée est (f′(x)=3x^2−3). En utilisant l'équation avec (n=1) (et une calculatrice qui affiche (10) chiffres), nous obtenons

[x_1=x_0−frac{f(x_0)}{f'(x_0)}=2−frac{f(2)}{f'(2)}=2−frac{3}{9} ≈1.666666667.]

Pour trouver l'approximation suivante, (x_2), nous utilisons l'équation avec (n=2) et la valeur de (x_1) stockée sur la calculatrice. On trouve que

[x_2=x_1=frac{f(x1)}{f'(x1)}≈1.548611111.]

En continuant ainsi, on obtient les résultats suivants :

[x_1≈1.666666667]

[x_2≈1.548611111]

[x_3≈1.532390162]

[x_4≈1.532088989]

[x_5≈1.532088886]

[x_6≈1.532088886.]

Notons que nous avons obtenu la même valeur pour (x_5) et (x_6). Par conséquent, toute application ultérieure de la méthode de Newton donnera très probablement la même valeur pour (x_n).

Exercice (PageIndex{1})

Soit (x_0=0), utilisons la méthode de Newton pour approximer la racine de (f(x)=x^3−3x+1) sur l'intervalle ([0,1]) en calculant ( x_1) et (x_2).

Indice

Utiliser l'équation

Répondre

[x_1≈0.333333333,x_2≈0.347222222]

La méthode de Newton peut également être utilisée pour approximer les racines carrées. Ici, nous montrons comment approximer (sqrt{2}). Cette méthode peut être modifiée pour approximer la racine carrée de tout nombre positif.

Exemple (PageIndex{2}) : Recherche d'une racine carrée

Utilisez la méthode de Newton pour approximer (sqrt{2}) (Figure). Soit (f(x)=x^2−2), soit (x_0=2), et calcule (x_1,x_2,x_3,x_4,x_5). (Nous notons que puisque (f(x)=x^2−2) a un zéro à (sqrt{2}), la valeur initiale (x_0=2) est un choix raisonnable pour approximer (sqrt{2}).)

Solution

Pour (f(x)=x^2−2,f′(x)=2x.) D'après l'équation, nous savons que

(x_n=x_{n−1}−frac{f(x_{n−1})}{f'(x_{n−1})})

(=x_{n−1}−frac{x^2_{n−1}−2}{2x_{n−1}})

(=frac{1}{2}x_{n−1}+frac{1}{x_{n−1}})

(=frac{1}{2}(x_{n−1}+frac{2}{x_{n−1}}).)

Par conséquent,

(x_1=frac{1}{2}(x_0+frac{2}{x_0})=frac{1}{2}(2+frac{2}{2})=1.5)

(x_2=frac{1}{2}(x_1+frac{2}{x_1})=frac{1}{2}(1.5+frac{2}{1.5})≈1.416666667.)

En continuant ainsi, on constate que

(x_1=1.5)

(x_2≈1.416666667)

(x_3≈1.414215686)

(x_4≈1.414213562)

(x_5≈1.414213562.)

Puisque nous avons obtenu la même valeur pour (x_4) et (x_5), il est peu probable que la valeur xn change lors d'une application ultérieure de la méthode de Newton. Nous concluons que (sqrt{2}≈1.414213562.)

Exercice (PageIndex{2})

Utilisez la méthode de Newton pour approximer (sqrt{3}) en laissant (f(x)=x^2−3) et (x_0=3). Recherchez (x_1) et (x_2).

Indice

Pour (f(x)=x^2−3), l'équation se réduit à (x_n=frac{x_{n−1}}{2}+frac{3}{2x_{n−1}} ).

Répondre

(x_1=2,x_2=1.75)

Lors de l'utilisation de la méthode de Newton, chaque approximation après la supposition initiale est définie en fonction de l'approximation précédente en utilisant la même formule. En particulier, en définissant la fonction (F(x)=x−[frac{f(x)}{f′(x)}]), nous pouvons réécrire l'équation sous la forme (x_n=F(x_{n -1})). Ce type de processus, où chaque (x_n) est défini en termes de (x_{n−1}) en répétant la même fonction, est un exemple de processus itératif. En bref, nous examinons d'autres processus itératifs. Tout d'abord, examinons les raisons pour lesquelles la méthode de Newton pourrait ne pas trouver de racine.

Échecs de la méthode de Newton

En règle générale, la méthode de Newton est utilisée pour trouver des racines assez rapidement. Cependant, les choses peuvent mal tourner. Voici quelques raisons pour lesquelles la méthode de Newton peut échouer :

  1. Les approximations (x_0,x_1,x_2,…) peuvent approcher une racine différente. Si la fonction (f) a plus d'une racine, il est possible que nos approximations ne s'approchent pas de celle que nous recherchons, mais s'approchent d'une racine différente (voir Figure). Cet événement se produit le plus souvent lorsque l'on ne choisit pas l'approximation (x_0) suffisamment proche de la racine désirée.
  2. Les approximations peuvent ne pas s'approcher entièrement d'une racine. Dans Exemple, nous fournissons un exemple de fonction et une estimation initiale (x_0) telles que les approximations successives ne s'approchent jamais d'une racine car les approximations successives continuent d'alterner entre deux valeurs.

Exemple (PageIndex{3}) : lorsque la méthode de Newton échoue

Considérons la fonction (f(x)=x^3−2x+2). Soit (x_0=0). Montrer que la séquence (x_1,x_2,…) ne parvient pas à s'approcher d'une racine de (f).

Solution

Pour (f(x)=x^3−2x+2,) la dérivée est (f′(x)=3x^2−2). Par conséquent,

[x_1=x_0−frac{f(x0)}{f′(x0)}=0−frac{f(0)}{f′(0)}=−frac{2}{−2} =1.]

A l'étape suivante,

[x_2=x_1−frac{f(x1)}{f'(x1)}=1−frac{f(1)}{f′(1)}=1−frac{1}{1} =0.]

Par conséquent, les nombres (x_0,x_1,x_2,…) continuent de rebondir entre (0) et (1) et ne se rapprochent jamais de la racine de (f) qui est au-dessus de la intervalle ([−2,−1]) (voir Figure). Heureusement, si nous choisissons une approximation initiale (x_0) plus proche de la racine réelle, nous pouvons éviter cette situation.

Exercice (PageIndex{3})

Pour (f(x)=x^3−2x+2,) soit (x_0=−1.5) et trouver (x_1) et (x_2).

Indice

Utilisez l'équation.

Répondre

(x_1≈−1.842105263,x_2≈−1.772826920)

D'après l'exemple, nous voyons que la méthode de Newton ne fonctionne pas toujours. Cependant, lorsque cela 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 approche 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. Voyons maintenant un exemple d'un type différent de processus itératif.

Considérons une fonction (F) et un nombre initial (x_0). Définissez les nombres suivants (x_n) par la formule (x_n=F(x_{n−1})). Ce processus est un processus itératif qui crée une liste de nombres (x_0,x_1,x_2,…,x_n,….) Cette liste de nombres peut approcher un nombre fini (x*) au fur et à mesure que (n) obtient plus grand, ou pas. Dans Exemple, nous voyons un exemple de fonction (F) et une estimation initiale (x_0) telles que la liste de nombres résultante approche une valeur finie.

Exemple (PageIndex{4}) : Recherche d'une limite pour un processus itératif

Soit (F(x)=frac{1}{2}x+4) et soit (x_0=0). Pour tout (n≥1), soit (x_n=F(x_{n−1})). Trouvez les valeurs (x_1,x_2,x_3,x_4,x_5). Faites une conjecture sur ce qui arrive à cette liste de nombres (x_1,x_2,x_3…,x_n,…) comme (n→∞). Si la liste de nombres (x_1,x_2,x_3,…) s'approche d'un nombre fini (x*), alors (x*) satisfait (x*=F(x*)), et ( x*) est appelé un point fixe de (F).

Solution : Si (x_0=0), alors

(x_1=frac{1}{2}(0)+4=4)

(x_2=frac{1}{2}(4)+4=6)

(x_3=frac{1}{2}(6)+4=7)

(x_4=frac{1}{2}(7)+4=7.5)

(x_5=frac{1}{2}(7.5)+4=7.75)

(x_6=frac{1}{2}(7.75)+4=7.875)

(x_7=frac{1}{2}(7.875)+4=7.9375)

(x_8=frac{1}{2}(7.9375)+4=7.96875)

(x _9=frac{1}{2}(7.96875)+4=7.984375.)

A partir de cette liste, nous conjecturons que les valeurs (x_n) se rapprochent de (8).

La figure fournit un argument graphique indiquant que les valeurs s'approchent de (8) comme (n→∞). En partant du point ((x_0,x_0)), nous traçons une ligne verticale jusqu'au point ((x_0,F(x_0))). Le numéro suivant dans notre liste est (x_1=F(x_0)). Nous utilisons (x_1) pour calculer (x_2). Par conséquent, nous traçons une ligne horizontale reliant ((x_0,x_1)) au point ((x_1,x_1)) sur la ligne (y=x), puis dessinons une ligne verticale reliant (( x_1,x_1)) jusqu'au point ((x_1,F(x_1))). La sortie (F(x_1)) devient (x_2). En continuant ainsi, nous pourrions créer un nombre infini de segments de ligne. Ces segments de ligne sont piégés entre les lignes (F(x)=frac{x}{2}+4) et (y=x). Les segments de ligne se rapprochent du point d'intersection de ces deux lignes, ce qui se produit lorsque (x=F(x)). En résolvant l'équation (x=frac{x}{2}+4,), nous concluons qu'ils se coupent en (x=8). Par conséquent, notre preuve graphique est en accord avec notre preuve numérique que la liste de nombres (x_0,x_1,x_2,…) approche (x*=8) comme (n→∞).

Exercice (PageIndex{4})

Considérons la fonction (F(x)=frac{1}{3}x+6). Soit (x_0=0) et soit (x_n=F(x_{n−1})) pour (n≥2). Recherchez (x_1,x_2,x_3,x_4,x_5). Faites une conjecture sur ce qui arrive à la liste de nombres (x1_,x_2,x_3,…x_n,… ) comme (n→∞.)

Indice

Considérez le point où les lignes (y=x) et (y=F(x)) se coupent.

Répondre

(x_1=6,x_2=8,x_3=frac{26}{3},x_4=frac{80}{9},x_5=frac{242}{27};x*=9)

Processus itératifs et chaos

Les processus itératifs peuvent produire 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 dans l'exemple que le processus itératif faisait des allers-retours entre deux valeurs. Nous appelons ce type de comportement un cycle à 2 cycles. Les processus itératifs peuvent converger vers des cycles avec diverses périodicités, telles que 2-cycles, 4-cycles (où le processus itératif répète une séquence de quatre valeurs), 8-cycles, et ainsi de suite.

Certains processus itératifs produisent ce que les mathématiciens appellent le chaos. Dans ce cas, le processus itératif saute de valeur en valeur de manière apparemment aléatoire et ne converge jamais ou ne s'installe dans un cycle. Bien qu'une exploration complète de le chaos dépasse le cadre de ce texte, dans ce projet, nous examinons l'une des propriétés clé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 petits changements dans les conditions initiales peuvent générer un comportement radicalement différent dans le processus itératif.

L'exemple le plus connu de chaos est probablement le Ensemble Mandelbrot (voir Figure), du nom de Benoit Mandelbrot (1924-2010), qui a étudié ses propriétés et contribué à populariser le domaine de la théorie du chaos. L'ensemble de Mandelbrot est généralement généré par ordinateur et montre des détails fascinants sur l'agrandissement, y compris l'auto-réplication de l'ensemble. Plusieurs versions colorisées de l'ensemble ont été montrées dans des musées et peuvent être trouvées en ligne et dans des livres populaires sur le sujet.

Dans ce projet, nous utilisons la carte logistique

[f(x)=rx(1−x)]

où (x∈[0,1]) et (r>0)

comme fonction dans notre processus itératif. La carte logistique est une fonction d'une simplicité trompeuse ; mais, selon la valeur de (r), le processus itératif résultant affiche un comportement très intéressant. Cela peut conduire à 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 avec le processus itératif que nous avons examiné plus tôt dans cette section, nous traçons d'abord une ligne verticale du point ((x_0,0)) au point ((x_0,f(x0))=(x_0,x_1 )). Nous traçons ensuite une ligne horizontale de ce point au point ((x_1,x_1),) puis dessinons une ligne verticale jusqu'à ((x_1,f(x_1))=(x_1,x_2)), et continuons le processus jusqu'à ce que le comportement à long terme du système devienne apparent. La figure montre le comportement à long terme de la carte logistique lorsque (r=3,55) et (x_0=0,2). (Les premières itérations (100) ne sont pas tracées.) Le comportement à long terme de ce processus itératif est un cycle (8).

  1. Que se passe-t-il lorsque (r=2) ?
  2. Laissez maintenant (r=4.) Calculer les premières valeurs de séquence (100) et générer un diagramme de toile d'araignée. Quel est le comportement à long terme dans ce cas?
  3. Répétez le processus pour (r=4,) mais laissez (x_0=0.201.) Comment ce comportement se compare-t-il avec le comportement pour (x_0=0.2) ?

Concepts clés

  • En règle générale, 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 car la liste de nombres (x_0,x_1,x_2,…) ne s'approche pas d'une valeur finie ou elle s'approche d'une valeur autre que la racine recherchée.
  • Tout processus dans lequel une liste de nombres (x_0,x_1,x_2,…) est générée en définissant un nombre initial (x_0) et en définissant les nombres suivants par l'équation (x_n=F(x_{n−1 })) pour certaines fonctions (F) est un processus itératif. La méthode de Newton est un exemple de processus itératif, où la fonction (F(x)=x−[frac{f(x)}{f′(x)}]) pour une fonction donnée (f) .

Glossaire

processus itératif
processus dans lequel une liste de nombres (x_0,x_1,x_2,x_3…) est générée en commençant par un nombre (x_0) et en définissant (x_n=F(x_{n−1})) pour (n≥1)
La méthode de Newton
méthode d'approximation des racines de (f(x)=0;) en utilisant une estimation initiale x0; chaque approximation suivante est définie par l'équation (x_n=x_{n−1}−frac{f(x_{n−1})}{f'(x_{n−1})})

Formules Newton-Côtes

En analyse numérique, le Formules Newton-Côtes, aussi appelé le Règles de quadrature Newton-Cotes ou simplement Règles de Newton-Côtes, sont un groupe de formules d'intégration numérique (également appelées quadrature) basé sur l'évaluation de l'intégrande à des points également espacés. Ils portent le nom d'Isaac Newton et de Roger Cotes.

Les formules de Newton-Cotes peuvent être utiles si la valeur de l'intégrande à des points également espacés est donnée. S'il est possible de changer les points auxquels l'intégrande est évalué, alors d'autres méthodes telles que la quadrature de Gauss et la quadrature de Clenshaw-Curtis sont probablement plus appropriées.


2 réponses 2

La règle des 3/8 présente deux avantages : Premièrement, le terme d'erreur est plus petit que la règle de Simpson.

La deuxième utilisation la plus importante de la règle des 3/8 est l'intégration de fonctions uniformément échantillonnées. Supposons que vous ayez une fonction connue à des points également espacés. Si le nombre de points est impair, alors la règle composite de Simpson fonctionne très bien. Si le nombre de points est pair, alors vous avez un problème à la fin. Une solution consiste à utiliser la règle des 3/8. Par exemple, si l'utilisateur a réussi 6 échantillons, alors vous utilisez Simpson pour les trois premiers points et 3/8 pour les 4 derniers (le point du milieu est commun aux deux). Cela préserve l'ordre de précision sans mettre une contrainte arbitraire sur le nombre d'échantillons.


3.8 : Méthode de Newton - Mathématiques

Avis de non-responsabilité : les informations sur la calculatrice affichées ici concernent les calculatrices TI-83. Il est possible d'adapter ces exemples pour d'autres calculatrices TI. Ces informations sont fournies pour rendre les calculs plus faciles et plus rapides, et ne sont pas destinées à remplacer la compréhension et la connaissance manuelle de ces méthodes.

Vous n'avez pas de calculatrice graphique ? Autre chose à essayer : la calculatrice graphique en ligne

Itération des fonctions de mise à jour

Les calculatrices peuvent rapidement itérer les fonctions. Commencez par saisir votre valeur initiale, puis profitez de la touche ANS pour créer une fonction à itérer simplement en appuyant plusieurs fois sur ENTER. Par exemple, itérer à partir d'une valeur initiale de 1 :

Interprétez la calculatrice : la valeur initiale est 1, la suivante est 15, et ainsi de suite. 2185 est la quatrième itération.

Voici un autre exemple, commençant à 0,8.

Dans ce cas, le comportement à long terme de la fonction de mise à jour tend vers 0. (Assurez-vous d'arrondir soigneusement avec une calculatrice et d'interpréter tous les résultats avant de les copier aveuglément.)

Méthode de Newton (Section 3.8)

La méthode de Newton fonctionne mieux avec un ordinateur ou une calculatrice qui peut effectuer les itérations rapidement. N'oubliez pas que le plus important est de vous assurer que vous pouvez utiliser la méthode de Newton : assurez-vous que votre équation est de la forme f(x)=0.

La première étape de la méthode de Newton consiste à saisir f(x) dans votre calculatrice, de la même manière que vous saisiriez une fonction à représenter graphiquement.

L'écran suivant montre une estimation initiale de 1 (appuyez sur 1, puis ENTER), puis la méthode de Newton sur une ligne. Itérer en appuyant plusieurs fois sur ENTER.

Appuyez plusieurs fois sur ENTER.

Remarquez comment les chiffres se sont stabilisés ? Que se passe-t-il si vous appuyez plusieurs fois sur ENTER ? Pourriez-vous être sûr de deviner que la réponse à cette équation est 2,7144176 ?

  • Y1 se trouve sous VARS, Y-VARS, Fonction
  • ANS est près de la touche (-)
  • nDeriv est MATH 8
  • Si vous ne voulez pas ou ne trouvez pas la commande nDeriv, placez simplement la dérivée dans Y2 et utilisez Y2(Ans) à la place de nDeriv(Y1,X,Ans)
  • Encore une fois, assurez-vous d'avoir résolu votre équation pour 0 avant d'utiliser la méthode de Newton !

Méthode d'Euler (Section 4.1)

Voici un programme pour la méthode d'Euler. Pour exécuter ce programme, vous devez d'abord entrer l'équation différentielle dans Y1. X est l'entrée initiale, Y est la sortie initiale et D est le pas de temps. Appuyez sur ENTER pour itérer. Lorsque vous en avez assez d'exécuter ce programme, appuyez sur ON.


3.8 : Méthode de Newton - Mathématiques

SOLUTION 2: On nous donne l'équation $ x^3=x^2+2 $, ou $ x^3-x^2-2=0 $, définissons donc la fonction $ f(x) = x^3-x ^2-2 $, dont le graphique est donné ci-dessous.

La dérivée de $f$ est $ f'(x) = 3x^2-2x $. Utilisez maintenant la méthode de Newton : $ x_ = x_ - < f(x_) sur f'(x_) > longrightarrow $ $ x_ = x_ - < x_^3-x_^2-2 sur 3x_^2-2x_ > longrightarrow $ (Simplifions le membre de droite de cette équation. Trouvez d'abord un dénominateur commun.) $ x_ = x_ < 3x_^2-2x_ plus de 3x_^2-2x_ > - < x_^3-x_^2-2 sur 3x_^2-2x_ > longrightarrow $ $ x_ = < 3x_^3-2x_^2 sur 3x_^2-2x_ > - < x_^3-x_^2-2 sur 3x_^2-2x_ > longrightarrow $ $ x_ = < 3x_^3-2x_^2 - ( x_^3-x_^2-2 ) sur 3x_^2-2x_ > longrightarrow $ $ x_ = < 2x_^3-x_^2+2 sur 3x_^2-2x_ > $ a.) Soit $ x_<0>=1 $. Ensuite, en utilisant la formule de la méthode de Newton, nous obtenons que $ x_ <1>= < 2x_<0>^3-x_<0>^2+2 over 3x_<0>^2-2x_ <0>> = < 2(1) ^3-(1)^2+2 over 3(1)^2-2(1) >= 3 $ et $ x_ <2>= < 2x_<1>^3-x_<1>^2+2 over 3x_<1>^2-2x_ <1>> = < 2(3)^3-(3)^2+2 over 3(3)^2-2(3) >= < 47 over 21 >approx 2.238095238 $ L'utilisation de la formule de la méthode de Newton pour 7 itérations dans une feuille de calcul donne :

Ainsi, la solution $r$ de l'équation originale à cinq décimales est $ r approx 1.69562 $.


b.) Soit $ x_<0>=2 $. Ensuite, en utilisant la formule de la méthode de Newton, nous obtenons que $ x_ <1>= < 2x_<0>^3-x_<0>^2+2 over 3x_<0>^2-2x_ <0>> = < 2(2) ^3-(2)^2+2 over 3(2)^2-2(2) >= < 14 over 8 >= 1,75 $ et $ x_ <2>= < 2x_<1>^3-x_ <1>^2+2 sur 3x_<1>^2-2x_ <1>> = < 2(1,75)^3-(1,75)^2+2 sur 3(1,75)^2-2(1,75) >= < 618 over 364 >approx 1.697802198 $ L'utilisation de la formule de la méthode de Newton pour 5 itérations dans une feuille de calcul donne :

Ainsi, la solution $r$ de l'équation originale à cinq décimales est $ r approx 1.69562 $.


c.) Soit $ x_<0>=0,5 $. Ensuite, en utilisant la formule de la méthode de Newton, nous obtenons que $ x_ <1>= < 2x_<0>^3-x_<0>^2+2 over 3x_<0>^2-2x_ <0>> = < 2(0.5) ^3-(0,5)^2+2 over 3(0,5)^2-2(0,5) >= -8 $ et $ x_ <2>= < 2x_<1>^3-x_<1>^2+ 2 sur 3x_<1>^2-2x_ <1>> = < 2(-8)^3-(-8)^2+2 sur 3(-8)^2-2(-8) >= < -1086 over 208 >approx -5.221153846 $ L'utilisation de la formule de la méthode de Newton pour 13 itérations dans une feuille de calcul donne :

Ainsi, la solution $r$ de l'équation originale à cinq décimales est $ r approx 1.69562 $.


d.) Soit $ x_<0>=1000 $. Ensuite, en utilisant la formule de la méthode de Newton, nous obtenons que (Utiliser la technologie.) $ x_ <1>= < 2x_<0>^3-x_<0>^2+2 over 3x_<0>^2-2x_ <0>> = < 2(1000)^3-(1000)^2+2 over 3(1000)^2-2(1000) >environ 666.7778526 $ et $ x_ <2>= < 2x_<1>^3-x_< 1>^2+2 sur 3x_<1>^2-2x_ <1>> = < 2(666.7778526 )^3-(666.7778526 )^2+2 sur 3(666.7778526 )^2-2(666.7778526 ) > = approx 444.6297922 $ L'utilisation de la formule de la méthode de Newton pour 21 itérations dans une feuille de calcul donne :

Ainsi, la solution $r$ de l'équation originale à cinq décimales est $ r approx 1.69562 $.


e.) Soit $ x_<0>=-500 $. Ensuite, en utilisant la formule de la méthode de Newton, nous obtenons que (Utiliser la technologie.) $ x_ <1>= < 2x_<0>^3-x_<0>^2+2 over 3x_<0>^2-2x_ <0>> = < 2(-500)^3-(-500)^2+2 over 3(-500)^2-2(-500) >approx -333.2223675 $ et $ x_ <2>= < 2x_<1> ^3-x_<1>^2+2 sur 3x_<1>^2-2x_ <1>> = < 2(-333.2223675)^3-(-333.2223675)^2+2 sur 3(-333.2223675) ^2-2(-333.2223675) >= approx -222.0373498 $ L'utilisation de la formule de la méthode de Newton pour 25 itérations dans une feuille de calcul donne :

Ainsi, la solution $r$ de l'équation originale à cinq décimales est $ r approx 1.69562 $.


Idée basique

L'idée derrière la méthode de Newton est simple -- approximation linéaire. C'est-à-dire que la plupart des fonctions à un point donné sont bien approximées par la ligne tangente à ce point. Si nous avons une bonne estimation (x_n) , alors nous pouvons améliorer cette estimation de manière itérative en la remplaçant par le zéro, (x_) , de la tangente à ((x_n, f(x_n))) .

Une image simple montre que nous avons un triangle de base (x_ - X_) , élévation (f(x_n) - 0) et pente (f'(x_n)) , en utilisant la formule "rise over run" :

L'algorithme de base des méthodes de Newton est alors :

Certains livres écrivent le côté droit sous la forme (x_n - f'(x_n)^ <-1>f(x_n)) , une forme qui se généralise à différents paramètres.

Comme la méthode de la bissection, la méthode de Newton est une méthode itérative. On commence par une estimation (appropriée) (x_0) . À partir de là, l'algorithme produit (x_1) qui est utilisé pour produire (x_2) , etc. L'idée est que l'on finira par se fixer sur une valeur (x_n) suffisamment proche de la racine désirée.

Mathématiquement, les indices indiquent que le côté droit est calculé et affecté au côté gauche. C'est exactement ce qui est fait en affectation au sein de julia , donc ce qui précède devient simplement :

Où f(x) est la fonction et fp(x) sa dérivée. Cette ligne commence par une valeur x préalablement définie et la met à jour en conséquence.

La mise à jour se poursuit - en exécutant exactement la même commande - jusqu'à ce que l'algorithme se soit suffisamment rapproché d'une réponse (c'est-à-dire qu'il ait convergé) ou que nous ayons abandonné sa convergence.

Nous pouvons déterminer de deux manières que le nombre est suffisamment proche de la réponse :

Les deux concepts nécessitent une tolérance. Pour le premier cas, il est plus facile d'arrêter lorsque la valeur imprimée de x cesse de changer. Il s'agit de 16 chiffres, ce qui peut poser problème avec des erreurs d'arrondi (par exemple, les 15 premiers chiffres peuvent rester fixes, tandis que le dernier oscille), bien que facile à utiliser sur la ligne de commande.

Pour la seconde, nous utiliserons une tolérance standard, la racine carrée de la limite de représentation en virgule flottante à (1) donnée commodément avec :

Réponses approximatives uniquement :

Il est important de réaliser que la réponse réelle ne sera probablement pas la valeur calculée par la méthode de Newton, que nous appelons parfois xstar. Dans la plupart des cas, la vraie réponse sera irrationnelle et xstar un nombre à virgule flottante, qui en fin de compte ne peut jamais être meilleur qu'une approximation d'un nombre irrationnel. C'est pourquoi nous devons être clairs sur ce que nous entendons par « assez près ».

Voici un exemple pour trouver un zéro de la fonction : (f(x) = x^3 - 2x - 5) .

La valeur résultante de x que nous pouvons voir lorsqu'elle est évaluée est inférieure à la tolérance en valeur absolue :

Vous pouvez voir dans ce cas que la convergence se produit rapidement dès que l'algorithme se rapproche.

Newton a regardé ce même exemple en 1699 (B.T. Polyak, La méthode de Newton et son utilisation en optimisation, Journal Européen de Recherche Opérationnelle. 02/2007 181(3):1086-1096.) bien que sa technique soit légèrement différente car il n'a pas utilisé le dérivé, en soi, mais plutôt une approximation basée sur le fait que sa fonction était un polynôme (bien qu'identique à la dérivée). Raphson (1690) a proposé la forme générale, d'où le nom usuel de méthode de Newton-Raphson.

Entraine toi

Question

Utiliser la méthode de Newton pour trouver (sqrt) (en résolvant les racines de (f(x) = x^2 - k) ) est également appelée méthode babylonienne, en raison de ses origines. La méthode résultante

Soit (k=15) et (x_0) égal à 3,24 . Quelle est la valeur de (x_3) ?

Question

La fonction (f(x) = sin(x)) a pour dérivée (f'(x) = cos(x)) . Utilisez la méthode de Newton pour résoudre (f(x) = 0) en commençant à (3) . Répétez jusqu'à ce que les chiffres cessent de changer. Quelle valeur obtenez-vous ?

(Cela peut être utilisé pour calculer (pi) numériquement, car la convergence est très rapide. Ici, il faut 4 étapes pour vérifier.)

Question

Soit (f(x) = x^2 - 3^x) . Cela a la dérivée (2x - 3^x cdot log(3)) . En commençant par (x_0=0) , sur quoi converge la méthode de Newton ?


Exemple 1

Considérons le système d'équations non linéaire suivant $left <eginx^3 + y = 1 y^3 - x = -1 enddroit.$ . Il existe une solution $(alpha, eta)$ telle que $alpha, eta > 0$ . Soit $(0.9, 0.9)$ une première approximation de ce système. Utilisez la méthode de Newton avec trois itérations pour approximer cette solution.

Il n'est pas difficile de voir que la solution d'intérêt est $(alpha, eta) = (1, 1)$ qui peut être obtenue en substituant l'une des équations à l'autre. Quoi qu'il en soit, nous utiliserons toujours la méthode de Newton pour démontrer l'algorithme.

Nous réécrivons d'abord notre système d'équations sous la forme :

Nous calculons maintenant les dérivées partielles de $f$ et $g$ . Nous avons ça :

Nous utiliserons la matrice ci-dessus pour chaque itération. Pour la première itération, nous devons résoudre le système d'équations suivant :

En résolvant ce système, nous obtenons que $delta_ = 0,101$ et que $delta_ = 0.383$ . On a donc ça :

Pour la deuxième itération, nous voulons résoudre le système d'équations suivant :

Lorsque nous résolvons ce système, nous obtenons que $delta_ = 0,2201143$ et $delta_ = 0.400208$ . On a donc ça :


Comment utilisez-vous la méthode de Newton pour approximer la valeur de la racine cubique ?

La méthode de Newton-Raphson rapproche les racines d'une fonction. Nous avons donc besoin d'une fonction dont la racine est la racine cubique que nous essayons de calculer.

Disons que nous essayons de trouver la racine cubique de #3# . Et disons que #x# est la racine cubique de #3# . Par conséquent,

Pour que la méthode de Newton-Raphson puisse opérer sa magie, nous devons remettre cette équation à zéro.

Rappelons maintenant l'équation itérative de Newton-Raphson.

La substitution de #f(x) = x^3 - 3# nous donne :

Maintenant, nous choisissons un nombre arbitraire (plus il est proche de #root3(3)# mieux c'est) pour #x_0# . Utilisons #x_0 = 0.5# . Ensuite, nous substituons chaque nombre précédent à #x_n# dans l'équation pour obtenir une approximation de plus en plus proche d'une solution de #x^3 - 3 = 0# .

#x_(1) = 0,5 - ((0,5)^3 - 3)/(3*(0,5)^2) = 4,33333 bar 3#
#x_(2) = x_1 - ((x_1)^3 - 3)/(3*(x_1)^2) environ 2.94214333#
#x_(3) = x_2 - ((x_2)^3 - 3)/(3*(x_2)^2) environ 2.07695292#
#x_(4) = x_3 - ((x_3)^3 - 3)/(3*(x_3)^2) environ 1.61645303#
#x_(5) = x_4 - ((x_4)^3 - 3)/(3*(x_4)^2) environ 1.46034889#
#x_(6) = x_5 - ((x_5)^3 - 3)/(3*(x_5)^2) environ 1.44247296#
#x_(7) = x_6 - ((x_6)^3 - 3)/(3*(x_6)^2) environ 1.4422496#
#x_(8) = x_7 - ((x_7)^3 - 3)/(3*(x_7)^2) environ 1.44224957#

Vous pouvez voir qu'avec seulement 8 itérations, nous avons obtenu une approximation de #root 3(3)# qui est correcte à 8 décimales !

Vous pouvez appliquer cette même logique à la racine cubique que vous souhaitez trouver, utilisez simplement #x^3 - a = 0# comme équation à la place, où #a# est le nombre dont vous recherchez la racine cubique.


3.8 : Méthode de Newton - Mathématiques

INTERPRÉTATION GRAPHIQUE : Soit l'équation donnée f(x) = 0 et l'approximation initiale pour la racine est X0. Tracer une tangente à la courbe y = f(x) à X0 et prolonger la tangente jusqu'à l'axe x. Alors le point d'intersection de la tangente et de l'axe des x est l'approximation suivante pour la racine de f(x) = 0. Répétez la procédure avec X0 = x1jusqu'à ce qu'il converge. Si m est la pente de la Tangente au point X 0 et b est l'angle entre la tangente et l'axe des x alors


f(x1) = f(x0+h) = f(x0 ) + hf '(x0) + h 2 f ''(x0) + . . .
2


0 = f(x0) + hf '(x0 ) + h 2 f ''(x0) + . . .
2
&ÉPINE
h = - f(x0)
f' (x0 )
&ÉPINE
X1= x0 - f(x0)
f' (x0 )

Étant donné une équation f(x) = 0
Soit la supposition initiale x0
Fais

Le processus itératif converge donc vers 1.89003 en quatre itérations.

Exemple 2 : Montrer que l'approximation initiale X0 pour trouver 1/NN est un entier + ve, par la méthode de Newton doit satisfaire 0 < x0 < 2/N pour la convergence. Preuve : Laisser f(x) = 1/x - N = 0 &ÉPINE f'(x) = -1/x 2

et la méthode de Newton est


Voir la vidéo: Newtonin menetelmä (Décembre 2021).