# Estimating the multiplicity of a root (numerically)

I'm working on a modified root finding script that uses the Newton method, but with a modification such that I estimate the order of the root to get faster convergence.

The basis of my motivation is that I read on wikipedia that if the multiplicity m of the root is known, one can use a modified algorithm, but that if the multiplicity is not known, it is possible to estimate m after carrying out one or two iterations, and then use that value to increase the rate of convergence.

Just for clarity, the Newton method I'm referring to is $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$

Now I'm afraid that it is not entirely clear to me how one would do this. It doesn't have to be the 'best' way there is, a simple approximation is just fine.

The way I'd start is from a taylor expansion. If $f(x)$ has a root r of order m, then

$\frac{f(x_n)}{f'(x_n)} \approx \frac{C(x_n-r)^m}{Cm(x_n-r)^{m-1}} = \frac{x_n-r}{m}$

Now, from the hint on wikipedia that it is possible to approximate m after a few iterations, I'd think I would just start with $x_0$, compute $x_1$, from that compute $x_2$ (using the approximation I made above of course), and then eliminate r using one of the equations in order to express m in terms of x0, x1 and x2. However, this is proving to be a rather ugly and overcomplicated expression, and I can't imagine that this is the most efficient method of doing so. Could anyone give me a nudge in the right direction?

Edit: I found an online reference. On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simpler (and thus less efficient) method similar to this.

• I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski? – Dennis Kraakman Mar 7 '15 at 22:23
• Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial. – Mariano Suárez-Álvarez Mar 7 '15 at 22:28

As far as I know, if $f(\cdot)$ has a root at $x$, it holds $f(x)=0$. Furthermore, if you want to calculate the multiplicity you have to find the minimum $m$ s.t.: $$f^{(m)}=0.$$
So, you can compute the derivatives, and if $|f^{(m)}|<\varepsilon$, where $\varepsilon$ represents a tolerance variable, thus $m$ is the number you are looking for.
• Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity. – 7raiden7 Mar 4 '14 at 12:48
• Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) \neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$? – user3183724 Mar 4 '14 at 13:11
• Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=\sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case). – 7raiden7 Mar 4 '14 at 13:44