Stable Look-Ahead Versions of the Euclidean and Chebyshev Algorithms
William B. Gragg, Martin H. Gutknecht · Birkhäuser Boston eBooks · 1994
We first review the basic relations between the regular formal orthogonal polynomials (FOPs) for a sequence of moments (Markov parameters), the nonsingular leading principal submatrices of the moment matrix M (which is an infinite Hankel matrix), the distinct entries on the main diagonal of the Padé table for the symbol of M (which is the generating function or z -transform of the moments), the corresponding continued fraction (which is a J-fraction or a P-fraction), and the Euclidean algorithm for power series in ζ -1 , which in the generic case is seen to reduce to the Chebyshev algorithm. The underlying recurrences are a special case of the general recurrences that are the basis of the Cabay-Meleshko algorithm which, in contrast to the aforementioned tools, is (weakly) stable. While, in the Toeplitz solver terminology, the Cabay-Meleshko algorithm is of Levinson type, we also outline the corresponding O ( N 2 ) Schur-type algorithm and a related O ( N log 2 N ) algorithm. Finally, we sketch three look-ahead strategies of which two are applicable to the O ( N log 2 N ) algorithm also. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.