[Math] Multiple root Newton-Raphson. Please help

functionsnewton raphsonnumerical methodsroots

I'm really trying to understand this. The paper says:

At a multiple root, the Newton-Raphson method converges linearly (I get that). The method is given by:

$$x_{i+1} = x_{i} – m {f(x_{i})\over f'(x_{i})}$$

Where $\space m \space$ is the multiplicity of the root, will restore quadratic convergence at such a root.

Here is what I don't understand.

I have been told to write a program in Maple (if that helps) that approximates $\space m \space$.

But isn't $\space x_{i+1} \space$ recursive?

I am given the value of $\space x_{0} \space$. But $\space x_{i+1} \space$ is still unknown because we don't know $\space m \space$.

Can someone help me please?
I hope I'm making sense.

Thank You.

Best Answer

Let be $e_n=\left\vert x_{n+1}-x_n\right\vert$. You can estimate the value of $m$ considering $$e_{n+1}=\frac{m-1}{m}e_n.$$ Just make two normal Newton steps and use $x_0,x_1,x_2$ to evaluate the two succesive errors. The first steps of any iterative method may not be very good, specially in multiple roots, so you can discard $x_0,x_1$ and take two additional steps before approximate $m$.

Deepening a little more: if a function $f$ has a multiple root $r$ with multiplicity $m$, then $f$ is of the form $$f(x)=(x-r)^mg(x)$$ with necessarly $g(r)\neq 0$ and $f^\prime(x)=f^{\prime\prime}(x)=\cdots =f^{(m-1)}(x)=0$. Let be $u(x)=f(x)/f^\prime (x)$. The function $u(x)$ has only one root (easy to proof) and you can use the iteration $$x_{n+1}=x_n-\frac{u(x)}{u^\prime (x)}$$ and it converges cuadratically.

Also you can dynamically estimate $m$ with $$m=\max\left\{1, INT\left(\frac{x_n-x_{n-1}}{u(x_n)-u(x_{n-1})}\right)\right\}$$ as William Kahan suggest.