# Is there a reason to prefer Newton's method for the computation of the roots?

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?

• What if $f'(a)=f(a)=0$? – Simply Beautiful Art Jun 8 '17 at 22:55
• 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. – littleO Jun 8 '17 at 22:56
• 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. – copper.hat Jun 8 '17 at 22:57
• I think the answer is that in some cases Newton's method converges to a high accuracy solution much faster than the secant method. – littleO Jun 8 '17 at 23:06
• "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. – Winther Jun 8 '17 at 23:26

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$.
• @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. – user14717 Jun 9 '17 at 17:39