Chebyshev-Vandermonde systems

Reichel, Lothar; Opfer, Gerhard

doi:10.1090/S0025-5718-1991-1094957-9

Chebyshev-Vandermonde systems
HTML articles powered by AMS MathViewer

by Lothar Reichel and Gerhard Opfer PDF

Math. Comp. 57 (1991), 703-721 Request permission

Abstract:

A Chebyshev-Vandermonde matrix \[ V = [{p_j}({z_k})]_{j,k = 0}^n \in {\mathbb {C}^{(n + 1) \times (n + 1)}}\] is obtained by replacing the monomial entries of a Vandermonde matrix by Chebyshev polynomials ${p_j}$ for an ellipse. The ellipse is also allowed to be a disk or an interval. We present a progressive scheme for allocating distinct nodes ${z_k}$ on the boundary of the ellipse such that the Chebyshev-Vandermonde matrices obtained are reasonably well-conditioned. Fast progressive algorithms for the solution of the Chebyshev-Vandermonde systems are described. These algorithms are closely related to methods recently presented by Higham. We show that the node allocation is such that the solution computed by the progressive algorithms is fairly insensitive to perturbations in the right-hand side vector. Computed examples illustrate the numerical behavior of the schemes. Our analysis can also be used to bound the condition number of the polynomial interpolation operator defined by Newton’s interpolation formula. This extends earlier results of Fischer and the first author.

References

Åke Björck and Victor Pereyra, Solution of Vandermonde systems of equations, Math. Comp. 24 (1970), 893–903. MR 290541, DOI 10.1090/S0025-5718-1970-0290541-1
Philip J. Davis, Interpolation and approximation, Dover Publications, Inc., New York, 1975. Republication, with minor corrections, of the 1963 original, with a new preface and bibliography. MR 0380189

Linpack users’ guide

S. W. Ellacott, Computation of Faber series with application to numerical polynomial approximation in the complex plane, Math. Comp. 40 (1983), no. 162, 575–587. MR 689474, DOI 10.1090/S0025-5718-1983-0689474-7

Engineering and scientific subroutine library

Bernd Fischer and Lothar Reichel, A stable Richardson iteration method for complex linear systems, Numer. Math. 54 (1988), no. 2, 225–242. MR 965923, DOI 10.1007/BF01396976
Bernd Fischer and Lothar Reichel, Newton interpolation in Fejér and Chebyshev points, Math. Comp. 53 (1989), no. 187, 265–278. MR 969487, DOI 10.1090/S0025-5718-1989-0969487-3
Walter Gautschi and Gabriele Inglese, Lower bounds for the condition number of Vandermonde matrices, Numer. Math. 52 (1988), no. 3, 241–250. MR 929571, DOI 10.1007/BF01398878
Walter Gautschi, The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl. 52/53 (1983), 293–300. MR 709357, DOI 10.1016/0024-3795(83)80020-2
Walter Gautschi, The condition of polynomials in power form, Math. Comp. 33 (1979), no. 145, 343–352. MR 514830, DOI 10.1090/S0025-5718-1979-0514830-6
Walter Gautschi, Optimally conditioned Vandermonde matrices, Numer. Math. 24 (1975), 1–12. MR 426401, DOI 10.1007/BF01437212
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Nicholas J. Higham, Fast solution of Vandermonde-like systems involving orthogonal polynomials, IMA J. Numer. Anal. 8 (1988), no. 4, 473–486. MR 975608, DOI 10.1093/imanum/8.4.473
Nicholas J. Higham, Stability analysis of algorithms for solving confluent Vandermonde-like systems, SIAM J. Matrix Anal. Appl. 11 (1990), no. 1, 23–41. MR 1032215, DOI 10.1137/0611002
Edmund Hlawka, The theory of uniform distribution, A B Academic Publishers, Berkhamsted, 1984. With a foreword by S. K. Zaremba; Translated from the German by Henry Orde. MR 750652

Chebyshev-Vandermonde systems

Functions of a complex variable

W. P. Tang and G. H. Golub, The block decomposition of a Vandermonde matrix and its applications, BIT 21 (1981), no. 4, 505–517. MR 644690, DOI 10.1007/BF01932847