Local Linearization Method

---

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 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 $\mathbf{𝐫}=\mathbf{𝐱}-\mathbf{𝐳}$.

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)

$\frac{d\mathbf{𝐱}\left(t\right)}{dt}=\mathbf{𝐟}(t,\mathbf{𝐱}\left(t\right)),t\in [t_0,T],(4.1)$

with initial condition $\mathbf{𝐱}(t_0)={\mathbf{𝐱}}_0$, where $\mathbf{𝐟}$ is a differentiable function.

Let ${\left(t\right)}_h=\{t_n:n=0,..,N\}$ be a time discretization of the time interval $[t_0,T]$ with maximum stepsize h such that $t_n<t_{n+1}$ and $h_n=t_{n+1}-t_n\le h$. After the local linearization of the equation (1) at the time step $t_n$ the variation of constants formula yields

$\mathbf{𝐱}(t_n+h)=\mathbf{𝐱}(t_n)+\mathit{\varphi }(t_n,\mathbf{𝐱}(t_n);h)+\mathbf{𝐫}(t_n,\mathbf{𝐱}(t_n);h),$

where

$\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h)=\underset{0}{\overset{h}{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)(h-s)}(\mathbf{𝐟}(t_n,{\mathbf{𝐳}}_n)+{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)s)ds$

results from the linear approximation, and

$\mathbf{𝐫}(t_n,{\mathbf{𝐳}}_n;h)=\underset{0}{\overset{h}{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)(h-s)}{\mathbf{𝐠}}_n(s,\mathbf{𝐱}(t_n+s))ds,(4.2)$

is the residual of the linear approximation. Here, ${\mathbf{𝐟}}_{\mathbf{𝐱}}$ and ${\mathbf{𝐟}}_t$ denote the partial derivatives of f with respect to the variables x and t, respectively, and ${\mathbf{𝐠}}_n(s,\mathbf{𝐮})=\mathbf{𝐟}(s,\mathbf{𝐮})-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)\mathbf{𝐮}-{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)(s-t_n)-\mathbf{𝐟}(t_n,{\mathbf{𝐳}}_n)+{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n){\mathbf{𝐳}}_n$.

Local Linear discretization

For a time discretization ${\left(t\right)}_h$, the Local Linear discretization of the ODE (1) at each point $t_{n+1}\in {\left(t\right)}_h$ is defined by the recursive expression

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h_n),with{\mathbf{𝐳}}_0={\mathbf{𝐱}}_0\text{.}(4.3)$

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 ${\left(t\right)}_h,$ a High Order Local Linear (HOLL) discretization of the ODE (1) at each point $t_{n+1}\in {\left(t\right)}_h$ is defined by the recursive expression

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h_n)+\widetilde{\mathbf{𝐫}}(t_n,{\mathbf{𝐳}}_n;h_n),with{\mathbf{𝐳}}_0={\mathbf{𝐱}}_0,(4.4)$

where $\tilde{r}$ is an order $\alpha$ (>2) approximation to the residual r $(i.e.,|\mathbf{𝐫}(t_n,{\mathbf{𝐳}}_n;h)-\widetilde{\mathbf{𝐫}}(t_n,{\mathbf{𝐳}}_n;h)|\propto h^{\alpha }).$ The HOLL discretization (4.4) converges with order $\alpha$ 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

$\frac{d\mathbf{𝐫}\left(t\right)}{dt}=\mathbf{𝐪}(t_n,{\mathbf{𝐳}}_n;t,\mathbf{𝐫}\left(t\right)\mathbf{)},with\mathbf{𝐫}\left(t_n\right)=\mathbf{𝟎},(4.5)$

for all $t\in [t_k,t_{k+1}]$, where

$\mathbf{𝐪}(t_n,{\mathbf{𝐳}}_n;s,\mathit{\xi })=\mathbf{𝐟}(s,{\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;s-t_n)+\mathit{\xi })-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;s-t_n)-{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)(s-t_n)-\mathbf{𝐟}(t_n,{\mathbf{𝐳}}_n).$

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

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h_n)+h_n\sum _{j=1}^s{b}_j{\mathbf{𝐤}}_j,with{\mathbf{𝐤}}_i=\mathbf{𝐪}(t_n,{\mathbf{𝐳}}_n;t_n+c_i{h}_n,h_n\sum _{j=1}^{i-1}{a}_{ij}{\mathbf{𝐤}}_j),$

which is obtained by solving (4.5) via a s-stage Runge–Kutta (RK) scheme with coefficients $\mathbf{𝐜}=\left[c_i\right],\mathbf{𝐀}=\left[a_{ij}\right]and\mathbf{𝐛}=\left[b_j\right]$.

• Local Linear Taylor discretization

$${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h_n)+\underset{0}{\overset{h_n}{\int }}{e}^{(h_n-s){\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)}\sum _{j=2}^p\frac{{\mathbf{𝐜}}_{n,j}}{j!}{s}^{j}ds,\text{ with }{\mathbf{𝐜}}_{n,j}=(\frac{d^{j+1}\mathbf{𝐱}\left(t\right)}{d{t}^{j+1}}-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)\frac{d^j\mathbf{𝐱}\left(t\right)}{d{t}^j}){\mid }_{t={\mathbf{𝐳}}_n},$$

which results from the approximation of ${\mathbf{𝐠}}_n$in (4.2) by its order-p truncated Taylor expansion.

• Multistep type Exponential Propagation discretization

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h)+h{\sum }_{j=0}^{p-1}{\gamma }_j{\mathrm{\nabla }}^j{\mathbf{𝐠}}_n(t_n,{\mathbf{𝐳}}_n),with{\gamma }_j=(-1{)}^j\underset{0}{\overset{1}{\int }}{e}^{(1-\theta )h{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)}\left(\begin{array}{c}-\theta \\ j\end{array}\right)d\theta ,$

which results from the interpolation of ${\mathbf{𝐠}}_n$in (4.2) by a polynomial of degree p on $t_n,\dots ,t_{n-p+1}$, where ${\mathrm{\nabla }}^j{\mathbf{𝐠}}_n(t_m,{\mathbf{𝐳}}_m)$ denotes the j-th backward difference of ${\mathbf{𝐠}}_n(t_m,{\mathbf{𝐳}}_m)$.

• Runge Kutta type Exponential Propagation discretization

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h)+h{\sum }_{j=0}^{p-1}{\gamma }_{j,p}{\mathrm{\nabla }}^j{\mathbf{𝐠}}_n(t_n,{\mathbf{𝐳}}_n),with{\gamma }_{j,p}=\underset{0}{\overset{1}{\int }}{e}^{(1-\theta )h{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)}\left(\begin{array}{c}\theta p\\ j\end{array}\right)d\theta ,$

which results from the interpolation of ${\mathbf{𝐠}}_n$in (4.2) by a polynomial of degree p on $t_n,\dots ,t_n+(p-1)h/p$,

• Linealized Exponential Adams discretization

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h)+h{\sum }_{j=1}^{p-1}{\sum }_{l=1}^j\frac{{\gamma }_{j+1}}{l}{\mathrm{\nabla }}^l{\mathbf{𝐠}}_n(t_n,{\mathbf{𝐳}}_n),with{\gamma }_{j+1}=(-1{)}^{j+1}\underset{0}{\overset{1}{\int }}{e}^{(1-\theta )h{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)}\theta \left(\begin{array}{c}-\theta \\ j\end{array}\right)d\theta ,$

which results from the interpolation of ${\mathbf{𝐠}}_n$in (4.2) by a Hermite polynomial of degree p on $t_n,\dots ,t_{n-p+1}$.

Local Linearization schemes

All numerical implementation ${\mathbf{𝐲}}_n$ of the LL (or of a HOLL) discretization ${\mathbf{𝐳}}_n$ involves approximations ${\tilde{\varphi }}_j$ to integrals ${\varphi }_j$ of the form

${\varphi }_j(\mathbf{𝐀},h)=\underset{0}{\overset{h}{\int }}{e}^{(h-s)\mathbf{𝐀}}{s}^{j-1}ds,j=1,2...,$

where A is an d $\times$ d matrix. Every numerical implementation ${\mathbf{𝐲}}_n$ of a Local Linear discretization ${\mathbf{𝐳}}_n$ of any order is generically called Local Linearization scheme.

Computing integrals involving matrix exponential

Among a number of algorithms to compute the integrals ${\varphi }_j$, those based on rational Padé and Krylov subspaces approximations for exponential matrix are preferred. For this, a central role is playing by the expression

$\sum _{i=1}^l{\varphi }_i(\mathbf{𝐀},h){\mathbf{𝐚}}_i=\mathbf{𝐋}{e}^{h\mathbf{𝐇}}\mathbf{𝐫},$

where ${\mathbf{𝐚}}_i$ are d-dimensional vectors,

$\mathbf{𝐇}=\left[\begin{array}{ccccc}\mathbf{𝐀}& {\mathbf{𝐯}}_l& {\mathbf{𝐯}}_{l-1}& \cdots & {\mathbf{𝐯}}_1\\ \mathbf{𝟎}& \mathbf{𝟎}& 1& \cdots & 0\\ \mathbf{𝟎}& \mathbf{𝟎}& 0& \ddots & 0\\ ⋮& ⋮& ⋮& \ddots & 1\\ \mathbf{𝟎}& \mathbf{𝟎}& 0& \cdots & 0\end{array}\right]\in {\mathbb{ℝ}}^{(d+l)\times (d+l)},$

$\mathbf{𝐋}=[\mathbf{𝐈}{\mathbf{𝟎}}_{d\times l}]$, $\mathbf{𝐫}=[{\mathbf{𝟎}}_{1\times (d+l-1)}1{]}^{⊺}$, ${\mathbf{𝐯}}_i={\mathbf{𝐚}}_i(i-1)!$, being $\mathbf{𝐈}$ the d-dimensional identity matrix.

If ${\mathbf{𝐏}}_{p,q}(2^{-k}\mathbf{𝐇}h)$ denotes the (p; q)-Padé approximation of $e^{2^{-k}\mathbf{𝐇}h}$ and k is the smallest integer number such that $|2^{-k}\mathbf{𝐇}h|\le \frac{1}{2},$

$|\sum _{i=1}^l{\varphi }_i(\mathbf{𝐀},h){\mathbf{𝐚}}_i-\mathbf{𝐋}{({\mathbf{𝐏}}_{p,q}(2^{-k}\mathbf{𝐇}h))}^{2^k}\mathbf{𝐫}|\propto h^{p+q+1}.$

If ${\mathbf{𝐤}}_{m,k}^{p,q}(h,\mathbf{𝐇},\mathbf{𝐫})$ denotes the (m; p; q; k) Krylov-Padé approximation of $e^{h\mathbf{𝐇}}\mathbf{𝐫}$,

$|\sum _{i=1}^l{\varphi }_i(\mathbf{𝐀},h){\mathbf{𝐚}}_i-{\mathbf{𝐋}\mathbf{𝐤}}_{m,k}^{p,q}(h,\mathbf{𝐇},\mathbf{𝐫})|\propto h^{\min m,p+q+1},$

where $m\le d$ is the dimension of the Krylov subspace.

Order 2 LL schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫},(4.6)$

where the matrices ${\mathbf{𝐌}}_n$, L and r are defined as

${\mathbf{𝐌}}_n=\left[\begin{array}{ccc}{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n)& {\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)& \mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(d+2)\times (d+2)},$

$\mathbf{𝐋}=\left[\begin{array}{ll}\mathbf{𝐈}& {\mathbf{𝟎}}_{d\times 2}\end{array}\right]$ and ${\mathbf{𝐫}}^{⊺}=\left[\begin{array}{ll}{\mathbf{𝟎}}_{1\times (d+1)}& 1\end{array}\right]$ with $p+q>1$ . For large systems of ODEs

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐋}\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐌}}_n,\mathbf{𝐫}),with{m}_n>1.$

Order 3 LL-Taylor schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐋}}_1({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐓}}_n{h}_n){)}^{2^{k_n}}{\mathbf{𝐫}}_1,(4.7)$

where for autonomous ODEs the matrices ${\mathbf{𝐓}}_n,{\mathbf{𝐋}}_1$ and ${\mathbf{𝐫}}_1$ are defined as

${\mathbf{𝐓}}_n=\left[\begin{array}{cccc}{\mathbf{𝐟}}_{\mathbf{𝐱}}({\mathbf{𝐲}}_n)& (\mathbf{𝐈}\otimes {\mathbf{𝐟}}^{⊺}({\mathbf{𝐲}}_n)){\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}({\mathbf{𝐲}}_n)\mathbf{𝐟}({\mathbf{𝐲}}_n)& \mathbf{𝟎}& \mathbf{𝐟}({\mathbf{𝐲}}_n)\\ 0& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(d+3)\times (d+3)},$

${\mathbf{𝐋}}_1=\left[\begin{array}{ll}\mathbf{𝐈}& {\mathbf{𝟎}}_{d\times 3}\end{array}\right]and{\mathbf{𝐫}}_1^{⊺}=\left[\begin{array}{ll}{\mathbf{𝟎}}_{1\times (d+2)}& 1\end{array}\right]$. Here, ${\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}$ denotes the second derivative of f with respect to x, and p + q > 2. For large systems of ODEs

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐋}\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐓}}_n,\mathbf{𝐫}),with{m}_n>2.$

Order 4 LL-RK schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐮}}_4+\frac{h_n}{6}(2{\mathbf{𝐤}}_2+2{\mathbf{𝐤}}_3+{\mathbf{𝐤}}_4),(4.8)$

where

${\mathbf{𝐮}}_j=\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-{\kappa }_j}{\mathbf{𝐌}}_n{c}_j{h}_n){)}^{2^{{\kappa }_j}}\mathbf{𝐫}$

and

${\mathbf{𝐤}}_j=\mathbf{𝐟}(t_n+c_j{h}_n,{\mathbf{𝐲}}_n+{\mathbf{𝐮}}_j+c_j{h}_n{\mathbf{𝐤}}_{j-1})-\mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐮}}_j-{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)c_j{h}_n,$

with ${\mathbf{𝐤}}_1\equiv \mathbf{𝟎},c=\left[\begin{array}{cccc}0& \frac{1}{2}& \frac{1}{2}& 1\end{array}\right],$ and p + q > 3. For large systems of ODEs, the vector ${\mathbf{𝐮}}_j$ in the above scheme is replaced by ${\mathbf{𝐮}}_j={\mathbf{𝐋}\mathbf{𝐤}}_{m_j,k_j}^{p,q}(c_j{h}_n,{\mathbf{𝐌}}_n,\mathbf{𝐫}).$

Locally Linearized Runge-Kutta of Dormand & Prince

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐮}}_s+h_n\sum _{j=1}^s{b}_j{\mathbf{𝐤}}_{j}and{\widehat{\mathbf{𝐲}}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐮}}_s+h_n\sum _{j=1}^s{\hat{b}}_j{\mathbf{𝐤}}_j,(4.9)$

where s = 6 is the number of stages,

${\mathbf{𝐤}}_j=\mathbf{𝐟}\mathbf{(}{t}_n+c_j{h}_n,{\mathbf{𝐲}}_n+{\mathbf{𝐮}}_j+h_n\sum _{i=1}^{s-1}{a}_{j,i}{\mathbf{𝐤}}_i)-\mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐮}}_j-{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)c_j{h}_n,$

with ${\mathbf{𝐤}}_1\equiv \mathbf{𝟎}$, and $a_{j,i},b_j,{\hat{b}}_{j}and{c}_j$ are the Runge-Kutta coefficients of Dormand and Prince and p + q > 4. For large systems of ODEs, the vector ${\mathbf{𝐮}}_j$ in the above scheme is replaced by ${\mathbf{𝐮}}_j={\mathbf{𝐋}\mathbf{𝐤}}_{m_j,k_j}^{p,q}(c_j{h}_n,{\mathbf{𝐌}}_n,\mathbf{𝐫}).$

 Stability and dynamics

Fig. 1 Phase portrait (dashed line) and approximate phase portrait (solid line) of the nonlinear ODE (4.10)-(4.11) computed by the LL2, RK4, LLRK4 schemes with step size h=1/2 , and p=q=6.

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

$p\le q\le p+2$

, 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

$m_n$

= 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

$\frac{d{x}_1}{dt}=-2x_1+x_2+1-\mu f(x_1,\lambda )(4.10)$ $\frac{d{x}_2}{dt}=x_1-2x_2+1-\mu f(x_2,\lambda )(4.11)$

with $f(u,\lambda )=u{(1+u+\lambda u^2)}^{-1}$, $\mu =15$ and $\lambda =57$, and its approximation by various schemes. This system has two stable stationary points and one unstable stationary point in the region $0\le x_1,x_2\le 1$.

LL methods for DDEs

Consider the d-dimensional Delay Differential Equation (DDE)

$\frac{d\mathbf{𝐱}\left(t\right)}{dt}=\mathbf{𝐟}(t,\mathbf{𝐱}\left(t\right),{\mathbf{𝐱}}_t(-{\tau }_1),\cdots ,{\mathbf{𝐱}}_t(-{\tau }_m)),t\in [t_0,T],(5.1)$

with m constant delays ${\tau }_i>0$ and initial condition ${\mathbf{𝐱}}_{t_0}(s)=\mathit{\phi }(s)$ for all $s\in [-\tau ,0],$ where f is a differentiable function, ${\mathbf{𝐱}}_t:[-\tau ,0]⟶{\mathbb{ℝ}}^d$ is the segment function defined as

${\mathbf{𝐱}}_t(s):=\mathbf{𝐱}(t+s),s\in [-\tau ,0],$

for all $t\in [t_0,T],\mathit{\phi }:[-\tau ,0]⟶{\mathbb{ℝ}}^d$ is a given function, and $\tau =\max \{{\tau }_{1,}...,{\tau }_m\}.$

Local Linear discretization

For a time discretization ${\left(t\right)}_h$ , the Local Linear discretization of the DDE (5.1) at each point $t_{n+1}\in {\left(t\right)}_h$ is defined by the recursive expression

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathrm{\Phi }(t_n,{\mathbf{𝐳}}_n,h_n;{\widetilde{\mathbf{𝐳}}}_{t_n}^1,..,{\widetilde{\mathbf{𝐳}}}_{t_n}^m),(5.2)$

where

$\mathrm{\Phi }(t_n,{\mathbf{𝐳}}_n,h_n;{\widetilde{\mathbf{𝐳}}}_{t_n}^1,..,{\widetilde{\mathbf{𝐳}}}_{t_n}^m)=\underset{0}{\overset{h_n}{\int }}{e}^{{\mathbf{𝐀}}_n(h_n-u)}[\sum _{i=1}^m{\mathbf{𝐁}}_n^i({\widetilde{\mathbf{𝐳}}}_{t_n}^i(u-{\tau }_i)-{\widetilde{\mathbf{𝐳}}}_{t_n}^i(-{\tau }_i))+{\mathbf{𝐝}}_n]du+\underset{0}{\overset{h_n}{\int }}\underset{0}{\overset{u}{\int }}{e}^{{\mathbf{𝐀}}_n(h_n-u)}{\mathbf{𝐜}}_{n}drdu$

${\widetilde{\mathbf{𝐳}}}_{t_n}^i:[-{\tau }_i,0]⟶{\mathbb{ℝ}}^d$ is the segment function defined as

${\widetilde{\mathbf{𝐳}}}_{t_n}^i(s):={\widetilde{\mathbf{𝐳}}}^i(t_n+s),s\in [-{\tau }_i,0],$

and

${\widetilde{\mathbf{𝐳}}}^i:[t_n-{\tau }_i,t_n]⟶{\mathbb{ℝ}}^d$

is a suitable approximation to

$\mathbf{𝐱}(t)$

for all

$t\in [t_n-{\tau }_i,t_n]$

such that

${\widetilde{\mathbf{𝐳}}}^i(t_n)={\mathbf{𝐳}}_n.$

Here,

${\mathbf{𝐀}}_n={\mathbf{𝐟}}_x(t_n,{\mathbf{𝐳}}_n,{\widetilde{\mathbf{𝐳}}}_{t_n}^1(-{\tau }_1),...,{\widetilde{\mathbf{𝐳}}}_{t_n}^m(-{\tau }_d)),{\mathbf{𝐁}}_n^i={\mathbf{𝐟}}_{x_t(-{\tau }_i)}(t_n,{\mathbf{𝐳}}_n,{\widetilde{\mathbf{𝐳}}}_{t_n}^1(-{\tau }_1),...,{\widetilde{\mathbf{𝐳}}}_{t_n}^m(-{\tau }_d))$

are constant matrices and

${\mathbf{𝐜}}_n={\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n,{\widetilde{\mathbf{𝐳}}}_{t_n}^1(-{\tau }_1),...,{\widetilde{\mathbf{𝐳}}}_{t_n}^m(-{\tau }_d))\text{ and }{\mathbf{𝐝}}_n=\mathbf{𝐟}\mathbf{(}{t}_n,{\mathbf{𝐳}}_n,{\widetilde{\mathbf{𝐳}}}_{t_n}^1(-{\tau }_1),...,{\widetilde{\mathbf{𝐳}}}_{t_n}^m(-{\tau }_d))$

are constant vectors. ${\mathbf{𝐟}}_t,{\mathbf{𝐟}}_{x}and{\mathbf{𝐟}}_{x_t(-{\tau }_i)}$ denote, respectively, the partial derivatives of f with respect to the variables t and x, and ${\mathbf{𝐱}}_t(-{\tau }_i)$. The Local Linear discretization (5.2) converges to the solution of (5.1) with order $\alpha =\min \{2,r\},$ if ${\widetilde{\mathbf{𝐳}}}_{t_n}^i$ approximates ${\mathbf{𝐳}}_{t_n}^i$ with order $r(i.e.,|{\mathbf{𝐳}}_{t_n}^i\mathbf{(}u-{\tau }_i\mathbf{)}-{\widetilde{\mathbf{𝐳}}}_{t_n}^i\mathbf{(}u-{\tau }_i\mathbf{)}|\propto h_n^r$ for all $u\in [0,h_n])$.

Local Linearization schemes

Fig. 2 Approximate paths of the Marchuk et al. (1991) antiviral immune model described by a stiff system of ten-dimensional nonlinear DDEs with five time delays. Step-size h=0.01 fixed, and p=q=6.

Depending of the approximations ${\widetilde{\mathbf{𝐳}}}_{t_n}^i$ and of the algorithm to compute $\mathit{\varphi }$ different Local Linearizations schemes can be defined. Every numerical implementation ${\mathbf{𝐲}}_n$ of a Local Linear discretization ${\mathbf{𝐳}}_n$ is generically called Local Linearization scheme.

Order 2 Polynomial LL schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫},(5.3)$

where the matrices ${\mathbf{𝐌}}_n,\mathbf{𝐋}$ and $\mathbf{𝐫}$ are defined as

${\mathbf{𝐌}}_n=\left[\begin{array}{ccc}{\mathbf{𝐀}}_n& {\mathbf{𝐜}}_n+\sum _{i=1}^m{\mathbf{𝐁}}_n^i{\mathit{\alpha }}_n^i& {\mathbf{𝐝}}_n\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(d+2)\times (d+2)},$

$\mathbf{𝐋}=\left[\begin{array}{ll}\mathbf{𝐈}& {\mathbf{𝟎}}_{d\times 2}\end{array}\right]$ and ${\mathbf{𝐫}}^{⊺}=\left[\begin{array}{ll}{\mathbf{𝟎}}_{1\times (d+1)}& 1\end{array}\right],h_n\le \tau$, and $p+q>1$. Here, the matrices ${\mathbf{𝐀}}_n$, ${\mathbf{𝐁}}_n^i$, ${\mathbf{𝐜}}_n$ and ${\mathbf{𝐝}}_n$ are defined as in (5.2), but replacing $\mathbf{𝐳}$ by $\mathbf{𝐲}$ and ${\mathit{\alpha }}_n^i=(\mathbf{𝐲}(t_{n+1}-{\tau }_i)-\mathbf{𝐲}(t_n-{\tau }_i))/h_n,$ where

$\mathbf{𝐲}\left(t\right)={\mathbf{𝐲}}_{n_t}+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_{n_t}(t-t_{n_t})){)}^{2^{k_n}}\mathbf{𝐫},$

with $n_t=\max \{n=0,1,2,...,:t_n\le t\text{ and }{t}_n\in {\left(t\right)}_h\}$, is the Local Linear Approximation to the solution of (5.1) defined through the LL scheme (5.3) for all $t\in [t_0,t_n]$ and by $\mathbf{𝐲}\left(t\right)=\mathit{\phi }\left(t\right)$ for $t\in [t_0-\tau ,t_0]$. For large systems of DDEs

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐋}\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐌}}_n,\mathbf{𝐫})and\mathbf{𝐲}\left(t\right)={\mathbf{𝐲}}_{n_t}+{\mathbf{𝐋}\mathbf{𝐤}}_{m_{n_t},k_{n_t}}^{p,q}(t-t_{n_t},{\mathbf{𝐌}}_{n_t},\mathbf{𝐫}),$

with $p+q>1$ and $m_n>2$.

LL methods for RDEs

Consider the d-dimensional Random Differential Equation (RDE)

$\frac{d\mathbf{𝐱}\left(t\right)}{dt}=\mathbf{𝐟}(\mathbf{𝐱}(t),\mathit{\xi }(t)),t\in [t_0,T],(6.1)$

with initial condition $\mathbf{𝐱}(t_0)={\mathbf{𝐱}}_0,$ where $\mathit{\xi }$ is a k-dimensional separable finite continuous stochastic process, and f is a differentiable function. Suppose that a realization (path) of $\mathit{\xi }$ is given.

Local Linear discretization

For a time discretization ${\left(t\right)}_h$, the Local Linear discretization of the RDE (6.1) at each point $t_{n+1}\in {\left(t\right)}_h$ is defined by the recursive expression

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h_n),with{\mathbf{𝐳}}_0={\mathbf{𝐱}}_0,$

where

$\mathit{\varphi }(t_n,{\mathbf{𝐳}}_n;h_n)=\underset{0}{\overset{h_n}{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}({\mathbf{𝐳}}_n,\mathit{\xi }(t_n))(h_n-u)}({\mathbf{𝐟}\mathbf{(}\mathbf{𝐳}}_n,\mathit{\xi }(t_n))+{\mathbf{𝐟}}_{\mathit{\xi }}({\mathbf{𝐳}}_n,\mathit{\xi }(t_n))(\tilde{\mathit{\xi }}(t_n+u)-\tilde{\mathit{\xi }}(t_n)))du$

and $\tilde{\mathit{\xi }}$ is an approximation to the process $\mathit{\xi }$ for all $t\in [t_0,T].$ Here, ${\mathbf{𝐟}}_x$ and ${\mathbf{𝐟}}_{\xi }$ denote the partial derivatives of $\mathbf{𝐟}$ with respect to $\mathbf{𝐱}$ and $\xi$, respectively.

Local Linearization schemes

Fig. 3 Phase portrait of trajectories of the Euler and LL schemes in the integration of the nonlinear RDE (6.2)-(6.3) with step size h=1/32, and p=q=6.

Depending of the approximations $\tilde{\mathit{\xi }}$ to the process $\mathit{\xi }$ and of the algorithm to compute $\mathit{\varphi }$ different Local Linearizations schemes can be defined. Every numerical implementation ${\mathbf{𝐲}}_n$ of the Local Linear discretization ${\mathbf{𝐳}}_n$ is generically called Local Linearization scheme.

LL schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫},$

where the matrices ${\mathbf{𝐌}}_n,\mathbf{𝐋}and\mathbf{𝐫}$ are defined as

${\mathbf{𝐌}}_n=\left[\begin{array}{ccc}{\mathbf{𝐟}}_{\mathbf{𝐱}}({\mathbf{𝐲}}_n,\mathit{\xi }(t_n))& {\mathbf{𝐟}}_{\mathit{\xi }}({\mathbf{𝐲}}_n,\mathit{\xi }(t_n)(\mathit{\xi }(t_{n+1})-\mathit{\xi }(t_n))/h_n& \mathbf{𝐟}({\mathbf{𝐲}}_n,\mathit{\xi }(t_n))\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(d+2)\times (d+2)},$

$\mathbf{𝐋}=\left[\begin{array}{ll}\mathbf{𝐈}& {\mathbf{𝟎}}_{d\times 2}\end{array}\right]$, ${\mathbf{𝐫}}^{⊺}=\left[\begin{array}{ll}{\mathbf{𝟎}}_{1\times (d+1)}& 1\end{array}\right]$, and p+q>1. For large systems of RDEs,

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐋}\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐌}}_n,\mathbf{𝐫}),p+q>1and{m}_n>2.$

The convergence rate of both schemes is $min\{2,2\gamma \}$, where is $\gamma$ the exponent of the Holder condition of $\mathit{\xi }$.

Figure 3 presents the phase portrait of the RDE

$\frac{d{x}_1}{dt}=-x_2+(1-x_1^2-x_2^2)x_1\sin (w^H(t){)}^2,x_1(0)=0.8(6.2)$

$\frac{d{x}_2}{dt}=x_1+(1-x_1^2-x_2^2)x_2\sin (w^H(t){)}^2,x_2(0)=0.1,(6.3)$

and its approximation by two numerical schemes, where $w^H$ denotes a fractional Brownian process with Hurst exponent H=0.45.

Strong LL methods for SDEs

Consider the d-dimensional Stochastic Differential Equation (SDE)

$d\mathbf{𝐱}(t)=\mathbf{𝐟}(t,\mathbf{𝐱}(t))dt+\sum _{i=1}^m{\mathbf{𝐠}}_i(t)d{\mathbf{𝐰}}^i(t),t\in [t_0,T],(7.1)$

with initial condition $\mathbf{𝐱}(t_0)={\mathbf{𝐱}}_0$, where the drift coefficient $\mathbf{𝐟}$ and the diffusion coefficient ${\mathbf{𝐠}}_i$ are differentiable functions, and ${\mathbf{𝐰}\mathbf{=}\mathbf{(}\mathbf{𝐰}}^1,\dots ,{\mathbf{𝐰}}^m\mathbf{)}$ is an m-dimensional standard Wiener process.

Local Linear discretization

For a time discretization ${\left(t\right)}_h$ , the order-$\mathbb{\gamma }$ (=1,1.5) Strong Local Linear discretization of the solution of the SDE (7.1) is defined by the recursive relation

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+{\mathit{\varphi }}_{\mathbb{\gamma }}(t_n,{\mathbf{𝐳}}_n;h_n)+\mathit{\xi }(t_n,{\mathbf{𝐳}}_n;h_n),with{\mathbf{𝐳}}_0={\mathbf{𝐱}}_0,$

where

${\mathit{\varphi }}_{\mathbb{\gamma }}(t_n,{\mathbf{𝐳}}_n;\delta )=\underset{0}{\overset{\delta }{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n)(\delta -u)}(\mathbf{𝐟}\mathbf{(}{t}_n,{\mathbf{𝐳}}_n)+{\mathbf{𝐚}}^{\mathbb{\gamma }}(t_n,{\mathbf{𝐳}}_n)u)du$

and

$\mathit{\xi }(t_n,{\mathbf{𝐳}}_n;\delta )=\sum _{i=1}^m\underset{t_n}{\overset{t_n+\delta }{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)(t_n+\delta -u)}{\mathbf{𝐠}}_i(u)d{\mathbf{𝐰}}^i(u).$

Here,

${\mathbf{𝐚}}^{\mathbb{\gamma }}(t_n,{\mathbf{𝐳}}_n)=\{\begin{array}{cc}{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)& for\mathbb{\gamma }=1\\ {\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)+\frac{1}{2}\sum _{j=1}^m(\mathbf{𝐈}\otimes {\mathbf{𝐠}}_j^{⊺}\left(t_n\right)){\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n){\mathbf{𝐠}}_j\left(t_n\right)& for\mathbb{\gamma }=1.5,\end{array}$

${\mathbf{𝐟}}_{\mathbf{𝐱}},{\mathbf{𝐟}}_t$ denote the partial derivatives of $\mathbf{𝐟}$ with respect to the variables $\mathbf{𝐱}$ and t, respectively, and ${\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}$ the Hessian matrix of $\mathbf{𝐟}$ with respect to $\mathbf{𝐱}$. The strong Local Linear discretization ${\mathbf{𝐳}}_{n+1}$ converges with order $\mathbb{\gamma }$ (=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 $(t_n,{\mathbf{𝐳}}_n)$, the equation for the residual $\mathbf{𝐫}$ is given by

$d\mathbf{𝐫}\left(t\right)={\mathbf{𝐪}}_{\gamma }(t_n,{\mathbf{𝐳}}_n;t,\mathbf{𝐫}\left(t\right))dt+\sum _{i=1}^m{\mathbf{𝐠}}_i(t)d{\mathbf{𝐰}}^i(t),\mathbf{𝐫}\left(t_n\right)=\mathbf{𝟎}$

for all $t\in [t_n,t_{n+1}]$, where

${\mathbf{𝐪}}_{\gamma }(t_n,{\mathbf{𝐳}}_n;s,\mathit{\xi })=\mathbf{𝐟}(s,{\mathbf{𝐳}}_n+{\mathit{\varphi }}_{\gamma }(t_n,{\mathbf{𝐳}}_n;s-t_n)+\mathit{\xi })-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n){\mathit{\varphi }}_{\gamma }(t_n,{\mathbf{𝐳}}_n;s-t_n)-{\mathbf{𝐚}}^{\gamma }(t_n,{\mathbf{𝐳}}_n)(s-t_n)-\mathbf{𝐟}(t_n,{\mathbf{𝐳}}_n).$

High Order Local Linear discretization of the SDE (7.1) at each point $t_{n+1}\in {\left(t\right)}_h$ is then defined by the recursive expression

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+{\mathit{\varphi }}_{\gamma }(t_n,{\mathbf{𝐳}}_n;h_n)+\widetilde{\mathbf{𝐫}}(t_n,{\mathbf{𝐳}}_n;h_n),with{\mathbf{𝐳}}_0={\mathbf{𝐱}}_0,$

where $\widetilde{\mathbf{𝐫}}$ is a strong approximation to the residual $\mathbf{𝐫}$ of order $\alpha$ higher than 1.5. The strong HOLL discretization ${\mathbf{𝐳}}_{n+1}$ converges with order $\alpha$ to the solution of (7.1).

Local Linearization schemes

Depending on the way of computing ${\mathit{\varphi }}_{\mathbb{\gamma }}$ , $\mathit{\xi }$ and $\widetilde{\mathbf{𝐫}}$ different numerical schemes could be obtained. Every numerical implementation ${\mathbf{𝐲}}_n$ of a strong Local Linear discretization ${\mathbf{𝐳}}_n$ of any order is generically called Strong Local Linearization scheme.

Order 1 SLL schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫}\mathbf{+}\sum _{i=1}^m{\mathbf{𝐠}}_i(t_n)\mathrm{\Delta }{\mathbf{𝐰}}_n^i,(7.2)$

where the matrices ${\mathbf{𝐌}}_n$, $\mathbf{𝐋}$ and $\mathbf{𝐫}$ are defined as in (4.6), $\mathrm{\Delta }{\mathbf{𝐰}}_n^i$ is a i.i.d. zero mean Gaussian random variable with variance $h_n$, and p+q>1. For large systems of SDEs, in the above scheme $({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫}$ is replaced by ${\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐌}}_n,\mathbf{𝐫})$.

Order 1.5 SLL schemes

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫}+\sum _{i=1}^m({\mathbf{𝐠}}_i(t_n)\mathrm{\Delta }{\mathbf{𝐰}}_n^i+{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\widetilde{\mathbf{𝐲}}}_n){\mathbf{𝐠}}_i(t_n)\mathrm{\Delta }{\mathbf{𝐳}}_n^i+\frac{d{\mathbf{𝐠}}_i(t_n)}{dt}(\mathrm{\Delta }{\mathbf{𝐰}}_n^i{h}_n-\mathrm{\Delta }{\mathbf{𝐳}}_n^i)),(7.3)$

where the matrices ${\mathbf{𝐌}}_n$, $\mathbf{𝐋}$ and $\mathbf{𝐫}$ are defined as

${\mathbf{𝐌}}_n=\left[\begin{array}{ccc}{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n)& {\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)+\frac{1}{2}\sum _{j=1}^m(\mathbf{𝐈}\otimes {\mathbf{𝐠}}_j^{⊺}\left(t_n\right)){\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐠}}_j\left(t_n\right)& \mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(d+2)\times (d+2)},$

$\mathbf{𝐋}=\left[\begin{array}{ll}\mathbf{𝐈}& {\mathbf{𝟎}}_{d\times 2}\end{array}\right],{\mathbf{𝐫}}^{⊺}=\left[\begin{array}{ll}{\mathbf{𝟎}}_{1\times (d+1)}& 1\end{array}\right]$, $\mathrm{\Delta }{\mathbf{𝐳}}_n^i$ is a i.i.d. zero mean Gaussian random variable with variance $E((\mathrm{\Delta }{\mathbf{𝐳}}_n^i{)}^2)=\frac{1}{3}{h}_n^3$ and covariance $E(\mathrm{\Delta }{\mathbf{𝐰}}_n^i\mathrm{\Delta }{\mathbf{𝐳}}_n^i)=\frac{1}{2}{h}_n^2$ and p+q>1. For large systems of SDEs, in the above scheme $({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫}$ is replaced by ${\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐌}}_n,\mathbf{𝐫})$.

Order 2 SLL-Taylor schemes

${\mathbf{𝐲}}_{t_{n+1}}={\mathbf{𝐲}}_n+\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫}+\sum _{j=1}^m{\mathbf{𝐠}}_j\left(t_n\right)\mathrm{\Delta }{\mathbf{𝐰}}_n^j+\sum _{j=1}^m{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐠}}_j\left(t_n\right){\tilde{J}}_{(j,0)}+\sum _{j=1}^m\frac{d{\mathbf{𝐠}}_{{}_j}}{dt}\left(t_n\right){\tilde{J}}_{(0,j)}$

$+\sum _{j_1,j_2=1}^m(\mathbf{𝐈}\otimes {\mathbf{𝐠}}_{j_2}^{⊺}\left(t_n\right)){\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐠}}_{j_1}\left(t_n\right){\tilde{J}}_{(j_1,j_2,0)},(7.4)$

where ${\mathbf{𝐌}}_n$, $\mathbf{𝐋}$, $\mathbf{𝐫}$ and $\mathrm{\Delta }{\mathbf{𝐰}}_n^i$ are defined as in the order-1 SLL schemes, and ${\tilde{J}}_{\alpha }$ is order 2 approximation to the multiple Stratonovish integral $J_{\alpha }$.

Order 2 SLL-RK schemes

File:Figure SSDE4.png

Fig. 4, Top: Evolution of domains in the phase plane of the harmonic oscillator (7.6), with ε=0 and ω=σ=1. Images of the initial unit circle (green) are obtained at three time moments T by the exact solution (black), and by the schemes SLL1 (blue) and Implicit Euler (red) with h=0.05. Bottom: Expected value of the energy (solid line) along the solution of the nonlinear oscillator (7.6), with ε=1 and ω=100, and its approximation (circles) computed via Monte Carlo with 10000 simulations of the SLL1 scheme with h=1/2 and p=q=6.

For SDEs with a single Wiener noise (m=1)

${\mathbf{𝐲}}_{t_{n+1}}={\mathbf{𝐲}}_n+\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;h_n)+\frac{h_n}{2}({\mathbf{𝐤}}_1+{\mathbf{𝐤}}_2)+\mathbf{𝐠}\left(t_n\right)\mathrm{\Delta }{w}_n+\frac{(\mathbf{𝐠}\left(t_{n+1}\right)-\mathbf{𝐠}\left(t_n\right))}{h_n}{J}_{(0,1)}(7.5)$

where

${\mathbf{𝐤}}_1=\mathbf{𝐟}(t_n+\frac{h_n}{2},{\mathbf{𝐲}}_n+\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;\frac{h_n}{2})+{\gamma }_{+})-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n)\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;\frac{h_n}{2})-\mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)-{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)\frac{h_n}{2},$${\mathbf{𝐤}}_2=\mathbf{𝐟}(t_n+\frac{h_n}{2},{\mathbf{𝐲}}_n+\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;\frac{h_n}{2})+{\gamma }_{-})-{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n)\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;\frac{h_n}{2})-\mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)-{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)\frac{h_n}{2},$

with ${\gamma }_{\pm }=\frac{1}{h_n}\mathbf{𝐠}\left(t_n\right)({\tilde{J}}_{(1,0)}\pm \sqrt{2{\tilde{J}}_{(1,1,0)}{h}_n-{\tilde{J}}_{(1,0)}^2})$. Here, $\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;h_n)=\mathbf{𝐋}({\mathbf{𝐏}}_{p,q}(2^{-k_n}{\mathbf{𝐌}}_n{h}_n){)}^{2^{k_n}}\mathbf{𝐫}$ for low dimensional SDEs, and $\tilde{\mathit{\varphi }}(t_n,{\mathbf{𝐲}}_n;h_n)={\mathbf{𝐋}\mathbf{𝐤}}_{m_n,k_n}^{p,q}(h_n,{\mathbf{𝐌}}_n,\mathbf{𝐫})$ for large systems of SDEs, where ${\mathbf{𝐌}}_n$, $\mathbf{𝐋}$, $\mathbf{𝐫}$, $\mathrm{\Delta }{\mathbf{𝐰}}_n^i$ and ${\tilde{J}}_{\alpha }$ are defined as in the order-2 SLL-Taylor schemes, p+q>1 and $m_n>2$.

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 $p\le q\le p+2$ 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 ${\mathbf{𝐠}}_i(t)\approx 0$), 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

$\begin{array}{ll}dx(t)=y(t)dt,& x_1(0)=0.01\\ dy(t)=-({\omega }^{2}x(t)+ϵx^4(t))dt+\sigma d{w}_t,& x_1(0)=0.1,\end{array}(7.6)$

and their approximations by two numerical schemes.

Weak LL methods for SDEs

Consider the d-dimensional stochastic differential equation

$d\mathbf{𝐱}(t)=\mathbf{𝐟}(t,\mathbf{𝐱}(t))dt+\sum _{i=1}^m{\mathbf{𝐠}}_i(t)d{\mathbf{𝐰}}^i(t),t\in [t_0,T],(8.1)$

with initial condition $\mathbf{𝐱}(t_0)={\mathbf{𝐱}}_0$, where the drift coefficient $\mathbf{𝐟}$ and the diffusion coefficient ${\mathbf{𝐠}}_i$ are differentiable functions, and ${\mathbf{𝐰}\mathbf{=}\mathbf{(}\mathbf{𝐰}}^1,\dots ,{\mathbf{𝐰}}^m\mathbf{)}$ is an m-dimensional standard Wiener process.

Local Linear discretization

For a time discretization ${\left(t\right)}_h$, the order-$\mathbb{\beta }$ $(=1,2)$ Weak Local Linear discretization of the solution of the SDE (8.1) is defined by the recursive relation

${\mathbf{𝐳}}_{n+1}={\mathbf{𝐳}}_n+{\mathit{\varphi }}_{\mathbb{\beta }}(t_n,{\mathbf{𝐳}}_n;h_n)+\mathit{\eta }(t_n,{\mathbf{𝐳}}_n;h_n),with{\mathbf{𝐳}}_0={\mathbf{𝐱}}_0,$

where

${\mathit{\varphi }}_{\mathbb{\beta }}(t_n,{\mathbf{𝐳}}_n;\delta )=\underset{0}{\overset{\delta }{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)(\delta -u)}(\mathbf{𝐟}\mathbf{(}{t}_n,{\mathbf{𝐳}}_n)+{\mathbf{𝐛}}^{\mathbb{\beta }}(t_n,{\mathbf{𝐳}}_n)u)du$

with

${\mathbf{𝐛}}^{\mathbb{\beta }}(t_n,{\mathbf{𝐳}}_n)=\{\begin{array}{ll}{\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)& \text{for }\mathbb{\beta }=1\\ {\mathbf{𝐟}}_t(t_n,{\mathbf{𝐳}}_n)+\frac{1}{2}\sum _{j=1}^m(\mathbf{𝐈}\otimes {\mathbf{𝐠}}_j^{⊺}\left(t_n\right)){\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n){\mathbf{𝐠}}_j\left(t_n\right)& \text{for }\mathbb{\beta }=2,\end{array}$

and $\mathit{\eta }(t_n,{\mathbf{𝐳}}_n;\delta )$ is a zero mean stochastic process with variance matrix

$\mathrm{\Sigma }(t_n,{\mathbf{𝐳}}_n;\delta )=\underset{0}{\overset{\delta }{\int }}{e}^{{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐳}}_n)(\delta -s)}\mathbf{𝐆}(t_n+s){\mathbf{𝐆}}^{⊺}(t_n+s)e^{{\mathbf{𝐟}}_{\mathbf{𝐱}}^{⊺}(t_n,{\mathbf{𝐳}}_n)(\delta -s)}ds.$

Here, ${\mathbf{𝐟}}_{\mathbf{𝐱}}$, ${\mathbf{𝐟}}_t$ denote the partial derivatives of $\mathbf{𝐟}$ with respect to the variables $\mathbf{𝐱}$ and t, respectively, ${\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}$ the Hessian matrix of $\mathbf{𝐟}$ with respect to $\mathbf{𝐱}$, and $\mathbf{𝐆}(t)=[{\mathbf{𝐠}}_1(t),...,{\mathbf{𝐠}}_m(t)]$. The weak Local Linear discretization ${\mathbf{𝐳}}_{n+1}$ converges with order $\mathbb{\beta }$ (=1,2) to the solution of (8.1).

Local Linearization schemes

Depending on the way of computing ${\mathit{\varphi }}_{\mathbb{\beta }}$ and $\mathrm{\Sigma }$ different numerical schemes could be obtained. Every numerical implementation ${\mathbf{𝐲}}_n$ of the Weak Local Linear discretization ${\mathbf{𝐳}}_n$ is generically called Weak Local Linearization scheme.

Order 1 WLL scheme

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐁}}_{14}+({\mathbf{𝐁}}_{12}{\mathbf{𝐁}}_{11}^{⊺}{)}^{1/2}{\mathit{\xi }}_n$

where, for SDEs with autonomous diffusion coefficients, ${\mathbf{𝐁}}_{11}$, ${\mathbf{𝐁}}_{12}$ and ${\mathbf{𝐁}}_{14}$ are the submatrices defined by the partitioned matrix $\mathbf{𝐁}={\mathbf{𝐏}}_{p,q}(2^{-k_n}{{ℳ}}_n{h}_n){)}^{2^{k_n}}$, with

${{ℳ}}_n=\left[\begin{array}{cccc}{\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n)& {\mathbf{𝐆}\mathbf{𝐆}}^{⊺}& {\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)& \mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n)\\ \mathbf{𝟎}& -{\mathbf{𝐟}}_{\mathbf{𝐱}}^{⊺}(t_n,{\mathbf{𝐲}}_n)& \mathbf{𝟎}& \mathbf{𝟎}\\ \mathbf{𝟎}& \mathbf{𝟎}& 0& 1\\ \mathbf{𝟎}& \mathbf{𝟎}& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(2d+2)\times (2d+2)},$

and $\{{\mathit{\xi }}_n\}$ is a sequence of d-dimensional independent two-points distributed random vectors satisfying $P({\xi }_n^k=\pm 1)=\frac{1}{2}$.

Order 2 WLL scheme

${\mathbf{𝐲}}_{n+1}={\mathbf{𝐲}}_n+{\mathbf{𝐁}}_{16}+({\mathbf{𝐁}}_{14}{\mathbf{𝐁}}_{11}^{⊺}{)}^{1/2}{\mathit{\xi }}_n$

where ${\mathbf{𝐁}}_{11}$, ${\mathbf{𝐁}}_{14}$ and ${\mathbf{𝐁}}_{16}$ are the submatrices defined by the partitioned matrix $\mathbf{𝐁}={\mathbf{𝐏}}_{p,q}(2^{-k_n}{{ℳ}}_n{h}_n){)}^{2^{k_n}}$ with

${{ℳ}}_n=\left[\begin{array}{cccccc}\mathbf{𝐉}& {\mathbf{𝐇}}_2& {\mathbf{𝐇}}_1& {\mathbf{𝐇}}_0& {\mathbf{𝐚}}_2& {\mathbf{𝐚}}_1\\ \mathbf{𝟎}& -{\mathbf{𝐉}}^{⊺}& \mathbf{𝐈}& \mathbf{𝟎}& \mathbf{𝟎}& \mathbf{𝟎}\\ \mathbf{𝟎}& \mathbf{𝟎}& -{\mathbf{𝐉}}^{⊺}& \mathbf{𝐈}& \mathbf{𝟎}& \mathbf{𝟎}\\ \mathbf{𝟎}& \mathbf{𝟎}& \mathbf{𝟎}& -{\mathbf{𝐉}}^{⊺}& \mathbf{𝟎}& \mathbf{𝟎}\\ \mathbf{𝟎}& \mathbf{𝟎}& \mathbf{𝟎}& \mathbf{𝟎}& 0& 1\\ \mathbf{𝟎}& \mathbf{𝟎}& \mathbf{𝟎}& \mathbf{𝟎}& 0& 0\end{array}\right]\in {\mathbb{ℝ}}^{(4d+2)\times (4d+2)},$

$\mathbf{𝐉}={\mathbf{𝐟}}_{\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐚}}_1=\mathbf{𝐟}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐚}}_2={\mathbf{𝐟}}_t(t_n,{\mathbf{𝐲}}_n)+\frac{1}{2}\sum _{i=1}^m(\mathbf{𝐈}\otimes ({\mathbf{𝐠}}^i(t_n){)}^{⊺}){\mathbf{𝐟}}_{\mathbf{𝐱}\mathbf{𝐱}}(t_n,{\mathbf{𝐲}}_n){\mathbf{𝐠}}^i(t_n)$

and

${\mathbf{𝐇}}_0=\mathbf{𝐆}(t_n){\mathbf{𝐆}}^{⊺}(t_n){\mathbf{𝐇}}_1=\mathbf{𝐆}(t_n)\frac{d{\mathbf{𝐆}}^{⊺}(t_n)}{dt}+\frac{d\mathbf{𝐆}(t_n)}{dt}{\mathbf{𝐆}}^{⊺}(t_n){\mathbf{𝐇}}_2=\frac{d\mathbf{𝐆}(t_n)}{dt}\frac{d{\mathbf{𝐆}}^{⊺}(t_n)}{dt}\text{.}$

Stability and dynamics

Fig. 5 Approximate mean of the SDE (8.2) computed via Monte Carlo with 100 simulations of various schemes with h=1/16 and p=q=6.

By construction, the weak LL discretizations inherit the stability and dynamics of the linear SDEs, but it is not the case of the weak LL schemes in general. WLL schemes, with

$p\le q\le p+2,$

preserve the first two moments of the linear SDEs, and inherits the mean-square stability or instability that such solution may have. This includes, for instance, the equations of coupled harmonic oscillators driven by random force, and large systems of stiff linear SDEs that result from the method of lines for linear stochastic partial differential equations. Moreover, these WLL schemes preserve the ergodicity of the linear equations, and are geometrically ergodic for some classes of nonlinear SDEs. For nonlinear SDEs with small noise (i.e., (8.1) with

${\mathbf{𝐠}}_i(t)\approx 0$

), the solutions of these WLL 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 mean of the WLL scheme. For instance, Fig. 5 shows the approximate mean of the SDE

$dx=-t^{2}xdt+\frac{3}{2(t+1)}{e}^{-t^3/3}d{w}_t,x(0)=1,(8.2)$

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. 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. doi:10.1007/11758501\_22, doi:10.1016/j.amc.2006.06.096 and doi: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-6

Reference

• Carbonell 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.; Jimenez J.C.; Ozaki T. (2006). "Local Linearization-Runge Kutta (LLRK) methods for solving ordinary differential equations,". Lecture Note in Computer Sciences, Springer-Verlag. Lecture Notes in Computer Science. 3991: 132–139. doi:10.1007/11758501_22. ISBN 978-3-540-34379-0.

• 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.

• 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.

• de la Cruz H.; Biscay R.J.; Jimenez J.C.; Carbonell F.; Ozaki T. (2010). "High Order Local Linearization methods: an approach for constructing A-stable high order explicit schemes for stochastic differential equations with additive noise,". BIT Numer. Math. 50 (3): 509–539. doi:10.1007/s10543-010-0272-6.

• de la Cruz H.; Jimenez J.C.; Zubelli J.P. (2017). "Locally Linearized methods for the simulation of stochastic oscillators driven by random forces,". BIT Numer. Math. 57: 123–151. doi:10.1007/s10543-016-0620-2.

• M. Hochbruck.; A. Ostermann. (2011). "Exponential multistep methods of Adams-type,". BIT Numer. Math. 51 (4): 889–908. doi:10.1007/s10543-011-0332-6.

• Jimenez J.C. (2009). "Local Linearization methods for the numerical integration of ordinary differential equations: An overview,". ICTP Technical Report. 035: 357–373.

• 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.

• Jimenez J.C.; Carbonell F. (2009). "Rate of convergence of local linearization schemes for random differential equations,". BIT Numer. Math. 49 (2): 357–373. doi:10.1007/s10543-009-0225-0.

• Jimenez J.C.; Carbonell F. (2015). "Convergence rate of weak Local Linearization schemes for stochastic differential equations with additive noise,". J. Comput. Appl. Math. 279: 106–122. doi:10.1016/j.cam.2014.10.021.

• 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.

• 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.

• 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.

• Tokman M. (2006). "Efficient integration of large stiff systems of ODEs with exponential propagation iterative (EPI) methods,". J. Comput. Physics. 213 (2): 748–776. Bibcode:2006JCoPh.213..748T. doi:10.1016/j.jcp.2005.08.032.

This article "Local Linearization Method" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Local Linearization Method. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---