Méthode de Newton

[Matheco]

Bonjour,
J'ai essayé de récapituler comment on approche le zéro d'une fonction grâce à la méthode de Newton.
Pouvez vous m'indiquer si j'ai bien tout retranscrit, s'il y a des imprécisions, s'il manque des conditions ou si il y a des erreurs tout simplement?

Soit f une fonction, on cherche à approximer le zéro de cette fonction c'est-à-dire x* tel que f(x*) = 0
On cherche x* en résolvant f(x*) = 0
On calcule f'(x*)
Si f'(x*) 0 on peut appliquer l'algorithme de Newton pour approcher x*.

La suite récurrente générée par la méthode de Newton pour approcher x* est;
x0 donné
xn+1 = xn – [f(xn)/f'(xn)] = g(xn)

g admet pour point fixe x* , si |g'(x*)| <1, x* est attractif
donc xn et la méthode de Newton converge vers x*
Le fait de montrer que |g'(x*)| <1 est il suffisant pour montrer que la suite converge ou doit-on étudier la convergence de cette suite de façon "classique" (décroissante minorée, croissante majorée) ?

Si g'(x*) différent de 0 la convergence est d'ordre 1
Si g'(x) = 0
Soit p le premier naturel supérieur à 1 tel que gp(x*) différent de 0, la convergence est d’ordre p
(avec gp la p-ième dérivée de g)
Je ne suis pas sûre de la véracité de ce que je dis là concernant l'ordre de convergence, je l'ai supposé en regardant la correction d'un exercice




Merci d'avance

[PierreCapd]

Bonjour

J'ai trouvé ce site qui explique la méthode de Newton et qui pourra peut être vous rendre service.

Pierre

[arnaud32]

http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton

[Matheco]

Bonjour Pierre,
Je pensais justement que la méthode de Newton consistait à trouver g, et ensuite appliquer la méthode du point fixe à g.

La méthode de Newton étant en fait la méthode du point fixe avec une étape supplémentaire :s ?

[PierreCapd]

La méthode de Newton étant en fait la méthode du point fixe avec une étape supplémentaire :s ?

Je ne sais malheureusement pas répondre à cette question. Voici la méthode de Newton que je connais :

1) Pour résoudre l'équation f(x) = 0 il faut connaître un intervalle [a, b] dans lequel se trouve la racine.
2) On calcule la dérivée f'(a) puis l'équation de la tangente à la courbe au point d'abscisse a.
3) On calcule l'abscisse c du point d'intersection de cette tangente avec l'axe Ox.

La racine cherchée se trouve dans l'intervalle [a, c] ou bien [c, b] selon la concavité de la courbe.

On peut recommencer l'opération à partir de ce nouvel intervalle. Je ne me rappelle pas les détails exacts, désolé.

Pierre

[Matheco]

D'accord merci :)

[paquito]

La méthode de newton ou méthode des tangentes est remarquable par sa simplicité.
Soit une équation de la forme on a démontré Que admettait une solution unique dans et on peut supposer que et que, sinon on résout; quitte à réduire l'amplitude de aura un signe constant sur
On choisit dans I et on obtient comme équation de la tangente au point d'abscisse , d'où , puis par récurrence , avec .

tu vérifiera que, et

[Ben314]

Quelques remarque sur ta façons de rédiger les choses :

Soit f une fonction, on cherche à approximer le zéro de cette fonction c'est-à-dire x* tel que f(x*) = 0
On cherche x* en résolvant f(x*) = 0 <= c'est un peu con de commencer par ça vu que, si on sait résoudre de façon exacte l'équation en question, c'est plus franchement la peine d'employer une méthode permettant d'approcher les solutions..
On calcule f'(x*) <= ça, c'est encore pire : vu qu'au départ (i.e. avant de commencer les calculs) on ne sait pas combien vaut x*, je vois pas trop comment on pourrait calculer f'(x*)

(Je regarderais la suite après)
En bref, lorsque l'on présente la méthode de Newton, dans les "hypothèses" qu'on met pour garantir que ça va marcher, on ne parle jamais de la valeur de x* (vu qu'on la connait pas) donc systématiquement, les hypothèses sont de la forme :

On a une fonction f définie sur un intervalle [a,b] telle que (...hypothèses...)
Alors (i.e. avec les hypothèses faites), on est sûr que la fonction f admet une unique racine sur [a,b] et on peut cette racine en utilisant la suite .....

[Ben314]

Concernant la suite :

Le fait de montrer que |g'(x*)| <1 est il suffisant pour montrer que la suite converge ou doit-on étudier la convergence de cette suite de façon "classique" (décroissante minorée, croissante majorée) ?

De nouveau, c'est trés con comme formulation vu qu'en général, on ne connait pas la valeur de x* au départ.
En plus, texto, c'est pas du tout clair ce que tu raconte vu que tu précise pas où tu va prendre le U0 initial de la suite.
Un truc qui est parfaitement vrai, c'est que :
Si f' est continue au voisinage de x* et que |f'(x*)|<1 alors, si on prend U0 "suffisamment proche" de x*, on est certain que la suite va converger vers x*.
Et on peut un préciser le "suffisamment proche" sous la forme "si |f'(x)|<1 sur l'intervalle [a,b] contenant x*" alors, quelque soit le U0 dans [a,b] la suite convergera vers x*.

Si g'(x*) différent de 0 la convergence est d'ordre 1
Si g'(x) = 0
Soit p le premier naturel supérieur à 1 tel que gp(x*) différent de 0, la convergence est d’ordre p
(avec gp la p-ième dérivée de g)
Je ne suis pas sûre de la véracité de ce que je dis là concernant l'ordre de convergence, je l'ai supposé en regardant la correction d'un exercice

ça c'est correct, modulo de préciser ce que tu entend par "convergence d'ordre p" et, évidement, de préciser que tout ça est vrai à condition que la fonction de départ f soit assez "régulière" (pour qu'on puisse parler des dérivées p-ièmes de g).

[paquito]

Bonjour,

un petit exemple:donner l'unique solution de: avec chiffres significatifs.

on trouve facilement et pour .

et prenons
un petit programme et avec chiffres significatifs.

[Matheco]

Non c'est pas "con" parce que si x* est pi ou racine de 2 par exemple ça permet d'approcher au maximum du nombre, les chiffres après la virgule

[de plus ça fait plusieurs fois que je dis n'importe quoi ou des choses très conne pour Ben apparemment mais en même temps si je pose des questions ici c'est que j'ai conscience de ne pas avoir la bonne réponse, je ne viens effectivement pas faire étalage ici de tous ce que je connais parfaitement, c'est pas le but]

[Matheco]

Merci beaucoup

[Ben314]

Non c'est pas "con" parce que si x* est pi ou racine de 2 par exemple ça permet d'approcher au maximum du nombre, les chiffres après la virgule

[de plus ça fait plusieurs fois que je dis n'importe quoi ou des choses très conne pour Ben apparemment mais en même temps si je pose des questions ici c'est que j'ai conscience de ne pas avoir la bonne réponse, je ne viens effectivement pas faire étalage ici de tous ce que je connais parfaitement, c'est pas le but]

Il y a effectivement certains cas particuliers (ceux que tu cite et quelques autres) où effectivement on "connait" le x* (je met des guillemet vu que de dire qu'on "connait" racine(2), ou pi ou e, c'est pas bien clair).
MAIS, tu reconnaitra que c'est bien con de décrire la méthode uniquement dans ces cas particuliers là alors que, pour (quasi) pas un kopeck de plus, tu peut la décrire de façon applicable en analyse numérique où on ne sait évidement pas d'avance quelle est la valeur du x*... qu'on cherche...

Et si je veut "enfoncer le clou" concernant ta prose, dans l'autre sens, tu ne parle absolument pas du truc qui est essentiel dans presque toute les applications de la méthode de Newton, qui est de savoir de quel U0 on doit partir pour garantir que ça converge.

Pour te donner un exemple tout ce qu'il y a de plus "concret", dans le cas du polynôme donné par Paquito, on peut prendre quelles valeur de U0 ?
Plus précisément, comment déterminer avec le moins de calculs possibles un U0 tel qu'on est sûr que ça marche ?
Ca c'est une question super utile dans presque tout les cas.

P.S. Et si tu me répond qu'on commence par évaluer la valeur de x* pour prendre U0 "assez proche" de x*, tu comprend bien que "ça le fait pas"...

[Matheco]

Si je parle d'un cas particulier ou x* est connu c'est parce que mon examen porte sur ce cas particulier. C'est mon côté pragmatique.
Si je ne donne pas la valeur de u0 c'est parce que j'ai essayé de théoriser la méthode (permettant de résoudre ce cas particulier ou x* est connu) c'est mon côté théorique.
La valeur de u0 dépend de l'exercice que je dois résoudre.

[Ben314]

Pas de soucis, mais dans ce cas, évite de "tromper l'ennemi" en commençant ton premier post par

J'ai essayé de récapituler comment on approche le zéro d'une fonction grâce à la méthode de Newton....

qui laisse à penser que tu t'intéresse au cas général d'application de la méthode de Newton (et où la plupart des matheux lisant le truc pensent "analyse numérique")

[paquito]

Salut Matheco,

Je crois que tu as encore besoin de conseils!!!

Si j'ai bien compris, tu dois utiliser la méthode de Newton pour déterminer x décimales d'un réel

donné. Ca demande de prendre quand même quelques précautions! Non seulement, il faut

savoir initialiser U_n, mais le choix de f est aussi primordial; Ben t'as bien précisé qu'on ne pouvait

pas faire n'importe quoi et moi je rajoute que si tu ne mais pas mieux qu'une calculatrice (13 où 14

chiffres significatifs ), ton exo est nul à chier.

Donc: choix de f; si, c'est et que tu utilise f(x)=exp (x)-2, ça n'a d'intérêt que que si tu

construit ta fonction exp toi même et avec une précision suffisante; sinon exp est convexe donc tu

peux prendre n'importe où, ça marchera.

Précision obtenue: en fait, tu es dans un premier cas où on idéalise le théorème du point fixe

puisque . On a alors, Si converge bien vers



l'assurance qu'il existe un réel, tel que

; l' idéal est de majorer k par 1 et par par exemple, ce

qui te donne:

Bon, je passe à l'application numérique avec et f(x)=exp(x)-2

[paquito]

[quote="paquito"]Salut Matheco,

Je crois que tu as encore besoin de conseils!!!

Si j'ai bien compris, tu dois utiliser la méthode de Newton pour déterminer x décimales d'un réel

donné. Ca demande de prendre quand même quelques précautions! Non seulement, il faut

savoir initialiser, mais le choix de f est aussi primordial; Ben t'a bien précisé qu'on ne pouvait

pas faire n'importe quoi et moi je rajoute que si tu ne mais pas mieux qu'une calculatrice (13 où 14

chiffres significatifs ), ton exo est nul à chier.

Donc: choix de f; si, c'est et que tu utilise f(x)=exp (x)-2, ça n'a d'intérêt que que si tu

construit ta fonction exp toi même et avec une précision suffisante; sinon exp est convexe donc tu

peux prendre n'importe où, ça marchera.

Précision obtenue: en fait, tu es dans un premier cas où on idéalise le théorème du point fixe

puisque . On a alors, Si converge bien vers , on a



l'assurance qu'il existe un réel, tel que

; l' idéal est de majorer k par 1 et par par exemple, ce

qui te donne:

Bon, je passe à l'application numérique avec et f(x)=exp(x)-2;

Tu calcules g(x)

Tu définis ton exp par exp(x), oùest une majoration du reste que tu chercheras pour avoir par exemple 1000 décimales exactes pour avoir 500 décimales

de ln(2), tu initialises àou mieux; reste à programmer sur un truc costaud après avoir

déterminé le nombre d'térations nécessaires

[mathelot]

soit la racine à approcher.



car





or, si f est de classe dans un voisinage de :



où
donc



On détermine un voisinage compact K de où l'inégalité


est vérifiée.

d'où
où

[Ben314]

A chacun sa prose...

On considère une fonction f:[a,b]->R de classe C2 sur [a,b], telle que f(a).f(b)0 on pose I=[a,xo] et U0=a et si f(a).f''(a)R;x->x-f(x)/f'(x).
La fonction g est dérivable sur I et, pour tout x de I, g'(x)=f(x)f''(x)/f'²(x) est de signe constant sur I donc g est monotone et on en déduit facilement que g(I) est contenu dans I ce qui permet de considérer la suite définie par U(n+1)=g(Un) [avec le U0 défini ci dessus]

3) g(x)-x=-f(x)/f'(x) est de signe constant sur I donc la suite Un est monotone ce qui assure qu'elle converge vers une limite L. Comme g est continue, on doit avoir g(L)=L, c'est à dire f(L)=0 donc L=xo.

4) f étant C2, on a et donc, si ,

Donc lorsque vu que

Remarque : Cet équivalent assure que la convergence va être très rapide à partir du moment où un sera suffisamment proche de xo, mais bien qu'il y ait systématiquement convergence, elle peut être au départ assez lente comme le montre l'exemple de avec U0 "grand" où, pour les premiers termes, on a .