<<

. 8
( 136 .)



>>

Clearly, series can converge at qualitatively different rates.


2.3 Orders of Convergence
It is useful to have precise de¬nitions for classifying the rate of convergence (Boyd, 1982a).
Warning: these are all asymptotic de¬nitions based on the behavior of the series coef¬-
cients for large n. They may be highly misleading if applied for small or moderate n.

De¬nition 2
The ALGEBRAIC INDEX OF CONVERGENCE k is the largest number for which

lim | an | nk < ∞, (2.15)
n >> 1
n’∞

where the an are the coef¬cients of the series. (For a Fourier series, the limit must be ¬nite for both
the cosine coef¬cients an and the sine coef¬cients bn .)
Alternative de¬nition: if the coef¬cients of a series are an and if

an ∼ O[1/nk ], (2.16)
n >> 1

then k is the algebraic index of convergence.

The two de¬nitions are equivalent, but the roundabout form (2.15) also gives an un-
ambiguous de¬nition of the order even for exotic cases for which the asymptotic form is
an ∼ O(log[n]/nk ) or the like.
Examples: the algebraic convergence order k is k = 1 for the Fourier series of the “saw-
tooth” function and k = 2 for that of the “half-wave recti¬er” function, whose coef¬cients
are proportional to 1/n2 for n >> 1. This de¬nition provides a guideline: One should
choose the spectral algorithm so as to maximize the algebraic convergence order for a given
problem; the method with the largest k will always give fastest asymptotic convergence.

De¬nition 3
If the algebraic index of convergence k is unbounded “ in other words, if the coef¬cients an decrease
faster than 1/nk for ANY ¬nite power of k “ then the series is said to have the property of “INFINITE
ORDER”, “EXPONENTIAL”, or “SPECTRAL” convergence.
Alternative de¬nition: If

an ∼ O[exp(’qnr )], (2.17)
n >> 1

with q a constant for some r > 0, then the series has INFINITE ORDER or EXPONENTIAL
convergence.

The equivalence of the second de¬nition to the ¬rst is shown by the identity

lim nk exp(’qnr ) = 0, (2.18)
all k, all r > 0
n’∞

(Abramowitz and Stegun, 1965, pg. 68). The reason for giving two de¬nitions is that (2.17),
which is more obvious and easier to understand, does not cover all possible cases. The
terms “exponential” and “in¬nite order” are synonyms and may be used interchangeably.
The term “spectral accuracy” is widely used. However, we shall avoid it because
algebraically-converging Chebyshev series are “spectral”, too. The popularity of this term
is a reminder that in¬nite order convergence is usual for any well-designed spectral algo-
rithm.
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
26

De¬nition 4
The EXPONENTIAL INDEX OF CONVERGENCE r is given by
log | log(| an |) |
r ≡ lim (2.19)
log(n)
n’∞

An equivalent de¬nition is that if s and q > 0 are constants and
an ∼ O(s exp[’qnr ]), (2.20)
n >> 1,
then the EXPONENTIAL INDEX OF CONVERGENCE is the exponent r.
Example: the coef¬cients of the function (2.12) are an = 2 exp(’{’ log p} n), which is
of the form of (2.20) with the constant s = 2, q = ’ log(p), and the exponential index of
convergence r = 1.
Not all functions have series coef¬cients in the form of (2.20); the coef¬cients of the j-th
derivative of f (x) = (1 ’ p2 )/[(1 + p2 ) ’ 2p cos(x)] are O[nj exp(’qn)] whereas the j-th
integral has coef¬cients that are O[ exp(’qn)/nj ]. The rigorous de¬nition (2.19) allows for
such algebraic factors of n multiplying the exponential ” by ignoring them.
The reason for ignoring algebraic factors is that nk varies very slowly in comparison
with the exponential for large n. (This is why (2.18) is true even for very large positive
values of k). We shall adopt the convention of representing such slowly-varying algebraic
factors of n by empty brackets [].
De¬nition 5 (Rates of Exponential Convergence) A series whose coef¬cients are an is said to
have the property of SUPERGEOMETRIC, GEOMETRIC, or SUBGEOMETRIC convergence de-
pending upon whether
±
∞ SU P ERGEOM ET RIC
lim log(| an |)/n = (2.21)
constant GEOM ET RIC

n’∞
0 SU BGEOM ET RIC
Alternative de¬nitions:
1. If an ∼ O([] exp{’(n/j) log(n)}), convergence is SUPERGEOMETRIC
2. If an ∼ O([] exp{’qn}), convergence is GEOMETRIC
3. If the exponential index of convergence r < 1, then the convergence is SUBGEOMETRIC.
(The empty brackets [] denote factors that vary more slowly with n than the exponentials.)
The motive for these de¬nitions is that the Fourier and Chebyshev series of so-called
“entire functions” [functions without singularities anywhere in the complex plane except
at ∞] have “supergeometric” convergence. For the expansion of functions with poles or
branch points which are a ¬nite distance off the expansion interval ” the usual case ”
geometric convergence is normal. Both entire functions and functions with singularities at
¬nite x (but off the expansion interval) have r = 1, so the exponential index of convergence
cannot discriminate between them even though these are quite distinct classes of functions.
“Subgeometric” convergence rarely occurs when solving problems on a ¬nite interval, but
it is normal for series on in¬nite or semi-in¬nite intervals in x.
These de¬nitions have been expressed in terms of the sequence of coef¬cients an . How-
ever, normalized basis functions are always O(1) so that the magnitude of the term an φn (x)
is that of the coef¬cient an .
The second comment is that the limits de¬ned above are meaningless when, for exam-
ple, every other coef¬cient is zero. Strictly speaking, the limits should be supremum limits
(see glossary). It often suf¬ces, however, to apply the ordinary limit to the non-zero coef¬-
cients.
2.4. CONVERGENCE ORDER 27

De¬nition 6 (ASYMPTOTIC RATE OF GEOMETRIC CONVERGENCE ) If a series has ge-
ometric convergence, that is, if an expansion has an exponential index of convergence r = 1 so that

an ∼ [ ] exp(’nµ) (2.22)

where an are the spectral coef¬cients, µ is a constant, and [ ] denotes unspeci¬ed factors that vary
more slowly with n than the exponential (such as nk for some k), then the ASYMPTOTIC RATE
OF GEOMETRIC CONVERGENCE is µ. Equivalently,

µ = lim {’ log | an | /n} (2.23)
n’∞

This de¬nition is meaningful only for geometrically converging series; it does not apply when the
algebraic index of convergence is < ∞ nor when the exponential index of convergence r < 1.

For power series, µ is simply the logarithm of the radius of convergence. Later in the
chapter, we shall explain how to calculate µ for Fourier and Chebyshev series in terms of
the singularities of the function being expanded.


2.4 Graphical Interpretation of Orders of Convergence
These abstract concepts become clearer with graphs. On a LOG-LINEAR graph, for example,
the coef¬cients of a GEOMETRICALLY converging series will ASYMPTOTE to a STRAIGHT
LINE as shown by the solid curve in Fig. 2.5. “Supergeometric” convergence can then
be graphically de¬ned as coef¬cients whose curve develops a more and more negative
slope (rather than a constant slope) on a log-linear graph. Similarly, subgeometric and


Log-Linear
0
10

-2 Algebraic
10
-4
10
Supe




Sub
geo
met
-6 ric
r




10
geom



Ge
om




-8
10
etric




etr
ic




-10
10
0 10 20 30 40
Figure 2.5: log | an | versus n for four rates of convergence. Circles: algebraic convergence,
such as an ∼ 1/n2 . Dashed: subgeometric convergence, such as an ∼ exp(’1.5 n2/3 ). Solid:
geometric convergence, such as exp(’µ n) for any positive µ. Pluses: supergeometric, such
as an ∼ exp(’n log(n) ) or faster decay.
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
28



Log-Log
0
10


-2
10
Algebraic




Su
Sup




bg Geome
eo
erge
-4




m
10




et
ric
ome
tric



tric
-6
10 0 1 2
10 10 10
Figure 2.6: Same as previous ¬gure except that the graph is log-log: the degree of the
spectral coef¬cient n is now plotted on a logarithmic scale, too.




0
10



-5
10



-10
10

0 1 2
10 10 n 10
Figure 2.7: Spectral coef¬cients for two series. Upper curve: an = 1/n2 . Lower curve:
an = exp(’n) + 10’8 /n2 .
2.4. CONVERGENCE ORDER 29

<<

. 8
( 136 .)



>>