Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 10
Текст из файла (страница 10)
TOL) THENIFLAG = 1RETURNEND IF20 CONTINUEPRINT 620,KP1MAX620 FORMAT(' NO CONVERGENCE IN ',I2,' STEPS.')IFLAG = 2RETURNENDCCEXERCISES2.4-1 The FORTRAN function TABLE given in the text terminates as soon as |pk+1 (XBAR)- p k (XBAR)| < TOL. Show that this does not guarantee that the value pk+1 (XBAR)returned by TABLE is within TOL of the desired number f(XBAR) by the followingexam les:(a) f(x) = x2; for some I, X(I) = -10, X(I + 1) = 10, XBAR = 0, TOL = 10-5.(b) f(x) = x 3 ; for some I, X(I) = -100, X(I + 1) = 0, X(I + 2) = 100, XBAR =-50, TOL = 10-5.2.4-2 Iterated linear interpolation is based on the following observation attributable toNeville: Denote by p i,j (x) the polynomial of degree < j - i which interpolates f(x) at thepoints xi, xi+1, . .
. , xj, i < j. ThenVerify this identity. [Hint: We used such an identity in Sec. 2.3; see Eq. (2.13).]2.4-3 Iterated linear interpolation (continued). The identity of Neville’s established in Exercise2.4-2 allows one to generate the entries in the following triangular tablecolumn by column, by repeatedly carrying out what looks like linear interpolation, to reacheventually the desired numberthe value atof the interpolating polynomial whichagrees with f(x) at the n + 1 points x0, . . . , xn. This is Neville's Algorithm. Aitken’s Algorithmis different in that one generates instead a triangular table whose jth column consists of the2.5THE ERROR OF THE INTERPOLATING POLYNOMIAL51numbersWith p0, 1, .
. . , j, r(x) (for r > j) the polynomial of degree < j + 1 which agrees with f(x) at thepoints x0, x1, . . . , xj, and xr.Show by an operations count that Neville’s algorithm is more expensive than Algorithm2.4. (Also, observe that Algorithm 2.4 provides, at no extra cost, a Newton form for theinterpolating polynomial for subsequent evaluation at other points, while the informationgenerated in Neville’s or Aitken’s algorithm is of no help for evaluation at other points.)2.4-4 In inverse interpolation in a table, one is given a number and wishes to find the pointso thatwhere f(x) is the tabulated function.
If f(x) is (continuous and) strictlymonotone-increasing or -decreasing, this problem can always be solved by considering thegiven table xi, f(xi), i = 0, 1, 2, . . . to be a table yi, g(yi), i = 0, 1, 2, . . . for the inversefunction g(y) = f-1(y) = x by taking yi = f(xi), g(yi) = xi, i = 0, 1, 2, . . . , and to interpolate for the unknown valuein this table. Use the FORTRAN function TABLE to findso that2.5 THE ERROR OF THE INTERPOLATING POLYNOMIALLet f(x) be a real-valued function on the interval I = [a,b], and letx0, . . . , xn be n + 1 distinct points in I. With pn(x) the polynomial ofdegree < n which interpolates f(x) at x0, . . . , xn, the interpolation erroris given by(2.15)Let nowbe any point different from x 0 , . . .
, x n . If p n+1 (x) is thepolynomial of degree < n + 1 which interpolates f(x) at x0, . . . , xn and atwhile by (2. 10),It follows thatTherefore,(2.16)showing the error to be “like the next term” in the Newton form.We cannot evaluate the right side of (2.16) without knowing thenumberBut as we now prove, the numberis closelyrelated to the (n + 1)st derivative of f(x), and using this information, wecan at times estimate52INTERPOLATION BY POLYNOMIALSTheorem 2.2 Let f(x) be a real-valued function, defined on [a,b] andk times differentiable in (a, b).
If x0, . . . , xk are k + 1 distinct pointsin [a, b], then there existssuch that(2.17)For k = 1, this is just the mean-value theorem for derivatives (see Sec.1.7). For the general case, observe that the error function ek(x) = f(x) pk(x) has (at least) the k + 1 distinct zeros x0, .
. . , xk in I = [a, b]. Hence,if f(x), and therefore e k (x), is k times differentiable on (a, b), then itfollows from Rolle’s theorem (see Sec. 1.7) that e’(x) has at least k zeros in(a, b); hence e”(x) has at least k - 1 zeros in (a, b) and continuing in thismanner, we finally get thathas at least one zero in (a, b).
Let beone such zero. ThenOn the other hand, we know that, for any x,since, by definition, f[x0, . . . , xk] is the leading coefficient of p k(x), and(2.17) now follows.By taking a = min, xi , b = maxi xi , it follows that the unknown pointin (2.17) can be assumed to lie somewhere between the xi ’s.If we apply Theorem 2.2 to (2.16), we get Theorem 2.3.Theorem 2.3 Let f(x) be a real-valued function defined on [a, b] andn + 1 times differentiable on (a, b). If p n (x) is the polynomial ofdegree < n which interpolates f(x) at the n + 1 distinct pointsthere existsx0, . . . , xn in [a, b], then for all(a, b) such that(2.18)It is important to note thatdepends on the point at whichthe error estimate is required.
This dependence need not even be continuous. As we have need in Chap. 7 to integrate and differentiate en(x) withrespect to x, we usually prefer for such purposes the formula (2.16). For, aswe show in Sec. 2.7, f[x0, . . . , xn, x] is a well-behaved function of x.The error formula (2.18) is of only limited practical utility since, ingeneral, we will seldom know f(n+1)(x), and we will almost never know thepointBut when a bound on |f(n+1)(x)| is known over the entire interval[a, b], then we can use (2.18) to obtain a (usually crude) bound on theerror of the interpolating polynomial in that interval.2.5THE ERROR OF THE INTERPOLATING POLYNOMIAL53Example 2.6 Find a bound for the error in linear interpolation.The linear polynomial interpolating f(x) at x0 and x1 isEquation (2.18) then yields the error formulawhere depends on .
If is a point between x0 and x1, thenHence, if we know that |f”(x)] < M on [x0, x1], thenThe maximum value ofhence is (x1 - x0)2/4. It follows that, for anyoccurs atExample 2.7 Determine the spacing h in a table of equallybetween 1 and 2, so that interpolation with athis table will yield a desired accuracy.By assumption, the table will contain f(xi), with xi = 1th en we approximatethe quadratic polynomial which interpolates f(x) at xi-1, xi,thenfor somein (xi-1, xi+1). Since we do not knowOne calculateslies between x0 and x1.spaced values of the functionsecond-degree polynomial in+ ih, i = 0, .
. . , N, wherewhere p 2 (x) isxi+1. By (2.18), the error iswe can merely estimateFurther,using the linear change of variables y = x - xi. Since the functionvanishes at y = - h and y = h, the maximum ofmust occur at one ofthe extrema ofThese extrema are found by solving the equation= 0, givingHenceWe are now assured that, for anyif p2(x) is chosen as the quadratic polynomial which interpolatesat the threetabular points nearest . If we wish to obtain seven-place accuracy this way, we would54INTERPOLATlON BY POLYNOMIALShave to choose h so thatgivingThe functionwhich appears in (2.18) depends,of course, strongly on the placement of the interpolation points.
It ispossible to choose these points for given n in the given interval a < x < bin such a way that maxthere is as small as possible. This choice ofpoints, the so-called Chebyshev points, is discussed in some detail in Sec.6.1. For the common choice of equally spaced interpolation points, thelocal maxima ofincrease as one moves from the middle of theinterval toward its ends, and this increase becomes more pronounced withincreasing n (see Fig 2.3).
In view of (2.18), it is therefore advisable (atleast when interpolating to uniformly spaced data) to make use of theinterpolating polynomial only near the middle data points. The interpolantbecomes less reliable as one approaches the leftmost or rightmost datapoint.
Of course, going beyond them is even worse. Such an undertaking iscalled extrapolation and should only be used with great caution.Figure 23 The functionequally spaced interpolation points(solid); (b) Chebyshev points for the same interval (dotted).EXERCISES2.5-l A table of values of cos x is required so that linear interpolation will yield six-decimalplace accuracy for any value of x inAssuming that the tabular values are to be equallyspaced, what is the minimum number of entries needed in the table?2.5-2 The function defined by2.6INTERPOLATION AT EQUALLY SPACED POINTS55has been tabulated for equally spaced values of x with step h = 0.1.
What is the maximumerror encountered if cubic interpolation is to be used to calculateany point on theinterval2.5-3 Prove: If the values f(x0), . . . , f(xn) are our only information about the function f(x),then we can say nothing about the errorat a pointthatis, the error may be “very large” or may be “very small.” [Hint: Consider interpolation atx 0 , x 1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
