When is the order of convergence of Newton-Raphson greater than 2?

Question

If some function $f$ has a simple root at $x_*$ then I know that the order of convergence of the Newton-Raphson iteration is at least 2. But when is this order strictly greater than 2?

Answer 1

Newton's method is an example of a functional iteration, i.e., $$x_{n+1} = g(x_n).$$ Newton's method corresponds to the choice of $$g(x) = x - \frac{f(x)}{f'(x)}.$$ In general, we say that $r$ is a fixed point of a function $g$ if and only if $g(r) = r$. If $r$ is a fixed point of $g$ and if $$g^{(j)}(r) = 0, \quad j=1,2,\dotsc,k-1 \quad \text{and} \quad g^{(k)}(r) \not = 0,$$ then the functional iteration $$x_{n+1} = g(x_n)$$ will converge to $r$ provided $x_0$ is sufficiently close to $r$. Moreover, the order of convergence is exactly $k$. This last bit follows from Taylor's formula. Specifically, there exists $\xi_n$ between $r$ and $x_n$ such that $$ x_{n+1} - r = g(x_n) - g(r) = \frac{1}{k!}g^{(k)}(\xi_n)(x_n-r)^k $$
When $x_n \rightarrow r$, the squeeze lemma will ensure that $\xi_n \rightarrow r$. Continuity of $g^{(k)}$ will therefore imply $$ \frac{|r - x_{n+1}|}{|r - x_n|^k} \rightarrow \frac{1}{k!}|g^{(k)}(r)| \not = 0 $$ which is exactly what we mean when we say that the order of convergence is $k$.

Now returning to the case of Newton's method. In general, we have $$ g'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'(x)^2} = \frac{f(x)f''(x)}{f'(x)^2}$$ Since $r = g(r)$ if and only if $f(r) = 0$ we always have $$g'(r) = 0.$$ This is the reason why Newton's method has at least quadratic convergence near an isolated root.

When do we have at least cubic convergence? We to that end we consider $g''(r)$. If $f$ is at least three times differentiable, then we have \begin{align} g''(x) &= \frac{(f'(x)f''(x)+f(x)f'''(x))f'(x)^2 - 2f(x)f''(x)f'(x)f''(x)}{f'(x)^4} \\ &= \frac{f'(x)^3f''(x) + f(x)f'(x)^2 f'''(x) - 2f(x)f'(x)f''(x)^2}{f'(x)^4} \end{align} It follows that $$ g''(r) = \frac{f''(r)}{f'(r)} $$ Conclusion: we can only have cubic convergence provided $f''(r) = 0$. This happens quite rarely. One example is $f(x) = \sin(x)$ and $r = \pi$. Here the convergence is cubical as we can just manage to see from the actual numbers: $$\begin{array}{c|c|c} n & x_n & x_n - \pi \\ \hline 0 & 3.000000000000000 & -1.415926535897931 \times 10^{-1} \\ 1 & 3.142546543074278 & 9.538894844847157 \times 10^{-3} \\ 2 & 3.141592653300477 & -2.893161266115385 \times 10^{-10} \\ 3 & 3.141592653589793 & 0 \end{array} $$