This book is a substantially revised and expanded edition reflecting major developments in stochastic numerics since the first edition was published in 2004. The new topics, in particular, include mean-square and weak approximations in the case of nonglobally Lipschitz coefficients of Stochastic Differential Equations (SDEs) including the concept of rejecting trajectories; conditional probabilistic representations and their application to practical variance reduction using regression methods; multi-level Monte Carlo method; computing ergodic limits and additional classes of geometric integrators used in molecular dynamics; numerical methods for FBSDEs; approximation of parabolic SPDEs and nonlinear filtering problem based on the method of characteristics.
SDEs have many applications in the natural sciences and in finance. Besides, the employment of probabilistic representations together with the Monte Carlo technique allows us to reduce the solution of multi-dimensional problems for partial differential equations to the integration of stochastic equations. This approach leads to powerful computational mathematics that is presented in the treatise. Many special schemes for SDEs are presented. In the second part of the book numerical methods for solving complicated problems for partial differential equations occurring in practical applications, both linear and nonlinear, are constructed. All the methods are presented with proofs and hence founded on rigorous reasoning, thus giving the book textbook potential. An overwhelming majority of the methods are accompanied by the corresponding numerical algorithms which are ready for implementation in practice. The book addresses researchers and graduate students in numerical analysis, applied probability, physics, chemistry, and engineering as well as mathematical biology and financial mathematics.
Author(s): Grigori N. Milstein, Michael V. Tretyakov
Series: Scientific Computation
Edition: 2
Publisher: Springer Nature Switzerland AG
Year: 2021
Language: English
Pages: 736
Tags: Stochastic Differential Equations, SDEs, backward SDEs, ergodic limits, geometric integration, multi-level Monte Carlo methods, variance reduction, stochastic PDEs, stochastic Hamiltonian systems, Langevin equation, nonlinear parabolic equations, Cauchy problem, Strong and Weak Approximation for SDE
Preface to the Second Edition
Preface to the First Edition
Contents
Frequently Used Notation
1 Mean-Square Approximation for Stochastic Differential Equations
1.1 Fundamental Theorem on the Mean-Square Order of Convergence
1.1.1 Statement of the Theorem
1.1.2 Proof of the Fundamental Theorem
1.1.3 The Fundamental Theorem for Equations in the Sense of Stratonovich
1.1.4 Discussion
1.1.5 The Explicit Euler Method
1.1.6 Almost Sure Convergence
1.2 Methods Based on Taylor-Type Expansion
1.2.1 Taylor Expansion of Solutions of Ordinary Differential Equations
1.2.2 Wagner–Platen Expansion of Solutions of Stochastic Differential Equations
1.2.3 Construction of Explicit Methods
1.3 Implicit Mean-Square Methods
1.3.1 Construction of Drift-Implicit Methods
1.3.2 The Balanced Method
1.3.3 Fully Implicit Mean-Square Methods: The Main Idea
1.3.4 Convergence Theorem for Fully Implicit Methods
1.3.5 General Construction of Fully Implicit Methods
1.4 Nonglobally Lipschitz Conditions
1.5 Modeling of Ito Integrals
1.5.1 Ito Integrals Depending on a Single Noise and Methods of Order 3/2 and 2
1.5.2 Modeling Ito Integrals by the Rectangle and Trapezoidal Methods
1.5.3 Modeling Ito Integrals by the Fourier Method
1.6 Explicit and Implicit Methods of Order 3/2 for Systems with Additive Noise
1.6.1 Explicit Methods Based on Taylor-Type Expansion
1.6.2 Implicit Methods Based on Taylor-Type Expansion
1.6.3 Stiff Systems of Stochastic Differential Equations with Additive Noise. A-Stability
1.6.4 Runge–Kutta Type Methods
1.6.5 Two-Step Difference Methods
1.7 Numerical Schemes for Equations with Colored Noise
1.7.1 Explicit Schemes of Orders 2 and 5/2
1.7.2 Runge–Kutta Schemes
1.7.3 Implicit Schemes
2 Weak Approximation for Stochastic Differential Equations: Foundations
2.1 One-Step Approximation
2.1.1 Properties of Remainders and Ito Integrals
2.1.2 One-Step Approximations of Third Order
2.1.3 The Taylor Expansion of Expectations
2.2 Global Errors of Weak Approximations
2.2.1 The General Convergence Theorem
2.2.2 Runge–Kutta Type Methods
2.2.3 The Talay–Tubaro Extrapolation Method
2.2.4 Implicit Method
2.2.5 The Concept of Rejecting Exploding Trajectories for SDEs with Nonglobally Lipschitz Coefficients
2.3 Variance Reduction
2.3.1 The Method of Important Sampling
2.3.2 A Family of Probabilistic Representations for the Cauchy Problem for Parabolic PDEs and Variance Reduction by Control Variates and Combining Method
2.3.3 Pathwise Approach for Derivatives u/xi(s,x)
2.3.4 Variance Reduction for Boundary Value Problems
2.4 Conditional Probabilistic Representations and Practical Variance Reduction via Regression
2.4.1 Regression Method of Estimating Conditional Expectation
2.4.2 Conditional Probabilistic Representations for u(s,x) and u/xi(s,x)
2.4.3 Evaluating u(s,x)
2.4.4 Evaluating u/xi(s,x)
2.4.5 Evaluating u/xi(s,x) Using the Malliavin Integration by Parts
2.4.6 Two-Run Procedure
2.4.7 Examples
2.5 Quasi-Monte Carlo and Multi-level Monte Carlo Methods
2.5.1 Quasi-Monte Carlo Methods
2.5.2 Multi-level Monte Carlo Method
2.6 Random Number Generators
3 Weak Approximation for Stochastic Differential Equations: Special Cases
3.1 Weak Methods for Systems with Additive Noise
3.1.1 Second Order Methods
3.1.2 Main Lemmas for Third Order Methods
3.1.3 Construction of a Method of Order Three
3.2 Weak Schemes for Systems with Colored Noise
3.3 Application of Weak Methods to Computation of Wiener Integrals
3.3.1 The Trapezoidal, Rectangle, and Other Methods of Second Order
3.3.2 A Fourth-Order Runge–Kutta Method for Computing Wiener Integrals of Functionals of Exponential Type
3.4 Conditional Wiener Integrals
3.4.1 Explicit Runge–Kutta Method of Order Four for Conditional Wiener Integrals of Exponential-Type Functionals
3.4.2 Implicit Runge–Kutta Methods for Conditional Wiener Integrals of Exponential-Type Functionals
3.4.3 Functionals of a General Form
3.4.4 Integral-Type Functionals
3.4.5 Extension to the Case of Pinned Diffusions
3.5 Numerical Experiments
3.6 Illustration from Financial Mathematics
3.6.1 Evaluation of Greeks
3.6.2 Finite Difference Estimators for Deltas
3.6.3 Influence of the Error of Numerical Integration on Evaluating Deltas by Finite Differences
3.6.4 Influence of the Monte Carlo Error on Evaluating Deltas by Finite Differences
3.6.5 Some Extensions
4 Numerical Methods for SDEs with Small Noise
4.1 Mean-Square Approximations and Estimation of Their Errors
4.1.1 Construction of One-Step Mean-Square Approximation
4.1.2 Theorem on Mean-Square Global Estimate
4.1.3 Selection of Time Step h Depending on Parameter ε
4.1.4 (h,ε)-Approach Versus (ε,h)-Approach
4.2 Some Specific Mean-Square Methods for Systems with Small Noise
4.2.1 Taylor-Type Numerical Methods
4.2.2 Runge-Kutta-Type Methods
4.2.3 Implicit Methods
4.2.4 Stratonovich SDEs with Small Noise
4.2.5 Mean-Square Methods for Systems with Small Additive Noise
4.3 Numerical Tests of Mean-Square Methods
4.3.1 Simulation of the Lyapunov Exponent of a Linear System with Small Noise
4.3.2 Stochastic Model of a Laser
4.4 The Main Theorem on Error Estimation and General Approach …
4.5 Some Specific Weak Methods
4.5.1 Taylor-Type Methods
4.5.2 Runge-Kutta Methods
4.5.3 Weak Methods for Systems with Small Additive Noise
4.6 Expansion of the Global Error in Powers of h and
4.7 Reduction of the Monte Carlo Error
4.8 Simulation of the Lyapunov Exponent of a Linear System with Small Noise by Weak Methods
5 Geometric Integrators and Computing Ergodic Limits
5.1 Preservation of Symplectic Structure
5.2 Mean-Square Symplectic Methods for Stochastic Hamiltonian Systems
5.2.1 General Stochastic Hamiltonian Systems
5.2.2 Explicit Methods in the Case of Separable Hamiltonians
5.3 Mean-Square Symplectic Methods for Hamiltonian Systems with Additive Noise
5.3.1 The Case of a General Hamiltonian
5.3.2 The Case of Separable Hamiltonians
5.3.3 The Case of Hamiltonian H(t,p,q)=12pTM-1p+U(t,q)
5.4 Numerical Tests of Mean-Square Symplectic Methods
5.4.1 Kubo Oscillator
5.4.2 A Model for Synchrotron Oscillations of Particles in Storage Rings
5.4.3 Linear Oscillator with Additive Noise
5.5 Liouvillian Methods for Stochastic Systems Preserving Phase Volume
5.5.1 Liouvillian Methods for Partitioned Systems with Multiplicative Noise
5.5.2 Liouvillian Methods for a Volume-Preserving System with Additive Noise
5.6 Weak Symplectic Methods for Stochastic Hamiltonian Systems
5.6.1 Hamiltonian Systems with Multiplicative Noise
5.6.2 Hamiltonian Systems with Additive Noise
5.6.3 Numerical Tests
5.7 Quasi-symplectic Mean-Square Methods for Langevin-Type Equations
5.7.1 Langevin Equation: Linear Damping and Additive Noise
5.7.2 Langevin-Type Equation: Nonlinear Damping and Multiplicative Noise
5.8 Quasi-symplectic Weak Methods for Langevin-Type Equations
5.8.1 Langevin Equation: Linear Damping and Additive Noise
5.8.2 Langevin-Type Equation: Nonlinear Damping and Multiplicative Noise
5.8.3 Numerical Examples
5.9 Rigid Body Dynamics: Langevin and Stochastic Gradient Equations
5.9.1 Hamiltonian System
5.9.2 Langevin Equations
5.9.3 Stochastic Gradient System
5.9.4 Numerical Methods
5.10 Stochastic Landau-Lifshitz Equation
5.10.1 Model
5.10.2 Semi-implicit Numerical Methods
5.11 Ergodic Limits
5.11.1 Ensemble-Averaging Estimators
5.11.2 Time-Averaging Estimators
5.11.3 An Efficient Second-Order Accurate Scheme in Approximating Ergodic Limits
6 Simulation of Space and Space-Time Bounded Diffusions
6.1 Mean-Square Approximation for Autonomous SDEs …
6.1.1 Local Approximation of Diffusion in a Space Bounded Domain
6.1.2 Global Algorithm for Diffusion in a Space Bounded Domain
6.1.3 Simulation of the Exit Point Xx(τx)
6.2 Systems with Drift in a Space Bounded Domain
6.3 Space-Time Brownian Motion
6.3.1 Auxiliary Knowledge
6.3.2 Some Distributions for One-Dimensional Wiener Process
6.3.3 Simulation of the Exit Time and Exit Point of Wiener Process from a Cube
6.3.4 Simulation of the Exit Point of the Space-Time Brownian Motion from a Space-Time Parallelepiped with Cubic Base
6.4 Approximations for SDEs in a Space-Time Bounded Domain
6.4.1 Local Mean-Square Approximation in a Space-Time Bounded Domain
6.4.2 Global Algorithm in a Space-Time Bounded Domain
6.4.3 Approximation of the Exit Point ( τ,X(τ))
6.4.4 Simulation of Space-Time Brownian Motion with Drift
6.5 Numerical Examples
6.6 Mean-Square Approximation of Diffusion with Reflection
7 Random Walks for Linear Boundary Value Problems
7.1 Algorithms for Solving the Dirichlet Problem Based on Time-Step Control
7.1.1 Theorems on One-Step Approximation
7.1.2 Numerical Algorithms and Convergence Theorems
7.2 The Simplest Random Walk for the Dirichlet Problem for Parabolic Equations
7.2.1 The Algorithm of the Simplest Random Walk
7.2.2 Convergence Theorem
7.2.3 Other Random Walks
7.2.4 Numerical Tests
7.3 Random Walks for the Elliptic Dirichlet Problem
7.3.1 The Simplest Random Walk for Elliptic Equations
7.3.2 Other Methods for Elliptic Problems
7.3.3 Numerical Tests
7.4 Specific Random Walks for Elliptic Equations and Boundary Layer
7.4.1 Conditional Expectation of Ito Integrals Associated with Wiener Process in the Ball
7.4.2 Specific One-Step Approximations for Elliptic Equations
7.4.3 The Average Number of Steps
7.4.4 Numerical Algorithms and Convergence Theorems
7.5 Methods for Elliptic Equations with Small Parameter at Higher Derivatives
7.6 Methods for the Neumann Problem for Parabolic Equations
7.6.1 Methods Based on Changing Local Coordinates near the Boundary
7.6.2 Simple Random Walk with Symmetric Reflection
8 Probabilistic Approach to Numerical Solution of the Cauchy Problem for Nonlinear Parabolic Equations
8.1 Probabilistic Approach to Linear Parabolic Equations
8.2 Layer Methods for Semilinear Parabolic Equations
8.2.1 The Construction of Layer Methods
8.2.2 Convergence Theorem for a Layer Method
8.2.3 Numerical Algorithms
8.3 Multi-dimensional Case
8.3.1 Multi-dimensional Parabolic Equation
8.3.2 Probabilistic Approach to Reaction-Diffusion Systems
8.4 Numerical Examples
8.5 Probabilistic Approach to Semilinear Parabolic Equations with Small Parameter
8.5.1 Implicit Layer Method and Its Convergence
8.5.2 Explicit Layer Methods
8.5.3 Numerical Algorithms Based on Interpolation
8.6 High-Order Methods for Semilinear Equation with Small Constant …
8.6.1 Two-Layer Methods
8.6.2 Three-Layer Methods
8.7 Numerical Tests
8.7.1 The Burgers Equation with Small Viscosity
8.7.2 The Generalized FKPP-Equation with a Small Parameter
9 Numerical Solution of the Nonlinear Dirichlet and Neumann Problems Based on the Probabilistic Approach
9.1 Layer Methods for the Dirichlet Problem for Semilinear Parabolic Equations
9.1.1 Construction of a Layer Method of First Order
9.1.2 Convergence Theorem
9.1.3 A Layer Method with a Simpler Approximation near the Boundary
9.1.4 Numerical Algorithms and Their Convergence
9.2 Numerical Tests of Layer Methods for the Dirichlet Problems
9.2.1 The Burgers Equation
9.2.2 Comparison Analysis
9.2.3 Quasilinear Equation with Power Law Nonlinearities
9.3 Layer Methods for the Neumann Problem for Semilinear Parabolic Equations
9.3.1 Construction of Layer Methods
9.3.2 Convergence Theorems
9.3.3 Numerical Algorithms
9.3.4 Some Other Layer Methods
9.4 Numerical Tests for the Neumann Problem
9.4.1 Comparison of Various Layer Methods
9.4.2 A Comparison Analysis of Layer Methods and Finite-Difference Schemes
10 Solving FBSDEs Using Layer Methods
10.1 Discretization of FBSDEs and Related Semilinear Parabolic PDEs
10.1.1 Four-Step Scheme for Solving FBSDEs
10.1.2 Approximation of the Derivative u/x by Finite Differences
10.1.3 Numerical Integration of FBSDEs
10.2 FBSDEs with Random Terminal Time
10.2.1 The Parabolic Case
10.2.2 The Elliptic Case
10.3 Numerical Integration of FBSDEs with Random Terminal Time
10.4 A Probabilistic Approach to Solving Quasilinear Parabolic Equations
10.4.1 Numerical Algorithms
10.4.2 Solution of the FBSDE (10.4.5)–(10.4.6)
10.4.3 Numerical Integration of FBSDEs
10.5 Numerical Experiments
10.5.1 Description of the Test Problems: Semilinear Case
10.5.2 Numerical Results
10.5.3 Description of the Test Problem: Quasi-Linear Case
10.5.4 Numerical Results
10.5.5 Quasilinear Equation with Power Law Nonlinearities
11 Solving Parabolic SPDEs by Averaging Over Characteristics
11.1 Conditional Probabilistic Representations of Solutions to Linear SPDEs
11.2 Numerical Methods Based on the Conditional …
11.2.1 Mean-Square Simulation of the Representation (11.1.6)–(11.1.7)
11.2.2 Weak Simulation of the Representation (11.1.6)–(11.1.7)
11.3 Other Probabilistic Representations, Monte Carlo Error, and Variance Reduction
11.4 Layer Methods for Linear SPDEs
11.5 Layer Methods for Semilinear SPDEs
11.6 Numerical Experiments
11.6.1 Model Problem: Ornstein-Uhlenbeck Equation
11.6.2 Numerical Results
11.7 Nonlinear Filtering
11.7.1 Kallianpur-Striebel Formula
11.7.2 Backward Pathwise Filtering Equations and Probabilistic Representation of Their Solutions
11.7.3 Backward SPDE for Nonlinear Filtering
Appendix References
Index
