American Institute of Mathematical Sciences

Advanced
doi: 10.3934/dcdsb.2020378

System specific triangulations for the construction of CPA Lyapunov functions

Peter Giesl 1, and  Sigurdur Hafstein 2,

1. 

Department of Mathematics, University of Sussex, Falmer BN1 9QH, United Kingdom
2. 

Faculty of Physical Sciences, University of Iceland, 107 Reykjavik, Iceland

Received  September 2020 Published  December 2020

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

Recently, a transformation of the vertices of a regular triangulation of $ {\mathbb {R}}^n $ with vertices in the lattice $ \mathbb{Z}^n $ was introduced, which distributes the vertices with approximate rotational symmetry properties around the origin. We prove that the simplices of the transformed triangulation are $ (h, d) $-bounded, a type of non-degeneracy particularly useful in the numerical computation of Lyapunov functions for nonlinear systems using the CPA (continuous piecewise affine) method. Additionally, we discuss and give examples of how this transformed triangulation can be used together with a Lyapunov function for a linearization to compute a Lyapunov function for a nonlinear system with the CPA method using considerably fewer simplices than when using a regular triangulation.

Keywords: Triangulation, Lyapunov function, nonlinear transformation, simplicial complex.
Mathematics Subject Classification: Primary: 93D30, 51M20, 37N30; Secondary: 65D05.
Citation: Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, doi: 10.3934/dcdsb.2020378
References:
[1]

S. Albertsson, P. Giesl, S. Gudmundsson and S. Hafstein, Simplicial complex with approximate rotational symmetry: A general class of simplicial complexes, J. Comput. Appl. Math., 363 (2020), 413-425.  doi: 10.1016/j.cam.2019.06.019.  Google Scholar

[2]

J. Anderson and A. Papachristodoulou, Advances in computational Lyapunov analysis using sum-of-squares programming, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2361-2381.  doi: 10.3934/dcdsb.2015.20.2361.  Google Scholar

[3]

J. Björnsson, S. Gudmundsson and S. Hafstein, Class library in C++ to compute Lyapunov functions for nonlinear systems, In Proceedings of MICNON, 1st Conference on Modelling, Identification and Control of Nonlinear Systems, no. 0155, 2015,788–793. Google Scholar

[4]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Math., vol. 1904, Springer, Berlin, 2007.  Google Scholar

[5]

P. Giesl and S. Hafstein, Implementation of a fan-like triangulation for the CPA method to compute Lyapunov functions, In Proceedings of the 2014 American Control Conference, Portland, OR, 2014, 2989–2994. doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[6]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems, J. Math. Anal. Appl., 410 (2014), 292-306.  doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[7]

P. Giesl and S. Hafstein, Computation and verification of Lyapunov functions, SIAM J. Appl. Dyn. Syst., 14 (2015), 1663-1698.  doi: 10.1137/140988802.  Google Scholar

[8]

P. Giesl and S. Hafstein, Review of computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2291-2331.  doi: 10.3934/dcdsb.2015.20.2291.  Google Scholar

[9] G. Golub and C. van Loan, Matrix Computations, 4th edition, John Hopkins University Press, Baltimore, MD, 2013.   Google Scholar
[10]

S. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete Contin. Dyn. Syst., 10 (2004), 657-678.  doi: 10.3934/dcds.2004.10.657.  Google Scholar

[11]

S. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dyn. Syst., 20 (2005), 281-299.  doi: 10.1080/14689360500164873.  Google Scholar

[12]

S. Hafstein, Implementation of simplicial complexes for CPA functions in C++11 using the armadillo linear algebra library, In Proceedings of the 3rd International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH), Reykjavik, Iceland, 2013, 49–57. Google Scholar

[13]

S. Hafstein, Simulation and Modeling Methodologies, Technologies and Applications, volume 873 of Advances in Intelligent Systems and Computing, chapter Fast Algorithms for Computing Continuous Piecewise Affine Lyapunov Functions, Springer, 2019,274–299. Google Scholar

[14]

S. Hafstein and A. Valfells, Study of dynamical systems by fast numerical computation of Lyapunov functions, In Proceedings of the 14th International Conference on Dynamical Systems: Theory and Applications (DSTA), Mathematical and Numerical Aspects of Dynamical System Analysis, 2017,220–240. Google Scholar

[15]

W. Hahn, Stability of Motion, Springer-Verlag New York, Inc., New York, 1967.  Google Scholar

[16]

R. Kamyar and M. Peet, Polynomial optimization with applications to stability analysis and control – alternatives to sum of squares, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2383-2417.  doi: 10.3934/dcdsb.2015.20.2383.  Google Scholar

[17]

H. Khalil, Nonlinear Systems, 3rd edition, Pearson, 2002. Google Scholar

[18]

A. M. Lyapunov, The general problem of the stability of motion, Internat. J. Control, 55 (1992), 521-790.  doi: 10.1080/00207179208934253.  Google Scholar

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150.  doi: 10.1080/0268111011011847.  Google Scholar

[20]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimiza, Ph.D thesis, California Institute of Technology, Pasadena, California, 2000. Google Scholar

[21]

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 Optim., 48 (2010), 4377-4394.  doi: 10.1137/090749955.  Google Scholar

[22]

S. Sastry, Nonlinear Systems: Analysis, Stability, and Control, Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-3108-8.  Google Scholar

[23]

J. Sherman and W. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics, 21 (1950), 124-127.  doi: 10.1214/aoms/1177729893.  Google Scholar

[24]

G. Valmorbida and J. Anderson, Region of attraction estimation using invariant sets and rational Lyapunov functions, Automatica J. IFAC, 75 (2017), 37-45.  doi: 10.1016/j.automatica.2016.09.003.  Google Scholar

[25]

A. Vannelli and M. Vidyasagar, Maximal Lyapunov functions and domains of attraction for autonomous nonlinear systems, Automatica J. IFAC, 21 (1985), 69-80.  doi: 10.1016/0005-1098(85)90099-8.  Google Scholar

[26]

M. Vidyasagar, Nonlinear System Analysis, 2nd edition, Classics in Applied Mathematics, vol. 42, SIAM, Philadelphia, PA, 2002. doi: 10.1137/1.9780898719185.  Google Scholar

[27]

T. Yoshizawa, Stability Theory by Liapunov's Second Method, Publications of the Mathematical Society of Japan, No. 9. The Mathematical Society of Japan, Tokyo, 1966.  Google Scholar

[28]

V. I. Zubov, Methods of A. M. Lyapunov and Their Application, P. Noordhoff Ltd., Groningen, 1964.  Google Scholar

show all references

References:
[1]

S. Albertsson, P. Giesl, S. Gudmundsson and S. Hafstein, Simplicial complex with approximate rotational symmetry: A general class of simplicial complexes, J. Comput. Appl. Math., 363 (2020), 413-425.  doi: 10.1016/j.cam.2019.06.019.  Google Scholar

[2]

J. Anderson and A. Papachristodoulou, Advances in computational Lyapunov analysis using sum-of-squares programming, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2361-2381.  doi: 10.3934/dcdsb.2015.20.2361.  Google Scholar

[3]

J. Björnsson, S. Gudmundsson and S. Hafstein, Class library in C++ to compute Lyapunov functions for nonlinear systems, In Proceedings of MICNON, 1st Conference on Modelling, Identification and Control of Nonlinear Systems, no. 0155, 2015,788–793. Google Scholar

[4]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Math., vol. 1904, Springer, Berlin, 2007.  Google Scholar

[5]

P. Giesl and S. Hafstein, Implementation of a fan-like triangulation for the CPA method to compute Lyapunov functions, In Proceedings of the 2014 American Control Conference, Portland, OR, 2014, 2989–2994. doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[6]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems, J. Math. Anal. Appl., 410 (2014), 292-306.  doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[7]

P. Giesl and S. Hafstein, Computation and verification of Lyapunov functions, SIAM J. Appl. Dyn. Syst., 14 (2015), 1663-1698.  doi: 10.1137/140988802.  Google Scholar

[8]

P. Giesl and S. Hafstein, Review of computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2291-2331.  doi: 10.3934/dcdsb.2015.20.2291.  Google Scholar

[9] G. Golub and C. van Loan, Matrix Computations, 4th edition, John Hopkins University Press, Baltimore, MD, 2013.   Google Scholar
[10]

S. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete Contin. Dyn. Syst., 10 (2004), 657-678.  doi: 10.3934/dcds.2004.10.657.  Google Scholar

[11]

S. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dyn. Syst., 20 (2005), 281-299.  doi: 10.1080/14689360500164873.  Google Scholar

[12]

S. Hafstein, Implementation of simplicial complexes for CPA functions in C++11 using the armadillo linear algebra library, In Proceedings of the 3rd International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH), Reykjavik, Iceland, 2013, 49–57. Google Scholar

[13]

S. Hafstein, Simulation and Modeling Methodologies, Technologies and Applications, volume 873 of Advances in Intelligent Systems and Computing, chapter Fast Algorithms for Computing Continuous Piecewise Affine Lyapunov Functions, Springer, 2019,274–299. Google Scholar

[14]

S. Hafstein and A. Valfells, Study of dynamical systems by fast numerical computation of Lyapunov functions, In Proceedings of the 14th International Conference on Dynamical Systems: Theory and Applications (DSTA), Mathematical and Numerical Aspects of Dynamical System Analysis, 2017,220–240. Google Scholar

[15]

W. Hahn, Stability of Motion, Springer-Verlag New York, Inc., New York, 1967.  Google Scholar

[16]

R. Kamyar and M. Peet, Polynomial optimization with applications to stability analysis and control – alternatives to sum of squares, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2383-2417.  doi: 10.3934/dcdsb.2015.20.2383.  Google Scholar

[17]

H. Khalil, Nonlinear Systems, 3rd edition, Pearson, 2002. Google Scholar

[18]

A. M. Lyapunov, The general problem of the stability of motion, Internat. J. Control, 55 (1992), 521-790.  doi: 10.1080/00207179208934253.  Google Scholar

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150.  doi: 10.1080/0268111011011847.  Google Scholar

[20]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimiza, Ph.D thesis, California Institute of Technology, Pasadena, California, 2000. Google Scholar

[21]

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 Optim., 48 (2010), 4377-4394.  doi: 10.1137/090749955.  Google Scholar

[22]

S. Sastry, Nonlinear Systems: Analysis, Stability, and Control, Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-3108-8.  Google Scholar

[23]

J. Sherman and W. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics, 21 (1950), 124-127.  doi: 10.1214/aoms/1177729893.  Google Scholar

[24]

G. Valmorbida and J. Anderson, Region of attraction estimation using invariant sets and rational Lyapunov functions, Automatica J. IFAC, 75 (2017), 37-45.  doi: 10.1016/j.automatica.2016.09.003.  Google Scholar

[25]

A. Vannelli and M. Vidyasagar, Maximal Lyapunov functions and domains of attraction for autonomous nonlinear systems, Automatica J. IFAC, 21 (1985), 69-80.  doi: 10.1016/0005-1098(85)90099-8.  Google Scholar

[26]

M. Vidyasagar, Nonlinear System Analysis, 2nd edition, Classics in Applied Mathematics, vol. 42, SIAM, Philadelphia, PA, 2002. doi: 10.1137/1.9780898719185.  Google Scholar

[27]

T. Yoshizawa, Stability Theory by Liapunov's Second Method, Publications of the Mathematical Society of Japan, No. 9. The Mathematical Society of Japan, Tokyo, 1966.  Google Scholar

[28]

V. I. Zubov, Methods of A. M. Lyapunov and Their Application, P. Noordhoff Ltd., Groningen, 1964.  Google Scholar

Figure 1.  Left: The triangulation $ {\mathcal T}^\text{ std}_{K} $, $ K = 4 $, with a triangle fan at the origin. Right: The transformed approximately rotationally symmetric triangulation $ {\mathcal T}_{\Phi, K} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 1, right, are mapped by the linear transformation $ {\bf x} \mapsto P^{-\frac{1}{2}} {\bf x} $, where $ P^{-\frac{1}{2}} $ is a symmetric and positive definite matrix. This triangulation is adapted to the structure of the system with a local Lyapunov function $ V( {\bf x}) = {\bf x}^\text{T}P {\bf x} $">Figure 2.  The vertices of the triangulations of Figure 1, right, are mapped by the linear transformation $ {\bf x} \mapsto P^{-\frac{1}{2}} {\bf x} $, where $ P^{-\frac{1}{2}} $ is a symmetric and positive definite matrix. This triangulation is adapted to the structure of the system with a local Lyapunov function $ V( {\bf x}) = {\bf x}^\text{T}P {\bf x} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.3 $ using a rectangular grid. Right: The rectangular grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3">Figure 4.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.3 $ using a transformed grid. Right: The transformed grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures. Note that the triangulation is much better adapted to the shape of the level-sets than when using a rectangular grid as in Figure 3
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.4 $ using a rectangular grid. Right: The rectangular grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. Both the area covered by the triangle fan, in both cases with $ 64 $ triangles, as well as the area covered overall are much larger than when using the rectangular grid, see Figure 5">Figure 6.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.4 $ using a transformed grid. Right: The transformed grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures. Note that the triangulation is much better adapted to the shape of the level-sets than when using a rectangular grid as in Figure 5. Both the area covered by the triangle fan, in both cases with $ 64 $ triangles, as well as the area covered overall are much larger than when using the rectangular grid, see Figure 5
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048
[2]

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

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3295-3317. doi: 10.3934/dcds.2020406
[4]

Wenmeng Geng, Kai Tao. Lyapunov exponents of discrete quasi-periodic gevrey Schrödinger equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 2977-2996. doi: 10.3934/dcdsb.2020216
[5]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[6]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2619-2633. doi: 10.3934/dcds.2020377
[7]

Wei Xi Li, Chao Jiang Xu. Subellipticity of some complex vector fields related to the Witten Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021047
[8]

Simão Correia, Mário Figueira. A generalized complex Ginzburg-Landau equation: Global existence and stability results. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021056
[9]

Joel Coacalle, Andrew Raich. Compactness of the complex Green operator on non-pseudoconvex CR manifolds. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021061
[10]

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

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004
[12]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[13]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019
[14]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070
[15]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020
[16]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011
[17]

Chenjie Fan, Zehua Zhao. Decay estimates for nonlinear Schrödinger equations. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3973-3984. doi: 10.3934/dcds.2021024
[18]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267
[19]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[20]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933

2019 Impact Factor: 1.27

Tools

Metrics

  • PDF downloads (25)
  • HTML views (125)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences