From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Vincent's method of finding roots of polynomials.
Date: 4 Dec 1995 22:50:32 GMT

In article <497u45$rk6@muir.math.niu.edu>, I wrote:

>There is a method of estimating the roots of a polynomial which is based on
>successive squaring of the roots until the ones of smaller magnitude
>become insignificant. (If I remember correctly, this is the one attributed
>to a Frenchman known only as "M. Vincent".) 

As several people have noted, the method I described in that post is
Graeffe's method. My apologies for the confusion.  I think I need to
set things to rights here and give Vincent's theorem correctly.

My source is Uspensky's "Theory of Equations", one of those delightfully
old-fashioned books in which one is presented with queer arrangements
of coefficients into tableaux which are manipulated in certain patterns.

Here is a quote from p. 128:

"The Theorem of Vincent can be stated as follows: let  a, b, c, ...
be an arbitrary sequence of positive integers. Transforming an
equation without multiple roots by a series of successive substitutions
	x=a+1/y, y=b+1/z, z=c+1/u, etc., 
after a number of such substitutions independent of the choice of
integers  a, b, c, ..., we come to a transformed equation with not
more than one variation [of sign in the coefficients]."

Thus Descarte's rule of sign can be used to compute the number of positive
roots in the transformed equation (zero or one). This in turn determines
the number of roots of the original polynomial within a certain interval.

The description of the algorithm and the proof illustrate that this
method is based on the continued fraction expansion of the roots.

I find it remarkable to note that Vincent's algorithm was published in
Volume 1  (of Series I)  of Liouville's Journal (Journal de Mathematiques
Pures at Appliquees), 1836. Uspensky suggests that the theorem was
quite forgotten by the end of the century, but does not account for its
rebirth.

I am not current on today's preferred methods of mechanized root
finding, but this method may be compared to current interest in exact
and interval arithmetic for numerical mathematics.

dave