Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 8
Текст из файла (страница 8)
. , xn be n + 1 distinct points on the real axis and let f(x) be areal-valued function defined on some interval I = [a,b] containing thesepoints. We wish to construct a polynomial p(x) of degree < n whichinterpolates f(x) at the points x0, . . . , xn, that is, satisfiesAs we will see, there are many ways to write down such a polynomial.It is therefore important to remind the reader at the outset that, by thecorollary to Lemma 2.1, there is at most one polynomial of degree < n whichinterpolates f(x) at the n + 1 distinct points x0, . .
. , xn.Next we show that there is at least one polynomial of degree < n whichinterpolates f(x) at the n + 1 distinct points x0, x1, . . . , xn. For this, weemploy yet another polynomial form, the Lagrange form(2.5)with(2.6)the Lagrange polynomials for the points x0, . . . , xn. The function lk(x) isthe product of n linear factors, hence a polynomial of exact degree n.Therefore, (2.5) does indeed describe a polynomial of degree < n.
Further,lk(x) vanishes at xi for alland takes the value 1 at xk, i.e.,This shows thati.e., the coefficients a0, . . . , an in the Lagrange form are simply the valuesof the polynomial p(x) at the points x0 , . . . , xn . Consequently, for anarbitrary function f(x),(2.7)is a polynomial of degree < n which interpolates f(x) at x0, . .
. , xn. Thisestablishes the following theorem.Theorem 2.1 Given a real-valued function f(x) and n + 1 distinctpoints x0, . . . , xn, there exists exactly one polynomial of degree < nwhich interpolates f(x) at x0, . . . , xn.2.2EXISTENCE AND UNIQUENESS OF THE INTERPOLATING POLYNOMIAL39Equation (2.7) is called the Lagrange formula for the interpolatingpolynomial.As a simple application, we consider the case n = 1; i.e., we are givenf(x) and two distinct points x0, x1.
ThenandThis is the familiar case of linear interpolation written in some of its manyequivalent forms.Example 2.2 An integral related to the complete elliptic integral is defined by(2.8)From a table of values of these integrals we find that, for various values of k measuredin degrees,Find K(3.5), using a second-degree interpolating polynomial.We haveThenThis approximation is in error in the last place.The Lagrange form (2.7) for the interpolating polynomial makes iteasy to show the existence of an interpolating polynomial.
But its evaluation at a point x takes at least 2(n + 1) multiplications/divisions and(2n + 1) additions and subtractions after the denominators of theLagrange polynomials have been calculated once and for all and dividedinto the corresponding function values. This is to be compared with nmultiplications and n additions necessary for the evaluation of a polynomial of degree n in power form by nested multiplication (see Algorithm2.1).40INTERPOLATION BY POLYNOMIALSA more serious objection to the Lagrange form arises as follows: Inpractice, one is often uncertain as to how many interpolation points to use.Hence, with p j (x) denoting the polynomial of degree < j which interpolates f(x) at x0, . .
. , xj, one calculates p0(x), p1(x), p2(x), . . . , increasing the number of interpolation points, and hence the degree of theinterpolating polynomial until, so one hopes, a satisfactory approximationpk(x) to f(x) has been found. In such a process, use of the Lagrange formseems wasteful since, in calculating p k(x), no obvious advantage can betaken of the fact that one already has p k-1(x) available. For this purposeand others, the Newton form of the interpolating polynomial is muchbetter suited.Indeed, write the interpolating polynomial p,(x) in its Newton form,using the interpolation points x0, . .
. , xn-1 as centers, i.e.,(2.9)For any integer k between 0 and n, let qk(x) be the sum of the first k + 1terms in this form,Then every one of the remaining terms in (2.9) has the factor (x - x0 )· · · (x - xk), and we can write (2.9) in the formfor some polynomial r(x) of no further interest. The point is that this lastterm (x - x0) · · · (x - xk)r(x) vanishes at the points x0, . . . , xk, henceqk(x) itself must already interpolate f(x) at x0, . . . , xk [since pn(x) does].Since q k(x) is also a polynomial of degree < k, it follows that q k(x) =p k (x); i.e., q k (x) must be the unique polynomial of degree < k whichinterpolates f(x) at x0, .
. . , xk.This shows that the Newton form (2.9) for the interpolating polynomial pn(x) can be built up step by step as one constructs the sequencep 0 (x), p1 (x), p2 (x), . . . , with p k(x) obtained from p k-1(x) by addition ofthe next term in the Newton form (2.9), i.e.,It also shows that the coefficient A, in the Newton form (2.9) for theinterpolating polynomial is the leading coefficient, i.e., the coefficient ofx k , in the polynomial p k (x) of degree < k which agrees with f(x) atx0 , .
. . , xk. This coefficient depends only on the values of f(x) at thepoints x0, . . . , xk; it is called the kth divided difference of f(x) at the pointsx0, . . . , xk (for reasons given in the next section) and is denoted byWith this definition, we arrive at the Newton formula for the interpolating2.3THE DIVIDED-DIFFERENCE TABLE41polynomialThis can be written more compactly as(2.10)if we make use of the convention thatFor n = 1, (2.10) readsand comparison with the formulaobtained earlier therefore shows that(2.11)The first divided difference, at any rate, is a ratio of differences.EXERCISES2.2-1 Prove that(x - xn). [Hint: Find the leading coefficient of the polynomial (2.7).]given in Exercise 2.2-l as22-2 Calculate the limit of the formula forwhile all other points remain fixed.2.2-3 Prove that the polynomial of degree < n which interpolates f(x) at n + 1 distinctpoints is f(x) itself in case f(x) is a polynomial of degree < n.2.2-4 Prove that the kth divided difference p[x0, .
. . , xk] of a polynomial p(x) of degree < kis independent of the interpolation points x0, xl, . . . , xk.2.2-5 Prove that the kth divided difference of a polynomial of degree < k is 0.2.3 THE DIVIDED-DIFFERENCE TABLEHigher-order divided differences may be constructed by the formula(2.12)whose validity may be established as follows.42INTERPOLATION BY POLYNOMIALSLet p,(x) be the polynomial of degree < i which agrees with f(x) atx0, . .
. , xi , as before, and let qk-1(x) be the polynomial of degree < k - 1which agrees with f(x) at the points x1, . . . , xk. Then(2.13)is a polynomial of degree < k, and one checks easily that p(xi ) = f(xi ),i = 0, . . . , k. Consequently, by the uniqueness of the interpolating polynomial, we must have p(x) = pk(x). Thereforeby definitionby (2.13)by definitionwhich proves the important formula (2.12).Example 2.3 Solve Example 2.2 using the Newton formula.In this example, we have to determine the polynomial p2(x) of degree < 2 whichsatisfiesBy (2.11) we can calculateTherefore, by (2.12)and (2.10) now givesSubstituting into this the value x = 3.5, we obtainwhich agrees with the result obtained in Example 2.2.Equation (2.12) shows the kth divided difference to be a differencequotient of (k - 1)st divided differences, justifying their name.
Equation(2.12) also allows us to generate all the divided differences needed for theNewton formula (2.10) in a simple manner with the aid of a so-calleddivided-difference table.2.3THE DIVIDED-DIFFERENCE TABLE43Such a table is depicted in Fig.
2.1, for n = 4.The entries in the table are calculated, for example, column bycolumn, according to the following algorithm.Algorithm 2.2: Divided-difference table Given the first two columns ofthe table, containing x 0 , x 1 , .
. . , x n and, correspondingly,If this algorithm is carried out by hand, the following directions mightbe helpful. Draw the two diagonals from the entry to be calculated throughits two neighboring entries to the left. If these lines terminate at f[xi] andf[xj], respectively, divide the difference of the two neighboring entries bythe corresponding difference x j - x i to get the desired entry. This isillustrated in Fig.
2.1 for the entry f[x1, . . . , x4].When the divided-difference table is filled out, the coefficientsf[x0, . . . , xi ], i = 0, . . . , n, for the Newton formula (2.10) can be foundat the head of their respective columns.For reasons of storage requirements, and because the DO variables inmany FORTRAN dialects can only increase, one would use a somewhatmodified version of Algorithm 2.2 in a FORTRAN program. First, for theevaluation of the Newton form according to Algorithm 2.1, it is moreconvenient to use the formFigure 2.1 Divided-difference table.44INTERPOLATION BY POLYNOMIALSi.e., to use the Newton formula with centers xn, xn-1, . .
. , x1. For then thevaluecan be calculated, according to Algorithm 2.1, bySecond, since we are then only interested in the numbers f[xi , . . . , xn],i = 0, . . . , n, it is not necessary to store the entire divided-difference table(requiring a two-dimensional array in which roughly half the entries wouldnot be used anyway, because of the triangular character of the divided-difference table).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
