Abstract
This paper addresses a fundamental problem in mathematics and numerical analysis, that of determining a polynomial interpolant to specified data. The data is taken as consisting of a set of points (abscissae), at each of which is specified a function value. Additionally, at each point, any number of leading derivative values of the function may be given.
Mathematically, this problem is solved. The classical Lagrangian interpolation formula applies in the derivative-free case, and the Newton form of the interpolating polynomial in general.Numerically, few reliable algorithms are available; most published algorithms concentrate on speed of computation. This paper describes an algorithm that delivers the required polynomial in Chebyshev form. It is based on the repeated use of the Newton representation, with a data ordering strategy and iterative refinement to improve accuracy, using a carefully devised merit function to measure success. The algorithm attempts to provide a polynomial that is stable in the sense of backward error analysis, i.e. that is exact for slightly perturbed data.
Implementations of the algorithm have been in use since the early 1980s in the NAG Library and NPL's Data Approximation Subroutine Library (DASL). In addition to providing polynomial interpolants in their own right, these implementations are used as computational modules in the NAG and DASL routines for constrained least-squares polynomial data fitting.
This paper constitutes the first detailed presentation of the algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G.T. Anthony and M.G. Cox, The National Physical Laboratory's Data Approximation Subroutine Library, in:Algorithms for Approximation, eds. J.C. Mason and M.G. Cox (Clarendon Press, Oxford, 1987) pp. 669–687.
å. Björck and V. Pereyra, Solution of Vandermonde systems of equations. Math. Comput. 24 (1970) 893–903.
E.O. Brigham,The Fast Fourier Transform (Prentice-Hall, New York, 1974).
C.W. Clenshaw, A note on the summation of Chebyshev series, Math. Tab. Wash. 9 (1955) 118–120.
C.W. Clenshaw, Curve fitting with a digital computer, Comp. J. 2 (1960) 170–173.
C.W. Clenshaw,Mathematical Tables, Vol. 5: Chebyshev Series for Mathematical Functions (Her Majesty's Stationary Office, 1962).
C.W. Clenshaw and J.G. Hayes, Curve and surface fitting, J. Inst. Math. Appl. 1 (1965) 164–183.
J.R.A. Cooper, NPL Algorithms Library Brief Guide — 1979, Technical Report CSU 3/79, National Physical Laboratory, Teddington, UK (1979).
M.G. Cox, An algorithm for spline interpolation, J. Inst. Math. Appl. 15 (1975) 95–108.
M.G. Cox, Piecewise Chebyshev series, Bull. Inst. Meth. Appl. 22 (1986) 163–166.
M.G. Cox, The NPL Data Approximation Subroutine Library: current and planned facilities, NAG Newsletter 2/87 (1987) 3–16.
C. de Boor,A Practical Guide to Splines (Springer, New York, 1978).
B. Fischer and L. Reichel, Newton interpolation in Fejér and Chebyshev points, Math. Comput. 531 (1989) 265–278.
B. Ford, J. Bentley, J.J. du Croz and S.J. Hague, The NAG Library “machine”, Software-Practice and Experience 9 (1979) 56–72.
G.E. Forsythe, Generation and use of orthogonal polynomials for data-fitting with a digital computer, J. Soc. Indust. Appl. Math. 5 (1957) 74–88.
W.M. Gentleman, An error analysis of Goertzel's (Watt's) method for computing Fourier coefficients, Comp. J. 12 (1969) 160–165.
M. Gershinsky and D.A. Levine, Aitken-Hermite interpolation, J. ACM 11 (1964) 352–356.
P.T. Graves-Morris, Practical, reliable, rational interpolation, J. Inst. Math. App. 25 (1980) 267–286.
N.J. Higham, Stability analysis of algorithms for solving confluent Vandermonde-like systems, Technical Report Numerical Analysis No. 148, University of Manchester (1987).
N.J. Higham, Fast solution of Vandermonde-like systems involving orthogonal polynomials, IMA J. Numer. Anal. 8 (1988) 473–486.
R.E. Huddlestone, CDC 6600 routines for the interpolation of data and of data with derivatives. Technical Report SLL-74-0214, Sandia Laboratories, Livermore, CA, USA (1974).
F.T. Krogh, Efficient algorithms for polynomial interpolation and numerical differentiation, Math. Comput. 24 (1970) 185–190.
F.T. Krogh, Recurrence relations for computing with modified divided differences, Technical Report 77-46, Jet Propulsion Laboratory, Pasadena, CA 91103 (1977).
A.C.R. Newbury, Interpolation by algebraic and trigonometric polynomials, Math. Comput. 20 (1966) 597–599.
J. Oliver, Stable methods for evaluating the points cos(iπ/n), J. Inst. Math. Appl. 16 (1975) 247–257.
J. Oliver, An error analysis of the modified Clenshaw method for evaluating Chebyshev and Fourier series, J. Inst. Math. Appl. 20 (1977) 379–391.
H.E. Salzer, A recurrence scheme for converting from one orthogonal expansion to another, Commun. ACM 16 (1973) 705–707.
H. Tal-Ezer, High degree polynomial interpolation in Newton form, SIAM J. Sci. Stat. Comp. 12 (1991) 648–667.
J.H. Wilkinson,Rounding Errors in Algebraic Processes, Notes in Applied Science No. 32 (Her Majesty's Stationary Office, London, 1963).
J.H. Wilkinson,The Algebraic Eigenvalue Problem (Clarendon Press, Oxford, 1965).
L.B. Winrich, Note on a comparison of evaluation schemes for the interpolating polynomial, Comp. J. 12 (1969) 154–155.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cox, M.G. Reliable determination of interpolating polynomials. Numer Algor 5, 133–154 (1993). https://doi.org/10.1007/BF02215677
Issue Date:
DOI: https://doi.org/10.1007/BF02215677