From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Polynomial roots
Date: 15 Feb 2001 11:51:52 GMT
Newsgroups: sci.math.num-analysis
Summary: Numerical algorithms to determine all real roots

In article <3a8a92f7.26574851@news.icon.co.za>,
 piern@cartoworld.com (Pier Nardin) writes:
|> Does anyone know of an efficient method to find all the real roots of
|> a real nth degree polynomial. The method must give ALL the real roots
|> and preferably not involve any complex arithmetic since I am only
|> interested in the real roots. Source code is useful but I would prefer
|> a description of the algorithm so that I can implement it myself.
|> 
|> Thanks
|> Pier

In principle it could be done using a sturm sequence algorithm,
as mentioned already by Dann Corbit. But this algorithm is notoriously 
illconditioned, hence the approach is questionable. In any case, there is 
a problem with multiple roots, which however is present for any polynomial 
roots algorithm. A multiple real root will transform to a cluster of complex
and real roots under the influence of roundoff. e.g. for a double real root 
this may mean that the real root vanishes and you get a complex conjugate pair.
Hence in this case and if you use an algorithm which is in principle
able to compute all roots, (rpoly, already mentioned, is indeed a good choice,
you get it from http://www/netlib.org in the directory toms, it is 493.)
this problem persists.

I have an algorithm for your problem, which however requires that you decide on
two things: which absolute values of the polynomial to consider as zero
(by default the algorithm computes the wilkinson error bound for 
horners scheme evaluation and takes values below this bound as zero), and a 
minimum step to proceed along the real axis. The algorithm computes an 
quadratic osculating polynomial with bounds the given one from above (if p<0) or
below (if p>0) on an interval [x_cur,x_cur+h], and proceeds either to x_cur+h
or to the real root of this second order polynomial whatever comes first,
proceeding from the left marden bound to the right marden bound of the roots.

If you are interested, drop me a mail. 
peter