0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dennis Kraakman Mar 7 '15 at 22:23
  • $\begingroup$ Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial. $\endgroup$ – Mariano Suárez-Álvarez Mar 7 '15 at 22:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more. $\endgroup$ – user3183724 Mar 4 '14 at 12:46
  • $\begingroup$ 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. $\endgroup$ – 7raiden7 Mar 4 '14 at 12:48
  • $\begingroup$ 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$? $\endgroup$ – user3183724 Mar 4 '14 at 13:11
  • $\begingroup$ 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). $\endgroup$ – 7raiden7 Mar 4 '14 at 13:44
  • 1
    $\begingroup$ Well, it's not going too well so far, but I did find an online reference: books.google.nl/… 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 simplified version of this. $\endgroup$ – user3183724 Mar 4 '14 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.