Shampine, Allen, Pruess - Fundamentals of Numerical Computing (523185), страница 19
Текст из файла (страница 19)
In this chapter we use third degree polynomials(cubits) to interpolate f and f' at two points. It will be convenient later to express theHermite cubic interpolant in a different form. If we writeH(x) = a + b(x - xn) + c(x - xn)2 + d(x - xn)3(3.11)and require thatH(xn) = fn, H´(xn) = f´nH(x n+1 ) = f n+l , H´(x n+1 ) = f´ n+1 ,then it is easy to show that for h = xn+1 - xn,a = fn,b= f´nc = [3(fn+l - f n )/h - 2f´n - f´n+1 ]/h(3.12)(3.13)d = [f´n + f´n+1 - 2(fn+l - fn )/h]/h 2 .(3.14)EXERCISES3.1 Is the interpolating polynomial (3.2) always of exactdegree N - l? If not, illustrate by an example.3.2 Suppose that f(x) is a polynomial of degree N - 1 orless.
Prove that if Pn(x) interpolates f(x) at N distinct points, then PN(x)f(x). Make up an example( N > 3) and verify by direct calculation.3.3 For the dataconstruct P2(x) using (3.2). Find a polynomial Q(X)of degree 2 that also interpolates these data. Does thiscontradict the theory about uniqueness of the interpolating polynomial? Explain.90CHAPTER 3INTERPOLATION3.4 An alternate method for computing PN(x) is to write2N-lPN(x) = cl + c2x + c3x + ··· + cNx.Then the interpolation conditions, PN(xi) = fi for1 < i < N, yield a system of N equations in the Nunknowns c1, c2, .
. . , cN that can be solved using thecodes Factor/Solve. Unfortunately, there are two difficulties with this method: (1) it is expensive (N 3 /3multiplications), and (2) the coefficient matrix can bevery ill-conditioned.(a) Implement this algorithm.(b) Test it on the data in Example 3.5. Use thesame six interpolating values and evaluate (see Exercise 3.5) at the remaining points. What is COND?How do the answers compare with those in the textfor&(x) computed by another method?3.5There arc several ways to evaluate PN(x) = c1 + c2x +··· + cNxN-1. As a first algorithm we could useP:= c1for i = 2, 3, . . . , N beginP:=P+ci*xi-lend i.How many multiplications does this algorithm require? A better approach is based on the nested formof PN(x) used in Section 3.3:c1 + x{ c2 + x[ c3 + x ( c4 + ··· + cNx) ··· ]}.end i.Compare the number of multiplications for this algorithm to those for the first one.3.6 Use the algorithm suggested by Exercise 3.4 to compute P12(w), which interpolates all the data in Example 3.5.
Plot P12(w) for 5 < w < 100. Does it lookreasonable?3.7 Verify the plot in Figure 3.3 of w9(x) to see thatit has smallest magnitude near the middle of thedata. Choose xi = -5 + i and evaluate w9(x) at{±0.5, ±1.5 , . . . ,±4.5, ±5 ±4.5, ±5}.3.8 Derivatives of f(x) can be estimated by the corresponding derivative of PN(x) for some choice of N andThe usual approach is to trySince PN(x) has degree at most N - 1,be a constant function (i.e., independent of x) .must(a) Use (3.2) to show that(b) What approximation to f’(x) results when N = 2?3.9 Verify that the functions given in (3.10) have the fundamental interpolation properties claimed.3.10 Derive equations (3.12)-(3.14).
Start withFor example,3 + 4x - 6x2+ 5x3 = 3 + x[4 + x(-6 + 5x)].The new algorithm isP:=cNfor i = N - l, N - 2, . . . , 1 beginP: = P * x + ciand then derive and solve the four equations for a, b, c,and d resulting from the conditions3.2 MORE ERROR BOUNDSFar more can be said about the error in polynomial interpolation. In this section someuseful results are discussed and some results are given for the error made in approximating derivatives by derivatives of an interpolating polynomial.One way to measure how well PN(x) approximates f(x) on an interval [a, b] is bythe worst error:3.2 MORE ERROR BOUNDS91A fundamental theorem due to Weierstrass (see [4]) states that any function f(x) continuous on a finite interval [a,b] can be approximated arbitrarily well by a polynomial.Stated formally, given any ε > 0, there is a polynomial P(X) such that ||f - P|| < ε. Itis plausible that interpolating f at more and more points in [a,b] would lead to a betterand better approximation.
The bound (3.7) shows that if MN does not grow too fast asthe interpolants PN approximate f arbitrarily well. Unfortunately, this is nottrue for all continuous f. A result due to Faber says that for any given set of nodesin [a,b], there is a function f(x) continuous on [a,b] such thatthe interpolants PN(x) of degree less than N defined bydo not even have ||f - PN|| bounded asRunge’s function(3.15)on [-5,5] is a classic example. It seems obvious that interpolating such a smoothfunction at more and more equally spaced points should lead to convergence, but itis found that for even modest N, the interpolants are completely unacceptable (seeExercise 3.11).It turns out that if one can interpolate at the good nodes (3.9), interpolation is aboutas good a way to approximate f(x) by a low degree polynomial as possible.
In fact,Runge’s function can be quite accurately approximated by a polynomial that interpolates at the Chebyshev points (see Exercise 3.12). In general, there is a polynomialof degree less than N that is the best approximation to f(x) on [a, b] in the sensethatprovides the smallest value of ||f - P|| for all polynomials P of degreeless than N. Let PN(x) interpolate f(x) at the nodes x1,. . . ,xN in [ a,b]. For any x,Nowis a polynomial of degree less than N, sobecause Lagrangian interpolation at N points is exact for such polynomials.
Using thefact that PN(xk) = fk, we then find thatand then92CHAPTER 3INTERPOLATIONThis inequality relates the error of PN to the error of the best possible polynomialby a factorwhich is given in terms of the points of interpolation alone. A simple analytical boundfor the particular nodes (3.9) is found in [17]:The surprising thing is that the bound is so small for moderate degrees N. For N < 20,it is less than 4.
Thusfor all N < 20. These easily constructed interpolating polynomials are, then, about asgood as possible.Interpolation is not so effective when the nodes cannot be chosen, and as Faber’stheorem suggests, high order interpolation can be quite unsatisfactory. It is common inpractice that a high order interpolating polynomial exhibits large amplitude oscillationseven when the data appear to come from a smooth function f(x). Examples are givenin the next section; for extreme examples the reader need only try interpolating the datain Exercises 3.22, 3.23, and 3.26 by polynomials.
For these reasons data are usuallyfit with relatively low degree polynomials, and a variety of devices are used to preventoscillations. Some of these are studied in Section 3.5.Polynomial interpolation is a basic tool in numerical analysis. As an example,derivatives of an interpolant PN(x) to f(x) can be used to approximate derivatives off(n).
An argument very similar to that of Theorem 3.2 (see [15, pp. 289-290] fordetails) can be used to show that for any r < Nwhere the pointsare known to be distinct and to satisfyThe pointdepends on x and lies in the same interval I as thein Theorem 3.2. Ithas been assumed here that xl < x2 < ··· < xN. As a consequence,(3.16)as long as xl < x < xN. The Lagrange form of the interpolating polynomial is convenient for deriving formulas for numerical differentiation. To approximate a derivativeof f(x) at a point z, given values fk at points {x1, . .
. ,xN}, we simply form the interpolant, differentiate it, and evaluate it at x = z:3.3 NEWTON DIVIDED DIFFERENCE FORM93Because the coefficients in this expression depend only on the nodes, we have here aformula that can be used for any f(x). The programs provided with this chapter for thecomputation of cubic splines approximate the first derivative at the ends of the rangeof nodes in this way. At one end they define a cubic polynomial C(x) interpolatingat the nodes x1,x2,x3,x4 and then approximate f´(x1) by C´(x1), and similarly at theother end. For closely spaced data, this provides an accurate approximation.Error bounds like (3.16) can be derived for the Hermite polynomials consideredat the end of the preceding section (see [2] for details).
Using the earlier notation,if f has four continuous derivatives for any x in the interval [ xn ,xn + h], then with(3.17)(3.18)(3.19)(3.20)EXERCISES3.11 Verify that using polynomials interpolating at the N = 3.12 Verify that using polynomials interpolating at the2 m + 1 equally spaced points xj = -5 + 5( j - 1)/mChebyshev points (3.9) gives good approximations togive poor approximations to Runge’s function f(x) =Runge’s function (3.15).
As in the preceding exerl/(1 + x2) on [-5,5].cise, compute the maximum value of |f(x) - PN(x)|over a large set of x values (not interpolating points)(a) Compute the maximum value of |f(x) in [-5,5] for N = 15, N = 21, and N = 27. What isP2m+1 (x)| over a large set of x values (not interpolatthe behavior of the errors as N gets bigger?ing points) in [-5,5] form = 7, m = 10, and m = 13.Are the errors increasing or decreasing as m gets big- 3.13 Repeat Exercise 3.11b for the function f(x) = |x| onger?[-l,l].
The {xj } are now xj = -1 + (j - 1)/m forj= 1, 2, . . . , 2m + l.(b) Repeat (a) but this time only compute error on[ -1, 1|. Use the same {xj} and the same three m val- 3.14 Repeat Exercise 3.12 for the function f(x) = |x| onues as in (a). What happens this time as N increases?[-l,l]. Use N = 21, 41, and 61 this time.3.3 NEWTON DIVIDED DIFFERENCE FORMWe have repeatedly used the fact that there is exactly one polynomial PN(x) of degreeless than N that assumes given values fj at N distinct points xj. The Lagrange form(3.2) is just one way to represent this polynomial. As we have seen in the case ofdifferentiation, it is well suited for many applications because of the simple dependence on the fj. On the other hand, the nodes xj do not appear in a simple way, andthis is inconvenient for some tasks.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
