Calculation of Zeros of a Real Polynomial Through Factorization Using Euclid’s Algorithm

A composite algorithm has been designed for finding zeros of real polynomials. The algorithm has proved to be extremely successful in determining zeros of polynomials with a greater degree of accuracy and, in most cases, with greater speed than has been previously available. It has been particularly successful in efficiently calculating multiple zeros which cause trouble for most root-finding algorithms. The composite algorithm consists of several basic parts. First, the input coefficients are scaled to minimize their variations of orders of magnitude. The scaled polynomial is then factored, through the use of the greatest common divisor of a polynomial and its derivative, into m factor polynomials, each possessing only simple zeros, m being the greatest multiplicity of any zero in the original polynomial. The real zeros of each factor polynomial are calculated by the use of Sturm's theorem in combination with the Newton–Raphson method. An interpolating polynomial is formed which uniquely represents a polynomial having the complex zeros of the original polynomial. The zeros of the interpolating polynomial are found by an iterative procedure which uses rational function approximations along with the Lehmer–Schur method to obtain initial values. The calculated zeros are scaled according to the scale factor which modified the original input coefficients. The composite algorithm has been tested on randomly generated polynomials having multiple zeros, as well as many other well- and ill-conditioned polynomials. It has proved to be computationally efficient, accurate and fast.