Heath - Scientific Computing (523150), страница 60

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

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

INTERPOLATION221Some families of functions commonly used for interpolation include:•••••PolynomialsPiecewise polynomialsTrigonometric functionsExponentialsRational functionsIn this chapter we will focus on interpolation by polynomials and piecewise polynomials.We will consider trigonometric interpolation in Chapter 12. We have already seen an example of interpolation by a rational function, namely, linear fractional interpolation, inSection 5.2.6. The use of more general rational functions of arbitrary degree, known asPadé approximation, is an important topic, but it is beyond the scope of this book.7.1.4Basis FunctionsThe family of functions chosen for interpolating a given set of data points is spanned bya set of basis functions φ1 (t), . . . , φn (t).

The interpolating function f is chosen as a linearcombination of these basis functions,f (t) =nXxj φj (t),j=1where the parameters xj are to be determined. Requiring that f interpolate the data (ti , yi )means thatnXf (ti ) =xj φj (ti ) = yi , i = 1, . . . , n,j=1which is a system of linear equations that we can write asAx = y,where the entries of the matrix A are given by aij = φj (ti ) (i.e., aij is the value of thejth basis function evaluated at the ith data point), the components of the right-hand-sidevector y are the known data values yi , and the components of the vector x to be determinedare the unknown parameters xj .We have chosen the number of basis functions to be the same as the number of datapoints so that we obtain a square linear system, and hence the data points can be fitexactly.

In other contexts, these two values would not necessarily be the same. In leastsquares approximation, for example, the number of basis functions, and thus the numberof parameters to be determined, is usually smaller than the number of data points (i.e., thesystem is overdetermined in that there are more equations than unknowns). Therefore, thedata usually cannot be fit exactly.For a given family of functions, there may be many different choices of basis functions.The particular choice of basis functions affects the conditioning of the linear system Ax = y,the work required to solve it, and the ease with which the resulting interpolating functioncan be evaluated or otherwise manipulated.2227.2CHAPTER 7. INTERPOLATIONPolynomial InterpolationThe simplest and commonest type of interpolation uses polynomials. There is a uniquepolynomial of degree at most n − 1 passing through n data points (ti , yi ), i = 1, . .

. , n,where the ti are distinct. There are many ways to represent or compute this polynomial,but all must give the same mathematical function. (Simple proof: if there were two, thentheir difference would be a polynomial of degree at most n − 1 having n zeros, which mustbe the zero polynomial.)For example, with the monomial basis,φj (t) = tj−1 ,j = 1, . . . , n,the interpolating polynomial has the formpn−1 (t) = x1 + x2 t + · · · + xn tn−1 ,and its coefficients are determined by the n × n linear system11. ..t1t2...1 tn   · · · tn−1y1x11n−1· · · t2   x2   y2  .

 =  . ... ....   ..   .. xnyn· · · tn−1nAs we saw in Section 3.2, a matrix of this form is called a Vandermonde matrix.Example 7.1 Monomial Basis. To illustrate polynomial interpolation using the monomial basis, we will find a polynomial of degree two interpolating the three data points(−2, −27), (0, −1), (1, 0). In general, there is a unique polynomialp2 (t) = x1 + x2 t + x3 t2of degree two interpolating three points (t1 , y1 ), (t2 , y2 ), (t3 , y3 ).

With the monomial basis,the coefficients of the polynomial are given by the system of linear equations   1 t1 t21x1y1 1 t2 t22   x2  =  y2  .1 t3 t23x3y3For this particular set of data, this system becomes  1 −2 4x1−2710 0   x2  =  −1  .11 1x30Solving this system by Gaussian elimination yields the solution x = [ −1the interpolating polynomial isp2 (t) = −1 + 5t − 4t2 .5−4 ]T , so that7.2.

POLYNOMIAL INTERPOLATION223Note that polynomial interpolation and polynomial evaluation are inverses of each otherin the following sense: if A is a Vandermonde matrix as just defined, then computing thematrix-vector product Ax evaluates at n points the polynomial whose coefficients are givenby the components of x, whereas computing the product A−1 y (by solving the linear systemAx = y) determines the coefficients of the polynomial whose values at n points are givenby the components of y.Solving the system Ax = y using a standard linear equation solver to determine thecoefficients of the interpolating polynomial requires O(n3 ) work.

[Solvers for Vandermondesystems with O(n2 ) complexity are possible, but they are based on other polynomial representations that we will see shortly.] Moreover, when using the monomial basis, the resultingVandermonde matrix A is often ill-conditioned, especially for high-degree polynomials. Thereason for this is illustrated in Fig. 7.1, in which the first several monomials are plottedon the interval [0, 1]. These functions are progressively less distinguishable as the degreeincreases, which makes the columns of the Vandermonde matrix nearly linearly dependent.For most choices of data points ti , the condition number of the Vandermonde matrix growsat least exponentially with the number of data points n.1.0 ...............................................................................................................................................................................................................................................................................................................................................................................................................................1.........

....................... .... ...........0.5....... .......................... ... .................. .................................................. .. ..................... .... ..... ........................... ...... ........................................ ... . . ....................... ...... ...................................................... ......

................................................ .. .. . ................ ...... ................................................. ... ... .. . .................... ...... ...... ................................................... ...... ...... ......................................................... ...... ...... ............................... . .2..................................

....... ...... ..... ....................................... ... . ........................ ....... ..... ...................................3....................... .......................... ........ ..... .......................................... . ............................... ............ ........ ....................................................... . ............................................ ...... .....

............................... ............. ................................................................................................... .............................................................................................................................................. ......................... ...................................................................................................................... .......................................... ...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ttt0.00.51.0Figure 7.1: Monomial basis functions.Note that this ill-conditioning does not prevent fitting the data points well, since theresidual for the solution to the linear system will be small in any case, but it does meanthat the values of the coefficients may be poorly determined.

Both the conditioning of thelinear system and the amount of computational work required to solve it can be improvedby using a different basis. A change of basis still gives the same interpolating polynomialfor a given data set (recall that the interpolating polynomial is unique).

What does changeis the representation of that polynomial in a different basis.The conditioning of the monomial basis can be improved somewhat by shifting andscaling the independent variable t so thatφj (t) =t−cdj−1,224CHAPTER 7. INTERPOLATIONwhere, for example, c = (t1 +tn )/2 and d = (tn −t1 )/2 are the midpoint and half the range ofthe data, respectively. Thus, the new independent variable lies in the interval [−1, 1]. Sucha transformation also helps avoid overflow or harmful underflow in computing the entriesof the basis matrix or evaluating the resulting polynomial. Even with optimal shifting andscaling, however, the monomial basis is usually still poorly conditioned, and we must seeksuperior alternatives.7.2.1Evaluating PolynomialsIn addition to the cost of determining the interpolating function, the cost of evaluating it ata given point is an important factor in choosing an interpolation method.

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

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