<<

. 13
( 136 .)



>>



for all f (z), all N , and all z ∈ [’1, 1].

PROOF: The Chebyshev polynomials are bounded by one, that is, | Tn (z) | ¤ 1 for all z ∈
[’1, 1] & for all n. This implies that the n-th term is bounded by | an |. Subtracting the
truncated series from the in¬nite series, bounding each term in the difference, and sum-
ming the bounds gives the theorem. Q. E. D.
The mapping alters the shape of the convergence region as described by the following.
1 Iff (z) does have symmetry, the basis can be further reduced. If f (z) = f (’z), then only the even cosines,
1, cos(2 θ), cos(4 θ), . . . , are needed. Similarly, only the odd cosines (or odd degree Chebyshev polynomials in z)
are needed if f (z) = ’f (’z).
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
48

Theorem 7 (CONVERGENCE ELLIPSE: CHEBYSHEV SERIES) Let z = x + iy. Introduc-
ing the elliptical coordinates (µ, ·) via the equations

µ ∈ [0, ∞]
x= cosh(µ) cos(·),
= ’ sinh(µ) sin(·), · ∈ [0, 2π], (2.79)
y

the surfaces of constant µ de¬ne ellipses in the complex z-plane with foci at z = ’1 and z = 1. (See
Fig. 2.16.) For large µ, elliptical coordinates tend to polar coordinates with µ proportional to log(r)
and · ’ ’θ.)
Suppse f (z) has poles, branch points or other singularities at the points (in elliptical coordi-
nates) (µj , ·j ), j = 1, 2, . . . in the complex z-plane. De¬ne

µ0 ≡ minj |µj | (2.80)

Then the Chebyshev series

(2.81)
f (z) = an Tn (z)
n=0

converges within the region bounded by the ellipse µ = µ0 ,

µ < µ0 , for all ·, [convergence] (2.82)

and diverges for all (x, y) outside this ellipse.
The coef¬cients are related to µ0 , the quasi-radial coordinate of the ellipse, by the equation

lim sup log (| an /an+1 |) = µ0 , [if the limit exists] (2.83)
n’∞

Note: the “ellipse” µ = 0 is the real interval [-1, 1]. If the coef¬cients an decrease algebraically
with n or if the convergence is exponential but subgeometric, then the Chebyshev series converges
only for µ = 0, i. e., only on the real interval z ∈ [’1, 1].

PROOF: Let the complex variable θ = · + iµ. Now a trigonometric identity shows that
for any (µ, ·),

cos(· + iµ) = cosh(µ) cos(·) ’ i sinh(µ) sin(·) (2.84)

(Abramowitz and Stegun,1965). Thus, the transformation z = cos(θ) relates (x, y) to (µ, ·)
just as de¬ned in (2.79). The straight lines which are the boundaries of the strip of Fourier
convergence in the complex θ-plane must be mapped into curves of constant µ in the z-
plane.
To show that µ = µ0 is indeed the equation of an ellipse, substitute Eq.(2.79) into

x2 /a2 + y 2 /b2 = 1 [central equation of ellipse] (2.85)

where the axes of the ellipse are a = cosh(µ0 ) and b = sinh(µ0 ). Cancelling the hyperbolic
functions reduces (2.85) to the identity cos2 (·) + sin2 (·) = 1. Q. E. D.
It is unusual to worry about imaginary values of z in applications, but since complex
singularities will limit the convergence of the series, we need to understand that a singu-
larity at one point on an ellipse will produce the same (asymptotic!) rate of convergence
as a pole or branch point on any other part of the same ellipse. This has two important
implications.
First, Fig. 2.16 shows that when µ is small, the ellipses of constant µ are long and narrow,
pass very close to z = ±1 and then cross the imaginary axis at much larger distances.
2.11. CONVERGENCE THEORY: CHEBYSHEV POLYNOMIALS 49


·=3 π/2




·=2 π
·=π
·=0




·=π/2

Figure 2.16: Elliptical coordinates (µ, ·) in the complex z-plane; z = x + i y via
x = cosh(µ) cos(·) & y = ’ sinh(µ) sin(·). which implies Tn (x + i y) = cos( n [· + i µ]) =
cosh(n µ) cos(n ·) ’ i sinh(n µ) sin(n ·). The surfaces of constant µ are ellipses; the
contours of constant “angle” · are hyperbolas. If a function f (z) has a pole or other singu-
larity anywhere on the ellipse µ = µ0 and no singularities on ellipses of smaller µ, then
the Chebyshev series of f (z) diverges everywhere outside the ellipse µ = µ0 and converges
everywhere inside this ellipse.


This implies that singularities very close to z = ±1 have no worse effect on convergence
than singularities on the imaginary axis that are much farther from the interval [-1, 1].
Chebyshev polynomials have a kind of inherent coordinate-stretching that makes them
much better at resolving singularities or boundary layers near the endpoints of [-1, 1] than
near the middle.
Second, Fig. 2.16 shows that singularities for real z will not destroy the property of
exponential convergence for the Chebyshev series as long as they lie outside the interval
[-1, 1]. Conversely, convergence on the “canonical interval”, even geometric convergence,
does not imply convergence for all real z, but no further than | z0 | where z0 is the location
of the nearest real singularity, and maybe not even that far if there are also poles or branch
points of f (z) for complex z.
If we know (or can estimate) the location of the convergence-limiting singularity, then
the following is very useful.

Theorem 8 ( CHEBYSHEV RATE of CONVERGENCE) The asymptotic rate of convergence
of a Chebyshev series for z ∈ [’1, 1] is equal to µ, the quasi-radial coordinate of the ellipse of
convergence. This is related to the location of the convergence-limiting singularity at (x0 , y0 ) in the
complex plane via

(2.86)
µ = Im{arccos[x0 + iy0 ]}
= log | z0 ± (z0 ’ 1)1/2 |
2
(2.87)
±2 ’ 1 (2.88)
= log ± +
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
50

where the sign in the second line is chosen to make the argument of the logarithm > 1 so that µ > 0
and where
1 1
±≡ (x0 ’ 1)2 + y0
2 2
(x0 + 1)2 + y0 + (2.89)
2 2

2.12 An Upper Bound on the Truncation Error: Last Coef¬-
cient Rule-of-Thumb


Theorem 9 (FOURIER TRUNCATION ERROR BOUND) Let
∞ ∞
(2.90)
f (x) = a0 + an cos(nx) + bn sin(nx)
n=1 n=1

and let fN (x) be the approximation to f (x) which is obtained by truncating each of the series in
(2.90) after N terms:
N N
fN (x) ≡ a0 + (2.91)
an cos(nx) + bn sin(nx)
n=1 n=1

Then the truncation error de¬ned by

ET (N ) ≡| f (x) ’ fN (x) |, (2.92)
[“truncation error ]

is bounded from above by the sum of the absolute values of all the neglected coef¬cients:

EN (N ) ¤ | an | + | bn | (2.93)
n=N +1

PROOF: Similar to the analogous Chebyshev result, Theorem 6.
Other basis functions satisfy similar theorems with slightly different numerical factors;
for Hermite functions, for example, we multiply the R. H. S. of (2.93) by 0.785.
This theorem is very powerful because it tells us that the coef¬cients of the spectral
series are also (roughly) the errors, or at least an upper bound on the errors. It is also seem-
ingly quite useless because we normally do not know what all the neglected coef¬cients
are, but let us look at a representative case.
EXAMPLE: For the “Symmetric, Imbricated-Lorentzian” function of the previous sec-
tion, the expansion is

pn cos(nx) (2.94)
f (x) = 1 + 2
n=1

The Truncation Error Bound Theorem then implies

| f (x) ’ fN (x) | ¤ 2 pn = 2pN +1 /(1 ’ p) (2.95)
n=N +1

since the geometric series can be explicitly summed. Because the terms of (2.94) are all
positive at x = 0, Eq. (2.95) is a tight upper bound.
2.13. CONVERGENCE THEORY FOR LEGENDRE POLYNOMIALS 51

When computing the hitherto-unknown solution of a differential equation, we do not
know the exact form of the neglected coef¬cients. However, we have already seen that
almost all Fourier and Chebyshev series for smooth, in¬nitely differentiable functions con-
verge asymptotically like geometric series. In other words, it is the rule rather than the
exception that

a n ∼ [ ] pn , (2.96)
n >> 1

where [ ] is a slowly varying (algebraic) function of n or a constant. This implies that while
we cannot get a numerical bound on the truncation error for unknown functions, we can
predict that they will behave qualitatively like the geometrically-converging Fourier series
(2.95).
The pay-off is the following assertion:

Rule-of-Thumb 2 (LAST COEFFICIENT ERROR ESTIMATE) The truncation error is the
same order-of-magnitude as the last COEFFICIENT RETAINED in the truncation for series with
geometric convergence. Since the truncation error is a quantity we can only estimate anyway (in
the absence of a known, exact solution), we can loosely speak of the last retained coef¬cient as being
the truncation error, that is:

ET (N ) ∼ O(| aN |) (2.97)

Extension: if the series has algebraic convergence index k, i. e., if an ∼ O(1/nk ) for large n,
then


ET (N ) ∼ O(N | aN | ) (2.98)

JUSTIFICATION: If we accept that a large class of Fourier and Chebyshev series con-
verge geometrically, then (2.97) follows immediately from (2.95). Note that the last re-
tained coef¬cient is an = 2 pN , so that (2.97) is true with the proportionality constant
p/(1 ’ p) ∼ O(1).
For algebraically converging series, note that

1 1
∼ (2.99)
, N >> 1
(k ’ 1)N k’1
k
n
n=N +1

(Bender and Orszag, 1978, pg. 379.) Thus, the bound in the error truncation theorem is
O(1/N k’1 ) while the last retained coef¬cient is O(1/N k ), and this implies (2.98).
The ultimate test of a numerical solution is to repeat the calculation with different N
and compare results. The rule-of-thumb is not intended to substitute for that. Rather, it
has two uses. First, it provides a quick-and-dirty way of estimating the error from a single
calculation; if the last retained coef¬cient is not small in comparison to the desired error,
then we need larger N . If it is small, and the lower coef¬cients decrease smoothly towards
an , the calculation is probably okay. Second, it provides order-of-magnitude guidelines for
estimating the feasibility of a calculation. Without such guidelines, one would waste lots
of time by attempting problems which far exceed the available computing power.


2.13 Convergence Theory for Legendre Polynomials
When the computational domain is split into a large number of subdomains with a separate
spectral series on each subdomain, a popular strategy is to mimic the ¬nite element method
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
52

0 1
10 10
Ratio
-2
Legendre
10

-4
10

-6
10

-8
Chebyshev
10

-10 0
10 10
0 1 2
0 50
10 10 10

<<

. 13
( 136 .)



>>