Geometric Numerical Integration : Structure-Preserving Algorithms for Ordinary Differential Equations

by Hairer, Ernst; Lubich, Christian; Wanner, Gerhard

• ISBN13: 9783540430032
• ISBN10: 3540430032
• Format: Hardcover
• Copyright: 2002-06-01
• Publisher: Springer Verlag

Summary

Numerical methods that preserve properties of Hamiltonian systems, reversible systems, differential equations on manifolds and problems with highly oscillatory solutions are the subject of this book. A complete self-contained theory of symplectic and symmetric methods, which include Runge-Kutta, composition, splitting, multistep and various specially designed integrators, is presented and their construction and practical merits are discussed. The long-time behaviour of the numerical solutions is studied using a backward error analysis (modified equations) combined with KAM theory. The book is illustrated by many figures, it treats applications from physics and astronomy and contains many numerical experiments and comparisons of different approaches.

Table of Contents

Examples and Numerical Experiments	1	(22)
Two - Dimensional Problems	1	(6)
The Lotka-Volterra Model	1	(3)
Hamiltonian Systems - the Pendulum	4	(3)
The Kepler Problem and the Outer Solar System	7	(5)
Exact Integration of the Kepler Problem	7	(2)
Numerical Integration of the Kepler Problem	9	(1)
The Outer Solar System	10	(2)
Molecular Dynamics	12	(4)
The Stormer/Verlet Scheme	13	(2)
Numerical Experiments	15	(1)
Highly Oscillatory Problems	16	(4)
A Fermi-Pasta-Ulam Problem	17	(1)
Application of Classical Integrators	18	(2)
Exercises	20	(3)
Numerical Integrators	23	(24)
Runge-Kutta and Collocation Methods	23	(11)
Runge-Kutta Methods	24	(2)
Collocation Methods	26	(4)
Gauss and Lobatto Collocation	30	(1)
Discontinuous Collocation Methods	31	(3)
Partitioned Runge-Kutta Methods	34	(4)
Definition and First Examples	34	(2)
Lobatto IIIA - IIIB Pairs	36	(1)
Nystrom Methods	37	(1)
The Adjoint of a Method	38	(1)
Composition Methods	39	(2)
Splitting Methods	41	(5)
Exercises	46	(1)
Order Conditions, Trees and B-Series	47	(46)
Runge-Kutta Order Conditions and B-Series	47	(15)
Derivation of the Order Conditions	47	(5)
B-Series	52	(3)
Composition of Methods	55	(2)
Composition of B-Series	57	(3)
The Butcher Group	60	(2)
Order Conditions for Partitioned Runge-Kutta Methods	62	(5)
Bi-Coloured Trees and P-Series	62	(2)
Order Conditions for Partitioned Runge-Kutta Methods	64	(1)
Order Conditions for Nystrom Methods	65	(2)
Order Conditions for Composition Methods	67	(11)
Introduction	67	(2)
The General Case	69	(2)
Reduction of the Order Conditions	71	(5)
Order Conditions for Splitting Methods	76	(2)
The Baker-Campbell-Hausdorff Formula	78	(5)
Derivative of the Exponential and Its Inverse	78	(2)
The BCH Formula	80	(3)
Order Conditions via the BCH Formula	83	(7)
Calculus of Lie Derivatives	83	(2)
Lie Brackets and Commutativity	85	(1)
Splitting Methods	86	(2)
Composition Methods	88	(2)
Exercises	90	(3)
Conservation of First Integrals and Methods on Manifolds	93	(38)
Examples of First Integrals	93	(4)
Quadratic Invariants	97	(4)
Runge-Kutta Methods	97	(1)
Partitioned Runge-Kutta Methods	98	(2)
Nystrom Methods	100	(1)
Polynomial Invariants	101	(4)
The Determinant as a First Integral	101	(2)
Isospectral Flows	103	(2)
Projection Methods	105	(5)
Numerical Methods Based on Local Coordinates	110	(5)
Manifolds and the Tangent Space	110	(2)
Differential Equations on Manifolds	112	(1)
Numerical Integrators on Manifolds	112	(3)
Differential Equations on Lie Groups	115	(3)
Methods Based on the Magnus Series Expansion	118	(3)
Lie Group Methods	121	(7)
Crouch-Grossman Methods	121	(2)
Munthe-Kaas Methods	123	(2)
Further Coordinate Mappings	125	(3)
Exercises	128	(3)
Symmetric Integration and Reversibility	131	(36)
Reversible Differential Equations and Maps	131	(3)
Symmetric Runge-Kutta Methods	134	(3)
Collocation and Runge-Kutta Methods	134	(2)
Partitioned Runge-Kutta Methods	136	(1)
Symmetric Composition Methods	137	(12)
Symmetric Composition of First Order Methods	138	(4)
Symmetric Composition of Symmetric Methods	142	(4)
Effective Order and Processing Methods	146	(3)
Symmetric Methods on Manifolds	149	(10)
Symmetric Projection	149	(5)
Symmetric Methods Based on Local Coordinates	154	(5)
Energy - Momentum Methods and Discrete Gradients	159	(5)
Exercises	164	(3)
Symplectic Integration of Hamiltonian Systems	167	(42)
Hamiltonian Systems	168	(2)
Lagrange's Equations	168	(1)
Hamilton's Canonical Equations	169	(1)
Symplectic Transformations	170	(5)
First Examples of Symplectic Integrators	175	(3)
Symplectic Runge-Kutta Methods	178	(4)
Criterion of Symplecticity	178	(3)
Connection Between Symplectic and Symmetric Methods	181	(1)
Generating Functions	182	(9)
Existence of Generating Functions	182	(2)
Generating Function for Symplectic Runge-Kutta Methods	184	(2)
The Hamilton-Jacobi Partial Differential Equation	186	(3)
Methods Based on Generating Functions	189	(2)
Variational Integrators	191	(8)
Hamilton's Principle	191	(1)
Discretization of Hamilton's Principle	192	(3)
Symplectic Partitioned Runge-Kutta Methods Revisited	195	(2)
Noether's Theorem	197	(2)
Characterization of Symplectic Methods	199	(7)
Symplectic P-Series (and B-Series)	199	(3)
Irreducible Runge-Kutta Methods	202	(1)
Characterization of Irreducible Symplectic Methods	203	(1)
Conjugate Symplecticity	204	(2)
Exercises	206	(3)
Further Topics in Structure Preservation	209	(46)
Constrained Mechanical Systems	209	(17)
Introduction and Examples	209	(2)
Hamiltonian Formulation	211	(2)
A Symplectic First Order Method	213	(3)
SHAKE and RATTLE	216	(2)
The Lobatto IIIA - IIIB Pair	218	(6)
Splitting Methods	224	(2)
Poisson Systems	226	(22)
Canonical Poisson Structure	226	(2)
General Poisson Structures	228	(3)
Simultaneous Linear Partial Differential Equations	231	(3)
Coordinate Changes and the Darboux-Lie Theorem	234	(3)
Poisson Integrators	237	(5)
Lie-Poisson Systems	242	(6)
Volume Preservation	248	(5)
Exercises	253	(2)
Structure-Preserving Implementation	255	(32)
Dangers of Using Standard Step Size Control	255	(3)
Reversible Adaptive Step Size Selection	258	(3)
Time Transformations	261	(5)
Symplectic Integration	261	(3)
Reversible Integration	264	(2)
Multiple Time Stepping	266	(6)
Fast-Slow Splitting: the Impulse Method	266	(3)
Averaged Forces	269	(3)
Reducing Rounding Errors	272	(3)
Implementation of Implicit Methods	275	(9)
Starting Approximations	275	(4)
Fixed-Point Versus Newton Iteration	279	(5)
Exercises	284	(3)
Backward Error Analysis and Structure Preservation	287	(40)
Modified Differential Equation - Examples	287	(5)
Modified Equations of Symmetric Methods	292	(1)
Modified Equations of Symplectic Methods	293	(5)
Existence of a Local Modified Hamiltonian	293	(1)
Existence of a Global Modified Hamiltonian	294	(3)
Poisson Integrators	297	(1)
Modified Equations of Splitting Methods	298	(2)
Modified Equations of Methods on Manifolds	300	(3)
Modified Equations for Variable Step Sizes	303	(1)
Rigorous Estimates - Local Error	304	(8)
Estimation of the Derivatives of the Numerical Solution	306	(1)
Estimation of the Coefficients of the Modified Equation	307	(3)
Choice of N and the Estimation of the Local Error	310	(2)
Long-Time Energy Conservation	312	(2)
Modified Equation in Terms of Trees	314	(5)
B-Series of the Modified Equation	315	(2)
Extension to Partitioned Systems	317	(2)
Modified Hamiltonian	319	(6)
Elementary Hamiltonians	321	(3)
Characterization of Symplectic P-Series	324	(1)
Exercises	325	(2)
Hamiltonian Perturbation Theory and Symplectic Integrators	327	(48)
Completely Integrable Hamiltonian Systems	328	(14)
Local Integration by Quadrature	328	(3)
Completely Integrable Systems	331	(4)
Action-Angle Variables	335	(2)
Conditionally Periodic Flows	337	(3)
The Toda Lattice - an Integrable System	340	(2)
Transformations in the Perturbation Theory for Integrable Systems	342	(9)
The Basic Scheme of Classical Perturbation Theory	343	(1)
Lindstedt-Poincare Series	344	(4)
Kolmogorov's Iteration	348	(2)
Birkhoff Normalization Near an Invariant Torus	350	(1)
Linear Error Growth and Near-Preservation of First Integrals	351	(4)
Near-Invariant Tori on Exponentially Long Times	355	(6)
Estimates of Perturbation Series	355	(4)
Near-Invariant Tori of Perturbed Integrable Systems	359	(1)
Near-Invariant Tori of Symplectic Integrators	360	(1)
Kolmogorov's Theorem on Invariant Tori	361	(7)
Kolmogorov's Theorem	361	(5)
KAM Tori under Symplectic Discretization	366	(2)
Invariant Tori of Symplectic Maps	368	(4)
A KAM Theorem for Symplectic Near-Identity Maps	369	(2)
Invariant Tori of Symplectic Integrators	371	(1)
Strongly Non-Resonant Step Sizes	371	(1)
Exercises	372	(3)
Reversible Perturbation Theory and Symmetric Integrators	375	(16)
Integrable Reversible Systems	375	(4)
Transformations in Reversible Perturbation Theory	379	(5)
The Basic Scheme of Reversible Perturbation Theory	379	(1)
Reversible Perturbation Series	380	(2)
Reversible KAM Theory	382	(2)
Reversible Birkhoff Type Normalization	384	(1)
Linear Error Growth and Near-Preservation of First Integrals	384	(2)
Invariant Tori under Reversible Discretization	386	(3)
Near-Invariant Tori over Exponentially Long Times	386	(1)
A KAM Theorem for Reversible Near-Identity Maps	387	(2)
Exercises	389	(2)
Dissipatively Perturbed Hamiltonian and Reversible Systems	391	(16)
Numerical Experiments with Van der Pol's Equation	391	(3)
Averaging Transformations	394	(2)
The Basic Scheme of Averaging	394	(1)
Perturbation Series	395	(1)
Attractive Invariant Manifolds	396	(4)
Weakly Attractive Invariant Tori of Perturbed Integrable Systems	400	(1)
Weakly Attractive Invariant Tori of Numerical Integrators	401	(4)
Modified Equations of Perturbed Differential Equations	402	(1)
Symplectic Methods	403	(2)
Symmetric Methods	405	(1)
Exercises	405	(2)
Highly Oscillatory Differential Equations	407	(48)
Towards longer Time Steps in Solving Oscillatory Differential Equations	407	(7)
The Stormer/Verlet Method vs. Multiple Time Scales	408	(1)
Gautschi's and Deuflhard's Trigonometric Methods	409	(2)
The Impulse Method	411	(1)
The Mollified Impulse Method	412	(1)
Gautschi's Method Revisited	413	(1)
Two-Force Methods	414	(1)
A Nonlinear Model Problem and Numerical Phenomena	414	(8)
Time Scales in the Fermi-Pasta-Ulam Problem	415	(1)
Numerical Methods	416	(2)
Accuracy Comparisons	418	(1)
Energy Exchange between Stiff Components	419	(1)
Near-Conservation of Total and Oscillatory Energy	420	(2)
Principal Terms of the Modulated Fourier Expansion	422	(4)
Decomposition of the Exact Solution	422	(2)
Decomposition of the Numerical Solution	424	(2)
Accuracy and Slow Exchange	426	(6)
Convergence Properties on Bounded Time Intervals	426	(5)
Intra-Oscillatory and Oscillatory-Smooth Exchanges	431	(1)
Modulated Fourier Expansions	432	(7)
Expansion of the Exact Solution	433	(2)
Expansion of the Numerical Solution	435	(3)
Expansion of the Velocity Approximation	438	(1)
Almost-Invariants of the Modulated Fourier Expansions	439	(8)
The Hamiltonian of the Modulated Fourier Expansion	440	(1)
Formal Invariant Close to the Oscillatory Energy	441	(2)
Almost-Invariants of the Numerical Method	443	(4)
Long-Time Near-Conservation of Total and Oscillatory Energy	447	(2)
Energy Behaviour of the Stormer/Verlet Method	449	(3)
Exercises	452	(3)
Dynamics of Multistep Methods	455	(38)
Numerical Methods and Experiments	455	(6)
Linear Multistep Methods	455	(2)
Multistep Methods for Second Order Equations	457	(2)
Partitioned Multistep Methods	459	(1)
Multi-Value or General Linear Methods	460	(1)
Related One-Step Methods	461	(9)
The Underlying One-Step Method	461	(2)
Formal Analysis for Weakly Stable Methods	463	(1)
Backward Error Analysis for Multistep Methods	464	(3)
Dynamics of Weakly Stable Methods	467	(1)
Invariant Manifold of the Augmented System	468	(2)
Can Multistep Methods be Symplectic?	470	(4)
Non-Symplecticity of the Underlying One-Step Method	470	(1)
Symplecticity in the Higher-Dimensional Phase Space	471	(3)
Symmetric Multi-Value Methods	474	(3)
Definition of Symmetry	474	(2)
A Useful Criterion for Symmetry	476	(1)
Stability of the Invariant Manifold	477	(13)
Partitioned General Linear Methods	477	(2)
The Linearized Augmented System	479	(2)
Dissipatively Perturbed Hamiltonian Systems	481	(2)
Numerical Instabilities and Resonances	483	(3)
Extension to Variable Step Sizes	486	(4)
Exercises	490	(3)
Bibliography	493	(16)
Index	509