Newton's method for roots of multiplicity $> 1$

Solution 1:

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.

Solution 2:

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