Advertisement
Help Keep Boards Alive. Support us by going ad free today. See here: https://subscriptions.boards.ie/.
If we do not hit our goal we will be forced to close the site.

Current status: https://keepboardsalive.com/

Annual subs are best for most impact. If you are still undecided on going Ad Free - you can also donate using the Paypal Donate option. All contribution helps. Thank you.
https://www.boards.ie/group/1878-subscribers-forum

Private Group for paid up members of Boards.ie. Join the club.

Roots of polynomials

  • 10-08-2010 04:13PM
    #1
    tolosenc
    Registered Users, Registered Users 2 Posts: 6,889 ✭✭✭


    Hi,

    I'm writing a program to solve n-order polynomials, which may or may not have both complex roots and complex coefficients.

    The algorithm I'm going for is:
    1. Equation of order n
    2. Newton's method to get a root
    3. Divide equation of order n by (x - the root from step 2) to get equation of order n-1
    4. Repeat
    Is this algorithm sound? The results I'm getting aren't what I'm expecting.

    Regards the polynomial division, I'm using little bézout's theorem for the remainder and I also noticed that dividing ax^4 + bx^3 + cx^2 + dx(^1) + e(x^0) by x-q gave ax^3 + (aq + b)x^2 + (aq^2 + bq + c)x + (aq^3 + bq^2 + cq + d), and that there seems to be a pattern there, is that correct?


Comments

  • #2
    Anonymo
    Registered Users, Registered Users 2 Posts: 151 ✭✭Anonymo


    tolosenc you will get problems with multiple roots with your algorithm. also any iteration scheme requires a choice of root not far from the actual root. so you need to input an initial solution each time. There's a nice wikipedia article that should help you for complex root finding (http://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method). By the way your last point is almost a tautology. If q is a root then (x-q) will factor your polynomial so it's no surprise that you find a cubic polynomial as the other factor! perhaps i missed your point as to the 'pattern'.


  • #3
    tolosenc
    Registered Users, Registered Users 2 Posts: 6,889 ✭✭✭tolosenc


    Anonymo wrote: »
    tolosenc you will get problems with multiple roots with your algorithm. also any iteration scheme requires a choice of root not far from the actual root. so you need to input an initial solution each time. There's a nice wikipedia article that should help you for complex root finding (http://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method). By the way your last point is almost a tautology. If q is a root then (x-q) will factor your polynomial so it's no surprise that you find a cubic polynomial as the other factor! perhaps i missed your point as to the 'pattern'.

    For the actual situation in which this will be implented, I have a reasonable idea of where each of the roots real and imaginary parts will be (between -1 and +1).

    Thanks for the link.

    I was talking about a repeating pattern in the coefficients of the lesser degree (resultant) polynomial. ((previous coefficient * q) + (current coefficient of higher order))


Advertisement