20CHAPTER2.CHEBYSHEV&FOURIERSERIESare useful to identify both errors and unexpected physics, and also to answer the question:Is agiven calculationfeasibleonmymachine?Wewill returntoeachof thesefourkeythemes inthemiddleofthechapter,thoughnotin the same order as above. First, though, a brief review of Fourier series.2.22FourierseriesTheFourier series ofageneral functionf(r)isf(a) = do +an cos(na) +bn sin(nr)(2.1) n=1n=1wherethe coefficients are0=(1/2元)f(r)daan = (1/元)f() cos(nz)dabn = (1/元) /(2.2)f() sin(nr)daFirst note: because the sines and cosines are periodic with a period of 2 π, we can alsocomputetheFourierexpansiononthe interval E[0,2].Theonlyalteration isthatthelimits ofintegration in the coefficient integrals (2.2) are also changed from[-π,] to [0,2元],Secondnote:thegeneralFourierseriescanalsobewritteninthecomplexformf(a) =Cnexp(inr)(2.3)wherethecoefficients areCn =(1/2元)f(a) exp(-inr)dr(2.4)The identities(2.5)cos(r)= (exp(ir)+exp(-ir))/2:sin(r) = (exp(ix) - exp(-ir))/(2i),show that (2.3) and (2.1) are completely equivalent, and we shall use whichever is conve-nient.Thecoefficientsofthetwoforms arerelatedbyn=0co=ao,(an - ibn)/2,n>0Cnn<0(an +ibn)/2,Often, it is unnecessary to use the full Fourier series. In particular, if f() is known tohave the property of being symmetric about = o, which means that f(r) = f(-) for allr,then all the sine coefficients are zero.The series with only the constant and the cosineterms isknown as a“Fourier cosine series".(A Chebyshev series is aFourier cosine serieswith a change of variable.) If f(α) = -f(-) for all r, then f() is said to be antisymmetricabout =O and all the an=0.Its Fourier series is a sine series.These special cases areextremelyimportant inapplicationsas discussed intheChapter8
20 CHAPTER 2. CHEBYSHEV & FOURIER SERIES are useful to identify both errors and unexpected physics, and also to answer the question: Is a given calculation feasible on my machine? We will return to each of these four key themes in the middle of the chapter, though not in the same order as above. First, though, a brief review of Fourier series. 2.2 Fourier series The Fourier series of a general function f(x) is f(x) = a0 + X∞ n=1 an cos(nx) + X∞ n=1 bn sin(nx) (2.1) where the coefficients are a0 = (1/2π) Z π −π f(x)dx an = (1/π) Z π −π f(x) cos(nx)dx bn = (1/π) Z π −π f(x) sin(nx)dx (2.2) First note: because the sines and cosines are periodic with a period of 2 π, we can also compute the Fourier expansion on the interval x ∈ [0, 2π]. The only alteration is that the limits of integration in the coefficient integrals (2.2) are also changed from [−π, π] to [0, 2π]. Second note: the general Fourier series can also be written in the complex form f(x) = X∞ n=−∞ cn exp(inx) (2.3) where the coefficients are cn = (1/2π) Z π −π f(x) exp(−inx)dx (2.4) The identities cos(x) ≡ (exp(ix) + exp(−ix))/2; sin(x) ≡ (exp(ix) − exp(−ix))/(2i), (2.5) show that (2.3) and (2.1) are completely equivalent, and we shall use whichever is convenient. The coefficients of the two forms are related by c0 = a0, n = 0 cn = ½ (an − ibn)/2, n> 0 (an + ibn)/2, n< 0 Often, it is unnecessary to use the full Fourier series. In particular, if f(x) is known to have the property of being symmetric about x = 0, which means that f(x) = f(−x) for all x, then all the sine coefficients are zero. The series with only the constant and the cosine terms is known as a “Fourier cosine series”. (A Chebyshev series is a Fourier cosine series with a change of variable.) If f(x) = −f(−x) for all x, then f(x) is said to be antisymmetric about x = 0 and all the an = 0. Its Fourier series is a sine series. These special cases are extremely important in applications as discussed in the Chapter 8
212.2.FOURIERSERIESDefinition1 (PERIODICITY)Afunctionf(r)isPERIODICwitha period of 2if(2.6)f()=(+2元)for all r.To illustrate these abstract concepts, we will look atfour explicit examples. These willallow us to develop an important theme:The smoother the function,morerapidly its spec-tral coefficients converge.EXAMPLEONE:"PiecewiseLinear”or“Sawtooth"FunctionSince the basis functions of the Fourier expansion, (1, cos(nz), sin(nr), all are peri-odic, it would be reasonable to suppose that the Fourier series would be useful only forexpandingfunctions that have this same property. In fact, this is only half-true.Fourier se-ries work bestfor periodic functions, and whenever possible, we will use them only whentheboundary conditionsarethatthe solution beperiodic.(Geophysical example:becausethe earth is round, atmospheric flows are always periodic in longitude). However, Fourierseries will converge, albeit slowly,for quite arbitrary f().In keeping with our ratherlow-brow approach, we will prove this by example. Supposewe take f(r) = , evaluate the integrals (2.2) and sum the series (2.1). What do we get?Because all thebasisfunctions areperiodic,theirsummustbeperiodic even if thefunction f(r) in the integrals is not periodic.The result is that the Fourier series convergesto the so-called "saw-tooth" function (Fig. 2.1).Sincef()=is antisymmetric,alltheanare0.Thesinecoefficientsarebn= (1/元)sin(nr)dr= (-1)n+1(2/n)(2.7)Since the coefficients are decreasing as O(1/n),the series does not converge with blaz-ing speed; in fact, this is the worst known example for an f(r) which is continuous.Nonetheless,Fig.2.2showsthataddingmoreandmoretermstothesineseriesdoesindeedgeneratea closer and closerapproximation toa straight line.The graph of the error shows that the discontinuity has polluted the approximationwith small, spurious oscillations everywhere.At any given fixed , however, the ampli-tude of these oscillations decreases as O(1/N).Near the discontinuity,there is a regionwhere (i)the error is always O(1)and (ii)theFourier partial sum overshoots f()bythesame amount, rising to a maximum ofabout1.18 instead of1, independent of N.Collec-tively,thesefacts areknown as“Gibbs'Phenomenon".Fortunately,through"filtering","sequenceacceleration"and"reconstruction",itispossibleto amelioratesomeofthese+T-0元2元一元2元3元Figure2.1:"Sawtooth”(piecewiselinear)function
2.2. FOURIER SERIES 21 Definition 1 (PERIODICITY) A function f(x) is PERIODIC with a period of 2 π if f(x) = f(x + 2π) (2.6) for all x. To illustrate these abstract concepts, we will look at four explicit examples. These will allow us to develop an important theme: The smoother the function, more rapidly its spectral coefficients converge. EXAMPLE ONE: “Piecewise Linear” or “Sawtooth” Function Since the basis functions of the Fourier expansion, {1, cos(nx), sin(nx)}, all are periodic, it would be reasonable to suppose that the Fourier series would be useful only for expanding functions that have this same property. In fact, this is only half-true. Fourier series work best for periodic functions, and whenever possible, we will use them only when the boundary conditions are that the solution be periodic. (Geophysical example: because the earth is round, atmospheric flows are always periodic in longitude). However, Fourier series will converge, albeit slowly, for quite arbitrary f(x). In keeping with our rather low-brow approach, we will prove this by example. Suppose we take f(x) = x, evaluate the integrals (2.2) and sum the series (2.1). What do we get? Because all the basis functions are periodic, their sum must be periodic even if the function f(x) in the integrals is not periodic. The result is that the Fourier series converges to the so-called “saw-tooth” function (Fig. 2.1). Since f(x) ≡ x is antisymmetric, all the an are 0. The sine coefficients are bn = (1/π) Z π −π x sin(nx)dx = (−1)n+1(2/n) (2.7) Since the coefficients are decreasing as O(1/n), the series does not converge with blazing speed; in fact, this is the worst known example for an f(x) which is continuous. Nonetheless, Fig. 2.2 shows that adding more and more terms to the sine series does indeed generate a closer and closer approximation to a straight line. The graph of the error shows that the discontinuity has polluted the approximation with small, spurious oscillations everywhere. At any given fixed x, however, the amplitude of these oscillations decreases as O(1/N). Near the discontinuity, there is a region where (i) the error is always O(1) and (ii) the Fourier partial sum overshoots f(x) by the same amount, rising to a maximum of about 1.18 instead of 1, independent of N. Collectively, these facts are known as “Gibbs’ Phenomenon”. Fortunately, through “filtering”, “sequence acceleration” and “reconstruction”, it is possible to ameliorate some of these −2π −π 0 π 2π 3π Figure 2.1: “Sawtooth” (piecewise linear) function
22CHAPTER2.CHEBYSHEV&FOURIERSERIES31.5N=182.5N=18/20.51.5N=30.50.52233-Figure 2.2: Left:partial sums of the Fourier series of the piecewise linear ("sawtooth")function(divided byπ)forN=3,6,9,12,15,18.Right:errors.Forclarity,boththepartialsums and errors havebeen shiftedwith upwards withincreasingN.problems.Because shock waves in fuids are discontinuities, shocks produce Gibbs'Phe-nomenon,too,and demandthesameremedies.EXAMPLETWO:"Half-Wave Rectifier"FunctionThisisdefined ontE[0,2] bysin(t),0<t<Tf(t) =0,π<t<2元and is extended to all t by assuming that this pattern repeats with a period of 2 . [Geo-physicalnote:thisapproximatelydescribesthetime dependence of thermal tides intheearth's atmosphere: the solar heating rises and falls during the day but is zero at night.jIntegration gives the Fourier coefficients as(2.8)Q2n = -2/[π(4n2 - 1)](n >0);a2n+1= 0(n ≥ 1)a0 = (1/元);(2.9)b1 = 1/2;b2n = 0(n > 1)Fig.2.3 shows the sum of the first four terms of the series, fa()=0.318+ 0.5 sin(t)0.212 cos(2t)-0.042 cos(4t). The graph shows that the series is converging muchfaster thanthat for the saw-tooth function. At t = /2, where f(t) = 1.000, the first four terms sum to0.988, an error of only 1.2 %This series converges more rapidly than that for the"saw-tooth"because the"half-wave rectifier"function is smoother than the"saw-tooth"function.The latter is discontin-uous and itscoefficientsdecreaseasO(1/n)inthe limit n→oo;the“half-waverectifier"iscontinuousbut itsfirstderivative isdiscontinous,so itscoefficients decreaseas O(1/n).Thisis a general property: the smoother a function is, the more rapidly its Fourier coefficients willdecrease, and we can explicitly derive the appropriate power of1/n
22 CHAPTER 2. CHEBYSHEV & FOURIER SERIES 0 1 2 3 0 0.5 1 1.5 2 2.5 3 N=18 N=3 0 1 2 3 -1 -0.5 0 0.5 1 1.5 N=18 N=3 Figure 2.2: Left: partial sums of the Fourier series of the piecewise linear (“sawtooth”) function (divided by π) for N=3 , 6, 9, 12, 15, 18. Right: errors. For clarity, both the partial sums and errors have been shifted with upwards with increasing N. problems. Because shock waves in fluids are discontinuities, shocks produce Gibbs’ Phenomenon, too, and demand the same remedies. EXAMPLE TWO: “Half-Wave Rectifier” Function This is defined on t ∈ [0, 2π] by f(t) ≡ sin(t), 0 <t<π 0, π<t< 2π and is extended to all t by assuming that this pattern repeats with a period of 2 π. [Geophysical note: this approximately describes the time dependence of thermal tides in the earth’s atmosphere: the solar heating rises and falls during the day but is zero at night.] Integration gives the Fourier coefficients as a0 = (1/π); a2n = −2/[π(4n2 − 1)] (n > 0); a2n+1 = 0(n ≥ 1) (2.8) b1 = 1/2; b2n =0 (n > 1) (2.9) Fig. 2.3 shows the sum of the first four terms of the series, f4(x)=0.318 + 0.5 sin(t) − 0.212 cos(2t)−0.042 cos(4t). The graph shows that the series is converging much faster than that for the saw-tooth function. At t = π/2, where f(t)=1.000, the first four terms sum to 0.988, an error of only 1.2 %. This series converges more rapidly than that for the “saw-tooth” because the “halfwave rectifier” function is smoother than the “saw-tooth” function. The latter is discontinuous and its coefficients decrease as O(1/n) in the limit n → ∞; the “half-wave rectifier” is continuous but its first derivative is discontinous, so its coefficients decrease as O(1/n2). This is a general property: the smoother a function is, the more rapidly its Fourier coefficients will decrease, and we can explicitly derive the appropriate power of 1/n
232.2.FOURIERSERIES0.52681012P0.523356Figure 2.3: Top: graph of the "half-wave rectifier" function. Bottom: A comparison of the"half-waverectifier"function[dashed]withthesumof thefirstfourFourierterms[solid]f(α) = 0.318 + 0.5 sin(t) - 0.212 cos(2 t) - 0.042 cos(4 t). The two curves are almostindistinguishable.Although spectral methods (and all other algorithms!) work best when the solution issmooth and infinitely differentiable, the "half-wave rectifier" shows that this is not alwayspossible.EXAMPLETHREE:InfinitelyDifferentiablebutSingularforRealr(2.10)f(r) = exp(- cos2()/ sin(r))This function has an essential singularity of the form exp(-1/2) at = 0. The powerseries aboutr =0is meaninglessbecause all the derivativesof (2.10)tend to0as -→0.However, the derivatives exist because their limit as r - o is well-defined and bounded.The exponential decayofexp(-1/2)is sufficienttoovercomethenegativepowers of athat appear when we differentiate so that none of the derivatives are infinite.Boyd (1982a)shows that theFourier coefficients of (2.10)are asymptoticallyofthe forman ~ [Jexp(-1.5n2/3) cos(2.60n2/3 + 六/4)(2.11)where denotes an algebraicfactor of n irrelevant for present purposes.Fast convergence,even though thepower series about =O is useless, is a clear signal that spectral expan-sions aremorepotentthanTaylorseries (Fig.2.4).This example may seem rather contrived.However,"singular-but-infinitely-differentiable"isactuallythemostcommoncaseforfunctionsonaninfiniteorsemi-infiniteinterval.Mostfunctions havesuch bounded singularitiesat infinity,that is,at one or both endpointsoftheexpansionintervalEXAMPLEFOUR:"Symmetric, Imbricated-Lorentzian"(SIP) Function(2.12)f() = (1 -p2)/ ((1 +p2) - 2pcos())
2.2. FOURIER SERIES 23 0 1 2 3 4 5 6 0 0.5 1 t 0 2 4 6 8 10 12 0 0.5 1 t Figure 2.3: Top: graph of the “half-wave rectifier” function. Bottom: A comparison of the “half-wave rectifier” function [dashed] with the sum of the first four Fourier terms [solid]. f4(x)=0.318 + 0.5 sin(t) − 0.212 cos(2 t) − 0.042 cos(4 t). The two curves are almost indistinguishable. Although spectral methods (and all other algorithms!) work best when the solution is smooth and infinitely differentiable, the “half-wave rectifier” shows that this is not always possible. EXAMPLE THREE: Infinitely Differentiable but Singular for Real x f(x) ≡ exp{− cos2(x)/ sin2(x)} (2.10) This function has an essential singularity of the form exp(−1/x2) at x = 0. The power series about x = 0 is meaningless because all the derivatives of (2.10) tend to 0 as x → 0. However, the derivatives exist because their limit as x → 0 is well-defined and bounded. The exponential decay of exp(−1/x2) is sufficient to overcome the negative powers of x that appear when we differentiate so that none of the derivatives are infinite. Boyd (1982a) shows that the Fourier coefficients of (2.10) are asymptotically of the form an ∼ [ ] exp(−1.5n2/3) cos(2.60n2/3 + π/4) (2.11) where [] denotes an algebraic factor of n irrelevant for present purposes. Fast convergence, even though the power series about x = 0 is useless, is a clear signal that spectral expansions are more potent than Taylor series (Fig. 2.4). This example may seem rather contrived. However, “singular-but-infinitely-differentiable” is actually the most common case for functions on an infinite or semi-infinite interval. Most functions have such bounded singularities at infinity, that is, at one or both endpoints of the expansion interval. EXAMPLE FOUR: “Symmetric, Imbricated-Lorentzian” (SIP) Function f(x) ≡ (1 − p2)/ © (1 + p2) − 2p cos(x) ª (2.12)
24CHAPTER2.CHEBYSHEV&FOURIERSERIESfFouriercoeffs10021020.830810001040.68h1080.4P391080.2红-101002-210203040xdegreenFigure 2.4: Left: graph of f() = exp(- cos2(r) / sin?() ). Right: Fourier cosine coeff-cients of this function.The sine coefficients are all zero because this function is symmetricwithrespectto r=0.wherep<1isa constant.Thisf()is aperiodicfunctionwhichis infinitelydifferentiableandcontinuous in all its derivatives. Its Fourier series is(2.13)f(a) =1 +2p" cos(n)n=This example illustrates the"exponential"and"geometric"convergence which is typ-ical of solutions to differential equations in the absence of shocks, corner singularities, ordiscontinuities.We may describe (2.13) as a "geometrically-converging" series because at = 0, this isa geometric series. Since cos(nz) I≤ 1 for all n and , each term in the Fourier series isbounded by the corresponding term in the geometric power series in p for all .Becausethis rate of convergence is generic and typical, it is important to understand that it is qual-itatively different from the rate of the convergence of series whose terms are proportionaltosomeinversepowerofn.Note that each coefficient in (2.13) is smaller than its predecessor by a factor of p wherep <1.However, if the coefficients were decreasing as O(1/n) for some finitek wherek=1for the"saw-tooth"and k=2forthe"half-waverectifier",thenan+1/an ~n*/(n+1)k~1-k/nforn>>k(2.14)~1[Non -exponential Convergence]Thus, even if k is a very large number, the ratio of an+i/an tends to 1 from belowfor large n. This never happens for a series with "exponential" convergence; the ratio ofI an+1/an |is always bounded away from one—by p in (2.13),for example
24 CHAPTER 2. CHEBYSHEV & FOURIER SERIES 10 20 30 40 10-10 10-8 10-6 10 -4 10 -2 100 degree n Fourier coeffs. -2 0 2 0 0.2 0.4 0.6 0.8 1 x f Figure 2.4: Left: graph of f(x) ≡ exp(− cos2(x) / sin2(x) ). Right: Fourier cosine coeffi- cients of this function. The sine coefficients are all zero because this function is symmetric with respect to x = 0. where p < 1 is a constant. This f(x) is a periodic function which is infinitely differentiable and continuous in all its derivatives. Its Fourier series is f(x)=1+2X∞ n=1 pn cos(nx) (2.13) This example illustrates the “exponential” and “geometric” convergence which is typical of solutions to differential equations in the absence of shocks, corner singularities, or discontinuities. We may describe (2.13) as a “geometrically-converging” series because at x = 0, this is a geometric series. Since | cos(nx) | ≤ 1 for all n and x, each term in the Fourier series is bounded by the corresponding term in the geometric power series in p for all x. Because this rate of convergence is generic and typical, it is important to understand that it is qualitatively different from the rate of the convergence of series whose terms are proportional to some inverse power of n. Note that each coefficient in (2.13) is smaller than its predecessor by a factor of p where p < 1. However, if the coefficients were decreasing as O(1/nk) for some finite k where k = 1 for the “saw-tooth” and k = 2 for the “half-wave rectifier”, then an+1/an ∼ nk/(n + 1)k ∼ 1 − k/n for n >> k (2.14) ∼ 1 [Non − exponential Convergence] Thus, even if k is a very large number, the ratio of an+1/an tends to 1 from below for large n. This never happens for a series with “exponential” convergence; the ratio of | an+1/an | is always bounded away from one — by p in (2.13), for example