Geometric Numerical Integration

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

• ISBN13: 9783540306634
• ISBN10: 3540306633
• Edition: 2nd
• Format: Hardcover
• Copyright: 2006-05-16
• 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. The second edition is substantially revised and enlarged, with many improvements in the presentation and additions concerning in particular non-canonical Hamiltonian systems, highly oscillatory mechanical systems, and the dynamics of multistep methods.

Table of Contents

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