# How does FindRoot work?

Posted 9 years ago
5661 Views
|
4 Replies
|
0 Total Likes
|
 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 functionf[x]:=Exp[1 - x] - 1whose Newton iteration function isNf[x_]:=E^(-1 + x) (-1 + E^(1 - x)) + xIterating 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 takingModule[{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.
4 Replies
Sort By:
Posted 9 years ago
 There is documentation about what the default method is under Newton's method and Line search methods.
Posted 9 years ago
 Is there a way to tell exactly what method was used, or are you using "inside" information?
Posted 9 years ago
 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 9 years ago
 The notes on internal implementation state that FindRoot uses a "damped" Newton's method.