Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
3  
See here and here –  ciao Mar 20 '14 at 9:19
    
To close voters: I think this question is distinct from the proposed duplicate, although it is related. –  Michael E2 May 18 at 1:53

1 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, it still limits the maximum step size (the first step in this case 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

share|improve this answer
1  
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. –  Guess who it is. May 18 at 2:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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