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

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.

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 $(-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 \begin{align} e_{n+1} &=\frac{(m-1)g(r)+e_ng'(r)+O(e_n^2)}{mg(r)+e_ng'(r)+O(e_n^2)}e_n \\[1em] &=\frac{m-1}{m}\frac{m(m-1)g(r)+me_ng'(r)+O(e_n^2)}{m(m-1)g(r)+(m-1)e_ng'(r)+O(e_n^2)}e_n \\[1em] &=\frac{m-1}{m}\left(1+\frac{mg'(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)}{mg(r)}e_n^2+O(e_n^3) \end{align} which should lead directly to the claim of your task.
• could you be more rigorous and calculate the error term out for O(en)? I thought the error term would be $1/6en^3f'''(xn)$ so $O(en^3)$ – james black Feb 18 '18 at 17:28
• No, that would be unreasonable as at simple roots the error term is only quadratic. I added the general quadratic error term. Note that $f^{(m)}(x)=m!g(x)+m!(x-r)g'(x)+...$ so that $g(r)=f^{(m)}(r)/m!$ and $g'(r)=f^{(m+1)}/(2\,m!)$. – LutzL Feb 18 '18 at 19:11
• 1. but $g(r)\ne0$ if i am not mistaken then shouldn't it be O(en) term from g(xn)-g(r) error? why is it $O(e_n^2)$ then? 2. the second last line, the denominator m(m−1)g(r)+O(en), shouldn't it be m(m−1)g(r)-g'(r)+O(en)? where did the -g('r) term go? – james black Feb 18 '18 at 22:07
• like you said $g(r)=f(m)(r)/m!$ so $m!(x−r)g′(x)$ or $m!eng′(x)$ should be the error term in O(en) – james black Feb 18 '18 at 22:20
• correction for 2. the second last line, the denominator m(m−1)g(r)+O(en), shouldn't it be $\frac {e_ng'(r)+O} {m(m−1)g(r)+(m-1)eng'(r)+O}$? where did the g('r) term go and where did the m in mg'(r) come from? – james black Feb 18 '18 at 22:27
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)$.