Ⅰ．Examples and Numerical Experiments 1
Ⅰ.1 First Problems and Methods 1
Ⅰ.1.1 The Lotka-Volterra Model 1
Ⅰ.1.2 First Numerical Methods 3
Ⅰ.1.3 The Pendulum as a Hamiltonian System 4
Ⅰ.1.4 The St？rmer-Verlet Scheme 7
Ⅰ.2 The Kepler Problem and the Outer Solar System 8
Ⅰ.2.1 Angular Momentum and Kepler's Second Law 9
Ⅰ.2.2 Exact Integration of the Kepler Problem 10
Ⅰ.2.3 Numerical Integration of the Kepler Problem 12
Ⅰ.2.4 The Outer Solar System 13
Ⅰ.3 The Hénon-Heiles Model 15
Ⅰ.4 Molecular Dynamics 18
Ⅰ.5 Highly Oscillatory Problems 21
Ⅰ.5.1 A Fermi-Pasta-Ulam Problem 21
Ⅰ.5.2 Application of Classical Integrators 23
Ⅰ.6 Exercises 24
Ⅱ．Numerical Integrators 27
Ⅱ.1 Runge-Kutta and Collocation Methods 27
Ⅱ.1.1 Runge-Kutta Methods 28
Ⅱ.1.2 Collocation Methods 30
Ⅱ.1.3 Gauss and Lobatto Collocation 34
Ⅱ.1.4 Discontinuous Collocation Methods 35
Ⅱ.2 Partitioned Runge-Kutta Methods 38
Ⅱ.2.1 Definition and First Examples 38
Ⅱ.2.2 Lobatto ⅢA-ⅢB Pairs 40
Ⅱ.2.3 Nystr？m Methods 41
Ⅱ.3 The Adjoint of a Method 42
Ⅱ.4 Composition Methods 43
Ⅱ.5 Splitting Methods 47
Ⅱ.6 Exercises 50
Ⅲ．Order Conditions,Trees and B-Series 51
Ⅲ.1 Runge-Kutta Order Conditions and B-Series 51
Ⅲ.1.1 Derivation of the Order Conditions 51
Ⅲ.1.2 B-Series 56
Ⅲ.1.3 Composition of Methods 59
Ⅲ.1.4 Composition of B-Series 61
Ⅲ.1.5 The Butcher Group 64
Ⅲ.2 Order Conditions for Partitioned Runge-Kutta Methods 66
Ⅲ.2.1 Bi-Coloured Trees and P-Series 66
Ⅲ.2.2 Order Conditions for Partitioned Runge-Kutta Methods 68
Ⅲ.2.3 OrderConditions for Nystr？m Methods 69
Ⅲ.3 Order Conditions for Composition Methods 71
Ⅲ.3.1 Introduction 71
Ⅲ.3.2 The General Case 73
Ⅲ.3.3 Reduction of the Order Conditions 75
Ⅲ.3.4 Order Conditions for Splitting Methods 80
Ⅲ.4 The Baker-Campbell-Hausdorff Formula 83
Ⅲ.4.1 Derivative of the Exponential and Its Inverse 83
Ⅲ.4.2 The BCH Formula 84
Ⅲ.5 Order Conditions via the BCH Formula 87
Ⅲ.5.1 Calculus of Lie Derivatives 87
Ⅲ.5.2 Lie Brackets and Commutativity 89
Ⅲ.5.3 Splitting Methods 91
Ⅲ.5.4 Composition Methods 92
Ⅲ.6 Exercises 95
Ⅳ．Conservation of First Integrals and Methods on Manifolds 97
Ⅳ.1 Examples of First Integrals 97
Ⅳ.2 Quadratic Invariants 101
Ⅳ.2.1 Runge-Kutta Methods 101
Ⅳ.2.2 Partitioned Runge-Kutta Methods 102
Ⅳ.2.3 Nystr？m Methods 104
Ⅳ.3 Polynomial Invariants 105
Ⅳ.3.1 The Determinant as a First Integral 105
Ⅳ.3.2 Isospectral Flows 107
Ⅳ.4 Projection Methods 109
Ⅳ.5 Numerical Methods Based on Local Coordinates 113
Ⅳ.5.1 Manifolds and the Tangent Space 114
Ⅳ.5.2 Differential Equations on Manifolds 115
Ⅳ.5.3 Numerical Integrators on Manifolds 116
Ⅳ.6 Differential Equations on Lie Groups 118
Ⅳ.7 Methods Based on the Magnus Series Expansion 121
Ⅳ.8 Lie Group Methods 123
Ⅳ.8.1 Crouch-Grossman Methods 124
Ⅳ.8.2 Munthe-Kaas Methods 125
Ⅳ.8.3 Further Coordinate Mappings 128
Ⅳ.9 Geometric Numerical Integration Meets Geometric Numerical Linear Algebra 131
Ⅳ.9.1 Numerical Integration on the Stiefel Manifold 131
Ⅳ.9.2 Differential Equations on the Grassmann Manifold 135
Ⅳ.9.3 Dynamical Low-Rank Approximation 137
Ⅳ.10 Exercises 139
Ⅴ．Symmetric Integration and Reversibility 143
Ⅴ.1 Reversible Differential Equations and Maps 143
Ⅴ.2 Symmetric Runge-Kutta Methods 146
Ⅴ.2.1 Collocation and Runge-Kutta Methods 146
Ⅴ.2.2 Partitioned Runge-Kutta Methods 148
Ⅴ.3 Symmetric Composition Methods 149
Ⅴ.3.1 Symmetric Composition of First Order Methods 150
Ⅴ.3.2 Symmetric Composition of Symmetric Methods 154
Ⅴ.3.3 Effective Order and Processing Methods 158
Ⅴ.4 Symmetric Methods on Manifolds 161
Ⅴ.4.1 Symmetric Projection 161
Ⅴ.4.2 Symmetric Methods Based on Local Coordinates 166
Ⅴ.5 Energy-Momentum Methods and Discrete Gradients 171
Ⅴ.6 Exercises 176
Ⅵ．Symplectic Integration of Hamiltonian Systems 179
Ⅵ.1 Hamiltonian Systems 180
Ⅵ.1.1 Lagrange's Equations 180
Ⅵ.1.2 Hamilton's Canonical Equations 181
Ⅵ.2 Symplectic Transformations 182
Ⅵ.3 First Examples of Symplectic Integrators 187
Ⅵ.4 Symplectic Runge-Kutta Methods 191
Ⅵ.4.1 Criterion of Symplecticity 191
Ⅵ.4.2 Connection Between Symplectic and Symmetric Methods 194
Ⅵ.5 Generating Functions 195
Ⅵ.5.1 Existence of Generating Functions 195
Ⅵ.5.2 Generating Function for Symplectic Runge-Kutta Methods 198
Ⅵ.5.3 The Hamilton-Jacobi Partial Differential Equation 200
Ⅵ.5.4 Methods Based on Generating Functions 203
Ⅵ.6 Variational Integrators 204
Ⅵ.6.1 Hamilton's Principle 204
Ⅵ.6.2 Discretization of Hamilton's Principle 206
Ⅵ.6.3 Symplectic Partitioned Runge-Kutta Methods Revisited 208
Ⅵ.6.4 Noether's Theorem 210
Ⅵ.7 Characterization of Symplectic Methods 212
Ⅵ.7.1 B-Series Methods Conserving Quadratic First Integrals 212
Ⅵ.7.2 Characterization of Symplectic P-Series（and B-Series） 217
Ⅵ.7.3 Irreducible Runge-Kutta Methods 220
Ⅵ.7.4 Characterization of Irreducible Symplectic Methods 222
Ⅵ.8 Conjugate Symplecticity 222
Ⅵ.8.1 Examples and Order Conditions 223
Ⅵ.8.2 Near Conservation of Quadratic First Integrals 225
Ⅵ.9 Volume Preservation 227
Ⅵ.10 Exercises 233
Ⅶ．Non-Canonical Hamiltonian Systems 237
Ⅶ.1 Constrained Mechanical Systems 237
Ⅶ.1.1 Introduction and Examples 237
Ⅶ.1.2 Hamiltonian Formulation 239
Ⅶ.1.3 A Symplectic First Order Method 242
Ⅶ.1.4 SHAKE and RATTLE 245
Ⅶ.1.5 The Lobatto ⅢA-ⅢB Pair 247
Ⅶ.1.6 Splitting Methods 252
Ⅶ.2 Poisson Systems 254
Ⅶ.2.1 Canonical Poisson Structure 254
Ⅶ.2.2 General Poisson Structures 256
Ⅶ.2.3 Hamiltonian Systems on Symplectic Submanifolds 258
Ⅶ.3 The Darboux-Lie Theorem 261
Ⅶ.3.1 Commutativity of Poisson Flows and Lie Brackets 261
Ⅶ.3.2 Simultaneous Linear Partial Differential Equations 262
Ⅶ.3.3 Coordinate Changes and the Darboux-Lie Theorem 265
Ⅶ.4 Poisson Integrators 268
Ⅶ.4.1 Poisson Maps and Symplectic Maps 268
Ⅶ.4.2 Poisson Integrators 270
Ⅶ.4.3 Integrators Based on the Darboux-Lie Theorem 272
Ⅶ.5 Rigid Body Dynamics and Lie-Poisson Systems 274
Ⅶ.5.1 History of the Euler Equations 275
Ⅶ.5.2 Hamiltonian Formulation of Rigid Body Motion 278
Ⅶ.5.3 Rigid Body Integrators 280
Ⅶ.5.4 Lie-poisson Systems 286
Ⅶ.5.5 Lie-Poisson Reduction 289
Ⅶ.6 Reduced Models of Quantum Dynamics 293
Ⅶ.6.1 Hamiltonian Structure of the Schr？dinger Equation 293
Ⅶ.6.2 The Dirac-Frenkel Variational Principle 295
Ⅶ.6.3 Gaussian Wavepacket Dynamics 296
Ⅶ.6.4 A Splitting Integrator for Gaussian Wavepackets 298
Ⅶ.7 Exercises 301
Ⅷ．Structure-Preserving Implementation 303
Ⅷ.1 Dangers of Using Standard Step Size Control 303
Ⅷ.2 Time Transformations 306
Ⅷ.2.1 Symplectic Integration 306
Ⅷ.2.2 Reversible Integration 309
Ⅷ.3 Structure-Preserving Step Size Control 310
Ⅷ.3.1 Proportional,Reversible Controllers 310
Ⅷ.3.2 Integrating,Reversible Controllers 314
Ⅷ.4 Multiple Time Stepping 316
Ⅷ.4.1 Fast-Slow Splitting：the Impulse Method 317
Ⅷ.4.2 Averaged Forces 319
Ⅷ.5 Reducing Rounding Errors 322
Ⅷ.6 Implementation of Implicit Methods 325
Ⅷ.6.1 Starting Approximations 326
Ⅷ.6.2 Fixed-Point Versus Newton Iteration 330
Ⅷ.7 Exercises 335
Ⅸ．Backward Error Analysis and Structure Preservation 337
Ⅸ.1 Modified Differential Equation-Examples 337
Ⅸ.2 Modified Equations of Symmetric Methods 342
Ⅸ.3 Modified Equations of Symplectic Methods 343
Ⅸ.3.1 Existence of a Local Modified Hamiltonian 343
Ⅸ.3.2 Existence of a Global Modified Hamiltonian 344
Ⅸ.3.3 Poisson Integrators 347
Ⅸ.4 Modified Equations of Splitting Methods 348
Ⅸ.5 Modified Equations of Methods on Manifolds 350
Ⅸ.5.1 Methods on Manifolds and First Integrals 350
Ⅸ.5.2 Constrained Hamiltonian Systems 352
Ⅸ.5.3 Lie-Poisson Integrators 354
Ⅸ.6 Modified Equations for Variable Step Sizes 356
Ⅸ.7 Rigorous Estimates-Local Error 358
Ⅸ.7.1 Estimation of the Derivatives of the Numerical Solution 360
Ⅸ.7.2 Estimation of the Coefficients of the Modified Equation 362
Ⅸ.7.3 Choice of N and the Estimation of the Local Error 364
Ⅸ.8 Long-Time Energy Conservation 366
Ⅸ.9 Modified Equation in Terms of Trees 369
Ⅸ.9.1 B-Series ofthe Modified Equation 369
Ⅸ.9.2 Elementary Hamiltonians 373
Ⅸ.9.3 Modified Hamiltonian 375
Ⅸ.9.4 First Integrals Close to the Hamiltonian 375
Ⅸ.9.5 Energy Conservation：Examples and Counter-Examples 379
Ⅸ.10 Extension to Partitioned Systems 381
Ⅸ.10.1 P-Series of the Modified Equation 381
Ⅸ.10.2 Elementary Hamiltonians 384
Ⅸ.11 Exercises 386
Ⅹ．Hamiltonian Perturbation Theory and Symplectic Integrators 389
Ⅹ.1 Completely Integrable Hamiltonian Systems 390
Ⅹ.1.1 Local Integration by Quadrature 390
Ⅹ.1.2 Completely Integrable Systems 393
Ⅹ.1.3 Action-Angle Variables 397
Ⅹ.1.4 Conditionally Periodic Flows 399
Ⅹ.1.5 The Toda Lattice-an Integrable System 402
Ⅹ.2 Transformations in the Perturbation Theory for Integrable Systems 404
Ⅹ.2.1 The Basic Scheme of Classical Perturbation Theory 405
Ⅹ.2.2 Lindstedt-Poincaré Series 406
Ⅹ.2.3 Kolmogorov's Iteration 410
Ⅹ.2.4 Birkhoff Normalization Near an Invariant Torus 412
Ⅹ.3 Linear Error Growth and Near-Preservation of First Integrals 413
Ⅹ.4 Near-Invariant Tori on Exponentially Long Times 417
Ⅹ.4.1 Estimates of Perturbation Series 417
Ⅹ.4.2 Near-Invariant Tori of Perturbed Integrable Systems 421
Ⅹ.4.3 Near-Invariant Tori of Symplectic Integrators 422
Ⅹ.5 Kolmogorov's Theorem on Invariant Tori 423
Ⅹ.5.1 Kolmogorov's Theorem 423
Ⅹ.5.2 KAM Tori under Symplectic Discretization 428
Ⅹ.6 Invariant Tori of Symplectic Maps 430
Ⅹ.6.1 A KAM Theorem for Symplectic Near-Identity Maps 431
Ⅹ.6.2 Invariant Tori of Symplectic Integrators 433
Ⅹ.6.3 Strongly Non-Resonant Step Sizes 433
Ⅹ.7 Exercises 434
Ⅺ．Reversible Perturbation Theory and Symmetric Integrators 437
Ⅺ.1 Integrable Reversible Systems 437
Ⅺ.2 Transformations in Reversible Perturbation Theory 442
Ⅺ.2.1 The Basic Scheme of Reversible Perturbation Theory 443
Ⅺ.2.2 Reversible Perturbation Series 444
Ⅺ.2.3 Reversible KAM Theory 445
Ⅺ.2.4 Reversible Birkhoff-Type Normalization 447
Ⅺ.3 Linear Error Growth and Near-Preservation of First Integrals 448
Ⅺ.4 Invariant Tori underReversible Discretization 451
Ⅺ.4.1 Near-Invariant Tori over Exponentially Long Times 451
Ⅺ.4.2 A KAM Theorem for Reversible Near-Identity Maps 451
Ⅺ.5 Exercises 453
Ⅻ．Dissipatively Perturbed Hamiltonian and Reversible Systems 455
Ⅻ.1 Numerical Experiments with Van der Pol's Equation 455
Ⅻ.2 Averaging Transformations 458
Ⅻ.2.1 The Basic Scheme of Averaging 458
Ⅻ.2.2 Perturbation Series 459
Ⅻ.3 Attractive Invariant Manifolds 460
Ⅻ.4 Weakly Attractive Invariant Tori of Perturbed Integrable Systems 464
Ⅻ.5 Weakly Attractive Invariant Tori of Numerical Integrators 465
Ⅻ.5.1 Modified Equations of Perturbed Differential Equations 466
Ⅻ.5.2 Symplectic Methods 467
Ⅻ.5.3 Symmetric Methods 469
Ⅻ.6 Exercises 469
ⅩⅢ．Oscillatory Differential Equations with Constant High Frequencies 471
ⅩⅢ.1 Towards Longer Time Steps in Solving Oscillatory Equations of Motion 471
ⅩⅢ.1.1 The St？rmer-Verlet Method vs.Multiple Time Scales 472
ⅩⅢ.1.2 Gautschi's and Deuflhard's Trigonometric Methods 473
ⅩⅢ.1.3 The Impulse Method 475
ⅪⅢ.1.4 The Mollified Impulse Method 476
ⅩⅢ.1.5 Gautschi's Method Revisited 477
ⅩⅢ.1.6 Two-Force Methods 478
ⅩⅢ.2 A Nonlinear Model Problem and Numerical Phenomena 478
ⅩⅢ.2.1 Time Scales in the Fermi-Pasta-Ulam Problem 479
ⅩⅢ.2.2 Numerical Methods 481
ⅩⅢ.2.3 Accuracy Comparisons 482
ⅩⅢ.2.4 Energy Exchange between Stiff Components 483
ⅩⅢ.2.5 Near-Conservation of Total and Oscillatory Energy 484
ⅩⅢ.3 Principal Terms of the Modulated Fourier Expansion 486
ⅩⅢ.3.1 Decomposition of the Exact Solution 486
ⅩⅢ.3.2 Decomposition of the Numerical Solution 488
ⅩⅢ.4 Accuracy and Slow Exchange 490
ⅩⅢ.4.1 Convergence Properties on Bounded Time Intervals 490
ⅩⅢ.4.2 Intra-Oscillatory and Oscillatory-Smooth Exchanges 494
ⅩⅢ.5 Modulated Fourier Expansions 496
ⅩⅢ.5.1 Expansion of the Exact Solution 496
ⅩⅢ.5.2 Expansion of the Numerical Solution 498
ⅩⅢ.5.3 Expansion of the Velocity Approximation 502
ⅩⅢ.6 Almost-Invariants of the Modulated Fourier Expansions 503
ⅪⅢ.6.1 The Hamiltonian of the Modulated Fourier Expansion 503
ⅩⅢ.6.2 A Formal Invariant Close to the Oscillatory Energy 505
ⅩⅢ.6.3 Almost-Invariants of the Numerical Method 507
ⅩⅢ.7 Long-Time Near-Conservation of Total and Oscillatory Energy 510
ⅩⅢ.8 Energy Behaviour of the St？rmer-Verlet Method 513
ⅩⅢ.9 Systems with Several Constant Frequencies 516
ⅩⅢ.9.1 Oscillatory Energies and Resonances 517
ⅩⅢ.9.2 Multi-Frequency Modulated Fourier Expansions 519
ⅩⅢ.9.3 Almost-Invariants of the Modulation System 521
ⅩⅢ.9.4 Long-Time Near-Conservation of Total and Oscillatory Energies 524
ⅩⅢ.10 Systems with Non-Constant Mass Matrix 526
ⅩⅢ.11 Exercises 529
Ⅹ．Oscillatory Differential Equations with Varying High Frequencies 531
ⅩⅣ.1 Linear Systems with Time-Dependent Skew-Hermitian Matrix 531
ⅩⅣ.1.1 Adiabatic Transformation and Adiabatic Invariants 531
ⅩⅣ.1.2 Adiabatic Integrators 536
ⅩⅣ.2 Mechanical Systems with Time-Dependent Frequencies 539
ⅩⅣ.2.1 Canonical Transformation to Adiabatic Variables 540
ⅩⅣ.2.2 Adiabatic Integrators 547
ⅩⅣ.2.3 Error Analysis of the Impulse Method 550
ⅩⅣ.2.4 Error Analysis of the Mollified Impulse Method 554
ⅩⅣ.3 Mechanical Systems with Solution-Dependent Frequencies 555
ⅩⅣ.3.1 Constraining Potentials 555
ⅩⅣ.3.2 Transformation to Adiabatic Variables 558
ⅩⅣ.3.3 Integrators in Adiabatic Variables 563
ⅩⅣ.3.4 Analysis of Multiple Time-Stepping Methods 564
ⅩⅣ.4 Exercises 564
ⅩⅤ．Dynamics of Multistep Methods 567
ⅩⅤ.1 Numerical Methods and Experiments 567
ⅩⅤ.1.1 Linear Multistep Methods 567
ⅩⅤ.1.2 Multistep Methods for Second Order Equations 569
ⅩⅤ.1.3 Partitioned Multistep Methods 572
ⅩⅤ.2 The Underlying One-Step Method 573
ⅩⅤ.2.1 Strictly Stable Multistep methods 573
ⅩⅤ.2.2 Formal Analysis for Weakly Stable Methods 575
ⅩⅤ.3 Backward Error Analysis 576
ⅩⅤ.3.1 Modified Equation for Smooth Numerical Solutions 576
ⅩⅤ.3.2 Parasitic Modified Equations 579
ⅩⅤ.4 Can Multistep Methods be Symplectic？ 585
ⅩⅤ.4.1 Non-Symplecticity of the Underlying One-Step Method 585
ⅩⅤ.4.2 Symplecticity in the Higher-Dimensional Phase Space 587
ⅩⅤ.4.3 Modified Hamiltonian of Multistep Methods 589
ⅩⅤ.4.4 Modified Quadratic First Integrals 591
ⅩⅤ.5 Long-Term Stability 592
ⅩⅤ.5.1 Role of Growth Parameters 592
ⅩⅤ.5.2 Hamiltonian of the Full Modified System 594
ⅩⅤ.5.3 Long-Time Bounds for Parasitic Solution Components 596
ⅩⅤ.6 Explanation of the Long-Time Behaviour 600
ⅩⅤ.6.1 Conservation of Energy and Angular Momentum 600
ⅩⅤ.6.2 Linear Error Growth for Integrable Systems 601
ⅩⅤ.7 Practical Considerations 602
ⅩⅤ.7.1 Numerical Instabilities and Resonances 602
ⅩⅤ.7.2 Extension to Variable Step Sizes 605
ⅩⅤ.8 Multi-Value or General Linear Methods 609
ⅩⅤ.8.1 Underlying One-Step Method and Backward Error Analysis 609
ⅩⅤ.8.2 Symplecticity and Symmetry 611
ⅩⅤ.8.3 Growth Parameters 614
ⅩⅤ.9 Exercises 615
Bibliography 617
Index 637