Newton versus bisection and cases of failure

Newton’s method is much faster than bisection, but it pays for this speed with lower robustness: it may fail to converge if the initial conditions are unfavourable.

Example — Comparison with bisection

Bisection applied to $x^2-2=0$ on $[1,2]$ gives an error $<10^{-6}$ after about $20$ iterations; Newton does it in $4$. Trade-off: bisection requires only $f$ (and a sign change); Newton requires $f'$ and an initial estimate that is “close enough”.

Warning — When Newton fails

Convergence is not guaranteed in every case:

• If $f'(x_n)=0$ at some point $\to$ division by zero, divergence.
• If $x_0$ is chosen badly, the iteration may “jump” away and oscillate (for example $f(x)=x^3-2x+2$ starting from $x_0=0$ produces a cycle $0,1,0,1,\ldots$).
• Near multiple zeros convergence is only linear, no longer quadratic.

The common strategy is hybrid: first a couple of bisection steps to “get close”, then Newton to refine quickly.

In summary: bisection is the safe but slow choice; Newton is the fast but delicate choice. In numerical practice the two are combined, exploiting the robustness of the one to guarantee a good initial estimate and the speed of the other for the final precision.

Links

Topics: Continuity
Concepts: Bisection algorithm · Quadratic convergence · Newton-Raphson method
Methods: Newton-Raphson
Skills: Analysis of limiting cases · Reasoning by cases