Summary
A forward error analysis is presented for the Björck-Pereyra algorithms used for solving Vandermonde systems of equations. This analysis applies to the case where the points defining the Vandermonde matrix are nonnegative and are arranged in increasing order. It is shown that for a particular class of Vandermonde problems the error bound obtained depends on the dimensionn and on the machine precision only, being independent of the condition number of the coefficient matrix. By comparing appropriate condition numbers for the Vandermonde problem with the forward error bounds it is shown that the Björck-Pereyra algorithms introduce no more uncertainty into the numerical solution than is caused simply by storing the right-hand side vector on the computer. A technique for computing “running” a posteriori error bounds is derived. Several numerical experiments are presented, and it is observed that the ordering of the points can greatly affect the solution accuracy.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adams, D.A.: A stopping criterion for polynomial root finding. Commun. ACM10, 655–658 (1967)
Almacany, M., Dunham, C.B., Williams, J.: Discrete Chebyshev approximation by interpolating rationals. IMA J. Numer. Anal.4, 467–477 (1984)
Ballester, C., Pereyra, V.: On the construction of discrete approximations to linear differential expressions. Math. Comput.21, 297–302 (1967)
Björck, Å., Elfving, T.: Algorithms for confluent Vandermonde systems. Numer. Math.21, 130–137 (1973)
Björck, Å. Pereyra, V.: Solution of Vandermonde systems of equations. Math. Comput.24, 893–903 (1970)
Conte, S.D., de Boor, C.: Elementary numerical analysis (Third edition). New York-Tokyo: McGraw-Hill 1980
de Boor, C., Pinkus, A.: Backward error analysis for totally positive linear systems. Numer. Math.27, 485–490 (1977)
Dunham, C.B.: Choice of basis for Chebyshev approximation. ACM Trans. Math. Software8, 21–25 (1982)
Freeman, T.L.: Solution of Vandermonde systems of equations: an alternative view. Numerical Analysis Report No. 45, University of Manchester, England, 1980
Gantmacher, F.R.: The Theory of Matrices, vol. Two. New York: Chelsea 1959
Gautschi, W.: On inverses of Vandermonde and confluent Vandermonde matrices. Numer. Math.4, 117–123 (1962)
Gautschi, W.: Optimally conditioned Vandermonde matrices. Numer. Math.24, 1–12 (1975)
Golub, G.H., Van Loan, C.F.: Matrix Computations. Baltimore, MD: Johns Hopkins University Press 1983
Gustafson, S.-Å.: Control and estimation of computational errors in the evaluation of interpolation formulae and quadrature rules. Math. Comput.24, 847–854 (1970)
Lyness, J.N., Moler, C.B.: Van der Monde systems and numerical differentiation. Numer. Math.8, 458–464 (1966)
Peters, G., Wilkinson, J.H.: Practical problems arising in the solution of polynomial equations. J. Inst. Math. Appl.8, 16–35 (1971)
Skeel, R.D.: Scaling for numerical stability in Gaussian elimination J. Assoc. Comput. Mach.26, 494–526 (1979)
Tang, W.P., Golub, G.H.: The block decomposition of a Vandermonde matrix and its applications. BIT21, 505–517 (1981)
Trapp, G.E., Squire, W.: Solving nonlinear Vandermonde systems. Comput. J.18, 373–374 (1975)
Traub, J.F.: Associated polynomials and uniform methods for the solution of linear problems. SIAM Rev.8, 277–301 (1966)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Higham, N.J. Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems. Numer. Math. 50, 613–632 (1987). https://doi.org/10.1007/BF01408579
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01408579