La pagina della guida di FindRoot dice:
“per impostazione predefinita, FindRoot utilizza il metodo di Newton” (Newton-Raphson) per risolvere un sistema non lineare “
(o unequazione non lineare suppongo). Tuttavia, cè qualcosa di nascosto per me nel comando FindRoot. Considera la funzione
f[x]:=Exp[1 - x] - 1, la cui funzione di iterazione di Newton è
Nf[x_]:=E^(-1 + x) (-1 + E^(1 - x)) + x Iterando con questa funzione utilizzando NestList si ottiene la sequenza di valori prodotta dal metodo di Newton. Il metodo di Newton per valori grandi dellipotesi iniziale presenta una convergenza lenta per questo problema. Prendendo $ x_0 = 10 $ otteniamo:
NestList[Nf, 10., 8] (* {10., -8092.08, -8091.08, -8090.08, -8089.08, -8088.08, -8087.08, -8086.08, -8085.08} *) dove possiamo vedere il convergenza lenta. Un grafico della funzione Nf[x] aiuta a comprendere il comportamento del metodo. Ma prendendo
Module[{s = 0, e = 0}, {FindRoot[f[x], {x, 10.}, StepMonitor :> s++, EvaluationMonitor :> e++], "Steps" -> s, "Evaluations" -> e}] si ottiene
{{x -> 1.}, "Steps" -> 7, "Evaluations" -> 11} che richiedono solo 7 passaggi per ottenere la soluzione $ x = 1 $. Perché FindRoot produce questo risultato ?. Ovviamente, FindRoot non sta utilizzando il metodo standard di Newton, non è vero? Qualcuno può aiutarmi? Grazie.
Commenti
- Vedi qui e qui
Risposta
Per impostazione predefinita FindRoot utilizza il "LineSearch" metodo di controllo dei passaggi come descritto nel tutorial tutorial/UnconstrainedOptimizationLineSearchMethods . Le impostazioni predefinite sono
FindRoot[Exp[1 - x] - 1, {x, 10.}, Method -> {"Newton", "StepControl" -> {"LineSearch", "CurvatureFactor" -> Automatic, "DecreaseFactor" -> 1/10000, "MaxRelativeStepSize" -> 10, Method -> Automatic}}] Per ottenere il metodo di Newton più o meno esattamente, non utilizzare il controllo dei passaggi. Tuttavia, FindRoot limita ancora la dimensione massima del passaggio (il primo passaggio nel caso seguente viene troncato a 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: impossibile convergere alla precisione o precisione richiesta entro 100 iterazioni. >>
(* {{x -> -1.07713}, "Steps" -> 100, "Evaluations" -> 101} *) Puoi utilizzare le opzioni
StepMonitor :> Print[{x}], EvaluationMonitor :> Print[x] per monitorare i passaggi e le valutazioni. Oppure puoi utilizza FindRootPlot nel pacchetto "Optimization`UnconstrainedProblems`". (Cerca attentamente i punti gialli che indicano una valutazione che non è un passaggio.)
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] 
Commenti
- In altre parole:
FindRoot[]utilizza una versione smorzata di Newton-Raphson, perché senza lo smorzamento, scelte sbagliate dei valori iniziali più spesso si tradurranno in divergenze. Lo smorzamento rende meno probabile che le iterazioni diventino selvagge.