<<

. 14
( 136 .)



>>

Figure 2.17: Left: absolute values of the coef¬cients of f (x; p) = 1/(1 ’ 2 p x + p2 )1/2 .
Legendre coef¬cients: upper curve. Chebyshev coef¬cients: bottom curve. Right: the
solid curve is the ratio of the absolute value of the n-th Legendre coef¬cient to the n-th
Chebyshev coef¬cient. The dashed line is the n1/2 .


with a so-called “weak” formulation. One crucial point is that the weak formulation is
greatly simpli¬ed by using a basis of Legendre polynomials instead of Chebyshev.
The good news is that the convergence theory for Legendre polynomials is virtually
identical with that of Chebyshev polynomials ” indeed, it is identical if one ignores alge-
braic factors of n, as done so often above. The bad news is that for a given arbitrary function
f (x), the maximum pointwise error of a Legendre series (or interpolant), truncated after N
terms, is worse than that of the corresponding Chebyshev series by a factor of the square
root of N .

Theorem 10 ( LEGENDRE POLYNOMIAL RATE of CONVERGENCE)
• The domain of convergence for Legendre series is the interior of the largest ellipse, with foci
at ±1, which is free of singularities of the function being expanded. This domain is identical
with the domain of convergence of the Chebyshev series for the same function.
• The asymptotic rate of convergence µ of a Legendre series is identical with that of the corre-
sponding Chebyshev series, that is, it is the elliptical coordinate of the boundary of the domain
of convergence in the complex plane.
• In the asymptotic limit N ’ ∞, the maximum pointwise error of a Legendre series is larger
than that of the Chebyshev series of the same order, also truncated after N terms, by O(N 1/2 ).

PROOF: The ¬rst part is proved in Davis (1975). The convergence domain implicitly
speci¬es the asymptotic rate of convergence. Fox and Parker (1968, pg. 17) prove an
asymptotic relation that suggests Legendre series are worse than Chebyshev by a factor
of 2/(π N ).
An example is instructive. The function

1
pn Pn (x) (2.100)
=
1 ’ 2 p x + p2 n=0
2.13. CONVERGENCE THEORY FOR LEGENDRE POLYNOMIALS 53



1



0.5



0



-0.5
-1 -0.5 0 0.5 1

Figure 2.18: Graph of P100 (x), the Legendre polynomial of degree one hundred. It is also a
schematic illustrating the form of all Legendre polynomials: Oscillations over most of the
interval whose amplitude at a ¬xed x is O(1/n1/2 ) plus narrow boundary layers near the
endpoints where the polynomial rises to ± 1.


has reciprocal-of-square root branch points in the complex plane which limit convergence.
The coef¬cients of the Chebyshev series for this function are not known in closed form, but
it is known that they are asymptotically of the form
pn
∼ constant √ , n’∞
a(Chebyshev) (2.101)
n
n
Fig 2.17 compares the Chebyshev and Legendre coef¬cients for this function. The left panel
shows that both sets asymptote to parallel straight lines, but the Chebyshev coef¬cients are
smaller. (Since Pn (1) = 1 and |Pn (x)| ¤ 1 for all n, just as for the Chebyshev polynomials,
these differences in coef¬cients translate directly into differences in errors between the two
basis sets.) The right panel shows that the ratio of the coef¬cients rapidly asymptotes to
(π/2)N .
Another way of stating the same thing is to inspect the Legendre polynomials them-
selves (Fig. 2.18). In contrast to the Chebyshev polynomials, which oscillate uniformly over
the interval x ∈ [’1, 1] (as obvious from the relation Tn (cos(θ)) ≡ cos(n θ)), the Legendre
polynomials are nonuniform with small amplitude over most of the interval except in ex-
tremely narrow boundary layers where the polynomial rises to one or falls to minus one.
The even polynomials have local maxima at both x = 1 and x = 0; the ratio of these is

2
ρn ≡ |Pn (0)/Pn (1)| ∼ n’ ∞
n even, (2.102)
,
πn
There are two reasons why this nonuniformity and the poorer error of Legendre poly-
nomials are not particularly upsetting to practitioners of spectral elements. First, the de-
gree of the polynomials on each element is rather small, rarely greater than N = 8. Sec-
ond, Fig. 2.18 shows that the boundary layers where the Legendre polynomial is large are
very thin. For arbitrary functions, this is still an embarrassment. However, the solutions
to boundary value problems are constrained by the boundary conditions. For spectral ele-
ments, some constraint exists even on interior subdomain walls because the expansions in
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
54

each adjoining element must have common values on the common walls. Thus, spectral
element expansions in Legendre polynomials are constrained by matching and boundary
conditions to be close to the exact solution in precisely those regions where the errors in a
Legendre series would otherwise be large.
The Chebyshev-Legendre theory also applies to the larger family of Gegenbauer poly-
nomials. All members of the Gegenbauer family converge in the same ellipse-bounded
domain at the same asymptotic rate of convergence. However, for Gegenbauer polynomi-
als Cn (x), which are orthogonal with respect to the weight factor w(x) = (1’x2 )m’1/2 , the
m

maximum pointwise errors are worse than Chebyshev by a factor of O(nm ) for suf¬ciently
large m. Legendre polynomials are the special case m = 1/2.


2.14 Quasi-Sinusoidal Rule of Thumb
It is easy to determine the cost of an accurate computation after the fact. (One can repeat
with different N to be sure the calculation is accurate.) In planning a computation, how-
ever, it is important to estimate in advance the approximate cost because this may determine
whether the computation is feasible.


Rule-of-Thumb 3 (TELLER™S LAW) A state-of-the-art calculation requires 100 hours of CPU
time on the state-of-the-art computer, independent of the decade.

The point of this maxim is that people push the current technology to the limit. This
will be as true in 2100 as it was in the time of Charles Babbage. However, there have always
been bureaucrats to put some limits on the enthusiasts (for which moderate users should
be grateful). Because of these constraints, one can get in enormous trouble if a proposed 20
hour calculation in fact requires 200.
There are several strategies for estimating costs a priori. One is library research: looking
up the costs and resolution of previously published calculations for similar problems.
A second strategy is the “Method of Model Functions”. One chooses a simple analytic
function which has the same behavior as is expected of the unknown solution ” boundary
layers, fronts, oscillations, whatever. One can then expand this as a series of basis functions
by performing a matrix multiplication or FFT. If the model has the same scales of variation
as the true solution, then one can obtain a good estimate of how many basis functions will
be needed. The rate at which the model™s {an } decrease will be roughly the same as that of
the coef¬cients of the unknown solution even though the individual numerical values will
be different.
A third strategy is to use rules-of-thumb.
The “quasi-sinusoidal” rule-of-thumb is based on the observation that a wide variety
of phenomena have oscillations. If we can estimate or guess the approximate wavelength
” strictly speaking, we should say local wavelength since the scale of oscillation may vary
from place to place ” then we ought to be able to estimate how many Chebyshev polyno-
mials are needed to resolve it. Gottlieb and Orszag™s method of estimation is quite simple:
solve the partial differential equation

x ∈ [’1, 1] (2.103)
u t + ux = 0

with initial and boundary conditions such that the exact solution is a steadily translating
sine wave, and then compare different numerical methods.
Table 2.1 shows the results. The solution is

u(x, t) = sin[M π(x ’ t ’ 1)] (2.104)
2.14. QUASI-SINUSOIDAL RULE OF THUMB 55


Table 2.1: RMS (L2 ) errors in the solution of the one-dimensional wave equation. The exact
solution is u(x) = sin(M π[x ’ t ’ 1]). There are a total of M wavelengths on the inter-
val [’1, 1]. N is the total number of grid points or Chebyshev polynomials. To achieve a
1% error, the second order method requires N/M > 40, the second order method needs
N/M > 15, while the spectral method needs N/M > 3.5. The Chebyshev-tau algorithm
was used here, but another graph in Gottlieb & Orszag (1977) shows that error is approx-
imately the same for Galerkin™s method and the pseudospectral method. The striking dif-
ferences are between the spectral methods and the ¬nite difference methods, not between
different variants within the family of spectral algorithms.


SECOND ORDER FOURTH ORDER CHEBYSHEV
N M ERROR N M ERROR N M ERROR
40 2 0.1 20 2 0.04 16 4 0.08
80 2 0.03 30 2 0.008 20 4 0.001
160 2 0.008 40 2 0.002 28 8 0.2
40 4 1. 40 4 0.07 32 8 0.008
80 4 0.2 80 4 0.005 42 12 0.2
160 4 0.06 160 4 0.0003 46 12 0.02




so that M = total number of wavelengths on the interval [’1, 1]. For all the numerical
methods, N is the total number of degrees of freedom.
As might be expected, the accuracy does not depend on either N or M alone, but only
on their ratio
number of grid points
N
≡ (2.105)
wavelengths
M
We ¬nd
Rule-of-Thumb 4 (QUASI-SINUSOIDAL RESOLUTION REQUIREMENT)
To achieve 5% accuracy for a wave-like solution, one needs roughly


SECOND ORDER [40 pts/wave
20 grid pts./wavelength
FINITE DIFFERENCE for 1 % error]

FOURTH ORDER [15 pts/wave
10 grid pts./wavelength
FINITE DIFFERENCE for 1 % error]

CHEBYSHEV [3.5 polys./wave
3.5 polys./wavelength
PSEUDOSPECTRAL for 1 % error]


To estimate the number of wavelengths M , let x be the smallest scale that one must resolve on
x ∈ [’1, 1]. Then
π
M≈
x
CHAPTER 2. CHEBYSHEV & FOURIER SERIES
56

0
10
-2
M=1
10
-4
10 M=5




M=20
-6
10




M=100
-8
10
-10
π
10
0 2 4 6 8 10
N/M

Figure 2.19: The errors in the approximation of f (x) ≡ 2’1/2 (cos(M πx) + sin(M πx)),
graphed versus N/M , that is, the number of Chebyshev polynomials retained in the trun-
cation divided by M , the number of wavelengths of f (x) on x ∈ [’1, 1]. The dashed vertical
line is the asymptotic limit M ’ ∞, which is at N/M = π.


This is but a rule-of-thumb ” an unkind wit might de¬ne “rule-of-thumb” as a syn-
onym for “educated guess” ” but it is representative of the extraordinary ef¬ciency of
pseudospectral methods versus ¬nite difference methods for large N . The rule-of-thumb
lists the needed resolution for 1% error to emphasize that the advantage of pseudospectral
over ¬nite difference methods increases very rapidly as the error decreases, even for rather
moderate accuracy.
Fig. 2.19 shows the errors in the Chebyshev expansion of sin(M π x). There is almost no
accuracy at all until N/M > π, and then the error just falls off the table.
One must be a little careful in applying the rule when M and N are small. The reason is
that when we increase N by 1 or 2, we typically decrease the error (for a sine function) by
an order-of-magnitude whether N is 10 or 10,000. This increase of N (for the sake of more
accuracy) has a negligible effect on the ratio N/M when M is huge, but N/M must be
signi¬cantly greater than 3 to obtain high accuracy when M is small. A more conservative
rule-of-thumb is to use

N = 6 + 4(M ’ 1) (2.106)

coef¬cients, allocating 6 polynomials to resolve the ¬rst wavelength and 4 for each addi-
tional wavelength.


2.15 Witch of Agnesi Rule“of“Thumb
Another caution is that sin(M πx) is an entire function, free of singularities, whereas most
real-life solutions have poles or branch-points which determine the asymptotic rate of con-
vergence. For this reason, we will derive a second rule-of-thumb, which we call poeti-

<<

. 14
( 136 .)



>>