2

How would you show that if f'(a)=0 then the Newton's Method is linear convergent when
1. $f''(a)\neq 0$
2. $f''(a)=0, f'''(a) \neq 0$?
I am having some trouble getting it to the point where you can take the limit of ratio of the error terms and using L'hospital's rule to prove this.

user88595
  • 4,549
cambelot
  • 2,411

1 Answers1

1

Write $f(x)=(x-a)^2g(x)$ resp. $f(x)=(x-a)^3g(x)$, both with $g(a)\ne0$ and compute the influence of these factorizations on the Newton iteration.

If $f(x)=(x-a)^mg(x)$ with $g(a)\ne 0$ then $f'(x)=m(x-a)^{m-1}g(x)+(x-a)^mg'(x)$ and $$ x_+=x-\frac{f(x)}{f'(x)}=x-\frac{(x-a)g(x)}{mg(x)+(x-a)g'(x)}=a+(x-a)\frac{(m-1)g(x)+(x-a)g'(x)}{mg(x)+(x-a)g'(x)} $$ For $x$ close to $a$ the term $(x-a)g'(x)$ becomes very small relative to $g(x)$, and the Newton iteration reduces to $$ x_+=a+(1-\tfrac1m)(x-a). $$ For a strict proof you have to quantify "becomes very small relative to" and use inequalities for $|x_+-a|\leqslant C|x-a|$, but the general idea is as above.

aidangallagher4
  • 902
Lutz Lehmann
  • 126,666
  • can you please explain more? I thought I did that but its not turning out any answer. – cambelot May 22 '14 at 18:26
  • Hi @LutzL a bit late here but hoping you see this. How do you know you are able to write $f$ in the form $f(x)=(x-a)^mg(x)$ when we have $f^{(n)}\neq 0$? Something to do with Taylor expanding $f$ or $g$? – aidangallagher4 May 24 '19 at 20:23
  • 1
    Yes, or by the definition of multiplicity, $f$ has a root of multiplicity $m$ at $a$ if it can be factorized as $f(x)=(x-a)^mg(x)$ with $g(a)\ne0 $. – Lutz Lehmann May 24 '19 at 20:33
  • @LutzL is this assuming that $f$ is a polynomial then (since we're talking about multiplicity)? – aidangallagher4 May 24 '19 at 20:36
  • 1
    No, this is a general definition for $f$ sufficiently smooth in $a$. You can very well say that all roots of $1+\sin x$ have multiplicity $2$. – Lutz Lehmann May 24 '19 at 20:39