<<

. 9
( 136 .)



>>



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

<<

. 9
( 136 .)



>>