A Three-State Algorithm for Real Polynomials Using Quadratic Iteration

Jenkins, M.A.; Traub, Joseph F.

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² 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.


  • thumnail for Traub__a_three_stage_algorithm_for_real_polynomials_using_quadratic_iteration.pdf Traub__a_three_stage_algorithm_for_real_polynomials_using_quadratic_iteration.pdf application/pdf 1.55 MB Download File

Also Published In

SIAM Journal on Numerical Analysis

More About This Work

Academic Units
Computer Science
Published Here
October 10, 2013