1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – james black Feb 18 '18 at 17:28
  • $\begingroup$ 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!)$. $\endgroup$ – LutzL Feb 18 '18 at 19:11
  • $\begingroup$ 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? $\endgroup$ – james black Feb 18 '18 at 22:07
  • $\begingroup$ 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) $\endgroup$ – james black Feb 18 '18 at 22:20
  • $\begingroup$ 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? $\endgroup$ – james black Feb 18 '18 at 22:27
0
$\begingroup$

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

$\endgroup$

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.