A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration

Abstract

We introduce a new three-stage process for calculating the zeros of a polynomial with real coefficients. The algorithm finds either a linear or quadratic factor, working completely in real arithmetic. In the third stage the algorithm uses one of two variable-shift iterations corresponding to the linear or quadratic case. The iteration for a linear factor is a real arithmetic version of the third stage of the algorithm for complex polynomials which we studied in an earlier paper. A new variable-shift iteration is introduced in this paper which is suitable for quadratic factors. If the complex algorithm and the new real algorithm are applied to the same real polynomial, then the real algorithm is about four times as fast. We prove that the mathematical algorithm always converges and show that the rate of convergence of the third stage is faster than second order. The problem and algorithm may be recast into matrix form. The third stage is a quadratic form of shifted inverse powering and a quadratic form of generalized Rayleigh iteration. The results of extensive testing are summarized. For an ALGOL W program run on an.IBM 360/67 we found that for polynomials ranging in degree from 20 to 50, the time required to calculate all zeros averaged $2n^2 $ milliseconds. An ALGOL 60 implementation of the algorithm and a program which calculates a posteriors bounds on the zeros may be found in Jenkins’ 1969 Stanford dissertation [2].