HOME

TheInfoList



Click Here for Items Related To - Leimkuhler–Matthews Method
OR:
Leimkuhler–Matthews Method on:   [Wikipedia]   [Google]   [Amazon]

In mathematics, the Leimkuhler-Matthews method (or LM method in its original paper ) is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for finding discretized solutions to the
Brownian dynamics Brownian dynamics (BD) can be used to describe the motion of molecules for example in molecular simulations or in reality. It is a simplified version of Langevin dynamics and corresponds to the limit where no average acceleration takes place. Thi ...
:\mathrm X = -\nabla V(X ) \, \mathrm t + \sigma \, \mathrm W, where \sigma>0 is a constant, V(X) is an
energy function Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
and W(t) is a
Wiener process In mathematics, the Wiener process is a real-valued continuous-time stochastic process named in honor of American mathematician Norbert Wiener for his investigations on the mathematical properties of the one-dimensional Brownian motion. It is o ...
. This
stochastic differential equation A stochastic differential equation (SDE) is a differential equation in which one or more of the terms is a stochastic process, resulting in a solution which is also a stochastic process. SDEs are used to model various phenomena such as stock pr ...
has solutions (denoted X(t) \in \mathbb^N at time t ) distributed according to \pi(X) \propto \exp(-V(x)) in the limit of large-time, making solving these dynamics relevant in sampling-focused applications such as classical
molecular dynamics Molecular dynamics (MD) is a computer simulation method for analyzing the physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a fixed period of time, giving a view of the dynamic "evolution" of the ...
and
machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...
. Given a time step \Delta t>0, the Leimkuhler-Matthews update scheme is compactly written as :X_ = X_t -\nabla V(X_t) \Delta t + \sigma\frac2 \, (R_t+R_), with initial condition X_0 := X(0) , and where X_t \approx X(t) . The vector R_t is a vector of independent normal random numbers redrawn at each step so \text R_t \cdot R_N\delta_ (where \text
bullet A bullet is a kinetic projectile, a component of firearm ammunition that is shot from a gun barrel. Bullets are made of a variety of materials, such as copper, lead, steel, polymer, rubber and even wax. Bullets are made in various shapes and co ...
/math> denotes expectation). Despite being of equal cost to the Euler-Maruyama scheme (in terms of the number of evaluations of the function \nabla V(X) per update), given some assumptions on \Delta t,\, V(X) and f(X) solutions have been shown to have a superconvergence property : \text Euler-Maruyama_scheme,_at_no_extra_cost.


_Discussion


_Comparison_to_other_schemes

The_obvious_method_for_comparison_is_the__Euler-Maruyama_scheme_as_it_has_the_same_cost,_requiring_one_evaluation_of_\nabla_V(X)_per_step._Its_update_is_of_the_form_ :\hat__=_\hat_t_-\nabla_V(\hat_t)_\Delta_t__+_\sigma_\,_R_t, with_error_(given_some_assumptions__)_as__\text f(\hat_)_-_f(X(t)), \leq_C_\Delta_t__with_constant_C>0_independent_of_t._Compared_to_the_above_definition,_the_only_difference_between_the_schemes_is_the_''one-step''_averaged_noise_term,_making_it_simple_to_implement. For_sufficiently_small_time_step_\Delta_t_and_large_enough_time_t_it_is_clear_that_the_LM_scheme_gives_a_smaller_error_than_Euler-Maruyama._While_there_are_many_algorithms_that_can_give_reduced_error_compared_to_the_Euler_scheme_(see_e.g._ Milstein,_ Runge-Kutta_or_
Heun's_method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical proc ...
)_these_almost_always_come_at_an_efficiency_cost,_requiring_more_computation_in_exchange_for_reducing_the_error._However_the_Leimkuhler-Matthews_scheme_can_give_significantly_reduced_error_with_minimal_change_to_the_standard_Euler_scheme._The_trade-off_comes_from_the_(relatively)_limited_scope_of_the_stochastic_differential_equation_ A_stochastic_differential_equation_(SDE)_is_a_differential_equation_in_which_one_or_more_of_the_terms_is_a_stochastic_process,_resulting_in_a_solution_which_is_also_a_stochastic_process._SDEs_are_used_to_model_various_phenomena_such_as__stock_pr_...
_it_solves:_\sigma_must_be_a_scalar_constant_and_the_drift_function_must_be_of_the_form_\nabla_V(X)._The_LM_scheme_also_is_not_ Markovian,_as_updates_require_more_than_just_the_state_at_time_t._However,_we_can_recast_the_scheme_as_a_Markov_process_by_extending_the_space.


_Markovian_Form

We_can_rewrite_the_algorithm_in_a_Markovian_form_by_extending_the_state_space_with_a_''momentum_vector''___P_t\in\mathbb^N_so_that_the_overall_state_is_(X_t,P_t)_at_time_t._Initializing_the_momentum_to_be_a_vector_of_N_standard_normal_random_numbers,_we_have :X'__=_X_t_-\nabla_V(X_t)_\Delta_t__+_\sigma\frac2_\,_P_t, :P__\sim_\text(0,I), :X__=_X'__+_\sigma\frac2_\,_P_, where_the_middle_step_completely_redraws_the_momentum_so_that_each_component_is_an_independent_normal_random_number._This_scheme_is_Markovian,_and_has_the_same_properties_as_the_original_LM_scheme.


_Applications

The_algorithm_has_application_in_any_area_where_the_weak_(i.e._average)_properties_of_solutions_to_Brownian_dynamics_ Brownian_dynamics_(BD)_can_be_used_to_describe_the_motion_of_molecules_for_example_in_molecular_simulations_or_in_reality._It_is_a_simplified_version_of_Langevin_dynamics_and_corresponds_to_the_limit_where_no_average_acceleration_takes_place._Thi_...
_are_required._This_applies_to_any_molecular_simulation_problem_(such_as_classical_molecular_dynamics_ Molecular_dynamics_(MD)_is_a_computer_simulation_method_for_analyzing_the__physical_movements_of__atoms_and__molecules._The_atoms_and_molecules_are_allowed_to_interact_for_a_fixed_period_of_time,_giving_a_view_of_the_dynamic_"evolution"_of_the_...
),_but_also_can_apply_to_statistical_ sampling_problems_due_to_the_properties_of_solutions_at_large_times._In_the_limit_of_t\to\infty,_solutions_will_become_distributed_according_to_the_
Probability_distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
_\pi(X)_\propto_\exp(-V(X))._Thus_we_can_generate_independent_samples_according_to_a_required_distribution_by_using_V(X)_=_-\log(\pi(X))_and_running_the_LM_algorithm_until_large_t._Such_strategies_can_be_efficient_in_(for_instance)_
Bayesian_inference Bayesian inference is a method of statistical inference in which Bayes' theorem is used to update the probability for a hypothesis as more evidence or information becomes available. Bayesian inference is an important technique in statistics, a ...
_problems.


__See_also_

*_ Euler-Maruyama_method *_
Milstein_method In mathematics, the Milstein method is a technique for the approximate numerical solution of a stochastic differential equation. It is named after Grigori N. Milstein who first published it in 1974. Description Consider the autonomous Itō stoch ...
*_ Runge–Kutta_method_(SDE) *_
Heun's_method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical proc ...


_References

Numerical_differential_equations_ Stochastic_differential_equations {{DEFAULTSORT:Leimkuhler-Matthews_method}.html" ;"title="f( X_t ) - f(X(t)), ] \leq C_1 e^ \Delta t + C_2 \Delta t^2 for constants C_k\geq0,\, \lambda>0 not depending on t. This means that as t gets large we obtain an effective second order with \Delta t^2 error in computed expectations. For small time step \Delta t this can give significant improvements over the Euler-Maruyama scheme, at no extra cost.


Discussion


Comparison to other schemes

The obvious method for comparison is the Euler-Maruyama scheme as it has the same cost, requiring one evaluation of \nabla V(X) per step. Its update is of the form :\hat_ = \hat_t -\nabla V(\hat_t) \Delta t + \sigma \, R_t, with error (given some assumptions ) as \text f(\hat_) - f(X(t)), \leq C \Delta t with constant C>0 independent of t. Compared to the above definition, the only difference between the schemes is the ''one-step'' averaged noise term, making it simple to implement. For sufficiently small time step \Delta t and large enough time t it is clear that the LM scheme gives a smaller error than Euler-Maruyama. While there are many algorithms that can give reduced error compared to the Euler scheme (see e.g. Milstein, Runge-Kutta or
Heun's method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical proc ...
) these almost always come at an efficiency cost, requiring more computation in exchange for reducing the error. However the Leimkuhler-Matthews scheme can give significantly reduced error with minimal change to the standard Euler scheme. The trade-off comes from the (relatively) limited scope of the
stochastic differential equation A stochastic differential equation (SDE) is a differential equation in which one or more of the terms is a stochastic process, resulting in a solution which is also a stochastic process. SDEs are used to model various phenomena such as stock pr ...
it solves: \sigma must be a scalar constant and the drift function must be of the form \nabla V(X). The LM scheme also is not Markovian, as updates require more than just the state at time t. However, we can recast the scheme as a Markov process by extending the space.


Markovian Form

We can rewrite the algorithm in a Markovian form by extending the state space with a ''momentum vector'' P_t\in\mathbb^N so that the overall state is (X_t,P_t) at time t. Initializing the momentum to be a vector of N standard normal random numbers, we have :X'_ = X_t -\nabla V(X_t) \Delta t + \sigma\frac2 \, P_t, :P_ \sim \text(0,I), :X_ = X'_ + \sigma\frac2 \, P_, where the middle step completely redraws the momentum so that each component is an independent normal random number. This scheme is Markovian, and has the same properties as the original LM scheme.


Applications

The algorithm has application in any area where the weak (i.e. average) properties of solutions to
Brownian dynamics Brownian dynamics (BD) can be used to describe the motion of molecules for example in molecular simulations or in reality. It is a simplified version of Langevin dynamics and corresponds to the limit where no average acceleration takes place. Thi ...
are required. This applies to any molecular simulation problem (such as classical
molecular dynamics Molecular dynamics (MD) is a computer simulation method for analyzing the physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a fixed period of time, giving a view of the dynamic "evolution" of the ...
), but also can apply to statistical sampling problems due to the properties of solutions at large times. In the limit of t\to\infty, solutions will become distributed according to the
Probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
\pi(X) \propto \exp(-V(X)). Thus we can generate independent samples according to a required distribution by using V(X) = -\log(\pi(X)) and running the LM algorithm until large t. Such strategies can be efficient in (for instance)
Bayesian inference Bayesian inference is a method of statistical inference in which Bayes' theorem is used to update the probability for a hypothesis as more evidence or information becomes available. Bayesian inference is an important technique in statistics, a ...
problems.


See also

* Euler-Maruyama method *
Milstein method In mathematics, the Milstein method is a technique for the approximate numerical solution of a stochastic differential equation. It is named after Grigori N. Milstein who first published it in 1974. Description Consider the autonomous Itō stoch ...
* Runge–Kutta method (SDE) *
Heun's method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical proc ...


References

Numerical differential equations Stochastic differential equations {{DEFAULTSORT:Leimkuhler-Matthews method}">f( X_t ) - f(X(t)), \leq C_1 e^ \Delta t + C_2 \Delta t^2 for constants C_k\geq0,\, \lambda>0 not depending on t. This means that as t gets large we obtain an effective second order with \Delta t^2 error in computed expectations. For small time step \Delta t this can give significant improvements over the Euler-Maruyama scheme, at no extra cost.


Discussion


Comparison to other schemes

The obvious method for comparison is the Euler-Maruyama scheme as it has the same cost, requiring one evaluation of \nabla V(X) per step. Its update is of the form :\hat_ = \hat_t -\nabla V(\hat_t) \Delta t + \sigma \, R_t, with error (given some assumptions ) as \text f(\hat_) - f(X(t)), \leq C \Delta t with constant C>0 independent of t. Compared to the above definition, the only difference between the schemes is the ''one-step'' averaged noise term, making it simple to implement. For sufficiently small time step \Delta t and large enough time t it is clear that the LM scheme gives a smaller error than Euler-Maruyama. While there are many algorithms that can give reduced error compared to the Euler scheme (see e.g. Milstein, Runge-Kutta or
Heun's method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical proc ...
) these almost always come at an efficiency cost, requiring more computation in exchange for reducing the error. However the Leimkuhler-Matthews scheme can give significantly reduced error with minimal change to the standard Euler scheme. The trade-off comes from the (relatively) limited scope of the
stochastic differential equation A stochastic differential equation (SDE) is a differential equation in which one or more of the terms is a stochastic process, resulting in a solution which is also a stochastic process. SDEs are used to model various phenomena such as stock pr ...
it solves: \sigma must be a scalar constant and the drift function must be of the form \nabla V(X). The LM scheme also is not Markovian, as updates require more than just the state at time t. However, we can recast the scheme as a Markov process by extending the space.


Markovian Form

We can rewrite the algorithm in a Markovian form by extending the state space with a ''momentum vector'' P_t\in\mathbb^N so that the overall state is (X_t,P_t) at time t. Initializing the momentum to be a vector of N standard normal random numbers, we have :X'_ = X_t -\nabla V(X_t) \Delta t + \sigma\frac2 \, P_t, :P_ \sim \text(0,I), :X_ = X'_ + \sigma\frac2 \, P_, where the middle step completely redraws the momentum so that each component is an independent normal random number. This scheme is Markovian, and has the same properties as the original LM scheme.


Applications

The algorithm has application in any area where the weak (i.e. average) properties of solutions to
Brownian dynamics Brownian dynamics (BD) can be used to describe the motion of molecules for example in molecular simulations or in reality. It is a simplified version of Langevin dynamics and corresponds to the limit where no average acceleration takes place. Thi ...
are required. This applies to any molecular simulation problem (such as classical
molecular dynamics Molecular dynamics (MD) is a computer simulation method for analyzing the physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a fixed period of time, giving a view of the dynamic "evolution" of the ...
), but also can apply to statistical sampling problems due to the properties of solutions at large times. In the limit of t\to\infty, solutions will become distributed according to the
Probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
\pi(X) \propto \exp(-V(X)). Thus we can generate independent samples according to a required distribution by using V(X) = -\log(\pi(X)) and running the LM algorithm until large t. Such strategies can be efficient in (for instance)
Bayesian inference Bayesian inference is a method of statistical inference in which Bayes' theorem is used to update the probability for a hypothesis as more evidence or information becomes available. Bayesian inference is an important technique in statistics, a ...
problems.


See also

* Euler-Maruyama method *
Milstein method In mathematics, the Milstein method is a technique for the approximate numerical solution of a stochastic differential equation. It is named after Grigori N. Milstein who first published it in 1974. Description Consider the autonomous Itō stoch ...
* Runge–Kutta method (SDE) *
Heun's method In mathematics and computational science, Heun's method may refer to the improved or modified Euler's method (that is, the explicit trapezoidal rule), or a similar two-stage Runge–Kutta method. It is named after Karl Heun and is a numerical proc ...


References

Numerical differential equations Stochastic differential equations {{DEFAULTSORT:Leimkuhler-Matthews method