Finding roots of an n-degree polynomial

incisor71

Hi all,

This has cropped up a few times during my studies last year. Extensive Googling and newsgroup searching have drawn a blank. Does anyone know where I would find an algorithm to obtain the roots (possibly complex) of an n-degree polynomial a + bx + cx^2 + ...... ?

(To simplify the matter - slightly - only real coefficients would be used in the polynomial whose roots I'm trying to find.)

About 12 years ago I found an algorithm on some newsgroup, which implemented "synthetic division" - one simply had to supply the degree of the polynomial and the (real) coefficients. My more recent attempts to find this gem have failed. {Edit: the algorithm was written in pre-ANSI C, though a version in an interpreted language such as BASIC or Perl would be fine.}

Can anyone guide me in the right direction?

Many thanks in advance for your help!

smiles

incisor71 wrote:

Hi all,

This has cropped up a few times during my studies last year. Extensive Googling and newsgroup searching have drawn a blank. Does anyone know where I would find an algorithm to obtain the roots (possibly complex) of an n-degree polynomial a + bx + cx^2 + ...... ?

(To simplify the matter - slightly - only real coefficients would be used in the polynomial whose roots I'm trying to find.)

About 12 years ago I found an algorithm on some newsgroup, which implemented "synthetic division" - one simply had to supply the degree of the polynomial and the (real) coefficients. My more recent attempts to find this gem have failed. {Edit: the algorithm was written in pre-ANSI C, though a version in an interpreted language such as BASIC or Perl would be fine.}

Can anyone guide me in the right direction?

Many thanks in advance for your help!

It has been proven that there is no general solution to n-th degree polynomial with degree greater than 4. Proved by Niels Henrik Abel (1824)
http://en.wikipedia.org/wiki/Abel-Ruffini_theorem

For cubic (x^3) and quartic (x^4) there are general solutions:
http://mathforum.org/dr.math/faq/faq.cubic.equations.html
(these were found by Scipione de Ferro and Lodovico Ferrari respectively (spelling may be off))

This may also be of help to you:
http://en.wikipedia.org/wiki/Polynomial#Polynomials_and_calculus

Perhaps extensive googling isn't what you were doing!

If you want to learn more about this topic it's generally done under the heading of Numerical Analysis, and I would recomend "Introduction to Numerical Analysis" by Suli & Mayers (actually talks about this stuff in the first page as far as I remember)

So instead of algorithms you will be working with approximations and different methods, ie, Euler's Methods, Improved & Modified Eulers, Runge-Kutta 2nd order and 4th order conditions. It's relatively easily done in MathLab and the error is bounded and can be shown using some of these methods.

Fio