# I Finding multiple roots of polynomial using numerical methods

1. Feb 29, 2016

### NotASmurf

Hey all, I seek to find where the derivative of a nth order polynomial is at a 0, so far I have used secant method to find it, which works, but issue is is that that returns only one root, sliding the interval could work, but then itd always point to the edge of the interval, any help appreciated. Base factoring wont work above 5th order poly's,

2. Feb 29, 2016

### RUber

Then you are asking for numerical approaches to find zeros of an (n-1)th order polynomial?
You will know that there are at most (n-1) real roots and exactly n-1 roots if complex roots are allowed.
How are you selecting your intervals? That seems to be the most important first step. A root should be in the interval for most methods to produce a reliable result.

3. Feb 29, 2016

### NotASmurf

yea, thing is, I don't want to use a method that finds just one root on an interval, I can in theory work with that in my program, but trying to see if a pre existing technique exists that can find n roots of a polynomial,

4. Feb 29, 2016

### RUber

I cannot think of a method that finds multiple roots at once. There may be one out there, but most I have seen require some partitioning of the interval to subintervals in order to find a single root of each subinterval.

5. Feb 29, 2016

### NotASmurf

6. Feb 29, 2016

### Staff: Mentor

From what I can tell from the description here, this method generates one root at a time.

7. Feb 29, 2016

### RUber

That looks like an effective method...algebraic rather than graphical. Depending on the size of your polynomial, I am interested to hear how long it takes to converge.

8. Feb 29, 2016

### NotASmurf

Thing is, my polynomial cannot easily be rearranged, so m looking for a method that works with f(xn) and xi $$x,i \in points$$, single root finding metods could still work, if i can find a way to eliminate the roots once im done with them WITHOUT using deflation (cannot use deflation for my current problem).

9. Feb 29, 2016

### RUber

How do you mean, "rearranged"? The Durand Kerner method outlined on Wikipedia seems to allow you to use any functional form you want for the polynomial. The most restrictive condition I see is that your initial values cannot be too close to each other.

10. Feb 29, 2016

### NotASmurf

Sorry ruled out Druand Kerner method in response to people seeming to think it would be slow and also due to it not being as amazing as i thought, is there any way to remove a root from a function without using deflation?

11. Feb 29, 2016

### NotASmurf

Tried out Durand Kerner, it works for some polynomials ive given it, but not others, so i tried changing my initial values (to the ones wikipedia said are good values) of p,q,r... but then it went for NaN (when the number explodes too big or divides by 0), even with the ones it worked on previously,

also tried others code out for spins, even the example referenced on wikipedia barely ever works, an other methods that spit out n roots like Durand Kerner is supposed to?

12. Feb 29, 2016

### Staff: Mentor

I misspoke earlier. From the Wikipedia article I linked to, it says that the method finds the roots simultaneously. Are you writing code for this?

A couple of the cautions are that,
1) The intial values are arbritrary, but can't be either real or roots of unity
2) You have to use complex arithmetic

13. Feb 29, 2016

### NotASmurf

I made code for that, and yes i used complex arithmatic. and yes i used non real roots of unity, the ones wikipedia suggested, still gives lots of trouble, doesnt converge to many polynomials i try,

14. Feb 29, 2016

### Staff: Mentor

The article said to NOT use roots of unity.

15. Mar 1, 2016

### NotASmurf

sorry typo :P i used 0.4 +0.9i

16. Mar 3, 2016

### Inventive

17. Mar 4, 2016

### mfig

Have you looked at MATLAB's roots function?

18. Mar 4, 2016

### epenguin

nth order polynomial? Do you mean nth degree polynomial? Pn(x) at x = 0?

That is just the nth coefficient multiplied by a number. If a polynomial is written in the form incorporating binomial coefficients which is often useful

P(x) = a0 + na1a1x + [n(n-1)/2]a2x2 +... [n!/r!(n-r)!]arxr+... +anxn

is (n!/r!)ar or something similar isn't it? Maybe you meant something different.

19. Mar 4, 2016

### Staff: Mentor

20. Nov 21, 2017

### James79gr

The Durand-Kerner method works fine, but one mustn't forget that the method itself is just a special case of a fixed-point iteration, and as such, will only converge under the conditions specified in fixed-point iteration.
As mentioned in the wikipedia article on the Durand-Kerner method, the method requires initial approximations of the roots to begin. Each approximation must lie within a range of the root such that it satisfies a Lipschitz inequality within that range, with a Lipschitz constant q < 1. Otherwise, it is possible for the method to diverge.
From a programmer's perspective, the method, if coded properly, converges fast. Typically takes 100msec or so on a Core 2 Duo to find the roots of a 5th-order polynomial (personal experience).