Chebyshev and Fourier Spectral Methods

1 Chebyshev and Fourier Spectral MethodsSecond EditionJohn P. BoydUniversity of MichiganAnn Arbor, Michigan 48109-2143email: jpboyd/2000 DOVER Publications, East 2nd StreetMineola, New York 115011 DedicationTo Marilyn, Ian, and Emma A computation is a temptation that should be resisted aslong as possible. J. P. Boyd, paraphrasing T. S. EliotiContentsPREFACExAcknowledgmentsxiv Errata and Extended-Bibliographyxvi1 with finite element with Finite of basis and Time-dependent FAQ: Frequently Asked The 172 Chebyshev & Fourier of of Equal s Taylor Series of Singularities & Compatibility : Integration-by-Parts Asymptotic Calculation of Fourier Convergence Theory: Chebyshev Last Coefficient Convergence Theory for Legendre Quasi-Sinusoidal Rule of Witch of Agnesi Rule of Boundary Layer 57iiCONTENTSiii3 Galerkin & Weighted Residual Weighted Residual and Boundary Product & Method.

2 Case & the Galerkin Matrix Galerkin Method 804 Interpolation, Collocation & All Integration & Pseudospectral Is Galerkin Method via 935 Cardinal Cardinal or Sinc Functions for Orthogonal and 1076 Pseudospectral Methods for of Basis Conditions: Behavioral & Boundary-Bordering .. Basis Recombination .. Cardinal Function Interpolation Basis Functions & Higher Dimensions: Higher Corner Matrix 1237 Linear Eigenvalue No-Brain Kinds of Sturm-Liouville for Rejecting Spurious the Condition Power Power Combining Global & Local Detouring into the Complex Common 1558 Symmetry & the Grid to Exploit Discrete & Apple-Slicing 1709 Explicit Time-Integration Shamrock and : KdV : RLW & 18110 Partial Summation, the FFT and Partial The Fast Fourier Transform.

3 Matrix Multiplication Costs of the Fast Fourier Generalized FFTs and Multipole Off-Grid Fast Fourier Transform: Practical 20011 Aliasing, Spectral Blocking, & Aliasing and 2 h-Waves and Spectral Aliasing Instability: History and Dealiasing and the Orszag Two-Thirds Energy-Conserving: Constrained Energy-Conserving Schemes: Aliasing Instability: 21812 Implicit Schemes & the Slow Dispersion and Amplitude Errors & CFL Limit for Explicit Implicit Time-Marching Semi-Implicit Speed-Reduction Slow Manifold: Slow Manifold: Definition & Numerically-Induced Slow The Method of Multiple Scales(Baer-Tribbia).. Galerkin of the Nonlinear Galerkin the Slow Parts to Multiple Scale 24913 Splitting & Its Fractional Steps for Pitfalls in Splitting, I: Boundary Pitfalls in Splitting, II: Operator Theory of High Order Splitting and Fluid 26214 Semi-Lagrangian Concept of an Integrating Misuse of Integrating Factor Semi-Lagrangian Advection: Advection & Method of Three-Level, 2D Order Multiply-Upstream Numerical Illustrations & Two-Level SL/SI Noninterpolating SL & Numerical Off-Grid Interpolation.

4 Spectral Low-order Polynomial McGregor s Taylor Series Higher Order SL and Relationships to Other 28915 Matrix-Solving Stationary One-Step Preconditioning: Finite Computing Iterates: FFT/Matrix Alternative Raising the Order Through Multigrid: An MRR Delves-Freeman Block-and-Diagonal & Formal Integration: Constant Coefficient Direct Methods for Separable PDE Iterations for Almost Separable Definite and Indefinite Newton & 322viCONTENTS16 Coordinate Programming Chebyshev Theory of 1-D Infinite and Semi-Infinite Maps for Endpoint & Corner Two-Dimensional Maps & Corner Branch Periodic Problems & the Arctan/Tan Adaptive Almost-Equispaced Kosloff/Tal-Ezer 33417 Methods for Unbounded Domain Domain Truncation for Rapidly-decaying Domain Truncation for Slowly-Decaying Domain Truncation for Time-Dependent Wave Propagation:Sponge Whittaker Cardinal or Sinc Hermite Semi-Infinite Interval.

5 Laguerre New Basis Sets via Change of Rational Chebyshev Behavioral versus Numerical Boundary Strategy for Slowly Decaying Examples: Rational Chebyshev Semi-Infinite Interval: Rational Examples: Chebyshev for Semi-Infinite : Oscillatory, Non-Decaying Sinh 37718 Spherical & Cylindrical Polar, Cylindrical, Toroidal, Apparent Singularity at the Polar Coordinates: Parity Radial Basis Sets and Radial One-Sided Jacobi Basis for the Radial Boundary Value & Eigenvalue Problems on a Unbounded Domains Including the Origin in Cylindrical Coordinates Annular Spherical Coordinates: An The Parity Factor for Scalars: Sphere versus Parity II: Horizontal Velocities & Other Vector Pole Problem: Spherical Spherical Harmonics: Transforms and Other FFT in Longitude/MMT in Substitutes and Accelerators for the Parity and Legendre Hurrah for Matrix/Vector Reduced Grid and Other Schuster-Dilts Triangular Matrix Generalized FFT: Multipoles and All Harmonics: Limited-Area Harmonics and Approximations, Approximations, : Spherical : Shallow and Topography: Fronts and Mechanics of Spherical Filter Filtering with Spatially-Variable Topographic Filtering in of Spectral Harmonics & Hough Coordinate: Spectral or Non- Spectral ?

6 Basis for Axial Coordinate in Cylindrical Axial Basis in Toroidal Vertical/Radial Basis in Spherical Convection in a Spherical Annulus: Glatzmaier (1984).. Grids: Icosahedral, Basis for the Latitudinal Fourier Filtering for Latitudinal Fourier Elements on the Harmonics and Elliptic Cylinder 44019 Special Sideband Special Basis Functions, I: Corner Special Basis Functions, II: Wave Weakly Nonlocal Solitary Root-Finding by Chebyshev Hilbert Spectrally-Accurate Quadrature Introduction: Gaussian and Clenshaw-Curtis Clenshaw-Curtis Integration of Periodic Functions and the Trapezoidal Infinite Intervals and the Trapezoidal Singular Sets and 460viiiCONTENTS20 Symbolic Summary and Open 47221 The -Approximation for a Rational Differential Canonical 47822 Domain Decomposition Connecting the Subdomains: Weak Coupling of Elemental Variational Choice of Basis & Patching versus Variational Matrix The Influence Matrix Mappings & Sectorial 49223 Books and Reviews494A A Bestiary of Basis Trigonometric Basis Functions: Fourier Chebyshev Polynomials:Tn(x).

7 Chebyshev Polynomials of the Second Kind:Un(x).. Legendre Polynomials:Pn(x).. Gegenbauer Hermite Polynomials:Hn(x).. Rational Chebyshev Functions:TBn(y).. Laguerre Polynomials:Ln(x).. Rational Chebyshev Functions:TLn(y).. Graphs of Convergence Domains in the Complex 511B Direct Matrix Banded Matrix-of-Matrices Block-Banded Elimination: the Lindzen-Kuo Block and Bordered Cyclic Banded Matrices (Periodic Boundary Conditions).. Parting 524 CONTENTSixC Newton Eigenvalue 534D The Continuation Initialization Limit Bifurcation Pseudoarclength 546E Change-of-Coordinate Derivative Transformations550F Cardinal Fourier Series: Endpoint Cosine Series: Endpoint Sine Series: Endpoint Cardinal Functions: Interior Cardinal Functions: Interior (x): Whittaker cardinal Gauss-Lobatto ( Endpoints ).

8 Polynomials: Interior or Roots Legendre Polynomials: Gauss-Lobatto 572G Transformation of Derivative Boundary Conditions575 Glossary577 Index586 References595 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, rationalChebyshev, sinc, and spherical harmonic notes evolved from a course I have taught the past five years to an audiencedrawn from half a dozen different disciplines at the University of Michigan: aerospaceengineering, meteorology, physical oceanography, mechanical engineering, naval architec-ture, and nuclear engineering.

9 With such a diverse audience, this book is not focused on aparticular discipline, but rather upon solving differential equations in general. The style isnot lemma-theorem-Sobolev space, but the course is aimed at graduate students, the required background is helps if the reader has taken an elementary course in computer Methods and also hasbeen 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-containedtreatment of basic convergence and interpolation who have been overawed by my course have suffered not from alack 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 tolook up things, but rather is a travel guide to the Chebyshev City where the individualalgorithms and identities interact to form a community.

10 In this mathematical village, thespecial functions are special friends. A differential equation is a pseudospectral matrix indrag. The program structure of grids point/basisset/collocation matrix is as basic to life ascloud/rain/ is not that Spectral concepts are difficult, but rather that they link together as the com-ponents of an intellectual and computational ecology. Those who come to the course withno previous adventures in numerical analysis will be like urban children abandoned in thewildernes. Such innocents will learn far more than hardened veterans of the arithmurgicalwars, but emerge from the forests with a lot more contrast, those who have had a couple of courses in numerical analysis should findthis book comfortable: an elaboration fo familiar ideas about basis sets and grid point rep-resentations.