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. Mind后A829%90o1 1
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 Acknowledgments xiv Errata and Extended-Bibliography xvi 1 Introduction 1 l.1 Series expansions.·.······· 1 1.2 First Example 2 1.3 Comparison with finite element methods 4 l.4 Comparisons with Finite Differences.·..·.····.······ 6 1.5 Parallel Computers.......·················· 1.6 Choice of basis functions.····················· 9 1.7 Boundary conditions........... 10 1.8 Non-Interpolating and Pseudospectral..·.·.·.····. 12 1.9 Nonlinearity........。。·...·。············· 13 l.l0Time-dependent problems.·.·.·.················ 15 1.11 FAQ:Frequently Asked Questions.....·.·····.···.· 16 1.12 The Chrysalis 1 2 Chebyshev Fourier Series 19 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.l0 Asymptotic Calculation of Fourier Coefficients.·..·.·.·.. 5 2.11 Convergence Theory:Chebyshev Polynomials 6 2.12 Last Coefficient Rule-of-Thumb.................... 50 2.l3 Convergence Theory for Legendre Polynomials.·.·.····.. 2.l4 Quasi-Sinusoidal Rule of Thumb..,.·.,.················· 54 2.l5 Witch of Agnesi Rule--of-Thumb.··...···········:.·····. 2.16 Boundary Layer Rule-of-Thumb 57 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 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 iiⅲ 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 4.2 Polynomial interpolation............ 8 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 98 5.2 Whittaker Cardinal or "Sinc"Functions... 9 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.. 44 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.l0 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 3 The Power Method.......··...·.···········. 145 7.9 Inverse Power Method....·.·················: 149
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 155 8 Symmetry Parity 159 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 g.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 ntroduction...············- 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 l0.6 Generalized FFTs and Multipole Methods.············ 195 10.7Off-Grid Interpolation..............·.·....·.... 198 l0.8 Fast Fourier Transform:Practical Matters···················· 200 l09 Summary......·...·...·.....。。·.·..·。· 200 11 Aliasing,Spectral Blocking,Blow-Up 202 11.1 Introduction.............. 202 11.2 Aliasing and Equality-on-the-Grid 202 ll.3“2h-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 1l.9 Summary...··· 218 12 Implicit Schemes the Slow Manifold 222 12.1 Introduction...············· 222 12.2 Dispersion and Amplitude Errors.... 224 l2.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.l0 nitialization.·················· 239
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 12.11The Method of Multiple Scales(Baer-Tribbia) 241 12.12Nonlinear Galerkin Methods 243 l2.l3 Weaknesses 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 ntroduction.......··...·.。.....···············- 252 l3.2 Fractional Steps for Diffusion.·.·.·.··.················· 255 l3.3 Pitfalls in Splitting.I:Boundary Conditions.·.··············· 256 13.4 Pitfalls in Splitting,II:Consistency 258 l3.5 Operator Theory of Time-Stepping......·.·.·············· 259 l3.6 High Order Splitting.....·.······· 261 l3.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 l4.10Of-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.13 Summary.··················· 289 15 Matrix-Solving Methods 290 15.1 ntroduction....··.....·.···················· 290 l5.2 Stationary One-Step Iterations........·..···············. 291 15.3 Preconditioning:Finite Difference 293 15.4 Computing Iterates:FFT/Matrix Multiplication 297 l5.5 Alternative Preconditioners.................·.···.····- 299 l5.6 Raising the Order Through Preconditioning...,·.·····. 301 l5.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 l5.11 Direct Methods for Separable PDE's················ 314 15.12Fast Iterations for Almost Separable PDEs............. 317 15.13Positive Definite and Indefinite Matrices.............. 318 l5.l4 Preconditioned Newton Flow.....,.···.··············· 320 l5.15 Summary&Proverbs...·.···················· 322
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