# American Institute of Mathematical Sciences

January  2021, 26(1): 299-336. doi: 10.3934/dcdsb.2020331

## Computing complete Lyapunov functions for discrete-time dynamical systems

 1 Department of Mathematics, University of Sussex, Falmer BN1 9QH, United Kingdom 2 Faculty of Physical Sciences, University of Iceland, 107 Reykjavik, Iceland

Received  May 2020 Revised  October 2020 Published  November 2020

Fund Project: The research in this paper was supported by the Icelandic Research Fund (Rannís) grant number 163074-052, Complete Lyapunov functions: Efficient numerical computation

A complete Lyapunov function characterizes the behaviour of a general discrete-time dynamical system. In particular, it divides the state space into the chain-recurrent set where the complete Lyapunov function is constant along trajectories and the part where the flow is gradient-like and the complete Lyapunov function is strictly decreasing along solutions. Moreover, the level sets of a complete Lyapunov function provide information about attractors, repellers, and basins of attraction.

We propose two novel classes of methods to compute complete Lyapunov functions for a general discrete-time dynamical system given by an iteration. The first class of methods computes a complete Lyapunov function by approximating the solution of an ill-posed equation for its discrete orbital derivative using meshfree collocation. The second class of methods computes a complete Lyapunov function as solution of a minimization problem in a reproducing kernel Hilbert space. We apply both classes of methods to several examples.

Citation: Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
##### References:

show all references

##### References:
Example (24) with solving $\Delta v(x,y) = -1$. Chain-recurrent set (top) approximated by the set $\{(x,y)\, \mid\, \Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (middle) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$. $\Delta v$ is approximately zero on the chain-recurrent set (origin) and negative everywhere else. Bottom: Constructed complete Lyapunov function $v(x,y)$, which has a minimum at the origin
Example (24) with equality and inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ (middle). Again, the orbital derivative $\Delta v$ is correctly approximated being zero on the chain-recurrent set (origin) and negative everywhere else. Bottom: Constructed complete Lyapunov function $v(x,y)$, which has a minimum at the origin. The point with equality constraint was $(0.5,0)$
Example (24) with inequality constraints. Chain recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ (middle). $\Delta v$ is approximately zero on the chain-recurrent set (origin) and negative everywhere else. Bottom: The constructed complete Lyapunov function $v(x,y)$, which has a minimum at the origin
Example (25) with solving $\Delta v(x,y) = -1$. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. The approximated chain-recurrent set includes the equilibria at the origin and $(\pm 1,0)$, but is much larger, in particular around the origin. Bottom: Constructed complete Lyapunov function $v(x,y)$, which has a saddle point at the origin and a local maximum at the unstable equilibria $(\pm 1,0)$
Example (25) with equality and inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. $\Delta v$ is approximately zero on the chain-recurrent set, consisting of three equilibria at the origin and $(\pm 1,0)$, and negative everywhere else. The approximation of the chain-recurrent set (the equilibria) is much better than when solving the equation $\Delta v(x,y) = -1$. Bottom: Constructed complete Lyapunov function $v(x,y)$, which has a saddle point at the origin and local maxima at the unstable equilibria $(\pm 1,0)$. Note that they have different levels, which is due to the extra point with equality constraint at $(0.5,0)$, resulting in an unsymmetric approximation
Example (25) with inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. $\Delta v$ is approximately zero on the chain-recurrent set, consisting of three equilibria at the origin and $(\pm 1,0)$, and negative everywhere else. The approximation of the chain-recurrent set (the equilibria) is much better than when solving the equation $\Delta v(x,y) = -1$. Bottom: Constructed complete Lyapunov function $v(x,y)$, which has a saddle point at the origin and local maxima at the unstable equilibria $(\pm 1,0)$
Example (26) with solving $\Delta v(x,y) = -1$. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$. The approximated chain-recurrent set does not resemble the Hénon attractor very well, neither using the orbital derivative nor as the local minimum of the constructed function
Example (26) with equality and inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. The characteristic shape of the Hénon attractor is clearly visible. Bottom: Constructed complete Lyapunov function $v(x,y)$ with a local minimum at the Hénon attractor. The point with equality constraint was $(0.5,0)$
Example (26) with inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. The characteristic shape of the Hénon attractor is clearly visible. Bottom: Constructed complete Lyapunov function $v(x,y)$ with a local minimum at the Hénon attractor
Example (27) with solving $\Delta v(x,y) = -1$. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$. The approximated chain-recurrent set shows the Hénon repeller better than the Hénon attractor in the previous example, but still not very clearly. It is not clearly visible as local maximum of the constructed function either
Example (27) with equality and inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$, showing the Hénon repeller as a local maximum. The repeller is clearly visible in all figures. The point with equality constraint was $(0.5,0)$
Example (27) with inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$, showing the Hénon repeller as a local maximum. The repeller is clearly visible in all figures
Example (28) with solving $\Delta v(x,y) = -1$. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$. The approximated chain-recurrent set shows the attractor relatively well in the orbital derivative, but not very clearly as local minimum of the constructed function
Example (28) with equality and inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$, showing the attractor as a local minimum. The attractor is clearer than in the previous method, both using the orbital derivative and as local minimum of the constructed function. The point with equality constraint was $(0.5,0)$, where the orbital derivative is fixed at $-1$
Example (28) with inequality constraints. Chain-recurrent set (top) approximated by the set $\{(x,y)\,\mid\,\Delta v(x,y)\ge \gamma\}$, see Table 2, and the orbital derivative (second) $\Delta v(x,y)$ of the constructed complete Lyapunov function $v$ over the chain-recurrent set. The third figure shows the orbital derivative in a larger set. Bottom: Constructed complete Lyapunov function $v(x,y)$, showing the attractor as a local minimum. The attractor is clearer than in the first method, both using the orbital derivative and as local minimum of the constructed function
Example (29) with solving $\Delta v(x,y,z) = -1$. Top: Chain-recurrent set approximated by the set $\{(x,y,z)\,\mid\,\Delta v(x,y,z)\ge \gamma\}$, see Table 2. The other figures show projections of this set: projections to the $xy-$ (second), $yz-$ (third) and $xz-$plane (bottom)
Example (29) with equality-inequality constrains. Top: Chain-recurrent set approximated by the set $\{(x,y,z)\,\mid\,\Delta v(x,y,z)\ge \gamma\}$, see Table 2. The other figures show projections of this set: projections to the $xy-$ (second), $yz-$ (third) and $xz-$plane (bottom). The figures are not as good as with the previous method. The point with equality constraint is $(0.4,0.4,0)$
Example (29) with inequality constrains. Top: Chain-recurrent set approximated by the set $\{(x,y,z)\,\mid\,\Delta v(x,y,z)\ge \gamma\}$, see Table 2. The other figures show projections of this set: projections to the $xy-$ (second), $yz-$ (third) and $xz-$plane (bottom)
Collocation points $X$ for the examples. We have used $N$ collocation points in a hexagonal grid with parameter $\alpha_{\text{Hexa-basis}}$ within a rectangle $(x,y)\in [x_{\rm min},x_{\rm max}]\times [y_{\rm min},y_{\rm max}]$ or $(x,y,z)\in [x_{\rm min},x_{\rm max}]\times [y_{\rm min},y_{\rm max}]\times [z_{\rm min},z_{\rm max}]$ for the three-dimensional example (29). The number of evaluation points is also displayed
 Example $N$ $\alpha_{\text{Hexa-basis}}$ #-evaluation $x_{\rm min}$ $x_{\rm max}$ $y_{\rm min}$ $y_{\rm max}$ $z_{\rm min}$ $z_{\rm max}$ (24) $3,584$ $0.072$ 1,779,556 $-2$ $2$ $-2$ $2$ (25) $10,108$ $0.03$ 2,003,001 $-2$ $2$ $-1$ $1$ (26) $1,440$ $0.05$ 1,334,000 $-1.5$ $1.5$ $-0.5$ $0.5$ (27) $5,520$ $0.025$ 1,334,000 $-1.5$ $1.5$ $-0.5$ $0.5$ (28) $2,900$ $0.08$ 1,779,556 $-2$ $2$ $-2$ $2$ (29) $5,301$ $0.07$ 1,030,301 $-0.2$ $0.9$ $-0.2$ $0.9$ $-0.2$ $0.9$
 Example $N$ $\alpha_{\text{Hexa-basis}}$ #-evaluation $x_{\rm min}$ $x_{\rm max}$ $y_{\rm min}$ $y_{\rm max}$ $z_{\rm min}$ $z_{\rm max}$ (24) $3,584$ $0.072$ 1,779,556 $-2$ $2$ $-2$ $2$ (25) $10,108$ $0.03$ 2,003,001 $-2$ $2$ $-1$ $1$ (26) $1,440$ $0.05$ 1,334,000 $-1.5$ $1.5$ $-0.5$ $0.5$ (27) $5,520$ $0.025$ 1,334,000 $-1.5$ $1.5$ $-0.5$ $0.5$ (28) $2,900$ $0.08$ 1,779,556 $-2$ $2$ $-2$ $2$ (29) $5,301$ $0.07$ 1,030,301 $-0.2$ $0.9$ $-0.2$ $0.9$ $-0.2$ $0.9$
The value of the parameter $\gamma\le 0$, close to $0$, for all examples. The chain-recurrent set is approximated by the set $\left(\Delta v \right)^{-1}([\gamma,\infty))$
 $\gamma$ for each method System $\Delta v(x)=-1$ equality-inequality inequality (24) $-0.1$ $-10^{-5}$ $0$ (25) $-0.2$ $-10^{-5}$ $-10^{-4}$ (26) $-0.1$ $0$ $-10^{-2}$ (27) $-0.1$ $0$ $0$ (28) $-0.1$ $0$ $0$ (29) $-0.1$ $0$ $0$
 $\gamma$ for each method System $\Delta v(x)=-1$ equality-inequality inequality (24) $-0.1$ $-10^{-5}$ $0$ (25) $-0.2$ $-10^{-5}$ $-10^{-4}$ (26) $-0.1$ $0$ $-10^{-2}$ (27) $-0.1$ $0$ $0$ (28) $-0.1$ $0$ $0$ (29) $-0.1$ $0$ $0$
 [1] Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015 [2] Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183 [3] Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393 [4] Emma D'Aniello, Saber Elaydi. The structure of $\omega$-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195 [5] Jonathan DeWitt. Local Lyapunov spectrum rigidity of nilmanifold automorphisms. Journal of Modern Dynamics, 2021, 17: 65-109. doi: 10.3934/jmd.2021003 [6] Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014 [7] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [8] Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881 [9] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [10] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [11] Khosro Sayevand, Valeyollah Moradi. A robust computational framework for analyzing fractional dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021022 [12] Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709 [13] Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973 [14] Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355 [15] M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202 [16] Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91 [17] Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087 [18] Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018 [19] Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623 [20] Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199

2019 Impact Factor: 1.27