On The Zero-Finding In Polynomials: A Survey

Polynomials constitute a very important class of functions in both theoretical and applied mathematics. In particular, polynomials are extremely important for numerical computations on computers, because computers can only perform finitely many arithmetic operations, which totally match the definition of polynomials. Since the definition of polynomials is so simple, one might assume that the properties of polynomials are also obvious. Of course, this cognition is not a fact. For example, Weierstraß's approximation theorem states that each function that is continuous on a closed and bounded interval can be approximated uniformly by a sequence of polynomials. It means that we always can use polynomials to approximate continuous functions within a given tolerable uncertainty. In addition, Bernstein polynomials have been constructed explicitly to support Weierstraß's approximation theorem. Furthermore, orthogonal polynomials are known being able to minimize the error caused by interpolation of a given continuous function. In particular, the roots of orthogonal polynomials play an important role in numerical integration. In this context, information on locations of roots of a polynomial is essential. It is especially important for the convergence and effectiveness of numerical computation of all the approximate roots. However, this is obviously not a trivial issue. In the literature, we find Descartes’s theorem, Fourier-Budan’s theorem, Sturm’s theorem, Rouch´e’s theorem and Hurwitz polynomials that concern with the positions of roots of polynomials in a complex plane. These properties have been known for more than a century. However, many of them are most likely unknown for engineers. This is a pity because they can be used to limit the seating range of the polynomial roots. On the other side, Newton’s approximation formula is well-known for numerical computation of a root of a polynomial, whereas Graeffe's root-squaring method is less familiar, which yet can numerically find out why roots are very close to each other. There yet exists another important numerical method for finding all the roots of a polynomial in a given domain, namely, the extended interval version of Newton’s method, which can numerically approximate all the roots without knowing their locations in advance. The presentation surveys properties and numerical methods on the zero-finding in polynomials. Keyword - Zero-finding, Polynomials