Chebyshev and Fourier Spectral Methods Second Edition John P. Boyd University of Michigan Ann Arbor, Michigan 48109-2143 email: jpboyd@engin.umich.edu http://www-personal.engin.umich.edu/∼jpboyd/ 2000 DOVER Publications, Inc. 31 East 2nd Street Mineola, New York 11501 1
Contents PREFACE x Acknowledgments xiv Errata and Extended-Bibliography xvi 1 Introduction 1 1.1 Series expansions . 1 1.2 First Example . 2 1.3 Comparison with finite element methods . 4 1.4 Comparisons with Finite Differences . 6 1.5 Parallel Computers . 9 1.6 Choice of basis functions . 9 1.7 Boundary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.8 Non-Interpolating and Pseudospectral . . . . . . . . . . . . . . . . . . . . . . 12 1.9 Nonlinearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.10 Time-dependent problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.11 FAQ: Frequently Asked Questions . . . . . . . . . . . . . . . . . . . . . . . . 16 1.12 The Chrysalis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Chebyshev & Fourier Series 19 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Orders of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 Convergence Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Assumption of Equal Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6 Darboux’s Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7 Why Taylor Series Fail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.8 Location of Singularities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.8.1 Corner Singularities & Compatibility Conditions . . . . . . . . . . . 37 2.9 FACE: Integration-by-Parts Bound . . . . . . . . . . . . . . . . . . . . . . . . 41 2.10 Asymptotic Calculation of Fourier Coefficients . . . . . . . . . . . . . . . . . 45 2.11 Convergence Theory: Chebyshev Polynomials . . . . . . . . . . . . . . . . . 46 2.12 Last Coefficient Rule-of-Thumb . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.13 Convergence Theory for Legendre Polynomials . . . . . . . . . . . . . . . . . 51 2.14 Quasi-Sinusoidal Rule of Thumb . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.15 Witch of Agnesi Rule–of–Thumb . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.16 Boundary Layer Rule-of-Thumb . . . . . . . . . . . . . . . . . . . . . . . . . 57 ii
CONTENTS iii 3 Galerkin & Weighted Residual Methods 61 3.1 Mean Weighted Residual Methods . . . . . . . . . . . . . . . . . . . . . . . . 61 3.2 Completeness and Boundary Conditions . . . . . . . . . . . . . . . . . . . . 64 3.3 Inner Product & Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4 Galerkin Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Integration-by-Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.6 Galerkin Method: Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.7 Separation-of-Variables & the Galerkin Method . . . . . . . . . . . . . . . . . 76 3.8 Heisenberg Matrix Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.9 The Galerkin Method Today . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4 Interpolation, Collocation & All That 81 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2 Polynomial interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3 Gaussian Integration & Pseudospectral Grids . . . . . . . . . . . . . . . . . . 86 4.4 Pseudospectral Is Galerkin Method via Quadrature . . . . . . . . . . . . . . 89 4.5 Pseudospectral Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5 Cardinal Functions 98 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Whittaker Cardinal or “Sinc” Functions . . . . . . . . . . . . . . . . . . . . . 99 5.3 Trigonometric Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.4 Cardinal Functions for Orthogonal Polynomials . . . . . . . . . . . . . . . . 104 5.5 Transformations and Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 107 6 Pseudospectral Methods for BVPs 109 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.2 Choice of Basis Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.3 Boundary Conditions: Behavioral & Numerical . . . . . . . . . . . . . . . . . 109 6.4 “Boundary-Bordering” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.5 “Basis Recombination” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.6 Transfinite Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.7 The Cardinal Function Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.8 The Interpolation Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 6.9 Computing Basis Functions & Derivatives . . . . . . . . . . . . . . . . . . . . 116 6.10 Higher Dimensions: Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.11 Higher Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.12 Corner Singularities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.13 Matrix methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.14 Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.15 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 7 Linear Eigenvalue Problems 127 7.1 The No-Brain Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.2 QR/QZ Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.3 Eigenvalue Rule-of-Thumb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.4 Four Kinds of Sturm-Liouville Problems . . . . . . . . . . . . . . . . . . . . . 134 7.5 Criteria for Rejecting Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.6 “Spurious” Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.7 Reducing the Condition Number . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.8 The Power Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.9 Inverse Power Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
iv CONTENTS 7.10 Combining Global & Local Methods . . . . . . . . . . . . . . . . . . . . . . . 149 7.11 Detouring into the Complex Plane . . . . . . . . . . . . . . . . . . . . . . . . 151 7.12 Common Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 8 Symmetry & Parity 159 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8.2 Parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8.3 Modifying the Grid to Exploit Parity . . . . . . . . . . . . . . . . . . . . . . . 165 8.4 Other Discrete Symmetries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.5 Axisymmetric & Apple-Slicing Models . . . . . . . . . . . . . . . . . . . . . . 170 9 Explicit Time-Integration Methods 172 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 9.2 Spatially-Varying Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 9.3 The Shamrock Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 9.4 Linear and Nonlinear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 9.5 Example: KdV Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 9.6 Implicitly-Implicit: RLW & QG . . . . . . . . . . . . . . . . . . . . . . . . . . 181 10 Partial Summation, the FFT and MMT 183 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 10.2 Partial Summation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 10.3 The Fast Fourier Transform: Theory . . . . . . . . . . . . . . . . . . . . . . . 187 10.4 Matrix Multiplication Transform . . . . . . . . . . . . . . . . . . . . . . . . . 190 10.5 Costs of the Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . 192 10.6 Generalized FFTs and Multipole Methods . . . . . . . . . . . . . . . . . . . . 195 10.7 Off-Grid Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 10.8 Fast Fourier Transform: Practical Matters . . . . . . . . . . . . . . . . . . . . 200 10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 11 Aliasing, Spectral Blocking, & Blow-Up 202 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 11.2 Aliasing and Equality-on-the-Grid . . . . . . . . . . . . . . . . . . . . . . . . 202 11.3 “2 h-Waves” and Spectral Blocking . . . . . . . . . . . . . . . . . . . . . . . . 205 11.4 Aliasing Instability: History and Remedies . . . . . . . . . . . . . . . . . . . 210 11.5 Dealiasing and the Orszag Two-Thirds Rule . . . . . . . . . . . . . . . . . . . 211 11.6 Energy-Conserving: Constrained Interpolation . . . . . . . . . . . . . . . . . 213 11.7 Energy-Conserving Schemes: Discussion . . . . . . . . . . . . . . . . . . . . 214 11.8 Aliasing Instability: Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 12 Implicit Schemes & the Slow Manifold 222 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.2 Dispersion and Amplitude Errors . . . . . . . . . . . . . . . . . . . . . . . . . 224 12.3 Errors & CFL Limit for Explicit Schemes . . . . . . . . . . . . . . . . . . . . . 226 12.4 Implicit Time-Marching Algorithms . . . . . . . . . . . . . . . . . . . . . . . 228 12.5 Semi-Implicit Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 12.6 Speed-Reduction Rule-of-Thumb . . . . . . . . . . . . . . . . . . . . . . . . . 230 12.7 Slow Manifold: Meteorology . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 12.8 Slow Manifold: Definition & Examples . . . . . . . . . . . . . . . . . . . . . . 232 12.9 Numerically-Induced Slow Manifolds . . . . . . . . . . . . . . . . . . . . . . 236 12.10Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
CONTENTS v 12.11The Method of Multiple Scales(Baer-Tribbia) . . . . . . . . . . . . . . . . . . 241 12.12Nonlinear Galerkin Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 12.13Weaknesses of the Nonlinear Galerkin Method . . . . . . . . . . . . . . . . . 245 12.14Tracking the Slow Manifold . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 12.15Three Parts to Multiple Scale Algorithms . . . . . . . . . . . . . . . . . . . . 249 13 Splitting & Its Cousins 252 13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 13.2 Fractional Steps for Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 13.3 Pitfalls in Splitting, I: Boundary Conditions . . . . . . . . . . . . . . . . . . . 256 13.4 Pitfalls in Splitting, II: Consistency . . . . . . . . . . . . . . . . . . . . . . . . 258 13.5 Operator Theory of Time-Stepping . . . . . . . . . . . . . . . . . . . . . . . . 259 13.6 High Order Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 13.7 Splitting and Fluid Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 14 Semi-Lagrangian Advection 265 14.1 Concept of an Integrating Factor . . . . . . . . . . . . . . . . . . . . . . . . . 265 14.2 Misuse of Integrating Factor Methods . . . . . . . . . . . . . . . . . . . . . . 267 14.3 Semi-Lagrangian Advection: Introduction . . . . . . . . . . . . . . . . . . . . 270 14.4 Advection & Method of Characteristics . . . . . . . . . . . . . . . . . . . . . 271 14.5 Three-Level, 2D Order Semi-Implicit . . . . . . . . . . . . . . . . . . . . . . . 273 14.6 Multiply-Upstream SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 14.7 Numerical Illustrations & Superconvergence . . . . . . . . . . . . . . . . . . 277 14.8 Two-Level SL/SI Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 14.9 Noninterpolating SL & Numerical Diffusion . . . . . . . . . . . . . . . . . . 281 14.10Off-Grid Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 14.10.1 Off-Grid Interpolation: Generalities . . . . . . . . . . . . . . . . . . . 283 14.10.2 Spectral Off-grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 14.10.3 Low-order Polynomial Interpolation . . . . . . . . . . . . . . . . . . . 284 14.10.4 McGregor’s Taylor Series Scheme . . . . . . . . . . . . . . . . . . . . 286 14.11Higher Order SL Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 14.12History and Relationships to Other Methods . . . . . . . . . . . . . . . . . . 286 14.13Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 15 Matrix-Solving Methods 290 15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 15.2 Stationary One-Step Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 15.3 Preconditioning: Finite Difference . . . . . . . . . . . . . . . . . . . . . . . . 293 15.4 Computing Iterates: FFT/Matrix Multiplication . . . . . . . . . . . . . . . . 297 15.5 Alternative Preconditioners . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 15.6 Raising the Order Through Preconditioning . . . . . . . . . . . . . . . . . . . 301 15.7 Multigrid: An Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 15.8 MRR Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 15.9 Delves-Freeman Block-and-Diagonal Iteration . . . . . . . . . . . . . . . . . 307 15.10Recursions & Formal Integration: Constant Coefficient ODEs . . . . . . . . . 312 15.11Direct Methods for Separable PDE’s . . . . . . . . . . . . . . . . . . . . . . . 314 15.12Fast Iterations for Almost Separable PDEs . . . . . . . . . . . . . . . . . . . . 317 15.13Positive Definite and Indefinite Matrices . . . . . . . . . . . . . . . . . . . . . 318 15.14Preconditioned Newton Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 15.15Summary & Proverbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
vi CONTENTS 16 Coordinate Transformations 323 16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 16.2 Programming Chebyshev Methods . . . . . . . . . . . . . . . . . . . . . . . . 323 16.3 Theory of 1-D Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . 325 16.4 Infinite and Semi-Infinite Intervals . . . . . . . . . . . . . . . . . . . . . . . . 326 16.5 Maps for Endpoint & Corner Singularities . . . . . . . . . . . . . . . . . . . . 327 16.6 Two-Dimensional Maps & Corner Branch Points . . . . . . . . . . . . . . . . 329 16.7 Periodic Problems & the Arctan/Tan Map . . . . . . . . . . . . . . . . . . . . 330 16.8 Adaptive Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 16.9 Almost-Equispaced Kosloff/Tal-Ezer Grid . . . . . . . . . . . . . . . . . . . . 334 17 Methods for Unbounded Intervals 338 17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 17.2 Domain Truncation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 17.2.1 Domain Truncation for Rapidly-decaying Functions . . . . . . . . . . 339 17.2.2 Domain Truncation for Slowly-Decaying Functions . . . . . . . . . . 340 17.2.3 Domain Truncation for Time-Dependent Wave Propagation: Sponge Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 17.3 Whittaker Cardinal or “Sinc” Functions . . . . . . . . . . . . . . . . . . . . . 341 17.4 Hermite functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 17.5 Semi-Infinite 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.11Semi-Infinite Interval: Rational Chebyshev T Ln . . . . . . . . . . . . . . . . 369 17.12Numerical Examples: Chebyshev for Semi-Infinite 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.11Spherical 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-Modified 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 Infinite Intervals and the Trapezoidal Rule . . . . . . . . . . . . . . . 458 19.8.6 Singular Integrands . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 19.8.7 Sets and Solitaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
viii CONTENTS 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 Influence Matrix Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 22.10Two-Dimensional Mappings & Sectorial Elements . . . . . . . . . . . . . . . 491 22.11Prospectus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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, eigenvalue and time-dependent problems. Although the title speaks only of Chebyshev polynomials 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 five years to an audience drawn from half a dozen different disciplines at the University of Michigan: aerospace engineering, meteorology, physical oceanography, mechanical engineering, naval architecture, 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. However, 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 unrelated 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 difficult, but rather that they link together as the components 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 find this book comfortable: an elaboration fo familiar ideas about basis sets and grid point representations. Spectral algorithms are a new worldview of the same computational landscape. 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