American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations
  • DCDS Home
  • This Issue
  • Next Article
    State constrained $L^\infty$ optimal control problems interpreted as differential games
September  2015, 35(9): 4019-4039. doi: 10.3934/dcds.2015.35.4019

Computation of Lyapunov functions for systems with multiple local attractors

Jóhann Björnsson 1, , Peter Giesl 2, , Sigurdur F. Hafstein 1, and  Christopher M. Kellett 3,

1. 

School of Science and Engineering, Reykjavik University, Menntavegi 1, Reykjavik, IS-101, Iceland, Iceland
2. 

Department of Mathematics, University of Sussex, Falmer BN1 9QH
3. 

School of Electrical Engineering and Computer Science, University of Newcastle, Callaghan, New South Wales 2308, Australia

Received  June 2014 Revised  October 2014 Published  April 2015

We present a novel method to compute Lyapunov functions for continuous-time systems with multiple local attractors. In the proposed method one first computes an outer approximation of the local attractors using a graph-theoretic approach. Then a candidate Lyapunov function is computed using a Massera-like construction adapted to multiple local attractors. In the final step this candidate Lyapunov function is interpolated over the simplices of a simplicial complex and, by checking certain inequalities at the vertices of the complex, we can identify the region in which the Lyapunov function is decreasing along system trajectories. The resulting Lyapunov function gives information on the qualitative behavior of the dynamics, including lower bounds on the basins of attraction of the individual local attractors. We develop the theory in detail and present numerical examples demonstrating the applicability of our method.
Keywords: numerical method., asymptotic stability, multiple local attractors, Lyapunov function, dynamical system.
Mathematics Subject Classification: Primary: 37B25, 37M99; Secondary: 37C1.
Citation: Jóhann Björnsson, Peter Giesl, Sigurdur F. Hafstein, Christopher M. Kellett. Computation of Lyapunov functions for systems with multiple local attractors. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4019-4039. doi: 10.3934/dcds.2015.35.4019
References:
[1]

R. Baier, L. Grüne and S. Hafstein, Linear programming based Lyapunov function computation for differential inclusions,, Discrete and Continuous Dynamical Systems Series B, 17 (2012), 33.  doi: 10.3934/dcdsb.2012.17.33.  Google Scholar

[2]

H. Ban and W. Kalies, A computational approach to Conley's decomposition theorem,, Journal of Computational and Nonlinear Dynamics, 1 (2006), 312.  doi: 10.1115/1.2338651.  Google Scholar

[3]

J. Barnat, J. Chaloupka and J. van de Pol, Distributed algorithms for SCC decomposition,, Journal of Logic and Computation, 21 (2011), 23.  doi: 10.1093/logcom/exp003.  Google Scholar

[4]

J. Björnsson, P. Giesl and S. Hafstein, Algorithmic verification of approximations to complete Lyapunov functions,, in Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, (2014), 1181.   Google Scholar

[5]

J. Björnsson, P. Giesl, S. Hafstein, C. M. Kellett and H. Li, Computation of continuous and piecewise affine Lyapunov functions by numerical approximations of the Massera construction,, in Proceedings of the 53rd IEEE Conference on Decision and Control, (2014), 5506.  doi: 10.1109/CDC.2014.7040250.  Google Scholar

[6]

C. Conley, Isolated Invariant Sets and the Morse Index,, CBMS Regional Conference Series no. 38, (1978).   Google Scholar

[7]

M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO-set oriented numerical methods for dynamical systems,, in Ergodic theory, (2001), 145.   Google Scholar

[8]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions,, no. 1904 in Lecture Notes in Mathematics, (1904).   Google Scholar

[9]

P. Giesl and S. Hafstein, Construction of Lyapunov functions for nonlinear planar systems by linear programming,, Journal of Mathematical Analysis and Applications, 388 (2012), 463.  doi: 10.1016/j.jmaa.2011.10.047.  Google Scholar

[10]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems,, Journal of Mathematical Analysis and Applications, 410 (2014), 292.  doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[11]

S. Hafstein, An Algorithm for Constructing Lyapunov Functions,, Electronic Journal of Differential Equations Mongraphs, (2007).   Google Scholar

[12]

S. Hafstein, C. M. Kellett and H. Li, Continuous and piecewise affine Lyapunov functions using the Yoshizawa construction,, in Proceedings of the 2014 American Control Conference, (2014), 548.  doi: 10.1109/ACC.2014.6858660.  Google Scholar

[13]

M. Hurley, Lyapunov functions and attractors in arbitrary metric spaces,, Proc. Amer. Math. Soc., 126 (1998), 245.  doi: 10.1090/S0002-9939-98-04500-6.  Google Scholar

[14]

O. Junge, Mengenorientierte Methoden zur Numerischen Analyse Dynamischer Systeme,, PhD thesis at the University of Paderborn, (2000).   Google Scholar

[15]

W. Kalies, K. Mischaikow and R. VanderVorst, An algorithmic approach to chain recurrence,, Foundations of Computational Mathematics, 5 (2005), 409.  doi: 10.1007/s10208-004-0163-9.  Google Scholar

[16]

S. Marinosson, Lyapunov function construction for ordinary differential equations with linear programming,, Dynamical Systems, 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar

[17]

S. Marinosson, Stability Analysis of Nonlinear Systems with Linear Programming: A Lyapunov Functions Based Approach,, PhD thesis, (2002).   Google Scholar

[18]

J. L. Massera, On Liapounoff's conditions of stability,, Annals of Mathematics, 50 (1949), 705.  doi: 10.2307/1969558.  Google Scholar

[19]

D. Norton, The fundamental theorem of dynamical systems,, Comment. Math. Univ. Carolinae, 36 (1995), 585.   Google Scholar

[20]

A. Papachristodoulou and S. Prajna, The construction of Lyapunov functions using the sum of squares decomposition,, in Proceedings of the 41st IEEE Conference on Decision and Control, 3 (2002), 3482.  doi: 10.1109/CDC.2002.1184414.  Google Scholar

[21]

M. Patrao, Existence of complete Lyapunov functions for semiflows on separable metric spaces,, Far East Journal of Dynamical Systems, 17 (2011), 49.   Google Scholar

[22]

M. Peet and A. Papachristodoulou, A converse sum-of-squares Lyapunov result: An existence proof based on the Picard iteration,, in Proceedings of the 49th IEEE Conference on Decision and Control, (2010), 5949.  doi: 10.1109/CDC.2010.5717536.  Google Scholar

[23]

S. Ratschan and Z. She, Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions,, SIAM J. Control and Optimization, 48 (2010), 4377.  doi: 10.1137/090749955.  Google Scholar

[24]

R. Tarjan, Depth-first search and linear graph algorithms,, SIAM J. Comput., 1 (1972), 146.  doi: 10.1137/0201010.  Google Scholar

[25]

A. R. Teel and L. Praly, A smooth Lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions,, ESAIM Control Optim. Calc. Var., 5 (2000), 313.  doi: 10.1051/cocv:2000113.  Google Scholar

[26]

W. Tucker, A rigorous ODE solver and Smale's 14th problem,, Found. Comput. Math., 2 (2002), 53.  doi: 10.1007/s002080010018.  Google Scholar

[27]

T. Yoshizawa, On the stability of solutions of a system of differential equations,, Memoirs of the College of Science, 29 (1955), 27.   Google Scholar

show all references

References:
[1]

R. Baier, L. Grüne and S. Hafstein, Linear programming based Lyapunov function computation for differential inclusions,, Discrete and Continuous Dynamical Systems Series B, 17 (2012), 33.  doi: 10.3934/dcdsb.2012.17.33.  Google Scholar

[2]

H. Ban and W. Kalies, A computational approach to Conley's decomposition theorem,, Journal of Computational and Nonlinear Dynamics, 1 (2006), 312.  doi: 10.1115/1.2338651.  Google Scholar

[3]

J. Barnat, J. Chaloupka and J. van de Pol, Distributed algorithms for SCC decomposition,, Journal of Logic and Computation, 21 (2011), 23.  doi: 10.1093/logcom/exp003.  Google Scholar

[4]

J. Björnsson, P. Giesl and S. Hafstein, Algorithmic verification of approximations to complete Lyapunov functions,, in Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, (2014), 1181.   Google Scholar

[5]

J. Björnsson, P. Giesl, S. Hafstein, C. M. Kellett and H. Li, Computation of continuous and piecewise affine Lyapunov functions by numerical approximations of the Massera construction,, in Proceedings of the 53rd IEEE Conference on Decision and Control, (2014), 5506.  doi: 10.1109/CDC.2014.7040250.  Google Scholar

[6]

C. Conley, Isolated Invariant Sets and the Morse Index,, CBMS Regional Conference Series no. 38, (1978).   Google Scholar

[7]

M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO-set oriented numerical methods for dynamical systems,, in Ergodic theory, (2001), 145.   Google Scholar

[8]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions,, no. 1904 in Lecture Notes in Mathematics, (1904).   Google Scholar

[9]

P. Giesl and S. Hafstein, Construction of Lyapunov functions for nonlinear planar systems by linear programming,, Journal of Mathematical Analysis and Applications, 388 (2012), 463.  doi: 10.1016/j.jmaa.2011.10.047.  Google Scholar

[10]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems,, Journal of Mathematical Analysis and Applications, 410 (2014), 292.  doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[11]

S. Hafstein, An Algorithm for Constructing Lyapunov Functions,, Electronic Journal of Differential Equations Mongraphs, (2007).   Google Scholar

[12]

S. Hafstein, C. M. Kellett and H. Li, Continuous and piecewise affine Lyapunov functions using the Yoshizawa construction,, in Proceedings of the 2014 American Control Conference, (2014), 548.  doi: 10.1109/ACC.2014.6858660.  Google Scholar

[13]

M. Hurley, Lyapunov functions and attractors in arbitrary metric spaces,, Proc. Amer. Math. Soc., 126 (1998), 245.  doi: 10.1090/S0002-9939-98-04500-6.  Google Scholar

[14]

O. Junge, Mengenorientierte Methoden zur Numerischen Analyse Dynamischer Systeme,, PhD thesis at the University of Paderborn, (2000).   Google Scholar

[15]

W. Kalies, K. Mischaikow and R. VanderVorst, An algorithmic approach to chain recurrence,, Foundations of Computational Mathematics, 5 (2005), 409.  doi: 10.1007/s10208-004-0163-9.  Google Scholar

[16]

S. Marinosson, Lyapunov function construction for ordinary differential equations with linear programming,, Dynamical Systems, 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar

[17]

S. Marinosson, Stability Analysis of Nonlinear Systems with Linear Programming: A Lyapunov Functions Based Approach,, PhD thesis, (2002).   Google Scholar

[18]

J. L. Massera, On Liapounoff's conditions of stability,, Annals of Mathematics, 50 (1949), 705.  doi: 10.2307/1969558.  Google Scholar

[19]

D. Norton, The fundamental theorem of dynamical systems,, Comment. Math. Univ. Carolinae, 36 (1995), 585.   Google Scholar

[20]

A. Papachristodoulou and S. Prajna, The construction of Lyapunov functions using the sum of squares decomposition,, in Proceedings of the 41st IEEE Conference on Decision and Control, 3 (2002), 3482.  doi: 10.1109/CDC.2002.1184414.  Google Scholar

[21]

M. Patrao, Existence of complete Lyapunov functions for semiflows on separable metric spaces,, Far East Journal of Dynamical Systems, 17 (2011), 49.   Google Scholar

[22]

M. Peet and A. Papachristodoulou, A converse sum-of-squares Lyapunov result: An existence proof based on the Picard iteration,, in Proceedings of the 49th IEEE Conference on Decision and Control, (2010), 5949.  doi: 10.1109/CDC.2010.5717536.  Google Scholar

[23]

S. Ratschan and Z. She, Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions,, SIAM J. Control and Optimization, 48 (2010), 4377.  doi: 10.1137/090749955.  Google Scholar

[24]

R. Tarjan, Depth-first search and linear graph algorithms,, SIAM J. Comput., 1 (1972), 146.  doi: 10.1137/0201010.  Google Scholar

[25]

A. R. Teel and L. Praly, A smooth Lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions,, ESAIM Control Optim. Calc. Var., 5 (2000), 313.  doi: 10.1051/cocv:2000113.  Google Scholar

[26]

W. Tucker, A rigorous ODE solver and Smale's 14th problem,, Found. Comput. Math., 2 (2002), 53.  doi: 10.1007/s002080010018.  Google Scholar

[27]

T. Yoshizawa, On the stability of solutions of a system of differential equations,, Memoirs of the College of Science, 29 (1955), 27.   Google Scholar

[1]

Jonathan DeWitt. Local Lyapunov spectrum rigidity of nilmanifold automorphisms. Journal of Modern Dynamics, 2021, 17: 65-109. doi: 10.3934/jmd.2021003
[2]

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
[3]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[4]

M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849
[5]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[6]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450
[7]

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
[8]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196
[9]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[10]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[11]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035
[12]

Khosro Sayevand, Valeyollah Moradi. A robust computational framework for analyzing fractional dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021022
[13]

Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294
[14]

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
[15]

Raghda A. M. Attia, Dumitru Baleanu, Dianchen Lu, Mostafa M. A. Khater, El-Sayed Ahmed. Computational and numerical simulations for the deoxyribonucleic acid (DNA) model. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021018
[16]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[17]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[18]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[19]

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
[20]

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

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (52)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences