《复变函数论》课程教学资源（书籍文献）傅里叶积分 Chebyshev and Fourier Spectral Methods（Second Edition）

Chebyshev and Fourier Spectral MethodsSecond EditionJohn P. BoydUniversity of MichiganAnn Arbor, Michigan 48109-2143email: jpboyd@engin.umich.eduhttp://www-personai.engin.umich.edu/~jpboyd/2000DOvERPublications,Inc.31East2ndStreetMineola,NewYork115011

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

ContentsPREFACEXAcknowledgmentsxivxviErrata and Extended-Bibliography11Introduction11.1Series expansions21.2First Example41.3Comparison with finite element methods61.4Comparisons with Finite Differences91.5Parallel Computers91.6Choice of basis functions101.7Boundaryconditions121.8Non-Interpolating and Pseudospectral1.913Nonlinearity151.10Time-dependentproblems161.11FAQ:FrequentlyAskedQuestions171.12The Chrysalis192Chebyshev&FourierSeries192.1Introduction2.220Fourier series2.325Ordersof Convergence272.4ConvergenceOrder.2.531AssumptionofEqualErrors...L322.6Darboux's Principle.2.735WhyTaylorSeriesFail362.8Location of Singularities372.8.1Corner Singularities &Compatibility Conditions412.9FACE:Integration-by-PartsBound452.10 Asymptotic Calculation of Fourier Coefficients462.11 Convergence Theory: Chebyshev Polynomials502.12 LastCoefficientRule-of-Thumb512.13 Convergence Theory for Legendre Polynomials542.14Quasi-SinusoidalRuleofThumb562.15WitchofAgnesiRule-of-Thumb572.16BoundaryLayerRule-of-Thumbii

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

iiCONTENTS613Galerkin&WeightedResidualMethods613.1MeanWeightedResidual Methods3.264Completeness and BoundaryConditions3.365Inner Product & Orthogonality673.4GalerkinMethod3.568Integration-by-Parts.3.670Galerkin Method: Case Studies763.7Separation-of-Variables&theGalerkinMethod3.877Heisenberg MatrixMechanics3.980The Galerkin Method Today814Interpolation,Collocation&All That4.181Introduction.824.2Polynomial interpolation4.386Gaussian Integration & Pseudospectral Grids4.489Pseudospectral Is Galerkin Method via Quadrature934.5PseudospectralErrors985Cardinal Functions985.1Introduction995.2Whittaker Cardinal or"Sinc"Functions5.3100TrigonometricInterpolation.5.4104CardinalFunctionsforOrthogonalPolynomials1075.5TransformationsandInterpolation1096Pseudospectral Methods for BVPs6.1109Introduction6.2109Choice of Basis Set6.3Boundary Conditions: Behavioral & Numerical .109...6.4111"Boundary-Bordering"*6.5112"Basis Recombination"..6.6Transfinite Interpolation114...1156.7TheCardinal Function Basis...:.1166.8The Interpolation Grid*6.9116Computing Basis Functions &Derivatives-...1186.10 Higher Dimensions: Indexing1206.11 Higher Dimensions..1206.12CornerSingularities..1216.13 Matrix methods-1216.14 Checking..1236.15SummaryS1277Linear Eigenvalue Problems1277.1The No-Brain Method7.2128QR/QZAlgorithm7.3Eigenvalue Rule-of-Thumb1297.4134FourKindsof Sturm-LiouvilleProblems1377.5Criteriafor Rejecting Eigenvalues7.6139"Spurious"Eigenvalues7.7142Reducing the Condition Number7.8145ThePowerMethod7.9149InversePowerMethod

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

ivCONTENTS1497.10CombiningGlobal&LocalMethods1517.11 Detouring into the Complex Plane1557.12 Common Errors1598Symmetry & Parity8.1159Introduction1598.2Parity8.3165Modifying the Grid to Exploit Parity8.4165OtherDiscreteSymmetries1708.5Axisymmetric &Apple-Slicing Models1729Explicit Time-Integration Methods9.1172Introduction9.2175Spatially-VaryingCoefficients9.3177TheShamrockPrinciple1789.4Linear and Nonlinear9.5179Example:KdVEquation1819.6Implicitly-Implicit: RLW&QG18310 Partial Summation, the FFT and MMT18310.1Introduction18410.2PartialSummation18710.3 TheFast Fourier Transform:Theory19010.4MatrixMultiplicationTransform19210.5CostsoftheFastFourierTransform19510.6 Generalized FFTs and Multipole Methods19810.7Off-GridInterpolation20010.8FastFourierTransform:PracticalMatters20010.9Summary20211 Aliasing, Spectral Blocking, & Blow-Up20211.1 Introduction20211.2 Aliasing and Equality-on-the-Grid20511.3"2h-Waves"and Spectral Blocking21011.4 AliasingInstability:History andRemedies21111.5 Dealiasing and the Orszag Two-Thirds Rule21311.6 Energy-Conserving:Constrained Interpolation21411.7Energy-ConservingSchemes:Discussion21611.8 Aliasing Instability: Theory21811.9Summary22212 Implicit Schemes &the Slow Manifold22212.1 Introduction22412.2Dispersion andAmplitudeErrors22612.3Errors&CFLLimitforExplicitSchemes22812.4ImplicitTime-MarchingAlgorithms22912.5Semi-ImplicitMethods23012.6Speed-ReductionRule-of-Thumb23112.7SlowManifold:Meteorology23212.8SlowManifold:Definition&Examples23612.9Numerically-InducedSlowManifolds23912.10Initialization

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

CONTENTSV24112.11TheMethod ofMultipleScales(Baer-Tribbia)24312.12NonlinearGalerkinMethods24512.13WeaknessesoftheNonlinearGalerkinMethod24812.14Tracking the Slow Manifold24912.15ThreePartstoMultipleScaleAlgorithms25213Splitting&ItsCousins25213.1Introduction：25513.2FractionalStepsforDiffusion25613.3 Pitfalls in Splitting, I: Boundary Conditions25813.4 Pitfalls in Splitting, II: Consistency25913.5 Operator Theoryof Time-Stepping26113.6HighOrderSplitting26213.7 Splitting and Fluid Mechanics26514 Semi-Lagrangian Advection26514.1ConceptofanIntegratingFactor26714.2Misuseof IntegratingFactorMethods27014.3 Semi-LagrangianAdvection:Introduction27114.4Advection&MethodofCharacteristics27314.5Three-Level,2DOrder Semi-Implicit.27514.6Multiply-UpstreamSL27714.7NumericalIllustrations&Superconvergence28014.8Two-LevelSL/SIAlgorithms28114.9NoninterpolatingSL&NumericalDiffusion28314.10Off-GridInterpolation14.10.1Off-Grid Interpolation: Generalities28328414.10.2SpectralOff-grid28414.10.3Low-orderPolynomialInterpolation28614.10.4 McGregor's Taylor Series Scheme28614.11HigherOrderSLMethods28614.12History and Relationships to Other Methods28914.13Summary29015Matrix-Solving Methods29015.1Introduction29115.2 Stationary One-Step Iterations29315.3 Preconditioning:Finite Difference29715.4 Computing Iterates:FFT/Matrix Multiplication29915.5AlternativePreconditioners30115.6 Raising the Order ThroughPreconditioning30115.7Multigrid:An Overview30415.8MRRMethod30715.9 Delves-FreemanBlock-and-Diagonal Iteration31215.10Recursions &Formal Integration: Constant Coefficient ODEs .31415.11DirectMethodsforSeparablePDE's31715.12FastIterationsforAlmostSeparablePDEs31815.13PositiveDefiniteandIndefiniteMatrices32015.14PreconditionedNewtonFlow32215.15Summary&Proverbs

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

viCONTENTS32316CoordinateTransformations32316.1Introduction...32316.2 Programming Chebyshev Methods16.3Theoryof1-DTransformations32532616.4InfiniteandSemi-InfiniteIntervals32716.5MapsforEndpoint&CornerSingularities32916.6Two-DimensionalMaps&CornerBranchPoints33016.7PeriodicProblems&theArctan/TanMap33216.8 Adaptive Methods33416.9Almost-EquispacedKosloff/Tal-EzerGrid33817 Methods for Unbounded Intervals33817.1Introduction...33917.2DomainTruncation33917.2.1 DomainTruncationforRapidly-decayingFunctions34017.2.2DomainTruncationforSlowly-DecayingFunctions17.2.3 Domain TruncationforTime-Dependent Wave Propagation:340SpongeLayers17.3 Whittaker Cardinal or"Sinc"Functions34134617.4 Hermitefunctions.35317.5Semi-InfiniteInterval:LaguerreFunctions35517.6NewBasisSetsviaChangeofCoordinate35617.7RationalChebyshevFunctions:TBn36117.8Behavioral versus Numerical Boundary Conditions36317.9 Strategy for Slowly Decaying Functions36617.10NumericalExamples:RationalChebyshevFunctions36917.11Semi-InfiniteInterval:RationalChebyshevTL,37017.12NumericalExamples:ChebyshevforSemi-InfiniteInterval37217.13Strategy:Oscillatory,Non-Decaying Functions37417.14Weideman-ClootSinhMapping17.15Summary37718 Spherical & Cylindrical Geometry38038018.1Introduction...18.2 Polar, Cylindrical, Toroidal, Spherical38138218.3ApparentSingularityatthePole38318.4PolarCoordinates:ParityTheorem18.5RadialBasisSetsandRadialGrids38538718.5.1One-SidedJacobiBasisfortheRadialCoordinate38918.5.2BoundaryValue&EigenvalueProblemsonaDisk18.5.3 Unbounded Domains Including the Origin in Cylindrical Coordinates 39039018.6AnnularDomains39118.7SphericalCoordinates:AnOverview39118.8TheParityFactorforScalars:SphereversusTorus18.9ParityII:Horizontal Velocities&OtherVector Components39539818.10ThePoleProblem:SphericalCoordinates39918.11SphericalHarmonics:Introduction40218.12LegendreTransformsandOtherSorrows40218.12.1FFTinLongitude/MMTinLatitude18.12.2 Substitutes and Accelerators for the MMT40318.12.3Parity and Legendre Transforms404

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

viiCONTENTS40418.12.4HurrahforMatrix/VectorMultiplication40518.12.5 Reduced Grid and Other Tricks.40518.12.6Schuster-DiltsTriangularMatrixAcceleration18.12.7Generalized FFT: Multipoles and All That40740718.12.8Summary18.13EquiarealResolution40840918.14SphericalHarmonics:Limited-Area Models41018.15Spherical Harmonics and Physics41018.16AsymptoticApproximations,I41218.17AsymptoticApproximations,I41418.18Software:SphericalHarmonics41618.19Semi-Implicit: ShallowWater41818.20FrontsandTopography:Smoothing/Filters41818.20.1FrontsandTopography41918.20.2Mechanics of Filtering18.20.3Spherical splines42042218.20.4FilterOrder42318.20.5 Filtering with Spatially-Variable Order42318.20.6TopographicFilteringinMeteorology18.21ResolutionofSpectralModels42542818.22VectorHarmonics&HoughFunctions42918.23Radial/VerticalCoordinate:SpectralorNon-Spectral?42918.23.1BasisforAxialCoordinateinCylindricalCoordinates42918.23.2Axial Basis inToroidalCoordinates42918.23.3Vertical/RadialBasis inSphericalCoordinates18.24Stellar Convection in a Spherical Annulus: Glatzmaier (1984)43043118.25Non-TensorGrids:Icosahedral,etc.43318.26RobertBasisfortheSphere:43418.27Parity-ModifiedLatitudinalFourierSeries43518.28ProjectiveFilteringforLatitudinalFourierSeries43718.29Spectral Elements on theSphere43818.30SphericalHarmonicsBesieged43918.31EllipticandEllipticCylinderCoordinates44018.32Summary44219Special Tricks44219.1Introduction44319.2SidebandTruncation44619.3SpecialBasisFunctions,I:CornerSingularities44819.4 Special Basis Functions, II: Wave Scattering45019.5WeaklyNonlocal SolitaryWaves45019.6Root-FindingbyChebyshevPolynomials19.7HilbertTransform.45345419.8Spectrally-AccurateQuadratureMethods45419.8.1 Introduction:Gaussian and Clenshaw-CurtisQuadrature45519.8.2Clenshaw-CurtisAdaptivity45619.8.3Mechanics19.8.4 Integration of Periodic Functions and the Trapezoidal Rule45719.8.5Infinite Intervals and the Trapezoidal Rule45845819.8.6SingularIntegrands19.8.7 Sets and Solitaries460

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

viliCONTENTS46120 SymbolicCalculations46120.1Introduction46220.2 Strategy.46520.3Examples47220.4SummaryandOpenProblems21 The Tau-Method47347321.1Introduction47421.2 T-Approximation for a Rational Function47621.3DifferentialEquations47621.4Canonical Polynomials21.5Nomenclature47847922 Domain Decomposition Methods47922.1Introduction48022.2Notation48022.3Connecting the Subdomains:Patching48122.4 Weak Coupling of Elemental Solutions48422.5 Variational Principles.48522.6Choice of Basis&Grid48622.7PatchingversusVariationalFormalism48722.8 Matrix Inversion.48822.9 The Influence Matrix Method49122.10Two-Dimensional Mappings & Sectorial Elements49222.11Prospectus49423BooksandReviews495AABestiaryof BasisFunctions495A.1 Trigonometric Basis Functions:Fourier Series497A.2 Chebyshev Polynomials: T(r)A.3 Chebyshev Polynomials of the Second Kind: Un(r)499500A.4 Legendre Polynomials: Pn()502A.5 Gegenbauer Polynomials .505A.6 Hermite Polynomials: H()507A.7 Rational Chebyshev Functions: TBn(y)508A.8 Laguerre Polynomials: Ln()A.9 Rational Chebyshev Functions: TLn(y)509A.10 Graphs of ConvergenceDomains in theComplexPlane511514BDirectMatrix-Solvers514B.1 MatrixFactorizations518B.2 Banded Matrix520B.3Matrix-of-MatricesTheorem520B.4 Block-Banded Elimination: the"Lindzen-Kuo"Algorithm522B.5Blockand"Bordered"Matrices524B.6Cyclic Banded Matrices (Periodic Boundary Conditions)524B.7Partingshots

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

ixCONTENTSCNewton Iteration526526C.1 IntroductionC.2 Examples529531C.3Eigenvalue ProblemsC.4Summary..534536D TheContinuationMethodD.1536Introduction537D.2 Examples.538D.3Initialization Strategies542D.4 Limit Points544D.5Bifurcation points546D.6Pseudoarclength ContinuationE550Change-of-Coordinate Derivative TransformationsR561Cardinal Functions561F.1Introduction，F.2562General Fourier Series:Endpoint GridF.3563Fourier Cosine Series: Endpoint Grid .F.4565Fourier Sine Series:Endpoint GridF.5CosineCardinalFunctions:InteriorGrid567568F.6Sine Cardinal Functions: Interior GridF.7569Sinc(r): Whittaker cardinal functionF.8570ChebyshevGauss-Lobatto ("Endpoints")F.9Chebyshev Polynomials: Interior or"Roots" Grid571572F.10 Legendre Polynomials: Gauss-Lobatto Grid575GTransformationofDerivativeBoundaryConditionsGlossary577Index586References595

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

Preace[Preface to theFirstEdition (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 functions.These 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,physicaloceanography,mechanicalengineering,naval architecture, and nuclear engineering. With such a diverse audience, this book is not focused on aparticular discipline, but rather upon solving differential equations in general. The style isnotlemma-theorem-Sobolevspace,butalgorithm-guidelines-rules-of-thumbAlthough 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 hasbeen exposed to Fourier series and complex variables at the undergraduate level. How-ever, even thisbackground is not absolutely necessary.Chapters 2 to 5 are a self-containedtreatment ofbasic convergence and interpolation theory.Undergraduates 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 individualalgorithmsand identities interacttoformacommunity.Inthismathematical 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/river/sea.It 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 withnopreviousadventuresinnumericalanalysiswill belikeurbanchildrenabandoned inthewildernes. Such innocents will learn far more than hardened veterans of the arithmurgicalwars, but emergefrom the forests with a lotmore bruises.In contrast, those who have had a couple of courses in numerical analysis should findthis book comfortable:anelaborationfofamiliarideas aboutbasis sets and gridpointrepresentations.Spectralalgorithmsarea newworldviewofthesamecomputational land-scape.These notes are structured so that each chapter is largely self-contained.Because of thisand 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 foundit necessary to omit seven chapters or appendices each term, so the book should serveequallywell asthetextforatwo-semestercourse.Although tese notes were written for a graduate course, this book should also be usefulto researchers. Indeed, half a dozen faculty colleagues have audited the course.X

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 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 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 difficult, 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 find 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