|
Title
|
|
|
|
Reliable root detection with the qd-algorithm: when Bernoulli, Hadamard and Rutishauser cooperate
|
|
|
Author
|
|
|
|
|
|
|
Abstract
|
|
|
|
| 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. |
|
|
|
Language
|
|
|
|
English
|
|
|
Source (journal)
|
|
|
|
Applied numerical mathematics. - Amsterdam
|
|
|
Publication
|
|
|
|
Amsterdam
:
2010
|
|
|
ISSN
|
|
|
|
0168-9274
|
|
|
DOI
|
|
|
|
10.1016/J.APNUM.2010.04.006
|
|
|
Volume/pages
|
|
|
|
60
:12
(2010)
, p. 1188-1208
|
|
|
ISI
|
|
|
|
000284082300003
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|