Heath - Scientific Computing (523150), страница 66
Текст из файла (страница 66)
Compare its performance withthat of your original implementation.(c) Which interpolant seems to give more reasonable values between the given data points?Can you explain why each curve behaves theway it does?7.3 (a) Write the system of equations derived in Example 7.6 in matrix form.(b) Use a library routine, or one of your owndesign, to solve the resulting 8×8 linear systemusing the data given in Example 7.1.(c) Plot the resulting natural cubic spline,along with the given data points. Also plot thefirst and second derivatives of the cubic splineand confirm that all of the required conditionsare met.(d ) Might piecewise linear interpolation be abetter choice for these particular data? Why?7.5 Interpolating the data pointstyty00255113664249793648164should give an approximation to the squareroot function.COMPUTER PROBLEMS243Year190019101920193019401950196019701980(a) Compute the polynomial of degree eightthat interpolates these nine data points.
Plotthe resulting polynomial as well as the corresponding values given by the built-in sqrtfunction over the domain [0, 64].(b) Use a cubic spline routine to interpolate thesame data and again plot the resulting curvealong with the built-in sqrt function.(c) Which of the two interpolants is more accurate over most of the domain?(d ) Which of the two interpolants is more accurate between 0 and 1?7.6 The gamma function is defined byΓ(x) =∞Ztx−1 e−t dt,x > 0.0For an integer argument n, the gamma function has the valueΓ(n) = (n − 1)! ,so interpolating the data pointsty11213246524should yield an approximation to the gammafunction over the given range.(a) Compute the polynomial of degree fourthat interpolates these five data points.
Plotthe resulting polynomial as well as the corresponding values given by the built-in gammafunction over the domain [1, 5].(b) Use a cubic spline routine to interpolate thesame data and again plot the resulting curvealong with the built-in gamma function.(c) Which of the two interpolants is more accurate over most of the domain?(d ) Which of the two interpolants is more accurate between 1 and 2?7.7 Consider the following population datafor the United States:Population76, 212, 16892, 228, 496106, 021, 537123, 202, 624132, 164, 569151, 325, 798179, 323, 175203, 302, 031226, 542, 199There is a unique polynomial of degree eightthat interpolates these nine data points, butof course that polynomial can be representedin many different ways.
Consider the following possible sets of basis functions φj (t),j = 1, . . . , 9:1.2.3.4.φj (t) = tj−1φj (t) = (t − 1900)j−1φj (t) = (t − 1940)j−1φj (t) = ((t − 1940)/40)j−1(a) For each of these four sets of basis functions, generate the corresponding Vandermonde matrix and compute its condition number using a library routine for condition estimation. How do the condition numbers compare? Explain your results.(b) Using the best-conditioned basis found inpart a, compute the polynomial interpolantto the population data. Plot the resultingpolynomial, using Horner’s nested evaluationscheme to evaluate the polynomial at one-yearintervals to obtain a smooth curve.
Also plotthe original data points on the same graph.(c) Use a cubic spline routine to interpolate thepopulation data, and again plot the resultingcurve on the same graph.(d ) Use both the polynomial and the spline toextrapolate the population to 1990 and compare the values obtained. How close are theseto the true value of 248,709,873 according tothe 1990 census?(e) Determine the Lagrange interpolant to thesame nine data points and evaluate it at thesame yearly intervals as in parts b and c.Compare the total execution time with thosefor Horner’s nested evaluation scheme and forevaluating the cubic spline.244(f ) Determine the Newton form of the polynomial interpolating the same nine data points.Now determine the Newton polynomial of onedegree higher that also interpolates the additional data point for 1990 given in part d,without starting over from scratch (i.e., usethe Newton polynomial of degree eight alreadycomputed to determine the new Newton polynomial).
Plot both of the resulting polynomi-CHAPTER 7. INTERPOLATIONals (of degree eight and nine) over the intervalfrom 1900 to 1990.(g) Round the population data for each yearto the nearest million and compute the corresponding polynomial interpolant of degreeeight using the same basis as in part b. Compare the resulting coefficients with those determined in part b. Explain your results.Chapter 8Numerical Integration and Differentiation8.1Numerical QuadratureThe numerical approximation of definite integrals is known as numerical quadrature.
Thisname derives from ancient methods for computing areas of curved figures, the most famousexample of which is the problem of “squaring the circle” (finding a square having the samearea as a given circle). In our case we wish to compute the area under a curve defined overan interval on the real line. Thus, the quantity we wish to compute is of the formI(f ) =Zbf (x) dx.aWe will generally take the interval of integration to be finite, and we will assume for themost part that the integrand f is continuous and smooth.
We will consider only brieflyhow to deal with an infinite interval of integration or an integrand function that may havediscontinuities or singularities.Note that we seek a single number as an answer, not a function or a symbolic formula.This feature distinguishes numerical quadrature from the solution of differential equationsor the evaluation of indefinite integrals, as in elementary calculus and in many packages forsymbolic computation.An integral is, in effect, an infinite summation.
It should come as no surprise that wewill approximate this infinite sum by a finite sum. Such a finite sum, in which the integrandfunction is sampled at a finite number of points in the interval of integration, is called aquadrature rule. Our main object of study will be how to choose the sample points and howto weight their contributions to the quadrature formula so that we obtain a desired levelof accuracy at a reasonable computational cost. For numerical quadrature, computationalwork is usually measured by the number of evaluations of the integrand function that arerequired.2452468.1.1CHAPTER 8. NUMERICAL INTEGRATION AND DIFFERENTIATIONQuadrature RulesAn n-point quadrature formula has the formI(f ) =ZnXbf (x) dx =awi f (xi ) + Rn .i=1The points xi at which the function f is evaluated are called the nodes or abscissas, themultipliers wi are called the weights, and Rn is the remainder or error.
To estimate thevalue of the integral, we simply compute the sumI(f ) ≈nXwi f (xi ),i=1which is known as a quadrature rule.The exact error term Rn usually involves information, such as higher derivatives of f ,that is inconvenient or even impossible to obtain, so we usually content ourselves withmerely estimating the possible error in using a given rule. The error term can be estimatedby means of a Taylor series expansion of the integrand function, as we will see in subsequentexamples.Quadrature rules are based on polynomial interpolation. In effect, the integrand function f is sampled at some number of points, the polynomial that interpolates the functionat those points is determined, and the integral of the interpolant is then taken as an approximation to the integral of the original function.
In practice, however, the interpolatingpolynomial is not determined explicitly each time a particular integral is to be evaluated.Instead, polynomial interpolation is used to determine the weights corresponding to thechosen nodes in a quadrature rule, which can be stored and then used in approximating anyintegral over the interval. For example, if Lagrange interpolation is used, then the weightsare given by the integrals of the corresponding Lagrange basis functions for the given set ofpoints,Z bwi =li (x) dx, i = 1, .
. . , n,aand these are independent of any particular integrand.8.28.2.1Newton-Cotes QuadratureNewton-Cotes Quadrature RulesIn general, for any value of n, polynomial interpolation of degree n − 1 can be used togenerate an n-point quadrature rule. If the nodes xi are equally spaced in the interval [a, b],the resulting interpolatory quadrature rule is known as a Newton-Cotes quadrature rule. ANewton-Cotes rule is said to be closed if its nodes include the endpoints a and b; otherwisethe rule is said to be open.As simple examples, interpolation at one, two, and three equally spaced points on theinterval [a, b] gives the first three Newton-Cotes quadrature rules:8.2. NEWTON-COTES QUADRATURE247• Interpolating the function value at the midpoint of the interval by a constant (i.e., apolynomial of degree zero) gives a one-point quadrature rule known as the midpoint ruleor rectangle rule:a+bI(f ) ≈ M (f ) = (b − a)f.2• Interpolating the function values at the two endpoints of the interval by a straight line(i.e., a polynomial of degree one) gives a two-point quadrature rule known as the trapezoidrule:b−a(f (a) + f (b)).I(f ) ≈ T (f ) =2• Interpolating the function values at three points (the two endpoints and the midpoint)by a quadratic polynomial gives a three-point quadrature rule known as Simpson’s rule:a+bb−af (a) + 4f+ f (b) .I(f ) ≈ S(f ) =62Example 8.1 Newton-Cotes Quadrature.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
