How does FindRoot work?

Questions
, ,
1

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}]

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.

2

The notes on internal implementation state that FindRoot uses a “damped” Newton’s method.

3

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.

4

Is there a way to tell exactly what method was used, or are you using “inside” information?

5

There is documentation about what the default method is under Newton’s method and Line search methods.