A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration

[摘要] We introduce a new three-stage process for calculating the zeros of a polynomial with complex coefficients. The algorithm is similar in spirit to the two-stage algorithms studied by Traub in a series of papers. The algorithm is restriction free, that is, it converges for any distribution of zeros. A proof of global convergence is given. Z eros are calculated in roughly increasing order of magnitude to avoid deflation instability. Shifting is incorporated in a natural and stable way to break equimodularity and speed convergence. The three stages use no shift, a fixed shift, and a variable shift, respectively. To obtain additional insight we recast the problem and algorithm into matrix form. The third stage is inverse iteration with the companion matrix, followed by generalized Rayleigh iteration. A program implementing the algorithm was written in a dialect of ALGOL 60 and run on Stanford University's IBM 360/67. The program has been extensively tested and testing is continuing. For polynomials with complex coefficients and of degrees ranging from 20 to 50, the time required to calculate all zeros averages $8n^2$ milliseconds. Timing information and a numerical example are provided. A description of the implementation, an analysis of the effects of finite-precision arithmetic, an ALGOL 60 program, the results of extensive testing, and a second program which clusters the zeros and provides a posteriori error bounds will appear elsewhere.

[学科分类] 计算机科学（综合）