Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Chebyshev-Vandermonde systems

Authors: Lothar Reichel and Gerhard Opfer
Journal: Math. Comp. 57 (1991), 703-721
MSC: Primary 65F30; Secondary 65D10
MathSciNet review: 1094957
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A Chebyshev-Vandermonde matrix

$\displaystyle 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 [Enhancements On Off] (What's this?)

  • [1] Å. Björck and V. Pereyra, Solution of Vandermonde systems of equations, Math. Comp. 24 (1970), 893-903. MR 0290541 (44:7721)
  • [2] P. J. Davis, Interpolation and approximation, Dover, New York, 1975. MR 0380189 (52:1089)
  • [3] J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart, Linpack users' guide, SIAM, Philadelphia, PA, 1979.
  • [4] S. W. Ellacott, Computation of Faber series with application to numerical polynomial approximation in the complex plane, Math. Comp. 40 (1984), 575-587. MR 689474 (84e:65021)
  • [5] Engineering and scientific subroutine library, IBM, 1987.
  • [6] B. Fischer and L. Reichel, A stable Richardson iteration method for complex linear systems, Numer. Math. 54 (1988), 225-242. MR 965923 (90a:65060)
  • [7] -, Newton interpolation in Fejér and Chebyshev points, Math. Comp. 53 (1989), 265-278. MR 969487 (90f:65015)
  • [8] W. Gautschi and G. Inglese, Lower bounds for the condition number of Vandermonde matrices, Numer. Math. 52 (1988), 241-250. MR 929571 (89b:65108)
  • [9] W. Gautschi, The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl. 52/53 (1983), 293-300. MR 709357 (84i:65043)
  • [10] -, The condition of polynomials in power form, Math. Comp. 33 (1979), 343-352. MR 514830 (80f:65034)
  • [11] -, Optimally conditioned Vandermonde matrices, Numer. Math. 24 (1975), 1-12. MR 0426401 (54:14344)
  • [12] G. H. Golub and C. F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Univ. Press, Baltimore, MD, 1989. MR 1002570 (90d:65055)
  • [13] N. J. Higham, Fast solution of Vandermonde-like systems involving orthogonal polynomials, IMA J. Numer. Anal. 8 (1988), 473-486. MR 975608 (89k:65067)
  • [14] -, Stability analysis of algorithms for solving confluent Vandermonde-like systems, SIAM J. Matrix Anal. Appl. 11 (1990), 23-41. MR 1032215 (91d:65062)
  • [15] E. Hlawka, The theory of uniform distribution, AB Academic Publishers, Berkhamsted, 1984. MR 750652 (85f:11056)
  • [16] L. Reichel and G. Opfer, Chebyshev-Vandermonde systems, BSC Report 88/48, Bergen Scientific Centre, Bergen, Norway, 1988.
  • [17] V. I. Smirnov and N. A. Lebedev, Functions of a complex variable, Iliffe Books, London, 1968.
  • [18] W. P. Tang and G. H. Golub, The block decompositions of a Vandermonde matrix and its applications, BIT 21 (1981), 505-517. MR 644690 (83e:65077)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30, 65D10

Retrieve articles in all journals with MSC: 65F30, 65D10

Additional Information

Keywords: Vandermonde-like matrix, ordering of nodes, numerical conditioning, progressive algorithm, Newton interpolation formula
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society