salut tous,

j'ai cru comprendre que dans certains cas un algorithme de Newon pouvait être plus lent que la methode de dichotomie.
Pr contre je n'ai pas trop compris dans quel cas on rencontre ce type de problemes ? lorsque la fonction est "plate" ?

pourriez vous m'expliquer svp?

C'est lorsque la fonction fait beaucoup de « vagues » près du zéro considéré qu'il y a des problèmes avec la méthode de Newton. Plus précisément, la méthode de Newton ne converge généralement pas bien si x₀, l'approximation initiale du zéro, est trop éloignée du vrai zéro (x_α) et que la dérivée de la fonction n'est pas monotone sur l'intervalle [x₀, x_α].

je viens de tester Newton sur des courbes qui ont posé probleme à un collegue, que penses tu de ce genre de courbe?


ça pourrait marcher correctement N-R ?

=> le 0 se trouve en plein milieu entre les bornes vertes et bleues qui sont un des points de départ possible

je pense que si on part de la borne verte ça va poser probleme car l'algo va partir à droite alors que la solution est à gauche ?
dans le cas de la borne bleu il risque d'avoir une tangente et diverger ?

C'est typiquement le cas où ta méthode ne va pas converger vu que ta dérivée semble quasi nulle en 0. En dehors des problèmes de convergence théorique, tu auras des problèmes de précision numérique vu que tu divises par un nombre très proche de 0.

Solution alternative : dichotomie sur la fonction ou Newton sur la dérivée seconde (ta courbe semble avoir un point d'inflexion en 0, ce qui veut dire que la dérivée seconde s'annule- et avec un peu de chance, la dérive triple ne sera pas nulle au point que tu veux trouver).

super merci pour cette confirmation. Par contre je n'ai pas compris ce que tu me dis sur la methode de newton. elle existe aussi à l'ordre 2 ?

tu aurais un lien vers un site qui explique ceci ?

Citation : sebsheep

C'est typiquement le cas où ta méthode ne va pas converger vu que ta dérivée semble quasi nulle en 0.

Non, dans ce cas la méthode va converger, mais elle va converger lentement.

pourriez vous m'expliquer s'il vous plait sur le schema ?

=> j'ai du mal à voir pourquoi il convergerait lentement ou pourquoi il ne convergerait pas

Si les deux algorithmes converges (cf la discution plus haut), le seul moyen pour la dichotomie d'être plus rapide que l'algorithme de Newton est de trouver le zéro en temps fini.

Ta fonction semble être quelque chose comme <math>\(f(x)=ax^3\)</math>, avec <math>\(a\approx-1.25\times10^{-27}\)</math>.

Que tu partes du point bleu (<math>\(x\approx-1\)</math>) ou du point vert (<math>\(x\approx1\)</math>), la méthode de Newton va converger, mais moins vite que la méthode de la dichotomie.

Newton:
<math>\(x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{ax_n^3}{3ax_n^2}=\frac23x_n\)</math>

<math>\(x_n=x_0\left(\frac23\right)^n\)</math>

<math>\(x_0=-1\Rightarrow x_n=-\left(\frac23\right)^n\)</math>

<math>\(x_0=1\Rightarrow x_n=\left(\frac23\right)^n\)</math>

L'erreur diminue d'un tiers à chaque itération, d'où que l'on parte. (Enfin, sauf si l'on part de <math>\(x_0 = 0\)</math> bien sûr. )


Dichotomie:

L'erreur diminue de moitié à chaque itération. La méthode de la dichotomie converge donc plus vite que celle de Newton dans ce cas précis.

j'aime beaucoup ton explication, merci !