Report Number: CS-TR-69-145
Institution: Stanford University, Department of Computer Science
Title: Methods of search for solving polynomial equations
Author: Henrici, Peter
Date: December 1969
Abstract: The problem of determining a zero of a given polynomial with guaranteed error bounds, using an amount of work that can be estimated a priori, is attacked here by means of a class of algorithms based on the idea of systematic search. Lehmer's "machine method" for solving polynomial equations is a special case. The use of the Schur-Cohn algorithm in Lehmer's method is replaced by a more general proximity test which reacts positively if applied at a point close to a zero of a polynomial. Various such tests are described, and the work involved in their use is estimated. The optimality and non-optimality of certain methods, both on a deterministic and on a probabilistic basis, are established.
http://i.stanford.edu/pub/cstr/reports/cs/tr/69/145/CS-TR-69-145.pdf