<<

. 117
( 136 .)



>>

one ¬nds

uy (y) ≈ ’x uxx (0)/x + O(x2 ) |x| (G.7)
1

which, after cancelling the common power of x, implies that the correct boundary condi-
tion is

uy (1) = ’uxx (0) (G.8)

Thus, THE CORRECT WAY TO IMPOSE THE BOUNDARY CONDITION ON THE FIRST
DERIVATIVE WITH RESPECT TO y IS TO IMPOSE IT ON THE SECOND DERIVATIVE
WITH RESPECT TO x, i. e.

uxx (0) = ’± = ’uy (1) (G.9)

Similarly, for the second derivative, note

1 cos(x)
uxx ’ (G.10)
uyy = ux
sin2 (x) sin3 (x)

Via Taylor expansions,

x2 x3
1 1 1
uyy ≈ uxxxx (0) ’
+ uxx (0) + + O(x) x uxx (0) + uxxxx (0)
x2 x3
3 2 6
(G.11)


1
uyy (1) ≡ {uxx (0) + uxxxx (0)} (G.12)
3
which means that on the transformed problem in x, we should impose the boundary con-
dition that

(G.13)
uxxxx (x = 0) = 3β + ± = 3 uyy (y = 1) + uy (y = 1)
Glossary

“Like Adam, naming the birds and the ¬‚owers”
” J. J. Sylvester [of his invention of many mathematical terms]



ALGEBRAIC CONVERGENCE: If the ALGEBRAIC INDEX OF CONVERGENCE for a
series is ¬nite, then the series has “algebraic convergence”. If an ∼ 1/nk , n ’ ∞ for
some ¬nite k, then the series has “algebraic convergence”.

ALGEBRAIC INDEX OF CONVERGENCE k: This index k is the largest number for which

lim |an | nk < ∞
n’∞

where the an are the series coef¬cients. The usual proof that a given function has
algebraic index of convergence k is to apply k integrations-by-parts to the coef¬cient
integrals. If this process of integration-by-parts can be repeated inde¬nitely so that
the equation is true for arbitrarily large k, then the convergence is “in¬nite order” or
“exponential”. If the coef¬cients an ∼ 1/nk , n ’ ∞, then k is the “algebraic index of
convergence”.

ANTISYMMETRIC: If a function is such that f (x) = ’f (x) for all x, it is said to be “AN-
TISYMMETRIC with respect to the origin” or to be of “odd PARITY”.

ARITHMURGY: Synonym for “number-crunching”. (From the Greek ±ρθµoσ, “number”,
and “ ργoσ, “working”.)

ASSUMPTION OF EQUAL ERRORS: This empirical principle, which cannot be rigor-
ously proved but is supported by strong heuristic arguments and by practical expe-
rience, states the “discretization error” and the “truncation error” are of the same
order-of-magnitude. Whenever it is true, one can estimate the total error in a spectral
calculation merely by estimating the truncation error, which is usually much easier
to estimate than the discretization error. (Chap. 2.)

ASYMPTOTIC RATE OF GEOMETRIC CONVERGENCE: If a series has GEOMETRIC
CONVERGENCE, that is, if

|an | < exp(’nµ) all n,

then the “asymptotic rate of geometric convergence” is the largest µ for which the
above bound is true. The asymptotic rate of convergence is unde¬ned for series with
algebraic or subgeometric convergence.

577
Glossary
578

BANDED (MATRIX): A label applied to a matrix whose elements Aij are all zero except
for diagonal bands around the main diagonal, that is, Aij = 0 if |i ’ j| > m for some
m. (Appendix B.)

BANDWIDTH (of a MATRIX): If the elements Aij = 0 unless |i ’ j| ¤ m, then (2m + 1)
is the BANDWIDTH of the BANDED MATRIX.

BASIS FUNCTIONS: The members of a BASIS SET. Examples of basis functions are the
Chebyshev polynomials and the Hermite functions (and in general all the classes of
functions described in Appendix A).

BASIS RECOMBINATION: A strategy for satisfying numerical boundary conditions in
which the original basis set, such as Chebyshev polynomials, is replaced by a new
basis composed of linear combinations of the original basis functions such that each
member of the new basis individually satis¬es the boundary conditions. The alterna-
tive strategy is BOUNDARY BORDERING. (Chap. 6, Sec. 4.)

BASIS SET: The collection of functions which are used to approximate the solution of a
differential equation. The Fourier functions {1, cos(nx), sin(nx) for n = 1, 2, . . . }
and the Chebyshev polynomials {Tn (x), n = 0, 1, . . . } are two examples of basis
sets.

BEHAVIORAL BOUNDARY CONDITION: A boundary condition that imposes a cer-
tain behavior on the solution rather specifying a numerical constraint. Examples of
behavioral boundary conditions include: (i) periodicity with a certain period L (ii)
boundedness and in¬nite differentiability at a point where the coef¬cients of the dif-
ferential equation are singular. It is usually possible to satisfy such conditions by
proper choice of basis function. For example, the sines and cosines of a Fourier series
are periodic, so no further action is needed to enforce periodicity on the solution.

BIFURCATION POINT: A point where two branches of a solution u(±) cross. Synonym
is “crossing point”. For both ± > ± limit and ± < ± limit , two different solutions exist
which meet at the bifurcation point. Newton™s method fails at a bifurcation point,
but it is possible to “shoot the bifurcation point” or switch branches as explained in
Appendix D. (When “bifurcation” is used in a broader sense, a “crossing point” is
also called a “trans-critical bifurcation”. )

BLOCKING, SPECTRAL: See SPECTRAL BLOCKING.

BOUNDARY BORDERING : A strategy for satisfying boundary conditions in which
these are imposed as explicit constraints in the matrix problem which is solved for
the spectral coef¬cients. Some of the collocation or Galerkin conditions on the resid-
ual are replaced by a “border” of rows which impose the constraints. The major
alternative is BASIS RECOMBINATION. (Chap. 6.)

CHOLESKY FACTORIZATION: Factorization of a SYMMETRIC matrix into the product
LLT where L is lower triangular and LT is its transpose; Cholesky factorization re-
quires only half as many operations as the usual LU factorization. (Appendix B.)

COLLOCATION: Adjective for labelling methods which determine the series coef¬cients
by demanding that the residual function be zero on a grid of points. In this book, a
synonym for PSEUDOSPECTRAL and for METHOD OF SELECTED POINTS. Else-
where in the literature, this adjective is also applied to certain ¬nite element methods.
Glossary 579

COLLOCATION POINTS: the grid of points where the residual function must vanish.
Synonym for INTERPOLATION POINTS.

COMPATIBILITY CONDITIONS: A countably in¬nite set of constraints on the initial
conditions of a time-dependent partial differential equation which are necessary for
the solution to be analytic everywhere in the space-time domain. Example: an incom-
pressible ¬‚ow will be strongly singular at t = 0 if the initial condition is divergent
at some point in the ¬‚uid, and will have discontinuities (vortex sheets) at rigid walls
if the initial velocity does not satisfy the no-slip boundary condition of vanishing at
the walls. If the initial ¬‚ow does not satisfy additional constraints, the ¬‚ow will be
singular, but more weakly in the sense of having more derivatives than if the nondi-
vergence and no-slip constraints are violated. The constraints are different from each
partial differential equation.

COMPLETENESS: A basis set is “complete” for a given class of functions if all functions
within the class can be represented to arbitrarily high accuracy as a sum of a suf¬-
ciently large number of basis functions.

CROUT REDUCTION: Solution of a matrix equation by direct LU FACTORIZATION.

DARBOUX™S PRINCIPLE: Theorem that for a function f (x), the asymptotic form of the
spectral coef¬cients an as n ’ ∞ are controlled by the singularities (poles, branch
points, etc.) of f (x). (Theorem 1.)

DENSE MATRIX: A matrix whose elements are mostly nonzero so that the zero elements
do not offer any structure which can be exploited to reduce the cost of LU factoriza-
tion. A synonym for FULL MATRIX; the opposite of a SPARSE MATRIX.

DIFFERENTIAL QUADRATURE/DIFFERENTIAL CUBATURE: Almost a synonym for
“PSEUDOSPECTRAL”. The DQ method, like the pseudospectral, uses difference for-
mulas, based on either trigonometric or polynomial interpolation, in which every
point on the grid (or every point on a coordinate line in multiple dimensions) con-
tributes to the approximation at every point on the grid (or coordinate line). The
difference from the pseudospectral method is that the distribution of points is com-
pletely arbitrary in theory. (In practice, the roots of Chebyshev polynomials are com-
monly used, making DQ identical with Chebyshev pseudospectral.) Differential Cu-
bature is a multi-dimensional scheme which does not use a tensor product basis, but
instead approximates derivatives using the grid point values at every point of the
two-dimensional or three-dimensional grid. (This is expensive!).

DIRECT MATRIX METHOD: A non-iterative algorithm for solving a matrix equation, as
in the phrase “fast direct methods”. Examples include Gaussian elimination, Crout
reduction, Cholesky factorization, LU factorization, skyline solver, and static conden-
sation (Appendix B).

DISCRETE ORDINATES METHOD: Synonym for “PSEUDOSPECTRAL” or “COLLO-
CATION” method. (This term is most common among physicists and chemists.)

DISCRETIZATION ERROR: This is the difference between the ¬rst (N +1) coef¬cients of
the exact solution and the corresponding coef¬cients as computed using a spectral or
pseudospectral algorithm with (N + 1) basis functions. It is distinct from (but usually
the same order-of-magnitude as) the “truncation error”. (Def. 9.)
Glossary
580

DOMAIN TRUNCATION: A method of solving problems on unbounded domains by re-
placing the interval y ∈ [’∞, ∞] by y ∈ [’L, L]. If |u(±L)| decays exponentially
with L, then it is possible to obtain solutions of arbitrary accuracy by choosing L
suf¬ciently large. (Chap. 17.)
ENVELOPE OF THE COEFFICIENTS: A smooth, monotonically decreasing curve which
is a tight bound on oscillatory Chebyshev or Fourier coef¬cients {an } in the sense that
the absolute value of the coef¬cients is arbitrarily close to the envelope in¬nitely often
as n ’ ∞. (Borrowed from wave theory, where the “envelope of a wave packet” has
the identical meaning.)
ENVELOPE OF THE INTERPOLATION ERROR: The envelope ρ is de¬ned by

EI (x; N )
ρ≡
¦N (x)

where EI (x; N ) is the interpolation error and ¦N (x) is the function whose roots are
the interpolation grid. (Boyd, 1990c.)
EQUAL ERRORS, ASSUMPTION OF: This empirical principle, unprovable but supported
by strong heuristic arguments and practical experience, states that the “DISCRETIZA-
TION ERROR” and “TRUNCATION ERROR” and “INTERPOLATION ERROR” are
the same order of magnitude. (Chap. 2.)
ESSENTIAL BOUNDARY CONDITION: A boundary condition is “essential” if it must
be explicitly imposed on the approximation to the solution of a differential equa-
tion; usually, essential boundary conditions are NUMERICAL BOUNDARY CONDI-
TIONS, that is, require the solution u or its derivative to equal a certain number or
function on the boundary.
EXPLICIT (TIME-MARCHING): A time-integration scheme in which the solution at the
next time level is given by an explicit formula that does NOT require solving a bound-
ary value problem. (See also IMPLICITLY-IMPLICIT.) (Chap. 9.)
EXPONENTIAL CONVERGENCE: A spectral series possesses the property of “exponen-
tial convergence” if the error decreases faster than any ¬nite inverse power of N as
N , the number of terms in the truncated series, increases. Typically, the series coef¬-
cients decrease as O(exp[’pnr ]) for some positive constants p and r. A synonym for
“in¬nite order convergence”.
EXPONENTIAL INDEX OF CONVERGENCE: If the series coef¬cients an satisfy

an ∼ O[s exp(’q nr )], n’∞

where s, q, and r are constants, then r is the “exponential convergence index”. Alter-
native de¬nitions are given in Chap. 2 as Def. 4.
FFT: Abbreviation for FAST FOURIER TRANSFORM. (Chap. 10.)
FINITE ELEMENT METHOD: A class of algorithms in which the domain is divided into
subdomains and the solution is approximated by a different polynomial on each sub-
domain. At high order, these piecewise approximations must be constructed by the
same strategies as for global spectral methods, and are therefore called SPECTRAL
ELEMENTS or “h-p” ¬nite elements.
FOLD POINT: Synonym for LIMIT POINT.
Glossary 581

GEOMETRIC CONVERGENCE: A series whose coef¬cients are decreasing
an ∼ ±(n)pn ” ±(n) exp[’n | log(p)|]) n’∞ |p| < 1
has the property of “geometric convergence” where ±(n) denotes a function that
varies algebraically, rather than exponentially, with n such as a power of n. The
reason for the name is that the terms of a geometrically convergent series can always
be bounded by those of a geometric series, that is, by the terms of the power series
expansion of ±/(β + x) for some ± and β where these are constants. (All convergent
power series have geometric convergence. All Chebyshev series for functions which
have no singularities on x ∈ [’1, 1] (including the endpoints) also have geometric
convergence).
GIBBS OSCILLATIONS: When a function with a discontinuity or a discontinuity in a
derivative of some order is approximated by a spectral series truncated at N terms,
the sum of the truncated series oscillates with a wavelength which is O(1/N ). These
oscillations are also called “SPECTRAL RINGING”.
GIBBS PHENOMENON: When a function with a discontinuity is approximated by a
spectral series truncated at N terms, the sum of the truncated series overshoots the
true value of the function at the edge of the discontinuity by a ¬xed amount (ap-
proximately 0.089 times the height of the jump), independent of N . GIBBS PHE-
NOMENON also includes GIBBS OSCILLATIONS.
GLOBAL ELEMENT: (Now rare.) Sometimes a synonym for SPECTRAL ELEMENTS,

<<

. 117
( 136 .)



>>