- Local Linearization Method
- Background
- High Order Local Linearization Method
- Local Linearization scheme
- LL methods for ODEs Local Linear discretization High Order Local Linear discretizations Local Linearization schemes Computing integrals involving matrix exponential Order 2 LL schemes Order 3 LL-Taylor schemes Order 4 LL-RK schemes Locally Linearized Runge-Kutta of Dormand & Prince Stability and dynamics
- LL methods for DDEs Local Linear discretization Local Linearization schemes Order 2 Polynomial LL schemes
- LL methods for RDEs Local Linear discretization Local Linearization schemes LL schemes
- Strong LL methods for SDEs Local Linear discretization High Order Local Linear discretizations Local Linearization schemes Order 1 SLL schemes Order 1.5 SLL schemes Order 2 SLL-Taylor schemes Order 2 SLL-RK schemes Stability and dynamics
- Weak LL methods for SDEs Local Linear discretization Local Linearization schemes Order 1 WLL scheme Order 2 WLL scheme Stability and dynamics
- Historical notes
- Reference
Local Linearization Method
In numerical analysis, the Local Linearization (LL) method is a general strategy for designing numerical integrators for differential equations based on a local (piecewise) linearization of the given equation on consecutive time intervals. The numerical integrators are then iteratively defined as the solution of the resulting piecewise linear equation at the end of each consecutive interval. The LL method has been developed for a variety of equations such as the ordinary, delayed, random and stochastic differential equations. The LL integrators are key component in the implementation of inference methods for the estimation of unknown parameters and unobserved variables of differential equations given time series of (potentially noisy) observations. The LL schemes are ideals to deal with complex models in a variety of fields as neuroscience, finance, forestry management, control engineering, mathematical statistics, etc.
Background
Differential equations have became an important mathematical tool for describing the time evolution of several phenomenon, e.g., rotation of the planets around the sun, the dynamic of assets prices in the market, the fire of neurons, the propagation of epidemics, etc. However, since the exact solutions of these equations are usually unknown, numerical approximations to them obtained by numerical integrators are necessary. Currently, many applications in engineering and applied sciences focused in dynamical studies demand the developing of efficient numerical integrators that preserve, as much as possible, the dynamics of these equations. With this main motivation, the Local Linearization integrators have been developed.
High Order Local Linearization Method
High Order Local Linearization (HOLL) method is a generalization of the Local Linearization method oriented to obtain high order integrators for differential equations that preserve the stability{{dn|date=November 2017}} and dynamics of the linear equations. The integrators are obtained by splitting, on consecutive time intervals, the solution x of the original equation in two parts: the solution z of the locally linearized equation plus an high order approximation of the residual 
.
Local Linearization scheme
A Local Linearization (LL) scheme is the final recursive algorithm that allows the numerical implementation of a discretization derived from the LL or HOLL method for a class of differential equations.
LL methods for ODEs
Consider the d-dimensional Ordinary Differential Equation (ODE)
with initial condition 
, where 
is a differentiable function.
Let 
be a time discretization of the time interval 
with maximum stepsize h such that 
and 
. After the local linearization of the equation (1) at the time step 
the variation of constants formula yields
where
results from the linear approximation, and
is the residual of the linear approximation. Here, 
and 
denote the partial derivatives of f with respect to the variables x and t, respectively, and 
.
Local Linear discretization
For a time discretization 
, the Local Linear discretization of the ODE (1) at each point 
is defined by the recursive expression
The Local Linear discretization (4.3) converges with order 2 to the solution of nonlinear ODEs, but it match the solution of the linear ODEs. The recursion (4.3) is also known as Exponential Euler discretization.
High Order Local Linear discretizations
For a time discretization 
a High Order Local Linear (HOLL) discretization of the ODE (1) at each point 
is defined by the recursive expression
where 
is an order 
(>2) approximation to the residual r 
The HOLL discretization (4.4) converges with order to the solution of nonlinear ODEs, but it match the solution of the linear ODEs.
HOLL discretizations can be derived in two ways: 1) (quadrature-based) by approximating the integral representation (4.2) of r; and 2) (integrator-based) by using a numerical integrator for the differential representation of r defined by
for all 
, where
The quadrature-based discretization is often called Exponential Propagation Iterative or Exponential Rosenbrock, whereas the integrator-based one is called Locally Linearized discretization.
HOLL discretizations are, for instance, the followings:
- Locally Linearized Runge Kutta discretization
which is obtained by solving (4.5) via a s-stage Runge–Kutta (RK) scheme with coefficients 
.
- Local Linear Taylor discretization
which results from the approximation of 
in (4.2) by its order-p truncated Taylor expansion.
- Multistep type Exponential Propagation discretization
which results from the interpolation of in (4.2) by a polynomial of degree p on 
, where 
denotes the j-th backward difference of 
.
- Runge Kutta type Exponential Propagation discretization
which results from the interpolation of in (4.2) by a polynomial of degree p on 
,
- Linealized Exponential Adams discretization
which results from the interpolation of in (4.2) by a Hermite polynomial of degree p on .
Local Linearization schemes
All numerical implementation 
of the LL (or of a HOLL) discretization 
involves approximations 
to integrals 
of the form
where A is an d 
d matrix. Every numerical implementation of a Local Linear discretization of any order is generically called Local Linearization scheme.
Computing integrals involving matrix exponential
Among a number of algorithms to compute the integrals , those based on rational Padé and Krylov subspaces approximations for exponential matrix are preferred. For this, a central role is playing by the expression
where 
are d-dimensional vectors,
, 
, 
, being 
the d-dimensional identity matrix.
If 
denotes the (p; q)-Padé approximation of 
and k is the smallest integer number such that 
If 
denotes the (m; p; q; k) Krylov-Padé approximation of 
,
where 
is the dimension of the Krylov subspace.
Order 2 LL schemes
where the matrices 
, L and r are defined as
and 
with 
. For large systems of ODEs
Order 3 LL-Taylor schemes
where for autonomous ODEs the matrices 
and 
are defined as
. Here, 
denotes the second derivative of f with respect to x, and p + q > 2. For large systems of ODEs
Order 4 LL-RK schemes
where
and
with 
and p + q > 3. For large systems of ODEs, the vector 
in the above scheme is replaced by 
Locally Linearized Runge-Kutta of Dormand & Prince
where s = 6 is the number of stages,
with 
, and 
are the Runge-Kutta coefficients of Dormand and Prince and p + q > 4. For large systems of ODEs, the vector in the above scheme is replaced by 
Stability and dynamics
with 
, 
and 
, and its approximation by various schemes. This system has two stable stationary points and one unstable stationary point in the region 
.
LL methods for DDEs
Consider the d-dimensional Delay Differential Equation (DDE)
with m constant delays 
and initial condition 
for all 
where f is a differentiable function, 
is the segment function defined as
for all 
is a given function, and 
Local Linear discretization
For a time discretization , the Local Linear discretization of the DDE (5.1) at each point 
is defined by the recursive expression
where
is the segment function defined as
and 
is a suitable approximation to 
for all 
such that 
Here,
are constant matrices and
are constant vectors. 
denote, respectively, the partial derivatives of f with respect to the variables t and x, and 
. The Local Linear discretization (5.2) converges to the solution of (5.1) with order 
if 
approximates 
with order 
for all 
.
Local Linearization schemes
Depending of the approximations and of the algorithm to compute 
different Local Linearizations schemes can be defined. Every numerical implementation of a Local Linear discretization is generically called Local Linearization scheme.
Order 2 Polynomial LL schemes
where the matrices 
and 
are defined as
and 
, and . Here, the matrices 
, 
, 
and 
are defined as in (5.2), but replacing 
by 
and 
where
with 
, is the Local Linear Approximation to the solution of (5.1) defined through the LL scheme (5.3) for all 
and by 
for 
. For large systems of DDEs
with and 
.
LL methods for RDEs
Consider the d-dimensional Random Differential Equation (RDE)
with initial condition 
where 
is a k-dimensional separable finite continuous stochastic process, and f is a differentiable function. Suppose that a realization (path) of 
is given.
Local Linear discretization
For a time discretization , the Local Linear discretization of the RDE (6.1) at each point is defined by the recursive expression
where
and 
is an approximation to the process for all 
Here, 
and 
denote the partial derivatives of with respect to 
and 
, respectively.
Local Linearization schemes
Depending of the approximations to the process and of the algorithm to compute different Local Linearizations schemes can be defined. Every numerical implementation of the Local Linear discretization is generically called Local Linearization scheme.
LL schemes
where the matrices 
are defined as
, , and p+q>1. For large systems of RDEs,
The convergence rate of both schemes is 
, where is 
the exponent of the Holder condition of .
Figure 3 presents the phase portrait of the RDE
and its approximation by two numerical schemes, where 
denotes a fractional Brownian process with Hurst exponent H=0.45.
Strong LL methods for SDEs
Consider the d-dimensional Stochastic Differential Equation (SDE)
with initial condition , where the drift coefficient and the diffusion coefficient 
are differentiable functions, and 
is an m-dimensional standard Wiener process.
Local Linear discretization
For a time discretization , the order-
(=1,1.5) Strong Local Linear discretization of the solution of the SDE (7.1) is defined by the recursive relation
where
and
Here,
denote the partial derivatives of with respect to the variables and t, respectively, and the Hessian matrix of with respect to . The strong Local Linear discretization 
converges with order (=1,1.5) to the solution of (7.1).
High Order Local Linear discretizations
After the local linearization of the drift term of (7.1) at 
, the equation for the residual is given by
for all 
, where
High Order Local Linear discretization of the SDE (7.1) at each point is then defined by the recursive expression
where 
is a strong approximation to the residual of order higher than 1.5. The strong HOLL discretization converges with order to the solution of (7.1).
Local Linearization schemes
Depending on the way of computing 
, and different numerical schemes could be obtained. Every numerical implementation of a strong Local Linear discretization of any order is generically called Strong Local Linearization scheme.
Order 1 SLL schemes
where the matrices , 
and are defined as in (4.6), 
is a i.i.d. zero mean Gaussian random variable with variance 
, and p+q>1. For large systems of SDEs, in the above scheme 
is replaced by 
.
Order 1.5 SLL schemes
where the matrices , and are defined as
, 
is a i.i.d. zero mean Gaussian random variable with variance 
and covariance 
and p+q>1. For large systems of SDEs, in the above scheme 
is replaced by 
.
Order 2 SLL-Taylor schemes
where , , and are defined as in the order-1 SLL schemes, and 
is order 2 approximation to the multiple Stratonovish integral 
.
Order 2 SLL-RK schemes
For SDEs with a single Wiener noise (m=1)
where
with 
. Here, 
for low dimensional SDEs, and 
for large systems of SDEs, where , , , and are defined as in the order-2 SLL-Taylor schemes, p+q>1 and .
Stability and dynamics
By construction, the strong LL and HOLL discretizations inherit the stability and dynamics of the linear SDEs, but it is not the case of the strong LL schemes in general. LL schemes (7.2)-(7.5) with 
are A-stable, including stiff and highly oscillatory linear equations. Moreover, for linear SDEs with random attractors, these schemes also have a random attractor that converges in probability to the exact one as the stepsize decreases and preserve the ergodicity of these equations for any stepsize. These schemes also reproduce essential dynamical properties of simple and coupled harmonic oscillators such as the linear growth of energy along the paths, the oscillatory behavior around 0, the symplectic structure of Hamiltonian oscillators, and the mean of the paths. For nonlinear SDEs with small noise (i.e., (7.1) with 
), the paths of these SLL schemes are basically the nonrandom paths of the LL scheme (4.6) for ODEs plus a small disturbance related to the small noise. In this situation, the dynamical properties of that deterministic scheme, such as the linearization preserving and the preservation of the exact solution dynamics around hyperbolic equilibrium points and periodic orbits, become relevant for the paths of the SLL scheme. For instance, Fig 4 shows the evolution of domains in the phase plane and the energy of the stochastic oscillator
and their approximations by two numerical schemes.
Weak LL methods for SDEs
Consider the d-dimensional stochastic differential equation
with initial condition , where the drift coefficient and the diffusion coefficient are differentiable functions, and 
is an m-dimensional standard Wiener process.
Local Linear discretization
For a time discretization , the order-
Weak Local Linear discretization of the solution of the SDE (8.1) is defined by the recursive relation
where
with
and 
is a zero mean stochastic process with variance matrix
Here, , denote the partial derivatives of with respect to the variables and t, respectively, the Hessian matrix of with respect to , and 
. The weak Local Linear discretization converges with order (=1,2) to the solution of (8.1).
Local Linearization schemes
Depending on the way of computing 
and 
different numerical schemes could be obtained. Every numerical implementation of the Weak Local Linear discretization is generically called Weak Local Linearization scheme.
Order 1 WLL scheme
where, for SDEs with autonomous diffusion coefficients, 
, 
and 
are the submatrices defined by the partitioned matrix 
, with
and 
is a sequence of d-dimensional independent two-points distributed random vectors satisfying 
.
Order 2 WLL scheme
where , and 
are the submatrices defined by the partitioned matrix 
with
and
Stability and dynamics
computed by various schemes.
Historical notes
Below is a time line of the main developments of the LL method.
- Pope D.A. (1963) introduces the LL discretization for ODEs and the LL scheme based on Taylor expantion. doi :10.1145/366707.367592- Ozaki T. (1985) introduces the LL method for the integration and estimation of SDEs. The term "Local Linearization" (LL) is used for first time. [https://doi.org/10.1016/S0169-7161(85)05004-0 doi:10.1016/S0169-7161(85)05004-0]- Biscay R. et al. (1996) reformulate the strong LL method for SDEs. doi:10.1007/BF00052324- Shoji I. and Ozaki T. (1997) reformulate the weak LL method for SDEs. doi: 10.1111/1467-9892.00064- Hochbruck M. et al. (1998) introduce the LL scheme for ODEs based on Krylov subspace approximation. doi:10.1137/S1064827595295337- Jimenez J.C. (2002) introduces the LL scheme for ODEs and SDEs based on rational Padé approximation. doi:10.1016/S0893-9659(02)00041-1- Carbonell F.M. et al. (2005) introduce the LL method for RDEs. doi: 10.1007/s10543-005-2645-9- Jimenez J.C. et al. (2006) introduce the LL method for DDEs. doi: 10.1137/040607356- de la Cruz H. et al. (2006, 2007) and Tokman (2006) introduce the two classes of HOLL integrators for ODEs: the integrator-based and the quadrature-based. 10.1007/11758501\\_22, 10.1016/j.amc.2006.06.096 and 10.1016/j.jcp.2005.08.032- de la Cruz H. et al. (2010) introduce the strong HOLL method for SDEs. doi:10.1007/s10543-010-0272-6Reference
- {{cite journal
|surname=Carbonell F.
|surname2=Jimenez J.C.
|surname3=Pedroso L.M.
|year=2008
|title=Computing multiple integrals involving matrix exponentials,
|journal=J. Comput. Appl. Math.
|volume=213
|page=300–305
|doi=10.1016/j.cam.2007.01.007
}}
- {{cite journal
|surname=de la Cruz H.
|surname2=Biscay R.J.
|surname3=Carbonell F.
|surname4=Jimenez J.C.
|surname5=Ozaki T.
|year=2006
|title=Local Linearization-Runge Kutta (LLRK) methods for solving ordinary differential equations,
|journal=Lecture Note in Computer Sciences, Springer-Verlag.
|volume=3991
|page=132–139
|doi=10.1007/11758501_22
|series=Lecture Notes in Computer Science
|isbn=978-3-540-34379-0
}}
- {{cite journal
|surname=de la Cruz H.
|surname2=Biscay R.J.
|surname3=Carbonell F.
|surname4=Ozaki T.
|surname5=Jimenez J.C.
|year=2007
|title=A higher order Local Linearization method for solving ordinary differential equations,
|journal=Appl. Math. Comput.
|volume=185
|page=197–212
|doi=10.1016/j.amc.2006.06.096
}}
- {{cite journal
|surname=de la Cruz H.
|surname2= Biscay R.J.
|surname3=Jimenez J.C.
|surname4=Carbonell F.
|year=2013
|title=Local Linearization - Runge Kutta Methods: a class of A-stable explicit integrators for dynamical systems,
|journal=Math. Comput. Modelling.
|volume=57
|issue= 3–4
|page=720–740
|doi=10.1016/j.mcm.2012.08.011
}}
- {{cite journal
|surname=de la Cruz H.
|surname2=Biscay R.J.
|surname3=Jimenez J.C.
|surname4=Carbonell F.
|surname5=Ozaki T.
|year=2010
|title=High Order Local Linearization methods: an approach for constructing A-stable high order explicit schemes for stochastic differential equations with additive noise,
|journal=BIT Numer. Math.
|volume=50
|issue=3
|page=509–539
|doi=10.1007/s10543-010-0272-6
}}
- {{cite journal
|surname=de la Cruz H.
|surname2=Jimenez J.C.
|surname3=Zubelli J.P.
|year=2017
|title=Locally Linearized methods for the simulation of stochastic oscillators driven by random forces,
|journal=BIT Numer. Math.
|volume=57
|page=123–151
|doi=10.1007/s10543-016-0620-2
}}
- {{cite journal
|surname=M. Hochbruck.
|surname2=A. Ostermann.
|year=2011
|title=Exponential multistep methods of Adams-type,
|journal=BIT Numer. Math.
|volume=51
|issue=4
|page=889–908
|doi=10.1007/s10543-011-0332-6
}}
- {{cite journal
|surname=Jimenez J.C.
|year=2009
|title=Local Linearization methods for the numerical integration of ordinary differential equations: An overview,
|journal=ICTP Technical Report.
|volume=035
|page=357–373
|url=http://publications.ictp.it
}}
- {{cite journal
|surname=Jimenez J.C.
|surname2=Biscay R.
|surname3=Mora C.
|surname4=Rodriguez L.M.
|year=2002
|title=Dynamic properties of the Local Linearization method for initial-value problems,
|journal=Appl. Math. Comput.
|volume=126
|page=63–68
|doi=10.1016/S0096-3003(00)00100-4
}}
- {{cite journal
|surname=Jimenez J.C.
|surname2=Carbonell F.
|year=2009
|title=Rate of convergence of local linearization schemes for random differential equations,
|journal=BIT Numer. Math.
|volume=49
|issue=2
|page=357–373
|doi=10.1007/s10543-009-0225-0
}}
- {{cite journal
|surname=Jimenez J.C.
|surname2=Carbonell F.
|year=2015
|title=Convergence rate of weak Local Linearization schemes for stochastic differential equations with additive noise,
|journal=J. Comput. Appl. Math.
|volume=279
|page=106–122
|doi=10.1016/j.cam.2014.10.021
}}
- {{cite journal
|surname=Jimenez J.C.
|surname2=de la Cruz H.
|year=2012
|title=Convergence rate of strong Local Linearization schemes for stochastic differential equations with additive noise,
|journal=BIT Numer. Math.
|volume=52
|issue=2
|page=357–382
|doi=10.1007/s10543-011-0360-2
}}
- {{cite journal
|surname=Jimenez J.C.
|surname2=Pedroso L.
|surname3=Carbonell F.
|surname4=Hernandez V.
|year=2006
|title=Local linearization method for numerical integration of delay differential equations,
|journal=SIAM J. Numer. Analysis.
|volume=44
|issue=6
|page=2584–2609
|doi=10.1137/040607356
}}
- {{cite journal
|surname=Jimenez J.C.
|surname2=Sotolongo A.
|surname3=Sanchez-Bornot J.M.
|year=2014
|title=Locally Linearized Runge Kutta method of Dormand and Prince,
|journal=Appl. Math. Comput.
|volume=247
|page=589–606
|doi=10.1016/j.amc.2014.09.001
}}
- {{cite journal |surname=Tokman M. |year=2006 |title=Efficient integration of large stiff systems of ODEs with exponential propagation iterative (EPI) methods, |journal=J. Comput. Physics. |volume=213 |issue=2 |page=748–776 |doi=10.1016/j.jcp.2005.08.032 |bibcode=2006JCoPh.213..748T }}
- Heterophleps
- Heterophobe
- Heteropholis
- Heterophrys
- Heterophyes Heterophyes
- Heterophyes heterophyes
- Heterophyidae
- Heterophysa
- Heterophytic
- Heteropithecia
- Heteroplacidium
- Heteroplexis
- Heteropneustes fossilis
- Heteropneustes kemratensis
- Heteropod
- Heteropoda dagmarae
- Heteropoda davidbowie
- Heteropoda maxima
- Heteropogon
- Heteroponera brounii
- Heteropriacanthus
- Heteroprox
- Heteropsilopus
- Heteropsis (butterfly)
- Heteropsis perspicua