# Rate of convergence of Newton's method near a double root ERROR bound proof

For the following proof I would like to know for $$e_{n+1}=\frac{(m-1)g(r)+e_ng'(r)+O(e_n)}{mg(r)+e_ng'(r)+O(e_n)}e_n=\frac{m-1}{m}e_n+O(e_n^2)$$ why does the first part lead to the second part? Can anyone show specific details and computations to that it leads to O(en^2) rigorously?

my idea was replacing g(r) with taylor terms and g'(r) with taylor terms by taking derivative on the taylor terms of g(r). but i cant seem to get the result.

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$.)

Proof

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 $$e_{n+1}=\frac{(m-1)g(r)+e_ng'(r)+O(e_n)}{mg(r)+e_ng'(r)+O(e_n)}e_n=\frac{m-1}{m}e_n+O(e_n^2)$$ which should lead directly to the claim of your task.

Starting from \begin{align}e_{n+1}&=\frac{(m-1)g(r)+e_ng^{\prime}(r)+O_1\left(e_n\right)}{mg(r)+e_ng^{\prime}(r)+O_2\left(e_n\right)}e_n\\ &=\frac{\frac{m-1}m+\frac{e_ng^{\prime}(r)+O_1\left(e_n\right)}{mg(r)}}{1+\frac{e_ng^{\prime}(r)+O_2\left(e_n\right)}{mg(r)}}e_n\\ &=\frac{K+y}{1+x}e_n\end{align} Where we have distinguished $O_1\left(e_n\right)$ from $O_2\left(e_n\right)$ as two different quantities both of the same order of magnitude and set \begin{align}K&=\frac{m-1}m\\ y&=\frac{e_ng^{\prime}(r)+O_1\left(e_n\right)}{mg(r)}\\ x&=\frac{e_ng^{\prime}(r)+O_2\left(e_n\right)}{mg(r)}\end{align} Then we know that $$\frac{K+y}{1+x}\approx(K+y)(1-x)\approx K+y-Kx$$ So we actually compute $$\frac{K+y}{1+x}-K-y+Kx=\frac{Kx^2-xy}{1+x}$$ And then $$e_{n+1}=Ke_n+\frac y{e_n}e_n^2-K\frac x{e_n}e_n^2+\frac{K\frac{x^2}{e_n^2}-\frac{xy}{e_n^2}}{1+x}e_n^3$$ Since $x$ and $y$ are both $O\left(e_n\right)$ it follows that $$\frac y{e_n}=\frac{g^{\prime}(r)+\frac{O_1\left(e_n\right)}{e_n}}{mg(r)}$$ and $$\frac x{e_n}=\frac{g^{\prime}(r)+\frac{O_2\left(e_n\right)}{e_n}}{mg(r)}$$ are both bounded as $e_n\rightarrow0$ so then $$\frac{e_{n+1}-\frac{m-1}me_n}{e_n^2}=\frac{e_{n+1}-Ke_n}{e_n^2}=\frac y{e_n}-K\frac x{e_n}+\frac{K\frac{x^2}{e_n^2}-\frac{xy}{e_n^2}}{1+x}e_n$$ Is bounded as $e_n\rightarrow0$ which is the same as saying $e_{n+1}-\frac{m-1}me_n=O\left(e_n^2\right)$
• That's exactly what you do in the definition of the derivative, isn't it? $$f(e_n)=O\left(e_n\right)$$ means that $$\frac{f(e_n)}{e_n}$$ is bounded as $e_n\rightarrow0$. – user5713492 Feb 19 '18 at 5:59
• I could have maybe gotten by subtracting $K$ instead of $K+y-Kx$ from $\frac{K+y}{1+x}$ and I think things would probably have still worked out. But the capability to replace that line with the wavy equals $(\approx)$ with an algebraically determined exact estimate makes it easy to transition from hand-wavy intuitive stuff to a rigorous proof. I remember seeing my mathematical physics professor do this for one proof and it left a great impression on me. – user5713492 Feb 19 '18 at 6:03