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 J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart, Linpack users’ guide, SIAM, Philadelphia, PA, 1979.
- 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, IBM, 1987.
- 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 L. Reichel and G. Opfer, Chebyshev-Vandermonde systems, BSC Report 88/48, Bergen Scientific Centre, Bergen, Norway, 1988. V. I. Smirnov and N. A. Lebedev, Functions of a complex variable, Iliffe Books, London, 1968.
- 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
Additional Information
- © Copyright 1991 American Mathematical Society
- Journal: Math. Comp. 57 (1991), 703-721
- MSC: Primary 65F30; Secondary 65D10
- DOI: https://doi.org/10.1090/S0025-5718-1991-1094957-9
- MathSciNet review: 1094957