Heath - Scientific Computing (523150), страница 61
Текст из файла (страница 61)
When representedin the monomial basis, a polynomialpn−1 (t) = x1 + x2 t + · · · + xn tn−1can be evaluated very efficiently using Horner’s method , also known as nested evaluationor synthetic division:pn−1 (t) = x1 + t(x2 + t(x3 + t(· · · (xn−1 + xn t) · · ·))),which requires only n additions and n multiplications. For example,1 − 4t + 5t2 − 2t3 + 3t4 = 1 + t(−4 + t(5 + t(−2 + 3t))).The same principle applies in forming a Vandermonde matrix:ai,j = φj (ti ) = tj−1= ti φj−1 (ti ) = ti ai,j−1ifor j = 2, . . .
, n,which is superior to using explicit exponentiation.Other manipulations of the interpolating polynomial, such as differentiation or integration, are also relatively easy with the monomial basis representation.7.2.2Lagrange InterpolationFor a given set of data points (ti , yi ), i = 1, . . .
, n, the Lagrange basis functions are givenbyQnk=1, k6=j (t − tk )lj (t) = Qn.k=1, k6=j (tj − tk )For the Lagrange basis, we havelj (ti ) =1 if i = j,0 if i 6= jwhich means that the matrix of the linear system Ax = y is the identity matrix I. Thus,in the Lagrange basis the polynomial interpolating the data points (ti , yi ) is given bypn−1 (t) = y1 l1 (t) + y2 l2 (t) + · · · + yn ln (t).7.2. POLYNOMIAL INTERPOLATION1.00.50.0225. ....................
... ... ........................................................................................24...................................................3....................... ....... ................ ............ . ........... ...................
.... ...... ..... ......................5.........1............................................................................................... ........ ........... ..................... .................................. ...................... ......................... ............... ................ ............................... ................. .. ... ................................................................................................................................................................................................................................................
.................................................................................................................................................................. ................................................................. ... ... ...
... ... ... ................ ................................................................................... ...... ...... ....... ...... ..lllll0.00.51.0Figure 7.2: Lagrange basis functions.Fig. 7.2 shows the Lagrange basis functions for five equally spaced points on the interval[0, 1]. Compare this graph with the corresponding graph for the monomial basis functionsin Fig. 7.1.Lagrange interpolation makes it easy to determine the interpolating polynomial for agiven set of data points, but the Lagrangian form of the polynomial is more expensiveto evaluate for a given argument compared with the monomial basis representation.
TheLagrangian form is also more difficult to differentiate, integrate, etc.Example 7.2 Lagrange Interpolation. We illustrate Lagrange interpolation by usingit to find the interpolating polynomial for the three data points (−2, −27), (0, −1), (1, 0)of Example 7.1. The Lagrange form for the polynomial of degree two interpolating threepoints (t1 , y1 ), (t2 , y2 ), (t3 , y3 ) isp2 (t) = y1(t − t2 )(t − t3 )(t − t1 )(t − t3 )(t − t1 )(t − t2 )+ y2+ y3.(t1 − t2 )(t1 − t3 )(t2 − t1 )(t2 − t3 )(t3 − t1 )(t3 − t2 )For this particular set of data, this formula becomes(t − 0)(t − 1)(t − (−2))(t − 1)(t − (−2))(t − 0)+ (−1)+0(−2 − 0)(−2 − 1)(0 − (−2))(0 − 1)(1 − (−2))(1 − 0)t(t − 1) (t + 2)(t − 1)= −27+.62p2 (t) = −27Depending on the use to be made of it, the polynomial can be evaluated in this form forany t, or it can be simplified to produce the same result as we saw previously for the samedata using the monomial basis (as expected, since the interpolating polynomial is unique).7.2.3Newton InterpolationWe have thus far seen two methods for polynomial interpolation, one for which the basismatrix A is full (Vandermonde) and the other for which it is diagonal (Lagrange).
As aresult, these two methods have very different trade-offs between the cost of computing the226CHAPTER 7. INTERPOLATIONinterpolant and the cost of evaluating it for a given argument. We will now consider Newtoninterpolation, for which the basis matrix is between these two extremes.For a given set of data points (ti , yi ), i = 1, . . . , n, the Newton interpolating polynomialhas the formpn−1 (t) = x1 + x2 (t − t1 ) + x3 (t − t1 )(t − t2 ) + · · · + xn (t − t1 )(t − t2 ) · · · (t − tn−1 ).Thus, the basis functions for Newton interpolation are given byφj (t) =j−1Y(t − tk ),j = 1, . . .
, n,k=1where we take the value of the product to be 1 when the limits make it vacuous. For i < j,we then have φj (ti ) = 0, so that the basis matrix A, with aij = φj (ti ), is lower triangular.Hence, the solution x to the system Ax = y, which determines the coefficients of the basisfunctions in the interpolant, can be computed by forward-substitution in O(n2 ) arithmeticoperations. In practice, the triangular matrix need not be formed explicitly, since its entriescan be computed as needed during the forward-substitution process.Fig. 7.3 shows the Newton basis functions for five equally spaced points on the interval[0, 2].
Compare this graph with the corresponding graphs for the monomial and Lagrangebasis functions given earlier.3.02.01.0.............. ..... ...... ..... ............................... ... ............... ... ... ....... ... ... ... .... ... .......... ... ... ... ..................... ........................... ... ............ ... .............................. ... ... .....................................................................................................................................................................................................................................................................................................................................................................................................
................................ ... ...1........... ... ................ ..... ... ................ ...... ..................................................2345........... ... ..... ........................... ... ......... ....... ... ................. ............................................ .................................................. ...........................
........................................... ........................... ...................................... ................... . ..................................φφ0.00.00.5φ1.0φ1.5φ2.0Figure 7.3: Newton basis functions.Example 7.3 Newton Interpolation. We illustrate Newton interpolation by using itto find the interpolating polynomial for the three data points (−2, −27), (0, −1), (1, 0) ofExample 7.1. With the Newton basis, we have the triangular linear system1110t2 − t1t3 − t1 0x1y10x2 = y2 .(t3 − t1 )(t3 − t2 )x3y37.2.
POLYNOMIAL INTERPOLATION227For this particular set of data, this system becomes 1 0 0x1−27 1 2 0 x2 = −1 ,1 3 3x30whose solution, obtained by forward-substitution, is x = [ −27interpolating polynomial is13−4 ]T . Thus, thep(t) = −27 + 13(t + 2) − 4(t + 2)t,which reduces to the same polynomial we obtained earlier by the other two methods.Once the coefficients xj have been determined, the resulting Newton polynomial interpolant can be evaluated efficiently for any argument using Horner’s nested evaluationscheme:pn−1 (t) = x1 + (t − t1 )(x2 + (t − t2 )(x3 + (t − t3 )(· · · (xn−1 + xn (t − tn−1 )) · · ·))).Thus, Newton interpolation has a better balance between the cost of computing the interpolant and the cost of evaluating it for a given argument than the other two methods.The Newton basis functions can be derived by considering the problem of building apolynomial interpolant incrementally as successive new data points are added. If pj (t) is apolynomial of degree j − 1 interpolating j given points, then for any constant xj+1pj+1 (t) = pj (t) + xj+1 φj+1 (t)is a polynomial of degree j that also interpolates the same j points.
The free parameterxj+1 can then be chosen so that pj+1 (t) interpolates the (j + 1)st point, yj+1 . Specifically,xj+1 =yj+1 − pj (tj+1 ).φj+1 (tj+1 )In this manner, Newton interpolation begins with the constant polynomial p1 (t) = y1interpolating the first data point and builds successively from there to incorporate theremaining data points into the interpolant.Example 7.4 Incremental Newton Interpolation.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
