0

10

n2

ex

p(-

-5

0.3

10 ex

n)

p(

-0

ex

.3

p(

- n)

0.3

-10 n)

10 /(n

log

(n

))

0 20 40 60 80 100

Figure 2.8: Spectral coef¬cients for three geometrically converging series. Although the

three sets of coef¬cients differ through algebraic coef¬cients ” the top curve is larger by

n2 than the middle curve, which in turn is larger by a factor of n log(n) than the bottom

curve ” the exponential dependence on n is the same for all. Consequently, all three sets of

coef¬cients asymptote to parallel lines on this log-linear plot.

0

10

-1

10

-2

10

-3

10

-4

10

-5

10

0 20 40 60 80 100

Figure 2.9: Solid: logarithm of the absolute value of the spectral coef¬cients of a

geometrically-converging series whose coef¬cients oscillate with degree n. Dashed: the

“envelope” of the spectral coef¬cients.

CHAPTER 2. CHEBYSHEV & FOURIER SERIES

30

algebraic convergence rates produce curves which bend upward away from the straight

line of geometric convergence: Their slopes tend to zero from below on a log-linear plot.

If we change the graph format from log-linear to log-log, then algebraic convergence

with algebraic index of convergence k can be de¬ned as coef¬cients whose curve asymp-

totes to a straight line whose slope is ’ k (Fig. 2.6). All species of exponential convergence

bend away with ever-increasing negative slopes on a plot of the logarithm of the absolute

value of { an } versus the logarithm of n. Graphically, “in¬nite order” convergence is a

synonym for “unbounded negative slope” on a log-log plot.

Four quali¬ers are necessary. First, these orders of convergence are meaningfully only

asymptotically. Fig. 2.7 compares the coef¬cients of two spectral series that have the same

(poor) asymptotic convergence rate. However, the lower curve shows that its coef¬cients

have fallen to O(10’8 ) before entering the asymptotic regime, so its slow convergence is

likely to be irrelevant in a practical sense.

Although the ¬gure is contrived, the same thing is common in real-life. Boyd(1986c)

compares the coef¬cients of the two-dimensional Chebyshev series for the solution of the

nonlinear eigenvalue problem known as Bratu™s equation with the corresponding series

for the solution to Poisson™s equation with constant forcing. Asymptotically, both spectral

series are sixth order because of weak singularities in the four corners of the square domain.

Although the Poisson series clearly exhibits this algebraic convergence on a log-log graph,

the Bratu coef¬cients appear to fall off exponentially on Boyd™s graph. The reason is that

the nonlinearity introduces additional singularities “ off the computational domain but

strong “ which dominate the early spectral coef¬cients. Only after the Bratu coef¬cients

have fallen to less than O(10’5 ) of the maximum of the solution does the slope of the

Bratu series alter to match that of the Poisson equation. We cannot repeat this too often:

Asymptotic concepts like “convergence order” are meaningful only for large n. For small

n, who knows!

The second point is that the de¬nitions above ignore algebraic factors of n which mod-

ulate the leading exponential; we have replaced these by empty square brackets in many

of the formulas of this chapter. Fig. 2.8 compares three series which differ only through

such algebraic factors. Obviously, the three series are not identical. A factor of n2 may

be anything but ignorable when n = 100! However, the graph shows that all three series

asymptote to parallel straight lines. It is in this sense that algebraic factors of n, such as pow-

ers and logarithms of n, are asymptotically irrelevant. The exponential factor of n must

dominate for suf¬ciently large n.

Third, what happens when the coef¬cients of a spectral series oscillate with degree n?

Fig. 2.9 shows, consistent with asymptotic theories of spectral coef¬cients, that it is possible

to tightly bound the spectral coef¬cients by a monotonically-decaying curve even when the

individual coef¬cients oscillate. This motivates the following.

De¬nition 7 (Envelope of the Spectral Coef¬cients)

The ENVELOPE of the spectral coef¬cients is de¬ned to be that curve, of the form of the leading

asymptotic term in the logarithm of the absolute value of the spectral coef¬cients, which bounds the

coef¬cients from above as tightly as possible.

Lastly, the asymptotic order may be defeated by the “Roundoff Plateau” illustrated in

Fig 2.10.

2.5. ASSUMPTION OF EQUAL ERRORS 31

0

10

-5

10

-10

10

Roundoff Plateau

-15

10

0 20 40 60 80 100

Figure 2.10: Numerically-generated spectral coef¬cients for a typical function. Let amax de-

note the maximum absolute value of the spectral coef¬cients aj for all j. Let denote a con-

stant proportional to the roundoff error or “machine epsilon”, typically around 10’16 on

most computers, but somewhat larger, perhaps by a factor of 100 or more. Then when the

exact coef¬cients fall below amax , spectral algorithms including interpolation will com-

pute roundoff-corrupted coef¬cients that will ¬‚atten out at roughly an ∼ amax for all suf-

¬ciently large n. (“Roughly” means that coef¬cients in the “Roundoff Plateau” ¬‚uctuate

randomly about the indicated magnitude.)

2.5 Assumption of Equal Errors

De¬nition 8 (Truncation Error)

The TRUNCATION ERROR ET (N ) is de¬ned to be the error made by neglecting all spectral

coef¬cients an with n > N .

De¬nition 9 (Discretization Error)

The DISCRETIZATION ERROR ED (N ) is the difference between the ¬rst (N + 1) terms of the

exact solution and the corresponding terms as computed by a spectral or pseudospectral method

using (N + 1) basis functions.

De¬nition 10 (Interpolation Error)

The INTERPOLATION ERROR EI (N ) is the error made by approximating a function by an N +

1-term series whose coef¬cients are chosen to make the approximation agree with the target function

exactly at each of N + 1 “interpolation” or “collocation” points, or it is the error in differential

equation approximations that use similar principles, i. e., the “pseudospectral” method.

It is generally impossible to estimate these various errors precisely for the unknown

solution to a differential equation. We have two useful alternatives. One is to look at the

numerically-computed spectral coef¬cients, as described in Sec. 12. The other strategy, and

the only one which can be applied a priori is de¬ned by the following.

De¬nition 11 (Method of Model Functions)

Truncation error is estimated by computing the expansion of a KNOWN function which is “simi-

lar”, in a technical sense to be explained later, to the solution of the target differential equation, and

then truncating the known expansion after N + 1 terms.

CHAPTER 2. CHEBYSHEV & FOURIER SERIES

32

It is rather disheartening to be forced to look at spectral coef¬cients and truncation

errors for models when what we want is the total error in computing the solution to a dif-

ferential equation. A numerical method that has a low truncation error is useless if the

corresponding discretization error is horrible. However, many years of numerical experi-

ence has established the following assumption which will underlie the rest of the chapter.

Rule-of-Thumb 1 (ASSUMPTION OF EQUAL ERRORS)

The discretization and interpolation errors are the same order-of-magnitude as the truncation error.

Therefore, we can roughly compare the effectiveness of various algorithms and estimate the smallest

truncation N that gives a speci¬ed accuracy by inspection of the truncation error alone.

This is a strong assumption, and one that cannot be “proved” in any sense. A few

counter-examples are known. However, the assumption is clearly true in a negative sense:

A method that gives a poor truncation error (unless N is huge) is a terrible way to solve the

differential equation. The truncation error is therefore a very safe way to determine what

numerical procedures not to use.

Later, we will evaluate both types of error for a couple of examples and show that the

assumption is true at least for these particular cases.

2.6 Darboux™s Principle

Theorem 1 (DARBOUX™S PRINCIPLE: SINGULARITIES & CONVERGENCE)

For all types of spectral expansions (and for ordinary power series), both the DOMAIN of CONVER-

GENCE in the complex plane and also the RATE of CONVERGENCE are controlled by the LOCATION

and STRENGTH of the GRAVEST SINGULARITY in the complex plane. “Singularity” in this context

denotes poles, fractional powers, logarithms and other branch points, and discontinuities of f (z) or

any of its derivatives.

Each such singularity gives its own additive contribution to the coef¬cients an in the asymptotic

limit n ’ ∞. The “gravest” singularity is the one whose contribution is larger than the others in

this limit; there may be two or more of equal strength.

For the special case of power series, this is “DARBOUX™s THEOREM” (Darboux, 1878a, b,

Dingle, 1973, Hunter, 1986).

Darboux™s Principle also justi¬es the assertion made in Sec. 2: the smoother f (x), the

faster the convergence of its spectral series. Table 2.2 (end of the chapter) catalogues the

relationship between the type of a singularity (logarithm, square root, etc.) and the asymp-

totic spectral coef¬cients.

Darboux™s Principle implies a corollary that clari¬es the Method of Model Functions.

Corollary 1 (SINGULARITY-MATCHING)

If two functions f (z) and g(z) have convergence-limiting singularities of the same type and

strength, then their asymptotic spectral coef¬cients are the same in the limit n ’ ∞. If f (z) ’ g(z)

is singular, but more weakly singular than either f (z) or g(z), the difference between the spectral

coef¬cients of f (z) and g(z) decreases as an algebraic function of the degree n. If f (z) ’ g(z) is

not singular at the location of the common gravest singularity of f (z) and g(z), then the difference

between spectral coef¬cients decreases exponentially fast with n.

This corollary is a direct consequence of Theorem 1: If we can compute asymptotic

expansions for the series coef¬cients which depend only on the gravest singularity, then

when the singularity is eliminated by taking the difference f (z) ’ g(z), the leading term in

the asymptotic approximation for the spectral coef¬cients is also eliminated. The spectral

2.6. DARBOUX™S PRINCIPLE 33

series for the difference must therefore converge more rapidly than the expansions for the

more singular functions f (z) and g(z).

This corollary de¬nes in what sense an explicit model function should resemble the

unknown solution to a differential equation: The model and the unknown u(x) should

have the same gravest, convergence-limiting singularities.

This theorem implies that the examples below are not merely special cases. Rather, each

is typical of a whole class of functions that have singularities of the same type at the same

point. For example, 1/(x + a) where a is an arbitrary complex parameter is representative

of all functions whose convergence is limited by a ¬rst order pole at x = ’a.

An example is useful in explaining Darboux™s Principle. The geometrically converg-

ing Fourier series (2.24) has a partial fraction expansion which explicitly shows that this

function is singular only through simple poles at x = ±ia along the imaginary axis and

the images of these two poles under the periodicity shift, x ’ x + 2 π m where m is an

arbitrary integer:

(1 ’ p2 )

»(x; p) ≡

(1 + p2 ) ’ 2 p cos(x)

∞

pn cos(n x) (2.24)

= 1+2

n=1

∞

1

(2.25)

= 2a

(a2 + (x ’ 2π m )2 )

m=’∞

where a ≡ ’ log(p) ’ p = exp( ’ a ).

In contrast, the elliptic function Dn has an in¬nite number of simple poles on the imag-

Fourier coeffs.

15

»

0

10

10

Dn

5

Dn

»

-1

0 10

0 0.5 0 10 20

x degree n