Reliable root detection with the qd-algorithm: When Bernoulli, Hadamard and Rutishauser cooperate

摘要

When using Rutishauser's qd-algorithm for the determination of the roots of a polynomial (originally the poles of a meromorphic function), or for related problems, conditions have been formulated for the interpretation of the computed q- and e-values. For a correct interpretation, the so-called critical indices play a crucial role. They index a column of e-values that tends to zero because of a jump in modulus among the poles. For more than 50 years the qd-algorithm in exact arithmetic was considered to be fully understood. In this presentation we push the detailed theoretical investigation of the qd-algorithm even further and we present a new aspect that seems to have been overlooked. We indicate a new element that makes a column of e-values tend to zero, namely a jump in multiplicity among equidistant poles. This result is obtained by combining the qd-algorithm with a deflation technique, and hence mainly relying on Bernoulli's method and Hadamard's formally orthogonal polynomials. Our results round up the theoretical analysis of the qd-algorithm as formulated in its original form, and are of importance in a variety of practical applications as outlined in the introduction.