Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials
- 1 October 1988
- journal article
- research article
- Published by Oxford University Press (OUP) in IMA Journal of Numerical Analysis
- Vol. 8 (4) , 473-486
- https://doi.org/10.1093/imanum/8.4.473
Abstract
Consider the (n + 1) × (n + 1) Vandermonde-like matrix P=[pi-1(αj-1)], where the polynomials po(x), …, pn(x) satisfy a three-term recurrence relation. We develop algorithms for solving the primal and dual systems, Px = b and PTa = f respectively, in O(n2) arithmetic operations and O(n) elements of storage. These algorithms generalize those of Björck & Pereyra which apply to the monomial case pi(x). When the pi(x) are the Chebyshev polynomials, the algorithms are shown to be numerically unstable. However, it is found empirically that the addition of just one step of iterative refinement is, in single precision, enough to make the algorithms numerically stable.Keywords
This publication has 0 references indexed in Scilit: