1

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.

Lutz Lehmann
  • 126,666
james black
  • 1,893

2 Answers2

5

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.

Lutz Lehmann
  • 126,666
  • 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!)$. – Lutz Lehmann Feb 18 '18 at 19:11
  • 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?
  • 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
  • I used $(m−1)e_ng'(r)=O(e_n)$, since that is also the error term in the numerator. – Lutz Lehmann Feb 19 '18 at 00:36
  • how did second last step go to last line then? $(a+b)/(c+d)!=a/c+b/d$ so why is $(mg′(r)+O(en)/m(m−1)g(r)+O(en))en^2 = g′(r)mg(r)en^2+O(e3n)$? – james black Feb 19 '18 at 02:06
  • I don't understand the step in "which implies" from $(m-1)g(x_{n})+e_{n}g'(x_{n})$ to $(m-1)g(r)+e_{n}g'(r)+O(e^{2}_{n})$ – David Shulman Jul 12 '21 at 10:56
  • @DavidShulman : This looks indeed hasty, I just replaced $x_n$ with $r$ as $g$ is assumed as slowly changing far away from zero, but correctly inserting the Taylor expansion $g(x_n)=g(r)+g'(r)e_n+O(e_n^2)$ gives a different result. The important leading terms describing the linear convergence however remain the same. – Lutz Lehmann Jul 12 '21 at 12:02