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 become 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 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 a 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 (4.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 (4.1) at each point is defined by the recursive expression Jimenez J.C. (2009). "Local Linearization methods for the numerical integration of ordinary differential equations: An overview". ICTP Technical Report. 035: 357–373.
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 (4.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
HOLL discretizations are, for instance, the followings: Locally Linearized Runge Kutta discretizationde la Cruz H.; Biscay R.J.; Carbonell F.; Jimenez J.C.; Ozaki T. (2006). "Local Linearization-Runge Kutta (LLRK) methods for solving ordinary differential equations". Lecture Note in Computer Sciences 3991: 132–139, Springer-Verlag. doi:10.1007/11758501 22. .de la Cruz H.; Biscay R.J.; Jimenez J.C.; Carbonell F. (2013). "Local Linearization - Runge Kutta Methods: a class of A-stable explicit integrators for dynamical systems". Math. Comput. Modelling. 57 (3–4): 720–740. doi:10.1016/j.mcm.2012.08.011.
which is obtained by solving (4.5) via a s-stage explicit 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 Tokman M. (2006). "Efficient integration of large stiff systems of ODEs with exponential propagation iterative (EPI) methods". J. Comput. Physics. 213 (2): 748–776. doi:10.1016/j.jcp.2005.08.032.
which results from the interpolation of in (4.2) by a polynomial of degree p on ,
Linealized exponential Adams discretizationM. Hochbruck.; A. Ostermann. (2011). "Exponential multistep methods of Adams-type". BIT Numer. Math. 51 (4): 889–908. doi:10.1007/s10543-011-0332-6.
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 a d × d matrix. Every numerical implementation of the LL (or of a HOLL) of any order is generically called Local Linearization scheme.Jimenez, J. C., & Carbonell, F. (2005). "Rate of convergence of local linearization schemes for initial-value problems". Appl. Math. Comput., 171(2), 1282-1295. doi:10.1016/j.amc.2005.01.118.
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 expressionCarbonell F.; Jimenez J.C.; Pedroso L.M. (2008). "Computing multiple integrals involving matrix exponentials". J. Comput. Appl. Math. 213: 300–305. doi:10.1016/j.cam.2007.01.007.de la Cruz H.; Biscay R.J.; Carbonell F.; Ozaki T.; Jimenez J.C. (2007). "A higher order Local Linearization method for solving ordinary differential equations". Appl. Math. Comput. 185: 197–212. doi:10.1016/j.amc.2006.06.096.Jimenez J.C.; Pedroso L.; Carbonell F.; Hernandez V. (2006). "Local linearization method for numerical integration of delay differential equations". SIAM J. Numer. Analysis. 44 (6): 2584–2609. doi:10.1137/040607356.
where are d-dimensional vectors,
, , being the d-dimensional identity matrix.
If denotes the (p; q)-Padé approximation of and k is the smallest natural number such that Jimenez J.C.; de la Cruz H. (2012). "Convergence rate of strong Local Linearization schemes for stochastic differential equations with additive noise". BIT Numer. Math. 52 (2): 357–382. doi:10.1007/s10543-011-0360-2.
If denotes the (m; p; q; k) Krylov-Padé approximation of , then
where is the dimension of the Krylov subspace.
Order-2 LL schemes
Jimenez J.C.; Biscay R.; Mora C.; Rodriguez L.M. (2002). "Dynamic properties of the Local Linearization method for initial-value problems". Appl. Math. Comput. 126: 63–68. doi:10.1016/S0096-3003(00)00100-4.
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 with
Locally linearized Runge–Kutta scheme of Dormand and Prince
Jimenez J.C.; Sotolongo A.; Sanchez-Bornot J.M. (2014). "Locally Linearized Runge Kutta method of Dormand and Prince". Appl. Math. Comput. 247: 589–606. doi:10.1016/j.amc.2014.09.001.Naranjo-Noda, Jimenez J.C. (2021) "Locally Linearized Runge_Kutta method of Dormand and Prince for large systems of initial value problems." J.Comput. Physics. 426: 109946. doi:10.1016/j.jcp.2020.109946.
where s = 7 is the number of stages,
with , and are the Runge–Kutta coefficients of Dormand and Prince and p + q > 4. The vector in the above scheme is computed by a Padé or Krylor–Padé approximation for small or large systems of ODE, respectively.
Stability and dynamics By construction, the LL and HOLL discretizations inherit the stability and dynamics of the linear ODEs, but it is not the case of the LL schemes in general. With , the LL schemes (4.6)-(4.9) are A-stable. With q = p + 1 or q = p + 2, the LL schemes (4.6)–(4.9) are also L-stable. For linear ODEs, the LL schemes (4.6)-(4.9) converge with order p + q. In addition, with p = q = 6 and = d, all the above described LL schemes yield to the ″exact computation″ (up to the precision of the floating-point arithmetic) of linear ODEs on the current personal computers. This includes stiff and highly oscillatory linear equations. Moreover, the LL schemes (4.6)-(4.9) are regular for linear ODEs and inherit the symplectic structure of Hamiltonian harmonic oscillators. These LL schemes are also linearization preserving, and display a better reproduction of the stable and unstable manifolds around hyperbolic equilibrium points and periodic orbits that other numerical schemes with the same stepsize. For instance, Figure 1 shows the phase portrait of the ODEs
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 on the approximations and on 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 . Fig. 2 Illustrates the stability of the LL scheme (5.3) and of that of an explicit scheme of similar order in the integration of a stiff system of DDEs.
LL methods for RDEs Consider the d-dimensional Random Differential Equation (RDE)