Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

Roots of polynomials

  • 10-08-2010 3: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