La page daide de FindRoot
dit:
« par défaut, FindRoot utilise la méthode de Newton (Newton-Raphson) pour résoudre un système non linéaire »
(ou une équation non linéaire je suppose). Néanmoins, il y a quelque chose de caché pour moi dans la commande FindRoot
. Considérez la fonction
f[x]:=Exp[1 - x] - 1,
dont la fonction ditération Newton est
Nf[x_]:=E^(-1 + x) (-1 + E^(1 - x)) + x
En itérant avec cette fonction en utilisant NestList
vous obtenez la séquence des valeurs produites par la méthode de Newton. La méthode de Newton pour les grandes valeurs de lestimation initiale présente une convergence lente pour ce problème. En prenant $ x_0 = 10 $, nous obtenons:
NestList[Nf, 10., 8] (* {10., -8092.08, -8091.08, -8090.08, -8089.08, -8088.08, -8087.08, -8086.08, -8085.08} *)
où nous pouvons voir le convergence lente. Un tracé de la fonction Nf[x]
permet de comprendre le comportement de la méthode. Mais prendre
Module[{s = 0, e = 0}, {FindRoot[f[x], {x, 10.}, StepMonitor :> s++, EvaluationMonitor :> e++], "Steps" -> s, "Evaluations" -> e}]
produit
{{x -> 1.}, "Steps" -> 7, "Evaluations" -> 11}
ne nécessitant que 7 étapes pour obtenir la solution $ x = 1 $. Pourquoi FindRoot
produit ce résultat ?. De toute évidence, FindRoot
nutilise pas la méthode standard de Newton, nest-ce pas? Quelquun peut-il maider? Merci.
Commentaires
- Voir ici et ici
Réponse
Par défaut FindRoot
utilise la "LineSearch"
méthode de contrôle pas à pas comme décrit dans le didacticiel tutorial/UnconstrainedOptimizationLineSearchMethods
. Les paramètres par défaut sont
FindRoot[Exp[1 - x] - 1, {x, 10.}, Method -> {"Newton", "StepControl" -> {"LineSearch", "CurvatureFactor" -> Automatic, "DecreaseFactor" -> 1/10000, "MaxRelativeStepSize" -> 10, Method -> Automatic}}]
Pour obtenir plus ou moins exactement la méthode de Newton, nutilisez aucune commande de pas. Cependant, FindRoot
limite toujours la taille maximale du pas (le premier pas dans le cas ci-dessous est tronqué à x == -100.
):
Module[{s = 0, e = 0}, {FindRoot[Exp[1 - x] - 1, {x, 10.}, Method -> {"Newton", "StepControl" -> None}, StepMonitor :> s++, EvaluationMonitor :> e++], "Steps" -> s, "Evaluations" -> e}]
FindRoot :: cvmit: Échec de la convergence vers lexactitude ou la précision demandée en 100 itérations. >>
(* {{x -> -1.07713}, "Steps" -> 100, "Evaluations" -> 101} *)
Vous pouvez utiliser les options
StepMonitor :> Print[{x}], EvaluationMonitor :> Print[x]
pour suivre les étapes et les évaluations. Ou vous pouvez utilisez FindRootPlot
dans le package "Optimization`UnconstrainedProblems`"
. (Recherchez attentivement les points jaunes indiquant une évaluation qui nest pas une étape.)
Needs["Optimization`UnconstrainedProblems`"] FindRootPlot[Exp[1 - x] - 1, {x, 10.}, PlotRange -> All]
FindRootPlot[Exp[1 - x] - 1, {x, 10.}, Method -> {"Newton", "StepControl" -> None}, PlotRange -> All]
Commentaires
- En dautres termes:
FindRoot[]
utilise une version amortie de Newton-Raphson, car sans lamortissement, les mauvais choix de valeurs de départ entraîneront plus souvent des divergences. Lamortissement rend les itérations moins susceptibles de devenir sauvages.