Institution: Stanford University, Department of Computer Science

Title: The QD-algorithm as a method for finding the roots of a polynomial equation when all roots are positive

Author: Andersen, Christian

Date: June 1964

Abstract: The Quotient-Difference (QD)-scheme, symmetric functions and some results from the theory of Hankel determinants are treated. Some well known relations expressing the elements of the QD-scheme by means of the Hankel determinants are presented. The question of convergence of the columns of the QD-scheme is treated. An exact expression for $q_{n}^{k}$ is developed for the case of different roots. It is proved that the columns of the QD-scheme will converge not only in the well known case of different roots, but in all cases where the roots are positive. A detailed examination of the convergence to the smallest root is presented. An exact expression for $q_{n}^{N}$ is developed. This expression is correct in all cases of multiple positive roots. It is shown that the progressive form of the QD-algorithm is only 'mildly unstable'. Finally, some ALGOL programs and some results obtained by means of these are given.

http://i.stanford.edu/pub/cstr/reports/cs/tr/64/9/CS-TR-64-9.pdf