11
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ See here and here $\endgroup$ – ciao Mar 20 '14 at 9:19
10
$\begingroup$

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]

Mathematica graphics

FindRootPlot[Exp[1 - x] - 1, {x, 10.}, 
 Method -> {"Newton", "StepControl" -> None}, PlotRange -> All]

Mathematica graphics

$\endgroup$
  • 2
    $\begingroup$ Put another way: FindRoot[] is using a damped version of Newton-Raphson, for without the damping, bad choices of starting values will more often result in divergence. The damping makes the iterations less likely to go wild. $\endgroup$ – J. M. is in limbo May 18 '15 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.