Content deleted Content added
A bit iffy (talk | contribs) + short description |
m Moving Category:Numerical integration (quadrature) to Category:Numerical integration per Wikipedia:Categories for discussion/Speedy |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 49:
=== Local linear discretization ===
For a time discretization <math>\left( t\right) _{h}</math>, the ''Local Linear discretization'' of the ODE (4.1) at each point <math>t_{n+1}\in \left(
t\right) _{h}</math> is defined by the recursive expression <ref name=":8">Jimenez J.C. (2009). "Local Linearization methods for the numerical integration of ordinary differential equations: An overview". [https://inis.iaea.org/search/search.aspx?orig_q=RN:40101978 ICTP Technical Report]. 035: 357–373.</ref>
<div style="text-align: center;">
Line 58:
The Local Linear discretization (4.3) [[Rate of convergence|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.<ref name=":22" />
=== High-order local linear discretizations ===
For a time discretization <math>(t)_h,</math> a ''high-order local linear (HOLL)'' discretization of the ODE (4.1) at each point <math>t_{n+1} \in (t)_h</math> is defined by the recursive expression <ref name= ":8"/><ref name= ":3"/><ref name= ":2"/><ref name=":1" />
Line 85:
HOLL discretizations are, for instance, the followings:
* ''Locally Linearized Runge Kutta discretization''<ref name=":1">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 3991: 132–139, Springer-Verlag. [[doi:10.1007/
<div style="text-align: left;">
<math>\qquad \mathbf{z}_{n+1}=\mathbf{z}_n+\mathbf{\phi }(t_n,\mathbf{z}_n;h_n)+h_n \sum_{j=1}^s b_j \mathbf{k}_j,\quad \text{ with } \quad \mathbf{k}_i = \mathbf{q}(t_n,\mathbf{z}_n;\text{ }t_n + c_i h_n \mathbf{,} \mathbf{} h_n \sum_{j=1}^{i-1} a_{ij}\mathbf{k}_j), </math>
Line 96:
</div>
which results from the approximation of <math>\mathbf{g}_{n}</math> in (4.2) by its order-''p'' truncated [[Taylor series|Taylor expansion]].
* ''Multistep-type exponential propagation discretization''
Line 110:
</div>
which results from the interpolation of <math>\mathbf{g}_{n}</math> in (4.2) by a polynomial of degree ''p'' on <math>t_{n},\ldots, t_{n-p+1}</math>, where <math>\nabla ^{j}\mathbf{g}_{n}(t_{m},\mathbf{z}_{m})</math> denotes the ''j''-th [[backward difference]] of <math>\mathbf{g}_{n}(t_{m},\mathbf{z}_{m})</math>.
* ''Runge Kutta type Exponential Propagation discretization'' <ref name=":17">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]].</ref>
Line 123:
</div>
which results from the interpolation of <math>\mathbf{g}_{n}</math> in (4.2) by a polynomial of degree ''p'' on <math>t_{n},\ldots, t_{n}+(p-1)h/p</math>,
* ''Linealized exponential Adams discretization''<ref name=":7">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]].</ref>
Line 136:
</div>
which results from the interpolation of <math>\mathbf{g}_{n}</math> in (4.2) by a [[Hermite polynomials|Hermite polynomial]] of degree ''p'' on <math>t_{n},\ldots, t_{n-p+1}</math>.
=== Local linearization schemes ===
Line 145:
</div>
where '''A''' is a ''d'' × ''d'' matrix. Every numerical implementation <math>\mathbf{y}_n</math> of the LL (or of a HOLL) <math>\mathbf{z}_{n}</math> of any order is generically called ''Local Linearization scheme''.<ref name= ":8"/><ref name=":25">
==== Computing integrals involving matrix exponential ====
Line 189:
where <math>m \leq d</math> is the dimension of the Krylov subspace.
==== Order-2 LL schemes ====
<div style="text-align: center;">
Line 221:
</div>
==== Order-3 LL-Taylor schemes ====
<div style="text-align: center;">
<math>\mathbf{y}_{n+1}=\mathbf{y}_n+\mathbf{L}_{1}(\mathbf{P}_{p,q}(2^{-k_n}
\mathbf{T}_n h_n))^{2^{k_n}}\mathbf{r}_1 \mathbf{,}</math> <ref name=":2" /> <math> \qquad \qquad (4.7)</math>
</div>
where for [[Autonomous system (mathematics)|autonomous]] ODEs the matrices <math>\mathbf{T}_{n}, \mathbf{L}_{1}</math> and <math>\mathbf{r}_{1}</math> are defined as
Line 262:
<div style="text-align: center;">
<math>\mathbf{y}_{n+1}=\mathbf{y}_{n}+\mathbf{u}_{4}+\frac{h_{n}}{6}(2\mathbf{k}
_{2}+2\mathbf{k}_{3}+\mathbf{k}_{4}),\quad</math> <ref name=":3" />
</div>
Line 293:
<div style="text-align: center;">
<math>\mathbf{y}_{n+1}=\mathbf{y}_n+\mathbf{u}_s+h_n\sum_{j=1}^s b_j \mathbf{k}_j \qquad \text{ and } \qquad \widehat{\mathbf{y}}_{n+1}=\mathbf{y}_n+\mathbf{u}_s+h_n\sum_{j=1}^s \widehat{b}_j \mathbf{k}_j,\quad </math>
<ref name=":15">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]].</ref><ref name=":16">
<math>\qquad \qquad (4.9)</math>
</div>
Line 307:
==== Stability and dynamics ====
[[File:Figure ODE.jpg|thumb|488x488px|'''Fig. 1''' Phase portrait (dashed line) and approximate phase portrait (solid line) of the nonlinear ODE (4.10)-(4.11) computed by the order-2 LL scheme (4.2), the order-4 classical Rugen-Kutta scheme [[Runge–Kutta methods|''RK''4]], ''and the order-4 LLRK''4 schemes (4.8) with step size h=1/2
: <math>
Line 359:
</div>
and <math>\widetilde{\mathbf{z}}^i:\left[ t_n-\tau_i,t_n\right] \longrightarrow \mathbb{R}^d</math> is a suitable approximation to <math>\mathbf{x}(t)</math> for all <math>t\in \lbrack t_n-\tau_i,t_n]</math> such that <math>\widetilde{\mathbf{z}}^i(t_n)=\mathbf{z}_n.</math> Here,<div style="text-align: center;">
<math>\mathbf{A}_n=\mathbf{f}_x(t_n,\mathbf{z}_n,\widetilde{\mathbf{z}}_{t_n}^1(-\tau_1),\ldots,\widetilde{\mathbf{z}}_{t_n}^m(-\tau_d)),
\text{ }\mathbf{B}_n^i=\mathbf{f}_{x_t(-\tau_i)}(t_n,\mathbf{z}_n,\widetilde{\mathbf{z}}_{t_n}^1(-\tau_1),\ldots,\widetilde{\mathbf{z}}_{t_n}^m(-\tau_d)) </math>
Line 374:
are constant vectors. <math>\mathbf{f}_{t}, \mathbf{f}_{x} \quad and \quad \mathbf{f}
_{x_{t}(-\tau _{i})}</math> denote, respectively, the partial derivatives of '''f''' with respect to the variables ''t'' and '''''x
\mathbf{)}-\widetilde{\mathbf{z}}_{t_{n}}^{i}\mathbf{(}u-\tau _{i}\mathbf{)}
\right\vert \propto h_{n}^{r}</math> for all <math>u\in \lbrack 0,h_{n}])</math>.
=== Local linearization schemes ===
[[File:Figure DDE.png|thumb|450x450px|'''Fig. 2''' Approximate paths of the [https://doi.org/10.1016/S0022-5193(05)80142-0 Marchuk et al. (1991)] antiviral immune model described by a stiff system of ten-dimensional nonlinear DDEs with five time delays: top, [[doi:10.1016/S0168-9274(00)00055-6|continuous Runge–Kutta (2,3)]] scheme
Depending on the approximations <math>\widetilde{\mathbf{z}}_{t_{n}}^{i}</math> and on the algorithm to compute <math>\mathbf{\phi }</math> different Local Linearizations schemes can be defined. Every numerical implementation <math>\mathbf{y}_{n}</math> of a Local Linear discretization <math>\mathbf{z}_{n}</math> is generically called ''local linearization scheme''.
Line 474:
<div style="text-align: center;">
<math>\mathbf{y}_{n+1}=\mathbf{y}_n+\mathbf{L}(\mathbf{P}_{p,q}(2^{-k_n} \mathbf{M}_n h_{n}))^{2^{k_n}}\mathbf{r,} \quad </math> <ref name=":24" />
where the matrices <math>\mathbf{M}_{n}, \quad \mathbf{L} \quad and \quad \mathbf{r}</math> are defined as
<math>\mathbf{M}_{n}=\left[
Line 488 ⟶ 487:
\end{array}
\right]</math>
<math>\mathbf{L}=\left[
Line 536 ⟶ 534:
=== Local linear discretization ===
For a time discretization <math>\left( t\right) _{h}</math> , the order-<math>\mathbb{\gamma }</math> (=1,1.5) ''Strong Local Linear discretization'' of the solution of the SDE (7.1) is defined by the recursive relation <ref name=":14">
<div style="text-align: center;">
Line 777 ⟶ 775:
_{11}^{\intercal })^{1/2}\mathbf{\xi }_{n} </math>
<ref name=":11">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]].</ref><ref name=":0">Carbonell F.; Jimenez J.C.; Biscay R.J. (2006). "Weak local linear discretizations for stochastic differential equations: convergence and numerical schemes". J. Comput. Appl. Math. 197: 578–596. [[doi:10.1016/j.cam.2005.11.032]].</ref>
</div>
where, for SDEs with autonomous diffusion coefficients, <math>\mathbf{B}_{11}</math>, <math>\mathbf{B}_{12}</math> and <math>\mathbf{B}_{14}</math> are the submatrices defined by the [[Block matrix|partitioned matrix]] <math>\mathbf{B}=\mathbf{P}_{p,q}(2^{-k_{n}}\mathcal{M}_{n}h_{n}))^{2^{k_{n}}}</math>, with
Line 801 ⟶ 799:
<math>\mathbf{y}_{n+1}=\mathbf{y}_{n}+\mathbf{B}_{16}+(\mathbf{B}_{14}\mathbf{B}
_{11}^{\intercal })^{1/2}\mathbf{\xi }_{n}, </math>
<ref name=":11" />
</div>
Line 842 ⟶ 840:
==== Stability and dynamics====
[[File:Figure WSDE.png|thumb|429x429px|'''''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 [[Random dynamical system|dynamics]] of the linear SDEs, but it is not the case of the weak LL schemes in general. WLL schemes, with <math>p\leq q\leq p+2,</math> preserve the [[Moment (mathematics)|first two moments]] of the linear SDEs, and inherits the mean-square stability or instability that such solution may have.<ref name=":11" /> 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.<ref name=":6">
<math>dx=-t^{2}x\text{ }dt+\frac{3}{2(t+1)}e^{-t^{3}/3}\text{ }dw_{t},\qquad \qquad x(0)=1, \qquad \quad(8.2)</math>
Line 851 ⟶ 849:
Below is a time line of the main developments of the Local Linearization (LL) method.
* Pope D.A. (1963) introduces the LL discretization for ODEs and the LL scheme based on Taylor expansion.
* Ozaki T. (1985) introduces the LL method for the integration and estimation of SDEs. The term "Local Linearization" is used for first time.
* Biscay R. et al. (1996) reformulate the strong LL method for SDEs.<ref name=":20">
* Shoji I. and Ozaki T. (1997) reformulate the weak LL method for SDEs.<ref name=":21">
* Hochbruck M. et al. (1998) introduce the LL scheme for ODEs based on Krylov subspace approximation.
* Jimenez J.C. (2002) introduces the LL scheme for ODEs and SDEs based on rational Padé approximation.
* Carbonell F.M. et al. (2005) introduce the LL method for RDEs.
* Jimenez J.C. et al. (2006) introduce the LL method for DDEs.
* De la Cruz H. et al. (2006, 2007) and Tokman M. (2006) introduce the two classes of HOLL integrators for ODEs: the integrator-based <ref name=":1" /> and the quadrature-based.<ref name=":17" /><ref name=":2" />
* De la Cruz H. et al. (2010) introduce strong HOLL method for SDEs.
== References ==
Line 866 ⟶ 864:
[[Category:Numerical analysis]]
[[Category:Numerical integration
| |||