What are the hidden specifications for FindRoot

Question

The Help page of FindRoot says:

"by default, FindRoot uses Newton's method (Newton-Raphson) to solve a nonlinear system"

(or a nonlinear equation I suppose). Nevertheless, there is something hidden for me in the FindRoot command. Consider the function

f[x]:=Exp[1 - x] - 1, 

whose Newton iteration function is

Nf[x_]:=E^(-1 + x) (-1 + E^(1 - x)) + x

Iterating with this function using NestList you obtain the sequence of values produced by Newton's method. The Newton method for large values of the initial guess presents slow convergence for this problem.Taking $x_0=10$ we get:

NestList[Nf, 10., 8]
(* {10., -8092.08, -8091.08, -8090.08, -8089.08, -8088.08, -8087.08, -8086.08, -8085.08} *)

where we can see the slow convergence. A plot of the function Nf[x] helps to understand the behaviour of the method. But taking

Module[{s = 0, e = 0}, {FindRoot[f[x], {x, 10.}, StepMonitor :> s++, 
 EvaluationMonitor :> e++], "Steps" -> s, "Evaluations" -> e}]

produces

{{x -> 1.}, "Steps" -> 7, "Evaluations" -> 11}

needing only 7 steps to get the solution $x=1$. Why FindRoot produces this result?. Obviously, FindRoot is not using the standard Newton's method, isn't it? Can anyone help me? Thanks.

Answer 1

By default FindRoot uses the "LineSearch" method of step control as described in the tutorial tutorial/UnconstrainedOptimizationLineSearchMethods. The default settings are

FindRoot[Exp[1 - x] - 1, {x, 10.},
 Method -> {"Newton", 
   "StepControl" -> {"LineSearch", "CurvatureFactor" -> Automatic, 
     "DecreaseFactor" -> 1/10000, "MaxRelativeStepSize" -> 10,  Method -> Automatic}}]

To get Newton's method more or less exactly, use no step control. However, FindRoot still limits the maximum step size (the first step in the case below is truncated to 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: Failed to converge to the requested accuracy or precision within 100 iterations. >>

(*  {{x -> -1.07713}, "Steps" -> 100, "Evaluations" -> 101}  *)

You can use the options

StepMonitor :> Print[{x}], EvaluationMonitor :> Print[x]

to monitor the steps and evaluations. Or you can use FindRootPlot in the "Optimization`UnconstrainedProblems`" package. (Look carefully for the yellow dots denoting an evaluation that is not a step.)

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]