Message Boards Message Boards

How does FindRoot work?

Posted 11 years ago
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 x0=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 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}]

{{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.
4 Replies
The notes on internal implementation state that FindRoot uses a "damped" Newton's method.
POSTED BY: Frank Kampas
It is a Newton method with step control, for the above example FindRoot actually uses Method -> {"Newton",
  "StepControl" -> {"LineSearch", Method -> "Backtracking"}}.

As a reference, I would recommend Chapter 6, "Globally convergent modifications of Newton's method" in the Dennis and Schnabel book.
POSTED BY: Ilian Gachevski
Is there a way to tell exactly what method was used, or are you using "inside" information?
POSTED BY: Frank Kampas
There is documentation about what the default method is under Newton's method and Line search methods.
POSTED BY: Ilian Gachevski
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract