Shampine, Allen, Pruess - Fundamentals of Numerical Computing (523185), страница 18
Текст из файла (страница 18)
. . , N, where each fj = f(xj) for someprobably unknown function f(x),find a polynomial PN(x) such that PN(xj) = fj, 1 < j < N.(3.1)What degree should PN have? A polynomial of degree N - 1,PN(x) = c1 + c2x + c3x2 + ··· + cNxN-1,has N free parameters, the coefficients ck. Since the polynomial must satisfy conditionsat N points xj, called interpolating points or nodes, we might expect to need thismany parameters to satisfy the conditions. In an exercise you are asked to show byexample that if the interpolating polynomial is allowed to be of degree N or higher,there are many polynomials satisfying the interpolation conditions. It is easy to showby example that if the degree is less than N - 1, it may not be possible to satisfy all theconditions.
Degree N - 1 is just right; with this degree there is always a solution to theinterpolation problem and only one.Given N distinct points {xj} there is one and only one polynoTheorem 3.1.mial PN (x) of degree less than N that interpolates a given function f(x) at these points.Proof. We first show that such a polynomial PN(x) exists and then show that itis unique. Writethe Lagrange form of the interpolating polynomial(3.2)where the functions {Lk(x)} are at our disposal and are to be chosen independently off(x). If PN(x) is to be a polynomial of degree less than N for any choice of the dataf1,...,fN, then each Lk (x) must also be a polynomial of degree less than N. Furthermore, in order to have PN(xj) = fj for 1 < j < N, again for any choice of the data,then the Lk(x) must satisfyThis says that the polynomial Lk(x) has zeros at each xj with jk, and so musthave the form Lk(x) =(x - x j) for some constant C.
The condition Lk(xk) = 184CHAPTER 3 INTERPOLATIONimplies that C =hence(3.3)To show that PN(x) is unique, let QN(x) be another polynomial of degree less thanN that satisfies QN(xj) = fj for 1 < j < N. The difference D(x) = PN(x) - QN(x) isalso a polynomial of degree less than N, and D(xj) = PN(xj) - QN(xj) = fj - fj = 0for 1 < j < N.
This says that D has N distinct zeros. But the Fundamental Theorem ofAlgebra states that any polynomial of degree less than N can have at most N - 1 zerosunless it is identically zero. Accordingly D0, which is to say that PN QN and theinterpolating polynomial is unique.nThe polynomial Lk(x) given by (3.3) is called a fundamental interpolating polynomial or shape function. The fundamental interpolating polynomials are of exact degreeN - 1, but the interpolant can be of lower degree. Indeed, it is important to appreciatethat when f(x) is a polynomial of degree less than N, the interpolant must be f(x)itself.
After all, the polynomial f(x) interpolates itself and its degree is less than N, soby uniqueness, PN(x) = f(x).Example 3.1. Let f(x) = sinx. Find the P3(x) that interpolates f(x) at the threepoints {0, π/2, π}. The corresponding function values are {0, 1, 0}, soExample 3.2.Let P4(x) interpolate the tabular dataxy1.820.00Then the Lagrange form of P4(x) is2.501.303.653.104.032.523.1 POLYNOMIAL INTERPOLATION85Figure 3.1 Plot of P4(x) for Example 3.2.The polynomial P4(x) is plotted in Figure 3.1.
Figure 3.2 shows plots of the fourfundamental polynomials L1, L2, L3, and L4 associated with these data.How well does PN approximate f? Will interpolating at more points (increasingN) improve the approximation? The next theorem helps answer these questions.Assume that f(x) has N continuous derivatives on an interval ITheorem 3.2.containing the interpolating pointsIf PN(x) is the polynomial of degree lessthan N interpolating f on these data, then for any x in I there is a pointin I suchthatthe error in polynomial interpolation is(3.4)where(3.5)andProof Clearly the equality is valid for x = xj, 1 < j < N.
For x not equal to anyof the interpolating points, define the new function86CHAPTER 3 INTERPOLATIONFigure 3.2 The four Lagrange polynomials for Example 3.2.Now G has N continuous derivatives on I andG(xj) = fj - fj - 0. [f(x) - PN(x)]/wN(x) = 0, 1 < j < N.Also, G(x) = f(x) - PN(x) - wN(X) [f(x) - PN(x)]/wN(x) = 0, so G has N + 1 distinctzeros. By Rolle’s theorem (see the appendix), G’ has at least N distinct zeros in I.Repeating this argument, G” has at least N - 1 distinct zeros in I, and so on, and G(N)has at least one zero in I. Denoting a zero of G(N) bywe find 0 = G (N)The polynomial PN is of degreeless than N, so its Nth derivative is identically zero.
The polynomial wN(t) is of degreeN with leading term tN, so its Nth derivative is N!. These observations show thatwhich is merely a rearrangement of (3.4).If the interval I = [a,b] and we letthen two upper bounds for the interpolation error are(3.6)(3.7)A sharper version of this last bound is3.1 POLYNOMIAL INTERPOLATION87Theorem 3.2 is a classic result about the error of interpolation. Sometimes it canbe used directly.
For example, along with the tables of [13] are instructions aboutthe degree of interpolating polynomial needed to get full tabular accuracy. As aconcrete example, the scaled exponential integral xexp(x ) E 1( x ) is tabulated for x =2.0, 2.1, 2.2,. . . , 10.0 and it is said that degree 4 is appropriate.
This is an example ofinterpolation for which we can choose the nodes from a set of possibilities. The assertion for the table assumes that the nodes have been chosen in an appropriate way, amatter to be taken up shortly. For a specific function that can be differentiated readilyand for specific nodes, a bound on the error of interpolation might be obtained fromthe theorem.
More often in practice we use guidelines that will be deduced below fromthe theorem.Example 3.3. Again consider f(x) = sinx and suppose values are known at the fivepoints {0.0, 0.2, 0.4, 0.6, 0.8}. Inequality (3.6) can be used to bound the error in approximating sin 0.28 by P5 (0.28). Sincewe have the bound| sin(0.28) - P5(0.28) | < | 0.28(0.28 - 0.2)(0.28 - 0.4)(0.28 - 0.6)(0.28 - 0.8) | /5!= 3.7 × 10-6An actual evaluation shows P5 (0.28) = 0.2763591, while sin0.28 = 0.2763556, so theexact error is -3.5 × 10-6.nTheorem 3.2 and the bounds provide insight and guidelines for practical interpolation.
The factor wN(x) in the error expression increases near the ends of the datainterval and increases very rapidly as x is taken farther away from [ a,b]; the higherthe degree, the more this is true. Because of this the bound (3.6) increases rapidly, butthe sharper equality (3.4) shows that this effect might be lessened for a given f andgiven x by a derivative factor that gets smaller. Approximating f(x) by PN(x) outsidethe smallest interval I containing the points of interpolation (the nodes) is sometimescalled extrapolation.
In general, it is clearly dangerous to extrapolate very far outsidethe span of the data, especially when using polynomials of high degree. On the otherhand, wN(x) is relatively small for x in the middle of the nodes. And, of course, because of continuity, the error must be small close to a node. These two observationssuggest that when possible, it is best to interpolate at nodes centered about the x ofinterest and as close to x as possible. This is what was meant earlier when referencewas made to choosing the nodes in an appropriate way.The plot of w9(x) = (x + 4) (x + 3) ··· (x - 3) (x - 4) on [-4,4] seen in Figure 3.3shows the qualitative behavior of this factor in the error expression. This functiongrows extremely fast outside the span of the nodes and is large toward the ends, butit is of modest size in the middle (as verified in Exercise 3.7).
Figure 3.6 shows apolynomial interpolant of high degree. Figure 3.7 displays the same data and interpolant over a subinterval in the middle of the data. The physical origin of the data and88CHAPTER 3 INTERPOLATIONFigure 3.3 Plot of w9(x) on the interval [-4,4].the plot of the data suggest that the underlying f(x) should vary slowly. Clearly theinterpolant P16(x) does not provide a plausible approximation to f(x) over the wholeinterval. Nevertheless, in the middle of the range the fit appears to be quite acceptable.The qualitative behavior seen here for a high degree polynomial interpolant might havebeen expected from consideration of the wN(x) factor in the error.Sometimes we can evaluate a function anywhere we like in an interval, but wishto approximate it by a simpler function so as to approximate its derivative or integralor .
. . . It is then natural to ask if there is a good choice of nodes for interpolating in thesense of making(3.8)small. The answer is known (e.g., [12, pp. 227-228]). The points(3.9)called Chebyshev points, make (3.8) as small as possible. More details about the quality of this approximation are provided in the next section.If derivative information is available, we can interpolate it along with the valuesof f. There are a great many possibilities and only one, called Hermite interpolation,will be described. Suppose that in addition to the values fj given at xj for j = 1,. . . , N,we have the first derivative values f´j With 2N independent values it is reasonable totry to interpolate with a polynomial of degree 2N - 1.
We leave as an exercise the factthat the fundamental polynomialsof degree less than 2N that satisfy3.1 POLYNOMIAL INTERPOLATION89are given by(3.10)Here the Lk(x) are given by (3.3). It is now obvious that the polynomialsatisfiesP(xj) = fj, j = l, . . . , NP´(xj) = f´j, j = 1,. . . , N.There is an expression like (3.4) for Hermite interpolation:where wN(x) is again given by (3.5).Two cases of Hermite interpolation are of special interest in this book. In thesolution of ordinary differential equations we use fifth degree polynomials (quintics)to interpolate f and f' at three points.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
