Symbolic-Numeric QD-algorithms with applications in Function theory and Linear algebra
The univariate qd-algorithm is very useful for the determination of poles of meromorphic functions and eigenvalues of certain tridiagonal matrices. Both applications are linked to the theory of orthogonal polynomials, in particular the formally orthogonal
- PDF / 1,657,470 Bytes
- 20 Pages / 481.89 x 691.654 pts Page_size
- 7 Downloads / 122 Views
1. Introduction The univariate qd-algorithm is very useful for the determination of poles of meromorphic functions and eigenvalues of certain tridiagonal matrices. Both applications are linked to the theory of orthogonal polynomials, in particular the formally orthogonal Hadamard polynomials. When looking for the pole curves of multivariate functions, or for the eigenvalue curves of some parameterized tridiagonal matrices, the qd-algorithm has to be generalized in order to deal with multivariate data. Indeed, the univariate algorithm only involves number manipulations and these multivariate problems require the manipulation of expressions. For the computation of the poles of a multivariate meromorphic function a symbolic generalization of the qd-algorithm implemented in floating-point polynomial arithmetic seems to be possible. For the parameterized eigenvalue problem a homogeneous version implemented in exact polynomial arithmetic can be used. In Section 2 we summarize the univariate prerequisites for the material. The multivariate pole detection problem and the floating-point polynomial qd-algorithm are treated in Section 3 while the parameterized eigenvalue problem is solved in Section 4 using the homogeneous version of the qd-algorithm.
2. The univariate floating-point qd-algorithm. Let us define a linear functional c from the vector space 0, then the qd-scheme associated with J has the following properties (put ZsH = 00 if J has only s poles): (a) for each m with 0 < m ~ sand IZm-ll < IZml < IZmHI, lim
q(n)
n-+-oo m
36
= Z-l m
(b) for each m with 0
< m:S; sand IZml < IZm+ll, lim
n-+oo
e(n) m
=0
Any index m such that the strict inequality
holds, is called a critical index. It is clear that the critical indices of a function do not depend on the order in which the poles of equal modulus are numbered. The theorem above states that if m is a critical index and f is m-normal, then lim
e(n)
n-+oo m
=0
Thus the qd-table of a meromorphic function is divided into subtables by those 'e-columns tending to zero. This property motivated Rutishauser [Henrici 1974, p. 614] to apply the rhombus rules satisfied by the q- and e-values, namely q (n+l)e(n+l) =e(n)q(n) m m m m+l e(n+l) m-l
+ q(n+l) m
m + e(n) m
=q(n)
in their progressive form [Henrici 1974]: when computing the q-values from the top down rather than from left to right, one avoids divisions by possibly small e-values that can inflate rounding errors. Other reformulations can be found in [Von Matt 1997] and [Fernando et al. 1994]. Any q-column corresponding to a simple pole of isolated modulus is flanked by such e-columns and converges to the reciprocal of the corresponding pole. If a subtable contains j > 1 columns of q-values, the presence of j poles of equal modulus is indicated. In [Henrici 1974] it is also explained how to determine these poles if j > 1. THEOREM 2 [[Henrici 1974, p. 642]: Let m and m + j with j > 1 be two consecutive critical indices and let (m + j)-normal. Let the polynomials pin) be defined by
f be
k=O,1, ... ,j-1
n~O
Data Loading...
