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,