Heath - Scientific Computing (523150), страница 65
Текст из файла (страница 65)
Examples include elementary functions such as exponential, logarithmic, andtrigonometric functions, as well as functions that commonly occur in mathematical physics(among other areas), such as the gamma and beta functions, Bessel functions, hypergeometric functions, elliptic integrals, and many others. The specialized techniques used inapproximating these functions are beyond the scope of this book, but good software is available for evaluating almost any standard function of interest. The most frequently occurringfunctions are typically supplied as built-in functions in most programming languages usedfor scientific computing. Software for many additional functions can be found in most of thegeneral-purpose libraries mentioned in Section 1.4.1.
In addition, netlib contains severalcollections of special function routines, including amos, elefunt, fdlibm, fn, specfun, andvfnlib, and routines for numerous individual functions can be found in TOMS. Of particularnote is the portable elementary function library fdlibm, available from netlib, which isbetter than the default libraries supplied by many system vendors. An extensive survey ofavailable software for special functions can be found in [166].7.5Historical Notes and Further ReadingAs the names associated with it—Newton, Lagrange, Hermite, and many others—suggest,polynomial interpolation has long been an important part of applied mathematics. Anexcellent reference on polynomial interpolation, approximation, orthogonal polynomials,and related topics is [51].
Spline functions were first formulated by Schoenberg in 1946.The theory of splines is presented in detail in [4, 221]. More computationally orientedreferences on splines are [53, 60, 236], all of which include software. The use of splinesin computer graphics and geometric modeling is detailed in [16]. For monotone piecewisecubic interpolation, see [88]. In addition to their use for interpolation, splines can also beused for more general approximation. For example, least squares fitting by cubic splines isa good method for smoothing noisy data; see [207, 208].Review Questions7.1 True or false: There are arbitrarily manydifferent mathematical functions that interpolate a given set of data points.7.2 True or false: If an interpolating function accurately reproduces the given data values, then this fact implies that the coefficientsin the linear combination of basis functions arewell-determined.7.3 True or false: If the polynomial interpolating a given set of data points is unique, thenso is the representation of that polynomial.7.4 True or false: When interpolating a continuous function by a polynomial at equallyspaced points on a given interval, the polynomial interpolant always converges to the function as the number of interpolation points increases.7.5 What is the basic distinction between interpolation and approximation of a function?7.6 State at least two different applicationsfor interpolation.2407.7 Give two examples of numerical methods(for problems other than interpolation itself)that are based on polynomial interpolation.7.8 Is it ever possible for two distinct polynomials to interpolate the same n data points?If so, under what conditions, and if not, why?7.9 State at least two important criteria forchoosing a particular set of basis functions foruse in interpolation.7.10 Determining the parameters of an interpolant can be interpreted as solving a linearsystem Ax = y, where the matrix A dependson the basis functions used and the vector ycontains the function values to be fit.
Describein words the pattern of nonzero entries in thematrix A for polynomial interpolation usingeach of the following bases:(a) Monomial basis(b) Lagrange basis(c) Newton basis7.11 (a) Is interpolation an appropriate procedure for fitting a function to noisy data?(b) If so, why, and if not, what is a good alternative?7.12 (a) For a given set of data points (ti , yi ),i = 1, . .
. , n, rank the following three methodsfor polynomial interpolation according to thecost of determining the interpolant (i.e., determining the coefficients of the basis functions),from 1 for the cheapest to 3 for the most expensive:Monomial basisLagrange basisNewton basis(b) Which of the three methods has the bestconditioned basis matrix A, where aij =φj (ti )?(c) For which of the three methods is evaluating the resulting interpolant at a given pointthe most expensive?7.13 (a) What is a Vandermonde matrix?(b) In what context does such a matrix arise?(c) Why is such a matrix often ill-conditionedwhen its order is relatively large?CHAPTER 7. INTERPOLATION7.14 Given a set of n data points, (ti , yi ),i = 1, ..., n, determining the coefficients xi ofthe interpolating polynomial requires the solution of an n × n system of linear equationsAx = y.(a) If we use the monomial basis 1, t, t2 , ..., givean expression for the entries aij of the matrixA that is efficient to evaluate.(b) Does the condition of A tend to get better,or worse, or stay about the same as n grows?(c) How does this change affect the accuracywith which the interpolating polynomial approximates the given data points?7.15 For Lagrange polynomial interpolationof n data points (ti , yi ), i = 1, .
. . , n,(a) What is the degree of each polynomialfunction lj (t) in the Lagrange basis?(b) What function results if we sum the n functions inPthe Lagrange basis [i.e., if we takeng(t) = j=1 lj (t), what function g(t) results]?7.16 List one advantage and one disadvantageof Lagrange interpolation compared with usingthe monomial basis for polynomial interpolation.7.17 What is the computational cost (number of additions and multiplications) of evaluating a polynomial of degree n using Horner’smethod?7.18 Why is interpolation by a polynomial ofhigh degree often unsatisfactory?7.19 How should the interpolation points beplaced in an interval in order to guarantee convergence of the polynomial interpolant to sufficiently smooth functions on the interval as thenumber of points increases?7.20 What does it mean for two polynomialsp and q to be orthogonal to each other on aninterval [a, b]?7.21 (a) What is meant by a Taylor polynomial?(b) In what sense does it interpolate a givenfunction?7.22 In fitting a large number of data points,what is the main advantage of piecewise polynomial interpolation over interpolation by asingle polynomial?EXERCISES7.23 (a) How does Hermite interpolation differ from ordinary interpolation?(b) How does a cubic spline interpolant differfrom a Hermite cubic interpolant?7.24 In choosing between Hermite cubic andcubic spline interpolation, which should onechoose(a) If maximum smoothness of the interpolantis desired?(b) If the data are monotonic and this propertyis to be preserved?7.25 (a) How many times is a Hermite cubicinterpolant continuously differentiable?(b) How many times is a cubic spline interpolant continuously differentiable?7.26 The continuity and smoothness requirements on a cubic spline interpolant still leavetwo free parameters.
Give at least two examples of additional constraints that might be imposed to determine the cubic spline interpolantto a set of data points.7.27 (a) How many parameters are requiredto define a piecewise cubic polynomial with nknots?241(b) Obviously, a similar number of equations isrequired to determine those parameters. Assuming the interpolating function is to be anatural cubic spline, explain how the requirements on the function account for the necessary number of equations in the linear systemto be solved for the parameters.7.28 Which of the following interpolants to ndata points are unique?(a) Polynomial of degree at most n − 1(b) Hermite cubic(c) Cubic spline7.29 For which of the following types of interpolation is it possible, in general, to preservemonotonicity in a set of n data points (i.e.,the interpolant is increasing or decreasing ifthe data points are increasing or decreasing)?(a) Polynomial of degree at most n − 1(b) Hermite cubic(c) Cubic spline7.30 Why is it advantageous if the basis functions used for interpolation are localized (i.e.,each basis function involves only a few datapoints)?Exercises7.1 Given the three data points (−1, 1),(0, 0), (1, 1), determine the interpolating polynomial of degree two:(a) Using the monomial basis(b) Using the Lagrange basis(c) Using the Newton basisShow that the three representations give thesame polynomial.7.2 Express the following polynomial inthe correct form for evaluation by Horner’smethod: p(t) = 5t3 − 3t2 + 7t − 2.7.3 Write a formal algorithm for evaluating a polynomial at a given argument usingHorner’s nested evaluation scheme(a) For a polynomial expressed in terms of themonomial basis(b) For a polynomial expressed in Newton form7.4 How many multiplications are requiredto evaluate a polynomial p(t) of degree n − 1at a given point t(a) Represented in the monomial basis?(b) Represented in the Lagrange basis?(c) Represented in the Newton basis?7.5 In general, is it possible to interpolaten data points by a piecewise quadratic polynomial, with knots at the given data points, suchthat the interpolant is(a) Once continuously differentiable?(b) Twice continuously differentiable?In each case, if the answer is “yes,” explainwhy, and if the answer is “no,” give the maximum value for n for which it is possible.7.6 Assuming that t1 , .
. . , tn are distinct,prove that the Vandermonde matrix A givenby aij = tj−1is nonsingular.i242CHAPTER 7. INTERPOLATION7.7 Compare the cost of forming a Vandermonde matrix inductively, as in Section 7.2.1,with the cost using explicit exponentiation.7.8 Use Lagrange interpolation to derive theformulas given in Section 5.2.5 for inversequadratic interpolation.7.9 Prove that the formula using divided differences given in Section 7.2.3,polant.7.10 (a) Verify directly that the first six Legendre polynomials given in Section 7.2.4 areindeed mutually orthogonal.(b) Verify directly that they satisfy the threeterm recurrence given in Section 7.2.4.xj = f [t1 , t2 , .
. . , tj ],(c) Express each of the first six monomials, 1,t, . . ., t5 , as a linear combination of the firstsix Legendre polynomials, p0 , . . ., p5 .indeed gives the coefficient of the jth basis function in the Newton polynomial inter-7.11 Verify the properties of B-splines enumerated in Section 7.3.4.Computer Problems7.1 (a) Write a routine that uses Horner’srule to evaluate a polynomial p(t) given its degree n, an array x containing its coefficients,and the value t of the independent variable atwhich it is to be evaluated.(b) Add options to your routine to evaluate theRbderivative p0 (t) or the integral a p(t) dt, givena and b.7.2 (a) Write a routine for computing theNewton polynomial interpolant for a given setof data points, and a second routine for evaluating the Newton interpolant at a given argument value using Horner’s rule.7.4 An experiment has produced the following data:ty0.00.00.51.61.02.06.02.07.01.59.00.0We wish to interpolate the data with a smoothcurve in the hope of obtaining reasonable values of y for values of t between the points atwhich measurements were taken.(a) Using any method you like, determine thepolynomial of degree five that interpolates thegiven data, and make a smooth plot of it overthe range 0 ≤ t ≤ 9.(b) Write a routine for computing the newNewton polynomial interpolant when a newdata point is added.(b) Similarly, determine a cubic spline that interpolates the given data, and make a smoothplot of it over the same range.(c) If your programming language supports recursion, write a recursive routine that implements part a by calling your routine for partb recursively.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
