Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 51
Текст из файла (страница 51)
Nosuch difficulties are encountered in piecewise-cubic interpolation. For, nomatter how large the number of interpolation points, the interpolant islocally always a very simple function, a cubic polynomial. Finally, if thefunction to be approximated is badly behaved somewhere, then the bestpolynomial approximant is apt to be a poor approximation everywhere(see Exercises 6.1-10 and 6.1-11). In piecewise-polynomial approximation,it is possible, by proper choice of the breakpoints, to confine such effectsto an interval close to the points of bad behavior, allowing good approximation everywhere else.EXERCISES6.7-l In the notation employed in this section, derive the equation which f1, f2, sl, s2 mustsatisfy in order for the “free-end” conditiong´´3(a) = 0to hold.6.7-2 Calculate the polynomial of appropriate degree which interpolates the design curve ofExample 6.16 at all the given data points from 6.1 to 18 (including slopes), and compare itwith the spline approximation calculated in Example 6.16.6.7-3 Interpolate the data of Example 6.16 by cubic Bessel interpolation and compare.6.7-4 Cubic Bessel interpolation is local in the sense that the value of the interpolatingfunction g 3 (x) at any point depends only on the four given function values nearestBycontrast, cubic spline interpolation is global; i.e., the value of g3(x) at any given point dependson all the given information about f(x).
Prove these two assertions.6.7-5 Try to construct a reasonable scheme of interpolating a given function by a piecewiseparabolic function g2(x). Can you make g2(x) continuously differentiable?Previous Home NextCHAPTERSEVENDIFFERENTIATION AND INTEGRATIONIn Chap. 2, we developed some techniques for approximating a givenfunction by a polynomial, typically by interpolation. In this chapter, weconsider a major use of such approximating polynomials-that of analyticsubstitution. Here we are concerned with replacing a complicated, or amerely tabulated, function by an approximating polynomial so that thefundamental operations of calculus can be performed more easily, or canbe performed at all. These operations includeand evenAbstractly, if L denotes one of these operations on functions (or a similarone), we approximate the number L(f) by the number L(p), where, forgiven f(x), p(x) is an approximation to f(x).
The hope is that the operationL can be carried out easily on p(x). and this hope is justified if p(x) is apolynomial and L is any one of the above operations.In estimating the error L(f) - L(p), it is of some help that theoperation L is usually linear (as are the operations mentioned above). Thismeans that2947.1NUMERICAL DIFFERENTIATION295where f(x) and g(x) are functions and a is a number. The linearity impliesthatL(f) - L(p) = L(e)where e(x) is the error in the approximation p(x) to f(x), that is,f(x) = p(x) + e(x)We will usually choose p(x) to be an interpolating polynomial; say,p(x) is the polynomial of degree < k which interpolates f(x) at the pointsx0, . .
. , xk. If these points are distinct, then, by (2.7),where the li (x) are the Lagrange polynomials for the points x0, . . . , xk. Ifnow the operation L is linear, it follows thatwhere the numbers wi are given bywi = L(li )i=0,...,kand do not depend on f(x); hence can be calculated once for all (for anyparticular point set x0 , . .
. , xk ). In this form, the approximation L(p) isusually called a rule [for the approximation of L(f)], the points x0, . . . , xkare its nodes, and the numbers wi are called its weights, or coefficients. Weobtain an expression for the errorE(f) = L(f) - L(p)in such a rule by applying the operation L to the error function ofpolynomial interpolation as given by (2.18) or (2.37), making use of thefact that the divided difference is a well-behaved function of its arguments.7.1 NUMERICAL DIFFERENTIATIONWe consider first some numerical techniques for approximating the derivative f’(x) of a given function. The resulting rules are of prime importancein the numerical solution of differential equations, and this is the majorreason for describing them here.
They can also be used to obtain numerical approximations to a derivative from function values. But, we shouldpoint out that numerical differentiation based on the interpolating polynomial is basically an unstable process and that we cannot expect goodaccuracy even When the original data are known to be accurate. As weshall see the error f´(x) - p´(x) may be very large, especially when thevalues of f(x) at the interpolating points are “noisy.” These comments willbe made more precise in what follows.296DIFFERENTIATION AND INTEGRATIONLet f(x) be a function continuously differentiable on the interval [c,d].If x0, .
. . , xk are distinct points in [c,d], we can write f(x) according to(2.37) as(7.1)where p k(x) is the polynomial of degree < k which interpolates f(x) atx0, . . . , xk, andBy (2.38)if f(x) is sufficiently smooth. Hence, in such a case, we can differentiate(7.1) to get(7.2)Define the operator D aswith a some point in [c,d]. If we approximate D(f) by D(pk), then by(7.2), the error in this approximation is(7.3)for someThe expression (7.3) for the error E(f) in numerical differentiationtells us in general very little about the true error, since we will seldomknow the derivatives f(k+1) and f(k+2) involved in E(f) and we will almostnever know the arguments ξ, η.
In some cases this error term can besimplified greatly either by choosing the point a at which the derivative isto be evaluated or by choosing the interpolating points x0 , . . . , xk appropriately.We consider first the case when a is one of the interpolation points.Let a = xi for some i. Then, sincecontains the factor (x - xi ), it= 0 and the first term in the error (7.3) drops out.follows thatMoreover,where7.1NUMERICAL DIFFERENTIATION297Therefore, if we choose a = xi , for some i, then (7.3) reduces toAnother way to simplify the error expression (7.3) is to choose a sothatfor then the second term in (7.3) will vanish. If k is an oddnumber, we can achieve this by placing the xi ’s symmetrically around a,that is, so that(7.5)For then( x - xj) (x-xk-j) = (x - a + a - xj) (x - a + a - xk-j)= (x - a)2 - (a - xj)2HenceSinceall jit then follows thatreduces to= 0.
To summarize, if (7.5) holds, then (7.3)(7.6)Note that the derivative of f(x) in (7.6) is of one order higher than the onein (7.4).We now consider specific examples. If k = 0, then D(pk) = 0, which isa safe but (usually) not very good approximation to D(f) = f´(a). Wechoose therefore k > 1. For k = 1,HenceD(p k ) = f[x0, x1 ]regardless of a.
If a = x0, then (7.2) and (7.4) give, with h = x1 - x0, theforward-difference formula(7.7)298DIFFERENTIATION AND INTEGRATIONOn the other hand, if we choose a = ½ (x0 + x1 ), then x0, x1 are symmetricaround a, and (7.6) gives, with x0 = a - h, x1 = a + h, h = ½(x1 - x0 ) ,the very popular central-difference formula(7.8)Hence, if x0 , x1 are “close together,”approximation to f´(a) at the midpoint apoint a = x0 or a = x1 . This is notmean-value theorem for derivatives (seef [ x0, x1 ] = f´(a)then f[ x0, x1 ] is a much better= ½(x0 + x1 ) than at either endsurprising since we know by theSec. 1.7) thatfor some a between x0 and x1This is also illustrated in Fig.
7.1.Next, we consider using three interpolation points so that k = 2. ThenPk (x) = f(x 0 ) + f[x 0 , x 1 ](x - x 0 ) + f[x 0 , x 1 , x 2 ](x - x 0 )(x - x 1 )so thatp´ k (x) = f[x 0 , x 1 ] + f[x 0 , x 1 , x 2 ](2x - x 0 - x 1 )Hence, if a = x0, then (7.2) and (7.4) give(7.9)Let now, in particular, x1 = a + h, x2 = a + 2 h. Then (7.9) reduces to(7.10)On the other hand, if we choose x1 = a - h, x2 = a + h, then we get(7.11)which is just (7.8).7.1NUMERICAL DIFFERENTIATION299Figure 7.1 Numerical differentiation.Formulas for approximating higher derivatives of f(x) can be obtainedin a similar manner.
Thus, on differentiating (7.1) twice, one gets(7.12)With k = 2 and a = x0, this givesHence, with x1 = a + h, x2 = a + 2 h ,(7.13)By choosing x1 = a - h, x2 = a + h instead, so that the interpolationpoints are symmetric around a, we get(7.14)Note that placing the interpolation points symmetrically around a hasresulted once again in a higher-order formula.300DIFFERENTIATION AND INTEGRATIONFinally, we infer from (2.17) thatis a “good” approximation to f (k) (a) provided the x i ‘s are all “closeenough” to a.Formulas (7.7), (7.8), and (7.10) are all of the general formD(f) = D(pk) + const hrf(r+1)(ξ)(7.15)with D(f) = f´(a) and h the spacing of the points used for interpolation.Further, the number D(p,) involves just the values of f(x) at a finitenumber of discrete points.
The process of replacing D(f) by D(p k ) istherefore known as discretization, and the error-term const h r f (r+1)(ξ) iscalled the discretization error.It follows from (7.15) that we should be able to calculate D(f) to anydesired accuracy merely by calculating D(pk) for small enough h. However, the fact that computers have limited word length, together with lossof significance caused when nearly equal quantities are subtracted, combine to make high accuracy difficult to obtain. Indeed, for a computer withfixed word length and for a given function, there is an optimum value of hbelow which the approximation will become worse. Consider, for instance,the values given in Table 7.1. These were computed using the IBM 7094computer in single-precision floating-point arithmetic.In this table, the column headed Dh gives f´(a) as estimated by (7.8),while the column with Dh2 gives f´´(a) as estimated by (7.14).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
