Finding multiple roots of polynomial using numerical methods

[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 won't work above 5th order poly's,

 

[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.

 

[NotASmurf]

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.

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,

 

[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.

 

[NotASmurf]

What about Durand Kerner method?

 

[Mark44]

What about Durand Kerner method?

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

 

[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.

 

[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 I am done with them WITHOUT using deflation (cannot use deflation for my current problem).

 

[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.

 

[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?

 

[NotASmurf]

Tried out Durand Kerner, it works for some polynomials I've 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?

 

[Mark44]

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

 

[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, doesn't converge to many polynomials i try,

 

[Mark44]

yes i used non real roots of unity

The article said to NOT use roots of unity.

There is nothing special about choosing 0.4 + 0.9 i except that it is neither a real number nor a root of unity.

 

[NotASmurf]

sorry typo :P i used 0.4 +0.9i

 

[Inventive]

Would this article help?

http://math.stackexchange.com/questions/200617/how-to-solve-an-nth-degree-polynomial-equation

 

[mfig]

Have you looked at MATLAB's roots function?

 

[epenguin]

nth order polynomial? Do you mean nth degree polynomial? Pⁿ(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) = a₀ + na₁a₁x + [n(n-1)/2]a₂x² +... [n!/r!(n-r)!]a_rx^r+... +a_nxⁿ

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

 

[Mark44]

Would this article help?

http://math.stackexchange.com/questions/200617/how-to-solve-an-nth-degree-polynomial-equation

This doesn't help the OP. He or she is interested in a method that spits out all of the roots, not just one at a time.

 

[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).

 

[jasonRF]

Have you looked at MATLAB's roots function?

I like Matlab's version too. It uses the fact that the eigenvalues of the companion matrix (https://en.wikipedia.org/wiki/Companion_matrix) are the roots of the polynomial. So if NotASmurf already has code to find eigenvalues then they are set - the eigenvalue calculator does all of the heavy lifting.

Jason

EDIT: Oops - I failed to look and see that this is a very, very stale thread!