Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 47

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

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

The numbermeasures theextent to which a simple harmonic motion of angular frequency j is presentin the total motion. The entire sequence(or, perhaps, thesequence of their squares) is called the power spectrum, or, simply, thespectrum of f(x). Note that, by Parseval’s relation (6.48), the spectrum forf(x) is bounded by ||f|| 2 , but f(x) may have widely differing behaviordepending on just how the “total energy”is distributed over thespectrum |f(0)|, |f(1)|, .

. . . A “noisy” function will have sizable |f(j)| forlarger j, while, for a “smooth” function, the spectrum will decrease rapidlyas j increases. See Fig. 6.7.A favorite method of smoothing consists in generating the Fouriercoefficients of the given function f(x) from data, filtering these coefficients,which means to suppress certain frequencies, usually the high frequencies,in some manner, and then reconstituting the function as a Fourier serieswith these “purified” or “filtered” coefficients.

See Fig. 6.7 for an example.It can be shown that(6.49)in case f(x) has k - 1 continuous derivatives (as a periodic function!) andi t s kth derivative is piecewise continuous (or even only of boundedvariation). For example, the “square wave”f(x) = signum (sin x) =Figure 6.7 Two real 2π -periodic functions and their power spectrum. The second is obtainedfrom the first by suppressing its higher frequencies.272APPROXMATIONis only piecewise continuous. We therefore expectto go to zero asno faster than 1/|j|.

This is confirmed by direct calculations:Note that the spectrum for the functionf(x) = xdecays no faster than 1/j even though the function is infinitely oftendifferentiable. This is so because Fourier analysis (as we have described ithere) treats this function as a 2π-periodic function whose value for0 < x < 2π is x. But this latter function has a jump discontinuity at allmultiples of 2π!It is usually not possible to calculate the Fourier coefficients (6.47)exactly, because the integral cannot be evaluated in closed form or, else,because the function f(x) is not known exactly.

In either case, numericalintegration is used. An introduction to this old and rich subject is given inChap. 7 in a general context. For the present purpose, the very simpleapproximation rule(6.50)suffices. This is the composite trapezoid rule (7.49) applied to the presentintegral, taking into account that the integrand g(x) is 2π -periodic, andtherefore, in particular, g(2π) = g(0). The rule can be obtained by replacing the 2π-periodic function g(x) under the integral sign by a piecewiselinear interpolant which agrees with g(x) at its equispaced breakpoints0, ±2π/N, ±2π2/N, ±2π3/N,.

. . , , ; see Fig. 6.8.We denote bythe corresponding approximation to(6.5 1)withThese points xn are called the sampling points and the numbers f(xn) arethe corresponding sample values. The number 2π/N is called the samplinginterval and its reciprocal, the number N/(2π ), is called the samplingfrequency.How accurate an approximation doesprovide toTo answerthis question, we now record the fact that the functions 1, e±ix, e±i2x, . . .*6.5APPROXIMATION BY TRIGONOMETRIC POLYNOMIALS273Figure 6.8 A 2π -periodic function (dashed line) and a piecewise-linear interpolant (solid line)on N = 4 points per period.have also certain orthogonality properties with respect to another kind ofscalar or inner product, namely the discrete inner product(6.52)Explicitly,(6.53)and a proof of this requires nothing deeper than summing a finite geometric series (see Exercise 6.5-8).With this, note thatHence, assuming that the Fourier seriesconverges absolutely tof(x) (this requires nothing more than the existence of the limitwe conclude with (6.53) that(6.54)orIn words: Our approximate Fourier coefficientis made up of all theexact Fourier coefficients f(k) whose corresponding function eikx cannotbe distinguished by the inner product (6.52) from the function eijx.This phenomenon has been called aliasing.

If k = j(mod N), thenk = j + mN for some integer m. But then, for any n,andThis says that theneikx = eijxikxi.e., the two functions efor x = xn = 2πn/N, and all nand eijx agree at every sampling point which is274 APPROXIMATIONused in the calculation ofi.e., in the discrete inner product < , >N. Ifwe only consider function values at the sampling points xn, all n, then wecannot tell the two functions eikx and eijx apart.A striking example of this effect is provided in the movies by wagonwheels which seem to stand still or even to rotate against the motion of thewagon.

Here a periodic motion is sampled every second, and is thenidentified by the viewer with the slowest motion compatible with theevidence.In the same way, it is customary (when sampling at N uniformlyspaced points in [0, 2π)) to identify the function eijx with the function eij´xfor which j´ = j(mod N) and whose (angular) frequency |j´| is as small aspossible.

Note that j´ is uniquely defined in this way by j and N, with thefollowing exception: If N is even and j is an odd multiple of N/2, thenboth N/2 and -N/2 could serve for j´. In this latter case, it has becomecustomary to choose the average of the two functions ei(N/2)x and e-i(N/2)x,namely the function cos (N/2)x, as the representative of its class.Correspondingly, although (6.5 1) provides the approximationfor every j, it is usually taken only as an approximation toThis makes particularly good sense when f(x) issmooth and |j| is much smaller than N/2.

For then, on combining (6.49)and (6.54), we find that(6.55)in case f(x) has k - 1 continuous derivatives and its kth derivative ispiecewise continuous.In effect, when we sample a function at N equally spaced points, in theinterval [0, 2π), the aliasing effect prevents us from seeing periodic phenomena in f(x) with frequencies higher than (N /2)/(2π ). Put positively, ifwe wish to observe a certain periodic phenomenon of frequency v, then wemust sample at a frequency at least as large as 2 v.We now discuss briefly the corresponding trigonometric polynomialapproximantHere, the last term is present only when N/2 is an integer, i.e., when N iseven. But, having mentioned this term for completeness’ sake (see Exercise6.5-11), we will now only discuss the case when N is odd,N = 2n + lIn this case, the N = 2n + 1 functions 1, e±ix, .

. . , e±inx are, by (6.53),orthonormal with respect to the discrete inner product < , >N, i.e.,(6.56)By the reasoning of Section 6.2, this implies the following theorem.*6.5APPROXIMATION BY TRIGONOMETRIC POLYNOMIALS275Theorem 6.5 For any m < n, the mth order trigonometric polynomialis the best approximation to f(x) by trigonometric polynomials oforder m with respect to the discrete mean-square normFor m = n, this means that the nth order trigonometric polynomialinterpolates f(x) at the sampling points xj = 2π j/N, all j.If f(x) is a real function, then we can write the interpolating polynomial, according to (6.45), in real form as(6.57)with(6.58a)(6.58b)Example 6.14 We construct the trigonometric interpolant of order 1 to f(x) - sin x.Then N - 3 and the relevant quantities are:These are important sinceFurther276APPROXIMATIONHence a1 = 2 Re (c1) = cl + c-1 = 0, b1 = -2 Im (c1) = i ( c1 - c-1) = 1, showingthatp 1 (x) = 0 + 0·cos 1x + 1·sin 1x = sin xas expected.We mention in passing that it is possible to interpolate uniquely bytrigonometric polynomials of order n at any 2n + 1 distinct points in[0,2π).

For the resulting interpolant pn(x) to f(x), one can show that(6.59)Here, the max-norm is taken over the interval [0, 2π],andwithshorthand for the statement “p(x) is a trigonometric polyordern.” One shows (6.59) much as the corresponding inequalitynomial of(6.17) for polynomial interpolation. In particular, the number constdepends on the interpolation points. In these terms, the uniformly spacedinterpolation points which we have been using here exclusively are optimalin that they make the number const in (6.59) as small as possible; see deBoor and Pinkus [39]. The value of this best constant has been calculatedby Ehlich and Zeller [38] to be(6.60)Thus, for values of n of practical interest, interpolation at uniformlyspaced points gives approximations which are not much worse than thebest possible uniform approximation from There is then usually noneed to go through the complicated process of constructing a best uniformapproximation, provided the interpolant is easy to obtain.

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

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