Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

. . , and assume that you know the numbersfor a certain polynomial pn(x) of degree < n. Show how toget from this information the values pn(xn+1), pn(xn+2), . . . , using just n additions per value.[Hint: By Exercise 2.6-5does not depend on i, while for allby definition of the forward difference.] This method is useful for graphingpolynomials. What is its connection with Algorithm 2.1?2.6-7 Make what simplifications you can in the Lagrange form of the interpolating polynomial when the data points are equally spaced.2.6-8 Derive the Newton backward-difference formulafor use near the right end of a table. It uses the differences along the diagonal markedFig. 2.4.in*2.7 THE DIVIDED DIFFERENCE AS A FUNCTION OF ITSARGUMENTS AND OSCULATORY INTERPOLATIONWe have so far dealt with divided differences only in their role ascoefficients in the Newton form for the interpolating polynomial, i.e., asconstants to be calculated from the given numbers f(xi ), i = 0, .

. . , n. Butthe appearance of the function gn(x) = f [x0, x1, . . . , xn, x] in the errorterm (2.18) for polynomial interpolation makes it necessary to understandhow the divided difference f[x0 , . . . , xk] behaves as one or all of thepoints x0, . . . , xk vary.We begin by extending the definition of the kth divided differencef[x0, . . . , xk] to all choices of x0, . .

. , xk; i.e., we drop the requirementthat the points x0, . . . , xk be pair-wise distinct. Since, to recall, the k t hdivided difference f[x0, . . . , xk] off at the points x0, . . . , xk is defined asthe leading coefficient (i.e., the coefficient of xk) in the polynomial pk(x)of degree < k which agrees with f(x) at the k + 1 points x0, . . . , xk, wemust then explain what we mean by the phrase “pk(x) agrees with f(x) atthe points x0, . . .

, xk,” in case some of these points coincide.Here is our definition of that phrase. We say that the two functions f(x)and g(x) agree at the points x0, . . . , xk in casefor every point z which occurs m times in the sequence x0, . . . , xk. Ineffect, f(x) and g(x) agree at the points x0, . . . , xk if their difference hasthe zeros x0, . .

. , xk, counting multiplicity (see Sec. 2.1).*2.7CONTINUITY OF DIVIDED DIFFERENCES AND OSCULATORY INTERPOLATION63Example f(x) and g(x) agree at the points 2, 1, 2, 4, 2, 5, 4 in caseThe Taylor polynomial(2.31)agrees with f(x) at the point c n + 1 times, according to this definition.Forand thereforeOne speaks of osculatory interpolation whenever the interpolating polynomial has higher than first-order contact with f(x) at an interpolationpoint (osculum is the Latin word for “kiss”).It does make good sense to talk about the polynomial of degree < kwhich agrees with a given function f(x) at k + 1 points since, by thecorollary to Lemma 2.2 (in Sec. 2.1), two polynomials of degree < k whichagree at k + 1 points (distinct or not, but counting multiplicity) must beidentical.

If this interpolating polynomial p k(x) of degree < k to f(x) atx0 , . . . , xk exists, then its leading coefficient is, by definition, the kthdivided difference f[x0, . . . , xk], henceis a polynomial of degree < k - 1. Since (x - x0) · · · (x - xk-1) agreeswith the zero function at x0 , . .

. , xk-1, it follows that p(x) agrees atx0, . . . , xk-1 with pk(x), hence with f(x), i.e., p(x) must be the polynomialof degree < k - 1 which agrees with f(x) at x0, . . . , xk-1. Induction on ntherefore establishes the Newton formula(2.32)for the polynomial of degree < n which agrees with f(x) at x0, . . . , xn.This formula is, of course, indistinguishable from the formula (2.10), whichis the whole point of this section.Finally, we should like to make certain that, for every choice ofinterpolation points x0, .

. . , xk and function f(x), there exists a polynomialof degree < k which agrees with the function f(x) at these points. This wecannot guarantee, for f(x) may not have as many derivatives as we arerequired to match by the coincidences among the xi ’s. But, if f(x) hasenough derivatives, then we can prove the existence of the interpolatingpolynomial pk(x) by induction on k and gain a useful formula [essentially(2.12) again] for the divided difference in the bargain.64INTERPOLATION BY POLYNOMIALSTheorem 2.4 If f(x) has m continuous derivatives and no point occursin the sequence x0, .

. . , xn more than m + 1 times, then there existsexactly one polynomial pn(x) of degree < n which agrees with f(x) atx0, . . . , xn.For the proof of existence, we may as well assume that the sequence ofinterpolation points is nondecreasing,For n = 0, there is nothing to prove. Assume the statement correct forn = k - 1 and consider it for n = k.

There are two cases.Case x0 = xk. Then x0 = . . . = xk and we must have m > k, byassumption; i.e., f(x) has at least k continuous derivatives. Then the Taylorpolynomialfor f(x) around the center c = x0 does the job, as alreadyremarked earlier; see (2.31). Note that its leading coefficient is the numberf(k)(x0)/k!, thus(2.33)Case x 0 < x k .

Then, by induction hypothesis, we can find a polynomial Pk-1(x) of degree < k - 1 which agrees with f(x) at x0, . . . , xk-1,and a polynomial q k-1 (x) of degree < k - 1 which agrees with f(x) atx1, . . . , xk. The polynomial(2.34)is then of degree < k, and we claim that it is the required polynomial; i.e.,pk(x) agrees with f(x) at x0, . . . , xk.

We have(2.35)Suppose z = xi = . . . = xi+r. If z = x0, thenfor j = 0,..., r - 1 and also(2.35),The argument for the case z = xk is analogous. Finally, ifand so, from (2.35),This proves the statement for n = k.then*2.7CONTINUITY OF DIVIDED DIFFERENCES AND OSCULATORY INTERPOLATION65On comparing leading coefficients on both sides of (2.34), we get againthe formula (2.12), i.e.,(2.36)Having extended the definition of f[x0, . . . , xk] to arbitrary choices ofx0, . . . , xk, we now consider how f[xo, . . . , xk] depends on these pointsx0, . . . , xk. These considerations will make clear that the extended definition was motivated by continuity considerations.We begin with the observation that f[x0 , .

. . , xk] is a symmetricfunction of its arguments; that is, f[x0 , . . . , xk] depends only on thenumbers x0, . . . , x k and not on the order in which they appear in theargument list. This is obvious since the entire interpolating polynomialpk(x) does not depend on the order in which we write down the interpolation points. This implies that we may assume without loss that thearguments x0, .

. . , xk of f[x0, . . . , xk] are in increasing order whenever itis convenient to do so.Next we show that f[x0, . . . , x k ] is a continuous function of itsarguments.Theorem 2.5 Assume that f(x) is n times continuously differentiableon [a, b], and let y0, . . . , yn, be points in [a, b], distinct or not. ThenThe proof is by induction on n. For n = 0, all assertions are triviallytrue. Assume the statements correct for n = k - 1, and consider n = k.We first prove (ii) in case not all n + 1 points y0, . .

. , yn, are the same.Then, assuming without loss that y0 < . . . < yn , we have y0 < yn andthereforefor all large r, and so, by (2.36),The last equality is by induction hypothesis. But this last expression equalsf[y0, . . . , yn], by (2.36), which proves (ii) for this case.66INTERPOLATION BY POLYNOMIALSNext, we prove (i). If y0 = y1 = · · · = yn, then (i) is just a restatement of (2.33). Otherwise, we may assume thatand then y0 < yn . But then we may find, for allin[a, b] so that.

By Theorem 2.2, we can findthenso thatBut then, by (ii) just proved for this case,for someby the continuity of f (n) (x),which proves (i).Finally, to prove (ii) in the case that y0 = y1 = · · · = yn, we now use(i) to conclude the existence ofso thatfor all r. But then, since y0 = · · · = ynall i, we haveandand so, with (2.36) and thecontinuity of f (n) (x) ,This proves both (i) and (ii) for n = k and for all choices of y0, . . . , ynin [a, b].We conclude this section with some interesting consequences of Theorem 2.5. It follows at once that the functionwhich appears in the error term for polynomial interpolation is defined forall x and is a continuous function of x if f(x) is sufficiently smooth. Thus itfollows that(2.37)for all x, and not only for[see (2.16)], and also for allx0, . .

Характеристики

Список файлов книги