. 1
( 136 .)



>>

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
Dedication


To Marilyn, Ian, and Emma




“A computation is a temptation that should be resisted as
long as possible.”
” J. P. Boyd, paraphrasing T. S. Eliot




i
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 ¬nite 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 Coef¬cients . . . . . . . . . . . . . . . . . 45
2.11 Convergence Theory: Chebyshev Polynomials . . . . . . . . . . . . . . . . . 46
2.12 Last Coef¬cient 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 Trans¬nite 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
CONTENTS
iv

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 Coef¬cients . . . . . . . . . . . . . . . . . . . . . . . . . . . 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: De¬nition & Examples . . . . . . . . . . . . . . . . . . . . . . 232
12.9 Numerically-Induced Slow Manifolds . . . . . . . . . . . . . . . . . . . . . . 236
12.10Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
CONTENTS v

12.11 The 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.11 Higher 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 Coef¬cient ODEs . . . . . . . . . 312
15.11 Direct Methods for Separable PDE™s . . . . . . . . . . . . . . . . . . . . . . . 314
15.12Fast Iterations for Almost Separable PDEs . . . . . . . . . . . . . . . . . . . . 317
15.13Positive De¬nite and Inde¬nite Matrices . . . . . . . . . . . . . . . . . . . . . 318
15.14Preconditioned Newton Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
15.15Summary & Proverbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
CONTENTS
vi

16 Coordinate Transformations 323
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
16.2 Programming Chebyshev Methods . . . . . . . . . . . . . . . . . . . . . . . . 323
16.3 Theory of 1-D Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . 325
16.4 In¬nite and Semi-In¬nite 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:

. 1
( 136 .)



>>