Rate of convergence of Newton's method near a double root.

Question

Suppose that $r$ is a double root of $f(x)=0$; that is, $f(r)=f′(r)=0$ but $f''(r)\ne 0$, and suppose that f and all derivatives up to and including the second are continuous in some neighborhood of $r$. Show that $e_{n+1} ≈ 1/2 e_n$ for Newton’s method and thereby conclude that the rate of convergence is linear near a double root. (If the root has multiplicity $m$, then $e_{n+1} ≈ [(m − 1)/m]e_n$.)

I fully understand Newton's method and its calculation. However, this question is a bit confusing and I do not really understand what I am supposed to do. Thanks for the help.

Answer 1

At a simple root of a sufficiently smooth $f$ you get quadratic convergence close to the root, that is $e_{n+1}\approx Ce_n^2$ if $e_n$ is small enough. At a multiple root or far away from a cluster of roots the convergence is linear, the worse the higher the multiplicity. You are to quantify this slow convergence.

---

Let $r$ be a root of multiplicity $m$. Then one can extract $m$ linear factors $(x-r)$ from $f$, so that $f(x)=(x-r)^mg(x)$, $g(r)\ne 0$, $g$ at least differentiable. Then $$f'(x)=m(x-r)^{m-1}g(x)+(x-r)^mg'(x)$$ and the Newton step gives $$ x_{n+1}-r=x_n-r-\frac{(x_n-r)^mg(x_n)}{m(x_n-r)^{m-1}g(x_n)+(x_n-r)^mg'(x_n)} \\~\\ =\frac{(m-1)g(x_n)+(x_n-r)g'(x_n)}{mg(x_n)+(x_n-r)g'(x_n)}(x_n-r) $$ which implies, using $g(x_n)=g(r)+g'(r)e_n+...$ \begin{align} e_{n+1} &=\frac{(m-1)g(r)+me_ng'(r)+O(e_n^2)}{mg(r)+(m+1)e_ng'(r)+O(e_n^2)}e_n \\[1em] &=\frac{m-1}{m}\frac{m(m-1)g(r)+m^2e_ng'(r)+O(e_n^2)}{m(m-1)g(r)+(m-1)(m+1)e_ng'(r)+O(e_n^2)}e_n \\[1em] &=\frac{m-1}{m}\left(1+\frac{g'(r)+O(e_n)}{m(m-1)g(r)+O(e_n)}e_n\right)e_n \\[1em] &=\frac{m-1}{m}e_n+\frac{g'(r)}{m(m-1)g(r)}e_n^2+O(e_n^3) \end{align} which should lead directly to the claim of your task.

Answer 2

Assume for simplicity that the root we are after is $r=0$, and that $$f(x)=x^m g(x),\qquad g(0)\ne0\ .$$ Then $$f'(x)=m x^{m-1}g(x)+x^m g'(x)=x^{m-1} g(x)\bigl(m + x g'(x)/g(x)\bigr)\ .$$ Newton's method then says that the approximation $x$ of $r=0$ should be replaced by $$x':=x-{f(x)\over f'(x)}=x-{x\over m+ x g'(x)/g(x)}=x\left(1-{1\over m+ x g'(x)/g(x)}\right)\ .$$ This implies that $${x'\over x}\approx{m-1\over m}$$ when $|x|$ is sufficiently small, depending on the value of $g'(0)/g(0)$.