From: tim274@aol.com (Tim274)
Newsgroups: sci.math.num-analysis
Subject: Re: Polynomial roots with multiple zeros.
Date: 11 Jan 1999 04:07:04 GMT
Keywords: Numerical root-finding appropriate with multiple roots

The problem with using the gcd of the polynomial and its derivative is that
this relies on the coefficients being integer/rational.

I have had great success over the years using jenkins algorithm (for real
coefficients), or jenkins-traub (for complex coefficients).

These algorithms used to be in the collected ACM algorithms.

Tim Norfolk
==============================================================================

From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Newsgroups: sci.math.num-analysis
Subject: Re: Polynomial roots with multiple zeros.
Date: 11 Jan 1999 12:11:07 GMT

In article <stevenj-1101990008570001@gil-galad.mit.edu>,
 stevenj@alum.mit.edu (Steven G. Johnson) writes:
|> tim274@aol.com (Tim274) wrote:
|> > The problem with using the gcd of the polynomial and its derivative is that
|> > this relies on the coefficients being integer/rational.
|> 
|> That isn't right, I think...you can divide polynomials and find the
|> remainders even if their coefficients are irrational.  That is all you
|> need to find the gcd (applying Euclid's algorithm).
in principle, all this is correct. but the bad message is that computing the
gcd is terribly unstable under roundoff, so besides some trivial cases 
computing the gcd numerically and obtaining the multiple roots from it
will fail. methods like Newton-Maehly (Newton with implicit deflation)
Laguerre or the already cited Jenkins-Traub algorithm do not suffer so 
much from root multiplicities as one might suspect. Of course, any multiple
root will inherently be illconditioned against perturbations and if one needs
high precision then roundoff free computation of the gcd is mandatory. 
but in real life applications, the coefficients of the polynomial itself 
will already be computed quantities and I cannot see any sense in computing 
high precision results from erroneous original data. 
hope this helps
peter