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.
Best Answer
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.