Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 42
Текст из файла (страница 42)
6.1. Then one verifies that the error f(x) - p(x) satisfies thealternation condition (6.8) with n = 1 and x 0 = -1, x 2 = 1, i.e., f (-1) - p(-1) =- [f(x1) - p(x1)] = f(1) - p(1) = (e1 + e-1 )/2 - a = 0.27880 · · · . Thus, this particular straight line must be the best uniform approximation to ex on -1 < x < 1 fromπ 1, and dist (ex, π1) = 0.27880 · · · . This shows our lower bound obtained in Example6.1 to be quite accurate.A particularly important example is provided by the best uniformapproximation on - 1 < x < 1 from πn to the function f(x) = xn+1. Forthe error in this approximation is, as we shall see in a moment, a multipleof Tn+1(x), the Chebyshev polynomial of degree n + 1.By definition, the Chebyshev polynomial of degree k is given (on-1 < x < 1) by the rule(6.9)Thus,T0(x) = 1T 1 (x) = x(6.10)and, by the addition formula for trigonometric functions,T k + 1 ( x ) = 2xTk(x)-Tk-1(x)k = 1, 2,.
. .(6.11)From thisT 2 (x) = 2xT1(x) - T0(x) = 2x2 - 1T 3 (x) = 2xT2(x) - T1(x) = 2x(2x2 - 1) - x = 4x3 - 3xetc.The first eight of these polynomials are listed in Table 6.1. Graphs of thefirst five are pictured in Figs. 6.2 and 6.3.Figure 6.1 Best uniform straight-line approximation to ex on -1 < x < 1.240APPROXIMATIONFigure 6.3Figure 6.2The recurrence relation (6.11) makes explicit that Tk(x) as defined by(6.9) is indeed a polynomial, of exact degree k and with leading coefficient2k-1. Further, it is evident from the definition (6.9) thatfor all -1 < x < 1(6.12)|Tk(x)| < 1and that Tk(x) attains this bound ± 1 alternately at the k + 1 pointsi.e., from (6.9),But this shows that, in particular,2-nTn+1(x)=xn+1-pn(x)for some polynomial p n (x) of degree < n and that this polynomial is, byTable 6.1T0(x)T1(x)T2(x)T3 (x)T4 (x)T5 (x)T6 (x)T7(x)= 1= x= 2x2 - 1= 4x3 - 3x= 8x4 - 8x2 + 1= 16x5 - 20x3 + 5x= 32x6 - 48x4 + 18x2 - 1= 64x7 - 112x5 + 56x3 - 7x6.1UNIFORM APPROXIMATION BY POLYNOMIALS241Theorem 6.2, the best uniform approximation to x n+1 on -1 < x < 1.Also,(6.13)The construction of a best uniform approximation from π n is, ingeneral, a nontrivial task.
Supposing the function f(x) to be differentiable,one would, based on Theorem 6.2, solve the nonlinear systemf(x i ) - p n *(x i ) = (-1) i dφ(xi )[f´(xi ) - pn*´(xi )] = 0i = 0, . . . , n + 1i = 0, . . . , n + 1(6.14)for the points x0, . . . , xn+1, the n + 1 coefficients of p n *(x) and the(positive or negative) number d = ±under the restriction thata < x0 < · · · < xn+1 < b. Here,if x = a or botherwiseThe function φ(x) serves to distinguish between an interior extremum ofthe error f(x) - pn*(x), at which the first derivative would have to be zero,and a boundary extremum, at which the derivative need not be zero(though it would have to satisfy some inequality not expressed here).
TheRemez algorithm and its Murnaghan-Wrench variant (see Rice [17])attempt to solve this system by Newton’s method as discussed in Chap. 5,but adapted to the special structure of (6.14). A first guess is easilyobtained from a suitable interpolantto f(x), using the coefficientsof pn(x) and the local extrema of f(x) - pn(x).We will not take the time to discuss construction of a best uniformpolynomial approximant in any more detail because it is possible toconstruct, with less effort, approximations which are almost best, byinterpolating appropriately.Indeed, by Theorem 6.2, we know that the error f(x) - pn*(x) in thebest uniform approximation on a < x < b to the continuous function f(x)must alternate n + 1 times; that is, it must satisfyi = 0, . .
. , n + 1with ε = signum[f(x0) - pn*(x0)] and a < x0 < · · · < xn+1 < b. But then,by the Intermediate Value Theorem for continuous functions (Theorem1.3), there must exist points ξo < · · · < ξn, with xi < ξi < xi+1, all i, atwhich the error f(x) - pn*(x) vanishes, i.e., at which the best approximation pn*(x) interpolates f(x).
In principle, then, we could construct even thebest approximation by interpolation, if we only knew where to interpolate.242APPROXIMATIONRecall now that the error in the best approximation to xn+1 from πnon the standard interval -1 < x < 1 is a multiple of Tn+1(x), theChebyshev polynomial of degree n + 1, which, by its very definition (6.9),vanishes at the n + 1 points(6.15)This means that, for the specific function f(x) = xn+1 , we can obtain itsbest uniform approximant from πn by interpolation at the points (6.15), theso-called Chebyshev points for the standard interval -1 < x < 1. As itturns out, this procedure produces rather good (if not best) approximationsto any continuous function.To see why this might be so, recall from (2.16) or (2.37) that the errorf(x) - pn(x) in the polynomial interpolant to f(x) at the points x0, .
. . , xnsatisfiesConsequently, by (6.4)|f(x) - pn(x)| < | x - x0 | · · · | x - xn | · W (x0, . . . , xn, x)provided x0, . . . , xn and x all lie in the interval of interest. Now, writex = xn+1. Then, from (6.3)and thereforewith(6.16)6.1UNIFORM APPROXIMATION BY POLYNOMIALS243the ith Lagrange polynomial [see (2.5) and (2.6)]. This proves the followingtheorem.Theorem 6.3 Let pn(x) be the polynomial of degree < n which interpolates f(x) at the points x0 < x1 < · · · < xn in the interval a < x <b of interest. Then(6.17)withand the Lagrange polynomial li (x) given by (6.16).This makes it desirable to choose the interpolation points x0, . .
. , xnof the Lebesguein a < x < b in such a way that the uniform normfunctionbe as small as possible. This, as it turns out, is almostaccomplished by the Chebyshev points (6.15) adjusted to the intervala < x < b of interest, i.e., by the pointsIn Fig. 6.4, we have plottedfor these points as a function of n. WeFigure 6.4 The numberfor the Chebyshev points (solid line) and for the expandedChebyshev points (dashed line) as a function of n.244APPROXIMATIONhave also plotted there the numbersexpanded Chebyshev pointscorresponding to the so-called(6.18e)is within 0.02 of the smallest possible valueIt can be shown thatforfor all n.We read off from Fig. 6.4 and from Theorem 6.3 that, for n < 47, theerror in the polynomial interpolating f(x) at the expanded Chebyshevpoints (6.18e) is never bigger than 4 times the best possible error, and isnormally smaller than that.
If, for example, the best uniform approximation pn*(x) would be everywhere on a < x < b within 10-5 of f(x), then theinterpolant would be, at worst, only within 4·10-5 of f(x), a loss of lessthan half a decimal digit in accuracy. Such a loss can usually be made upby interpolating by a polynomial of one or two degrees higher.By contrast, ifdenotes the Lebesgue function for a uniform spacingof interpolation points such as occurs when interpolating in a table, then(6.19)which grows very rapidly with n. (See, e.g., Rivlin [35; p.
99] for a result ofthis kind.)forExample 6.4 We obtained in Example 6.2 the lower bound 0.002 <f(x) =on the standard interval -1 < x < 1, and stated that, actually,If one interpolates to this f(x) at the five expandedChebyshev points (6.18e ), one obtains a polynomial p(x) (ideally of degree 3 because ofsymmetry) for whichwhich is only 1.4 times as big as thesmallest possible error. Adding just one interpolation point [which is computationallycheaper than constructing p 4 * (x)] produces a polynomial of degree 5 whose distancefrom f(x) is 0.00068 · · · , a considerable improvement over 0.0041 · · · =EXERCISESon the interval -1 < x < 1 from below.
Compare6.1-l Use (6.7) to estimatewith the distance of the function ex from the polynomial p3(x) of degree < 3 which agreeswith ex at the four expanded Chebyshev points [see (6.18e ) with n = 3].6.1-2 Repeat Exercise 6.1-1, but for the interval 0 < x < 1. (Hint: Consider the functione (x+1)/2 on the interval -1 < x < 1 instead.)6.1-3 In Exercises 6.1-1 and 6.1-2, use the interpolant p3(x) and Theorem 6.1 to get anotherlower bound for(Note: For the biggest lower bound one would calculate theextreme of ex - p3(x), for example by Newton’s method.)6.1-4 Calculate p3*(x) for ex on the standard intervalmethod to solve (6.14) for this case, starting withExercise 6.1-1, as a first guess for p3*(x) and the local= 1 of the error ex - p3(x) as the first guess for theNote that x0 = -1, x4 = 1, by Theorem 6.2.]-1 < x < 1.
[Hint: Use Newton’sthe interpolant p 3 (x) constructed inextrema -1 =points x0 < · · · < x4 of alternation.6.2DATA FITTING2456.1-5 Prove (6.6). [Hint: Verify that, with (xi) given by (6.5), w(x) = cn (1 - x2 )T´n+1(x)forsome appropriate constant c n , since the x i ’s are the local extrema of Tn+1 (x).
Derive thedifferential equation (1 - x2 ) T´´k(x) - XT´k(X) - k2Tk(x) by differentiating (6.9) with respectto θ and use it to eliminate (1 - x2 ) T´´n+1(x) from your expression for w´(x). Use it also toprove that X T´n+1 (X ) = (n + 1)2Tn+1(x) for x = x0, xn+1. Finally, you will need the fact thatT´n+1 (xj ) = 0, Tn+1 (xj ) = (-l)j, for j = 1, . . . , n.]6.1-6 Rove that, for a convex function f(x) on some interval a < x < b, the best linearuniform approximation p1*(x) to f(x) is of the form p1*(x) = p1(x) + ½p1(y) }, with p1(x) the straight line which agrees with f(x) at a and b.6.1-7 Let pn*(x) be the best uniform approximation to f(x) on the standard interval -1 < x< 1.
Use the uniqueness of the pn*(x) to prove that pn*(x) is odd (even) in case f(x) is odd(even), i.e., in case f(-x) = -f(x) (f(-x) = f(x)) for all x.Conclude that the lower bound obtained in Example 6.2 foris alreadya lower bound for6.1-8 Suppose the functionis orthogonal to polynomials of degree < n on the interval= 0 for allProve that thenfor any particular continuous function f(x).6.1-9 Use the addition formula for the cosine to prove (6.11).6.1-10 Calculate a good polynomial approximation of degree n on 0 < x < 1 to f(x)for n - 1, 2, 3, . . . , 10, and so verify thatFrom this, estimatethe degree n required for which6.1-11 Repeat Exercise 6.1-10 on the interval -1 < x < 1. Assuming thatconst n-α, what is your guess for α?6.1-12 Repeat the calculations of Example 2.4, but use the expanded Chebyshev points(6.18 e) as interpolation points instead of equally spaced interpolation points.
Compare yourresults with those of Example 2.4 and try to explain them in terms of Fig. 6.4 and (6.19).6.1-13 Repeat 6.1-12, but for the function f(x) = |x|. (This is a nice illustration of the factthat, in polynomial approximation, bad behavior in the function somewhere results in a poorapproximation everywhere. Use a piecewise-polynomial approximant is a good way toavoid this disagreeable feature of polynomial approximation.)6.1-14 Prove that the lower bound which is given in (6.4) can be calculated as|f[x0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
