References
Polynomial root-finding is an important, well-developed topic in numerical analysis, so most books on
numerical methods or numerical analysis include a section on finding polynomial roots. Those that
have been most helpful to me follow.
Numerical Recipes in FORTRAN; The Art of Scientific Computing
Press, Teukolsky, Vetterling and Flannery, 1992, Cambridge University Press.
Section 9.5 is devoted to finding roots of polynomials, and describes the processes of deflation and
inverting the coefficients. Some other methods are discussed, including the eigenvalue technique
(used by cybernesto's proots()) and mention of the Jenkins-Traub and Lehmer-Schur algorithms.
Numerical Methods that (usually) Work
Forman S. Acton, 1990, The Mathematical Association of America.
Acton discusses polynomial root-finding in all of chapter 7, Strategy versus Tactics. He dismisses
Laguerre's method as "not sufficiently compatible with our other algorithms', but discusses it, anyway.
Mr. Acton's objection seems to be the requirement for complex arithmetic, but points out that
Laguerre's method is guaranteed to converge to a real root when all coefficients are real.
A survey of numerical mathematics, volume 1
David M. Young, Robert Todd Gregory, 1988, Dover.
Chapter 5 is a thorough (70 page) development and examination of the entire process of finding
polynomial roots and determining if the roots are 'good enough'. Starting with general properties of
polynomials, developed in a theorem and proof format, Young and Gregory continue by examining the
methods of Newton, Lin and Lin-Bairstow, and the secant method. They proceed to the methods of
Muller and Cauchy before developing procedures for finding approximate values of roots, including
Descarte's rule of signs, Sturm sequences, and the Lehmer-Schur method. Acceptance criteria for real
and complex roots are derived. Matrix-related (eigenvalue) methods are described, including Bernoulli,
modified Bernoulli and inverse-power (IP). The chapter continues with a discussion of polyalgorithms,
which consist of two phases of root-finding: an initial phase, and an assessment/refinement phase. In
the final section, other methods are very briefly discussed, including Jenkins-Traub and Laguerre,
which the authors describe as "An excellent method for determining zeroes of a polynomial having only
real zeroes ..."
Rounding errors in Algebraic Processes
J.H. Wilkinson, 1994, Dover Publications.
Wilkinson devotes chapter 2 to polynomials and polynomial roots, and develops several important
ideas in solving polynomials in general. This book is a 'classic' in numerical analysis.
Validating polynomial numerical computations with complementary automatic methods
Phillipe Langlois, Nathalie Revol, June 2001, INRIA Research Report No. 4205, Institut National de
Recherche en Informatique et en Automatique.
(This paper is available at http://www.inria.fr/index.en.html.)
While the focus of this paper is on using stochastic, deterministic and interval arithmetic methods to
estimate the number of significant digits in calculated polynomial roots, section 3 summarizes the best
attainable accuracy of multiple root solutions. This paper is also the source of the example polynomial
p(x) = 1.47x
3
+ 1.19x
2
-1.83x + 0.45.
The following web sites are useful or at least interesting:
Mcnamee's bibliography on roots of polynomials
http://www.elsevier.com/homepage/sac/cam/mcnamee/
6 - 126
To Next Page
Loading...
Need help?
General
