A página de Ajuda de FindRoot diz:
“por padrão, FindRoot usa o método de Newton (Newton-Raphson) para resolver um sistema não linear”
(ou uma equação não linear, suponho). No entanto, há algo oculto para mim no comando FindRoot. Considere a função
f[x]:=Exp[1 - x] - 1, cuja função de iteração de Newton é
Nf[x_]:=E^(-1 + x) (-1 + E^(1 - x)) + x Iterando com esta função usando NestList você obtém a seqüência de valores produzida pelo método de Newton. O método de Newton para grandes valores da estimativa inicial apresenta convergência lenta para este problema. Tomando $ x_0 = 10 $ obtemos:
NestList[Nf, 10., 8] (* {10., -8092.08, -8091.08, -8090.08, -8089.08, -8088.08, -8087.08, -8086.08, -8085.08} *) onde podemos ver o convergência lenta. Um gráfico da função Nf[x] ajuda a entender o comportamento do método. Mas pegar
Module[{s = 0, e = 0}, {FindRoot[f[x], {x, 10.}, StepMonitor :> s++, EvaluationMonitor :> e++], "Steps" -> s, "Evaluations" -> e}] produz
{{x -> 1.}, "Steps" -> 7, "Evaluations" -> 11} precisando de apenas 7 etapas para obter a solução $ x = 1 $. Por que FindRoot produz esse resultado ?. Obviamente, FindRoot não está usando o método de Newton padrão, não é? Alguém pode me ajudar? Obrigado.
Comentários
- Veja aqui e aqui
Resposta
Por padrão FindRoot usa o "LineSearch" método de controle de etapas conforme descrito no tutorial tutorial/UnconstrainedOptimizationLineSearchMethods . As configurações padrão são
FindRoot[Exp[1 - x] - 1, {x, 10.}, Method -> {"Newton", "StepControl" -> {"LineSearch", "CurvatureFactor" -> Automatic, "DecreaseFactor" -> 1/10000, "MaxRelativeStepSize" -> 10, Method -> Automatic}}] Para obter o método de Newton mais ou menos exatamente, não use controle de etapas. No entanto, FindRoot ainda limita o tamanho máximo da etapa (a primeira etapa no caso abaixo é truncada para 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: falha ao convergir para a exatidão ou precisão solicitada em 100 iterações. >>
(* {{x -> -1.07713}, "Steps" -> 100, "Evaluations" -> 101} *) Você pode usar as opções
StepMonitor :> Print[{x}], EvaluationMonitor :> Print[x] para monitorar as etapas e avaliações. Ou você pode use FindRootPlot no pacote "Optimization`UnconstrainedProblems`". (Observe atentamente os pontos amarelos que indicam uma avaliação que não é uma etapa.)
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] 
Comentários
- Dito de outra forma:
FindRoot[]está usando uma versão amortecida de Newton-Raphson, pois sem o amortecimento, más escolhas de valores iniciais resultarão mais freqüentemente em divergência. O amortecimento torna as iterações menos propensas a se descontrolar.