0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am completely confused how can you divide by en when en is approcahing zero? $\endgroup$ – james black Feb 19 '18 at 5:55
  • $\begingroup$ is that any more concise and about equally rigorous way to prove it? $\endgroup$ – james black Feb 19 '18 at 5:58
  • $\begingroup$ 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$. $\endgroup$ – user5713492 Feb 19 '18 at 5:59
  • $\begingroup$ 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. $\endgroup$ – user5713492 Feb 19 '18 at 6:03
  • $\begingroup$ without this rigorous proof, can you dirrectly come up with the last two steps of my last line m−1/m*en+O(e2n) and its previous term? Because I dont know how the proof directly derived that result. $\endgroup$ – james black Feb 19 '18 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.