3
$\begingroup$

The Newton method for root computation is adored for its "dramatic" convergence speed, which is quadratic (the number of exact decimal doubles on every iterations). It is preferred over the secant method (and variants) featuring only φ-order convergence.

But

Newton's method requires one evaluation of the function plus one evaluation of its derivative per iteration. In many cases, the derivative is as costly to evaluate (and often more) so that there are actually two evaluations per iterations, and this makes the convergence speed in fact √2-order.

In addition, Newton gives no guarantee of convergence to a root close to the initial guess, whereas the regula falsi variant guarantees to converge inside the interval where a change of sign was observed.

So my question: why is Newton preferred at all?

$\endgroup$
  • $\begingroup$ What if $f'(a)=f(a)=0$? $\endgroup$ – Simply Beautiful Art Jun 8 '17 at 22:55
  • 1
    $\begingroup$ A similar issue comes up in convex optimization, when deciding whether to use Newton's method (which requires an expensive Hessian computation and solving a linear system) or a quasi-Newton method (which avoids the Hessian computation and does not require solving a linear system). Quasi-Newton methods are kind of similar to the secant method. In optimization, Newton's method offers the potential to converge to high accuracy in a small number of iterations, but each iteration might be very expensive. Whether a quasi-Newton method is superior to Newton's method, depends on the problem. $\endgroup$ – littleO Jun 8 '17 at 22:56
  • $\begingroup$ You need to consider the application context in order to determine if it is the preferred method. It is guaranteed to converge to a simple root if you start close enough. It provides 'inspiration' for other methods such as variable metric. $\endgroup$ – copper.hat Jun 8 '17 at 22:57
  • $\begingroup$ I think the answer is that in some cases Newton's method converges to a high accuracy solution much faster than the secant method. $\endgroup$ – littleO Jun 8 '17 at 23:06
  • $\begingroup$ "why is Newton preferred at all?" Because in the wast majority of applications the concerns you have is not an issue. Modern computers are so fast that it's only for special problems (using it billions of times; having very complicated functions ; $f'$ is hard/impossible to compute analytically etc.) one even need to think about these issues. Newton's method is the fiducial method for many people because of it's simplicity. It's very easy to remember, easy to implement and usually it just works. $\endgroup$ – Winther Jun 8 '17 at 23:26
3
$\begingroup$

I've written a couple of root finders which employ Newton's method.

My experience is that if you have no clue where a root is, Newton's method will turn on you. Much of my time writing these methods is spent scouring the literature for asymptotics which bracket the roots. Even with the asymptotics, it's not enough to just blindly apply Newton's methods to (say) the average of the brackets; first a few iterations of bisection is required to get the root to an accuracy of (say) 1 part in 100.

As to the second concern about the cost of evaluation of $f$ and $f'$: It is not generally that case that you must evaluate the function and its derivative independently. Generally you wish to make a routine that evaluates both at the same time. This is particularly important for evaluation of (say) a power series where the coefficients must be transferred from cache (or worse RAM) to registers. For a power series, it's easy to write a routine that will evaluate both $f$ and $f'$ at once with very little overhead relative to evaluation of $f$.

Finally, there is a very good reason to switch from bisection to Newton's method, even if you aren't interested in speed. Bisection must evaluate a function very near a root to be accurate. But the condition number of function evaluation is unbounded at the root, leading to large error. Newton's method suffers from this problem as well, but from my observation Newton's method exploits the differentiable structure of the function and will recover every digit correct up to the precision of the type. (I cannot prove this statement but I do have unit tests which show it's validity for a few cases.)

$\endgroup$
  • $\begingroup$ I like the condition number argument, and indeed having the analytical derivative handy avoids having to compute the function in small increments. In the case of derivative free methods, only the sign of the function really matters (linear interpolation is numerically safe around a change of sign). Very close to the root, the sign will indeed start to behave randomly. This means that we are at the limit of accuracy and Newton won't do better. $\endgroup$ – Yves Daoust Jun 9 '17 at 6:44
  • $\begingroup$ By the way, I was comparing to the secant method, no bisection. $\endgroup$ – Yves Daoust Jun 9 '17 at 6:44
  • $\begingroup$ @YvesDaoust: Suppose that $|x^* - x_n|/|x^*| \approx 10^{-p/2}$ where $p$ is the precision of the type. Evaluation of $f(x_{n})$ can be well-conditioned, because $10^{-p/2}$ is still "far" from the root. Then $x_{n+1}$ is accurate to $10^{-p}$, recovering full precision, and we never have to evaluate $f(x_{n+1})$ if our termination criteria understands the convergence rate of Newton's method. $\endgroup$ – user14717 Jun 9 '17 at 17:39

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.