Newton's method for roots of multiplicity $> 1$ I'm studying numerical analysis and I read in Wikipedia that "If the root being sought has multiplicity greater than one, the convergence rate is merely linear".
The article in Wikipedia also mentions that "if the multiplicity $m$ of the root is known, one can use the following modified algorithm that preserves the quadratic convergence rate:
$$x_{n+1} = x_n -m \bigl[f(x_n)/f'(x_n)\bigr].$$
I tried proving this and I couldn't do it (I only managed to prove that convergence rate is at least linear).
Any ideas on how can this be proven ?
 A: Suppose that $x$ is a m-multiple root.
then you can have $f(x_k)=(x_k-x)^mf^{(m)}(x)/m!+O((x_k-x)^{m+1})$, derivate it 
$f'(x_k)=m(x_k-x)^{m-1}f^{(m)}(x)/m!+O((x_k-x)^m)$
$$x_{k+1}-x=x_k-f(x_k)/f'(x_k)-x$$
$$=x_k-x-(x_k-x)/m+O((x_k-x)^2)$$
you see this is linear convergence.
But if you change here $x_{k+1}=x_k-m[f(x_k)/f'(x_k)]$
then you can get this result $x_k-x-m(x_k-x)/m+O((x_k-x)^2)=O((x_k-x)^2)$
A: Hum, I am not going to write full details... write $f(x) = (x-a)^m g(x)$ with $g(a)\ne 0$.
Then 
$$\phi(x) = x - m {f(x) \over f'(x)} = x - { (x-a) g(x) \over g(x) + {1\over m} (x-a) g'(x)} $$
Set $x_{n+1} = \phi(x_n)$ and $y_n = x_n - a$. Then readily
$$y_{n+1} = y_n \left( 1 - {1 \over 1 + {1\over m} y_n {g'(a+y_n)\over g(a+y_n)}}\right).$$
A first order approximation gives
$$y_{n+1} \simeq y_n^2 {1\over m} {g'(a+y_n)\over g(a+y_n)},$$
hence the quadratic convergence (here I leave you some gory details).
Note that without the $m$ the same computations leads to
$$y_{n+1} \simeq y_n \left( {m-1\over m} + {1\over m} y_n {g'(a+y_n)\over g(a+y_n)} \right) \simeq {m-1\over m} y_n,$$
so you will get a linear rate of convergence.
