<<

. 2
( 136 .)



>>

Sponge Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
17.3 Whittaker Cardinal or “Sinc” Functions . . . . . . . . . . . . . . . . . . . . . 341
17.4 Hermite functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
17.5 Semi-In¬nite Interval: Laguerre Functions . . . . . . . . . . . . . . . . . . . . 353
17.6 New Basis Sets via Change of Coordinate . . . . . . . . . . . . . . . . . . . . 355
17.7 Rational Chebyshev Functions: T Bn . . . . . . . . . . . . . . . . . . . . . . . 356
17.8 Behavioral versus Numerical Boundary Conditions . . . . . . . . . . . . . . 361
17.9 Strategy for Slowly Decaying Functions . . . . . . . . . . . . . . . . . . . . . 363
17.10Numerical Examples: Rational Chebyshev Functions . . . . . . . . . . . . . 366
17.11 Semi-In¬nite Interval: Rational Chebyshev T Ln . . . . . . . . . . . . . . . . 369
17.12Numerical Examples: Chebyshev for Semi-In¬nite Interval . . . . . . . . . . 370
17.13Strategy: Oscillatory, Non-Decaying Functions . . . . . . . . . . . . . . . . . 372
17.14Weideman-Cloot Sinh Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . 374
17.15Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

18 Spherical & Cylindrical Geometry 380
18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
18.2 Polar, Cylindrical, Toroidal, Spherical . . . . . . . . . . . . . . . . . . . . . . 381
18.3 Apparent Singularity at the Pole . . . . . . . . . . . . . . . . . . . . . . . . . 382
18.4 Polar Coordinates: Parity Theorem . . . . . . . . . . . . . . . . . . . . . . . . 383
18.5 Radial Basis Sets and Radial Grids . . . . . . . . . . . . . . . . . . . . . . . . 385
18.5.1 One-Sided Jacobi Basis for the Radial Coordinate . . . . . . . . . . . 387
18.5.2 Boundary Value & Eigenvalue Problems on a Disk . . . . . . . . . . . 389
18.5.3 Unbounded Domains Including the Origin in Cylindrical Coordinates 390
18.6 Annular Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
18.7 Spherical Coordinates: An Overview . . . . . . . . . . . . . . . . . . . . . . . 391
18.8 The Parity Factor for Scalars: Sphere versus Torus . . . . . . . . . . . . . . . 391
18.9 Parity II: Horizontal Velocities & Other Vector Components . . . . . . . . . . 395
18.10The Pole Problem: Spherical Coordinates . . . . . . . . . . . . . . . . . . . . 398
18.11 Spherical Harmonics: Introduction . . . . . . . . . . . . . . . . . . . . . . . . 399
18.12Legendre Transforms and Other Sorrows . . . . . . . . . . . . . . . . . . . . 402
18.12.1 FFT in Longitude/MMT in Latitude . . . . . . . . . . . . . . . . . . . 402
18.12.2 Substitutes and Accelerators for the MMT . . . . . . . . . . . . . . . . 403
18.12.3 Parity and Legendre Transforms . . . . . . . . . . . . . . . . . . . . . 404
CONTENTS vii

18.12.4 Hurrah for Matrix/Vector Multiplication . . . . . . . . . . . . . . . . 404
18.12.5 Reduced Grid and Other Tricks . . . . . . . . . . . . . . . . . . . . . . 405
18.12.6 Schuster-Dilts Triangular Matrix Acceleration . . . . . . . . . . . . . 405
18.12.7 Generalized FFT: Multipoles and All That . . . . . . . . . . . . . . . . 407
18.12.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
18.13Equiareal Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
18.14Spherical Harmonics: Limited-Area Models . . . . . . . . . . . . . . . . . . . 409
18.15Spherical Harmonics and Physics . . . . . . . . . . . . . . . . . . . . . . . . . 410
18.16Asymptotic Approximations, I . . . . . . . . . . . . . . . . . . . . . . . . . . 410
18.17Asymptotic Approximations, II . . . . . . . . . . . . . . . . . . . . . . . . . . 412
18.18Software: Spherical Harmonics . . . . . . . . . . . . . . . . . . . . . . . . . . 414
18.19Semi-Implicit: Shallow Water . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
18.20Fronts and Topography: Smoothing/Filters . . . . . . . . . . . . . . . . . . . 418
18.20.1 Fronts and Topography . . . . . . . . . . . . . . . . . . . . . . . . . . 418
18.20.2 Mechanics of Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
18.20.3 Spherical splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
18.20.4 Filter Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
18.20.5 Filtering with Spatially-Variable Order . . . . . . . . . . . . . . . . . 423
18.20.6 Topographic Filtering in Meteorology . . . . . . . . . . . . . . . . . . 423
18.21Resolution of Spectral Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
18.22Vector Harmonics & Hough Functions . . . . . . . . . . . . . . . . . . . . . . 428
18.23Radial/Vertical Coordinate: Spectral or Non-Spectral? . . . . . . . . . . . . . 429
18.23.1 Basis for Axial Coordinate in Cylindrical Coordinates . . . . . . . . . 429
18.23.2 Axial Basis in Toroidal Coordinates . . . . . . . . . . . . . . . . . . . 429
18.23.3 Vertical/Radial Basis in Spherical Coordinates . . . . . . . . . . . . . 429
18.24Stellar Convection in a Spherical Annulus: Glatzmaier (1984) . . . . . . . . . 430
18.25Non-Tensor Grids: Icosahedral, etc. . . . . . . . . . . . . . . . . . . . . . . . . 431
18.26Robert Basis for the Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
18.27Parity-Modi¬ed Latitudinal Fourier Series . . . . . . . . . . . . . . . . . . . . 434
18.28Projective Filtering for Latitudinal Fourier Series . . . . . . . . . . . . . . . . 435
18.29Spectral Elements on the Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . 437
18.30Spherical Harmonics Besieged . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
18.31Elliptic and Elliptic Cylinder Coordinates . . . . . . . . . . . . . . . . . . . . 439
18.32Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

19 Special Tricks 442
19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
19.2 Sideband Truncation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
19.3 Special Basis Functions, I: Corner Singularities . . . . . . . . . . . . . . . . . 446
19.4 Special Basis Functions, II: Wave Scattering . . . . . . . . . . . . . . . . . . . 448
19.5 Weakly Nonlocal Solitary Waves . . . . . . . . . . . . . . . . . . . . . . . . . 450
19.6 Root-Finding by Chebyshev Polynomials . . . . . . . . . . . . . . . . . . . . 450
19.7 Hilbert Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
19.8 Spectrally-Accurate Quadrature Methods . . . . . . . . . . . . . . . . . . . . 454
19.8.1 Introduction: Gaussian and Clenshaw-Curtis Quadrature . . . . . . 454
19.8.2 Clenshaw-Curtis Adaptivity . . . . . . . . . . . . . . . . . . . . . . . 455
19.8.3 Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
19.8.4 Integration of Periodic Functions and the Trapezoidal Rule . . . . . . 457
19.8.5 In¬nite Intervals and the Trapezoidal Rule . . . . . . . . . . . . . . . 458
19.8.6 Singular Integrands . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
19.8.7 Sets and Solitaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
CONTENTS
viii

20 Symbolic Calculations 461
20.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
20.2 Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
20.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
20.4 Summary and Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 472

21 The Tau-Method 473
21.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
21.2 „ -Approximation for a Rational Function . . . . . . . . . . . . . . . . . . . . 474
21.3 Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
21.4 Canonical Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
21.5 Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478

22 Domain Decomposition Methods 479
22.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
22.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
22.3 Connecting the Subdomains: Patching . . . . . . . . . . . . . . . . . . . . . . 480
22.4 Weak Coupling of Elemental Solutions . . . . . . . . . . . . . . . . . . . . . . 481
22.5 Variational Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
22.6 Choice of Basis & Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
22.7 Patching versus Variational Formalism . . . . . . . . . . . . . . . . . . . . . . 486
22.8 Matrix Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
22.9 The In¬‚uence Matrix Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
22.10Two-Dimensional Mappings & Sectorial Elements . . . . . . . . . . . . . . . 491
22.11 Prospectus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492

23 Books and Reviews 494

A A Bestiary of Basis Functions 495
A.1 Trigonometric Basis Functions: Fourier Series . . . . . . . . . . . . . . . . . . 495
A.2 Chebyshev Polynomials: Tn (x) . . . . . . . . . . . . . . . . . . . . . . . . . . 497
A.3 Chebyshev Polynomials of the Second Kind: Un (x) . . . . . . . . . . . . . . 499
A.4 Legendre Polynomials: Pn (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
A.5 Gegenbauer Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
A.6 Hermite Polynomials: Hn (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
A.7 Rational Chebyshev Functions: T Bn (y) . . . . . . . . . . . . . . . . . . . . . 507
A.8 Laguerre Polynomials: Ln (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
A.9 Rational Chebyshev Functions: T Ln (y) . . . . . . . . . . . . . . . . . . . . . 509
A.10 Graphs of Convergence Domains in the Complex Plane . . . . . . . . . . . . 511

B Direct Matrix-Solvers 514
B.1 Matrix Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
B.2 Banded Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
B.3 Matrix-of-Matrices Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
B.4 Block-Banded Elimination: the “Lindzen-Kuo” Algorithm . . . . . . . . . . 520
B.5 Block and “Bordered” Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 522
B.6 Cyclic Banded Matrices (Periodic Boundary Conditions) . . . . . . . . . . . 524
B.7 Parting shots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
CONTENTS ix

C Newton Iteration 526
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
C.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
C.3 Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
C.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534

D The Continuation Method 536
D.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
D.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
D.3 Initialization Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
D.4 Limit Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
D.5 Bifurcation points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
D.6 Pseudoarclength Continuation . . . . . . . . . . . . . . . . . . . . . . . . . . 546

E Change-of-Coordinate Derivative Transformations 550

F Cardinal Functions 561
F.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
F.2 General Fourier Series: Endpoint Grid . . . . . . . . . . . . . . . . . . . . . . 562
F.3 Fourier Cosine Series: Endpoint Grid . . . . . . . . . . . . . . . . . . . . . . . 563
F.4 Fourier Sine Series: Endpoint Grid . . . . . . . . . . . . . . . . . . . . . . . . 565
F.5 Cosine Cardinal Functions: Interior Grid . . . . . . . . . . . . . . . . . . . . 567
F.6 Sine Cardinal Functions: Interior Grid . . . . . . . . . . . . . . . . . . . . . . 568
F.7 Sinc(x): Whittaker cardinal function . . . . . . . . . . . . . . . . . . . . . . . 569
F.8 Chebyshev Gauss-Lobatto (“Endpoints”) . . . . . . . . . . . . . . . . . . . . 570
F.9 Chebyshev Polynomials: Interior or “Roots” Grid . . . . . . . . . . . . . . . 571
F.10 Legendre Polynomials: Gauss-Lobatto Grid . . . . . . . . . . . . . . . . . . . 572

G Transformation of Derivative Boundary Conditions 575

Glossary 577

Index 586

References 595
Preface

[Preface to the First Edition (1988)]
The goal of this book is to teach spectral methods for solving boundary value, eigen-
value and time-dependent problems. Although the title speaks only of Chebyshev poly-
nomials and trigonometric functions, the book also discusses Hermite, Laguerre, rational
Chebyshev, sinc, and spherical harmonic functions.
These notes evolved from a course I have taught the past ¬ve years to an audience
drawn from half a dozen different disciplines at the University of Michigan: aerospace
engineering, meteorology, physical oceanography, mechanical engineering, naval architec-
ture, and nuclear engineering. With such a diverse audience, this book is not focused on a
particular discipline, but rather upon solving differential equations in general. The style is
not lemma-theorem-Sobolev space, but algorithm-guidelines-rules-of-thumb.
Although the course is aimed at graduate students, the required background is limited.
It helps if the reader has taken an elementary course in computer methods and also has
been exposed to Fourier series and complex variables at the undergraduate level. How-
ever, even this background is not absolutely necessary. Chapters 2 to 5 are a self-contained
treatment of basic convergence and interpolation theory.
Undergraduates who have been overawed by my course have suffered not from a
lack of knowledge, but a lack of sophistication. This volume is not an almanac of un-
related facts, even though many sections and especially the appendices can be used to
look up things, but rather is a travel guide to the Chebyshev City where the individual
algorithms and identities interact to form a community. In this mathematical village, the
special functions are special friends. A differential equation is a pseudospectral matrix in
drag. The program structure of grids point/basisset/collocation matrix is as basic to life as
cloud/rain/river/sea.
It is not that spectral concepts are dif¬cult, but rather that they link together as the com-
ponents of an intellectual and computational ecology. Those who come to the course with
no previous adventures in numerical analysis will be like urban children abandoned in the
wildernes. Such innocents will learn far more than hardened veterans of the arithmurgical
wars, but emerge from the forests with a lot more bruises.
In contrast, those who have had a couple of courses in numerical analysis should ¬nd
this book comfortable: an elaboration fo familiar ideas about basis sets and grid point rep-
resentations. Spectral algorithms are a new worldview of the same computational land-
scape.
These notes are structured so that each chapter is largely self-contained. Because of this
and also the length of this volume, the reader is strongly encouraged to skip-and-choose.
The course on which this book is based is only one semester. However, I have found
it necessary to omit seven chapters or appendices each term, so the book should serve
equally well as the text for a two-semester course.
Although tese notes were written for a graduate course, this book should also be useful
to researchers. Indeed, half a dozen faculty colleagues have audited the course.

x
Preface xi

The writing style is an uneasy mixture of two in¬‚uences. In private life, the author
has written fourteen published science ¬ction and mystery short stories. When one has
described zeppelins jousting in the heavy atmosphere of another world or a stranded ex-
plorer alone on an arti¬cial toroidal planet, it is dif¬cult to write with the expected scienti¬c
dullness.
Nonetheless, I have not been too proud to forget most of the wise precepts I learned in
college English: the book makes heavy use of both the passive voice and the editorial “we”.
When I was still a postdoc, a kindly journal editor took me in hand, and circled every single
“I” in red. The scienti¬c abhorrence of the personal pronoun, the active voice, and lively
writing is as hypocritical as the Victorian horror of “breast” and “pregnant”. Nevertheless,
most readers are so used to the anti-literature of science that what would pass for good
writing elsewhere would be too distracting. So I have done my best to write a book that is
not about its style but about its message.
Like any work, this volume re¬‚ects the particular interests and biases of the author.
While a Harvard undergraduate, I imagined that I would grow up in the image of my pro-
fessors: a pillar of the A. M. S., an editorial board member for a dozen learned journals, and
captain and chief executive of¬cer of a large company of graduate students and postdocs.
My actual worldline has been amusingly different.
I was once elected to a national committee, but only after my interest had shifted. I said
nothing and was not a nuisance. I have never had any connection with a journal except
as a reviewer. In twelve years at Michigan, I have supervised a single Ph. D. thesis. And
more than three-quarters of my 65 papers to date have had but a single author.
This freedom from the usual entanglements has allowed me to follow my interests:
chemical physics as an undergraduate, dynamic meteorology as a graduate student, hydro-
dynamic stability and equatorial ¬‚uid mechanics as an assistant professor, nonlinear waves
and a stronger interest in numerical algorithms after I was tenured. This book re¬‚ects these
interests: broad, but with a bias towards ¬‚uid mechanics, geophysics and waves.
I have also tried, not as successfully as I would have wished, to stress the importance of
analyzing the physics of the problem before, during, and after computation. This is partly a
re¬‚ection of my own scienti¬c style: like a sort of mathematical guerrilla, I have ambushed
problems with Pad´ approximants and perturbative derivations of the Korteweg-deVries
e
equation as well as with Chebyshev polynomials; numerical papers are only half my pub-
lished articles.
However, there is a deeper reason: the numerical agenda is always set by the physics.
The geometry, the boundary layers and fronts, and the symmetries are the topography of
the computation. He or she who would scale Mt. Everest is well-advised to scout the
passes before beginning the climb.
When I was an undergraduate ” ah, follies of youth ” I had a quasi-mystical belief in
the power of brute force computation.
Fortunately, I learned better before I could do too much damage. Joel Primack (to him
be thanks) taught me John Wheeler™s First Moral Principle: Never do a calculation until
you already know the answer.
The point of the paradox is that one can usually deduce much about the solution ”
orders-of-magnitude, symmetries, and so on ” before writing a single line of code. A
thousand errors have been published because the authors had no idea what the solution
ought to look like. For the scientist, as for Sherlock Holmes, it is the small anomalies that
are the clues to the great pattern. One cannot appreciate the profound signi¬cance of the
unexpected without ¬rst knowing the expected.

<<

. 2
( 136 .)



>>