Accurate Quotient-Difference algorithm: error analysis, improvements and applications

Peibing Du, Roberto Barrio, Hao Jiang, Lizhi Cheng

Published 2016-06-29Version 1

The quotient-difference (qd) algorithm and some of its modifications are present in several numerical algorithms and applications. As the standard qd algorithm is numerically unstable, we study in detail the error analysis of the qd algorithm and we propose a new compensated version, Compqd. The Compqd algorithm is obtained by applying Error-Free Transformations to improve the traditional qd algorithm. To perform the error analysis of the algorithms we introduce new condition numbers of the qd algorithm so that the relative forward round-off error bounds of the qd and Compqd algorithms are directly derived. Our numerical experiments illustrate that the Compqd algorithm is more accurate than the qd algorithm and faster than the DDqd algorithm (qd algorithm in double-double arithmetic). Finally, three applications in the obtention of continued fractions and in pole and zero detection are shown.