1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Finding multiple roots of polynomial using numerical methods

  1. Feb 29, 2016 #1
    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. jcsd
  3. Feb 29, 2016 #2

    RUber

    User Avatar
    Homework Helper

    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.
     
  4. Feb 29, 2016 #3
    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,
     
  5. Feb 29, 2016 #4

    RUber

    User Avatar
    Homework Helper

    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.
     
  6. Feb 29, 2016 #5
    What about Durand Kerner method?
     
  7. Feb 29, 2016 #6

    Mark44

    Staff: Mentor

    From what I can tell from the description here, this method generates one root at a time.
     
  8. Feb 29, 2016 #7

    RUber

    User Avatar
    Homework Helper

    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.
     
  9. Feb 29, 2016 #8
    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).
     
  10. Feb 29, 2016 #9

    RUber

    User Avatar
    Homework Helper

    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.
     
  11. Feb 29, 2016 #10
    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?
     
  12. Feb 29, 2016 #11
    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?
     
  13. Feb 29, 2016 #12

    Mark44

    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
     
  14. Feb 29, 2016 #13
    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,
     
  15. Feb 29, 2016 #14

    Mark44

    Staff: Mentor

    The article said to NOT use roots of unity.
     
  16. Mar 1, 2016 #15
    sorry typo :P i used 0.4 +0.9i
     
  17. Mar 3, 2016 #16
  18. Mar 4, 2016 #17
    Have you looked at MATLAB's roots function?
     
  19. Mar 4, 2016 #18

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  20. Mar 4, 2016 #19

    Mark44

    Staff: Mentor

  21. Nov 21, 2017 #20
    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Finding multiple roots of polynomial using numerical methods
Loading...