Three-Stage Variable-Shift Iterations for the Solution of Polynomial Equations with a Posteriori Error Bounds for the Zeros

摘要

Two new algorithms are introduced for solving polynomial equations and their implementation in ALGOL 60. An ALGOL 60 program is included for finding error bounds and improved approximations. The first zerofinding algorithm is a three-stage process for complex polynomials which is related to applying inverse iteration to the companion matrix. The three stages correspond to using inverse iteration with no shift, a fixed shift and a variable shift. A proof is included that the three stage algorithm always converges and that the third stage has a 'better than quadratic' rate of convergence. The second zerofinding algorithm is a related three-stage process for real polynomials which finds either linear or quadratic factors. The bound program finds individual bounds with an option for improving the approximations. Numerical tests indicate that the amount of work done by the zerofinding program is almost independent of the configuration of the zeros. (Author)