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