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