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
| |
Volume/pages
|
|
|
|
60
:12
(2010)
, p. 1188-1208
| |
ISI
|
|
|
|
000284082300003
| |
Full text (Publisher's DOI)
|
|
|
|
| |
|