×

Computation and verification of Lyapunov functions. (English) Zbl 1360.37045

Summary: Lyapunov functions are an important tool to determine the basin of attraction of equilibria in Dynamical Systems through their sublevel sets. Recently, several numerical construction methods for Lyapunov functions have been proposed, among them the RBF (Radial Basis Function) and CPA (Continuous Piecewise Affine) methods. While the first method lacks a verification that the constructed function is a valid Lyapunov function, the second method is rigorous, but computationally much more demanding. In this paper, we propose a combination of these two methods, using their respective strengths: we use the RBF method to compute a potential Lyapunov function. Then we interpolate this function by a CPA function. Checking a finite number of inequalities, we are able to verify that this interpolation is a Lyapunov function. Moreover, sublevel sets are arbitrarily close to the basin of attraction. We show that this combined method always succeeds in computing and verifying a Lyapunov function, as well as in determining arbitrary compact subsets of the basin of attraction. The method is applied to two examples.

MSC:

37B25 Stability of topological dynamical systems
65N35 Spectral, collocation and related methods for boundary value problems involving PDEs
93D30 Lyapunov and storage functions
65N15 Error bounds for boundary value problems involving PDEs
34D20 Stability of solutions to ordinary differential equations
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] R. Baier, L. Grüne, and S. F. Hafstein, {\it Linear programming based Lyapunov function computation for differential inclusions}, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), pp. 33-56. · Zbl 1235.93222
[2] J. Björnsson, P. Giesl, S. Hafstein, C. Kellett, and H. Li, {\it Computation of Lyapunov functions for systems with multiple attractors}, Discrete Contin. Dyn. Syst. Ser. A, 35 (2015), pp. 4019-4039. · Zbl 1366.37028
[3] F. Camilli, L. Grüne, and F. Wirth, {\it A generalization of Zubov’s method to perturbed systems}, SIAM J. Control Optim., 40 (2001), pp. 496-515. · Zbl 1006.93061
[4] M. Dellnitz and O. Junge, {\it Set oriented numerical methods for dynamical systems}, in Handbook of Dynamical Systems, Vol. 2, North-Holland, Amsterdam, 2002, pp. 221-264. · Zbl 1036.37030
[5] L. Evans, {\it Partial Differential Equations}, Grad. Stud. Math. 19, AMS, Providence, RI, 1998. · Zbl 0902.35002
[6] C. Franke and R. Schaback, {\it Solving partial differential equations by collocation using radial basis functions}, Appl. Math. Comput., 93 (1998), pp. 73-82. · Zbl 0943.65133
[7] P. Giesl, {\it Construction of Global Lyapunov Functions Using Radial Basis Functions}, Lecture Notes in Math. 1904, Springer, Berlin, 2007.
[8] P. Giesl and S. Hafstein, {\it Construction of Lyapunov functions for nonlinear planar systems by linear programming}, J. Math. Anal. Appl., 388 (2012), pp. 463-479. · Zbl 1248.34083
[9] P. Giesl and S. Hafstein, {\it Computation of Lyapunov functions for nonlinear discrete time systems by linear programming}, J. Difference Equ. Appl., 20 (2014), pp. 610-640. · Zbl 1319.39010
[10] P. Giesl and S. Hafstein, {\it 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, pp. 2989-2994 (no. 0202).
[11] P. Giesl and S. Hafstein, {\it Revised CPA method to compute Lyapunov functions for nonlinear systems}, J. Math. Anal. Appl., 410 (2014), pp. 292-306. · Zbl 1317.34134
[12] P. Giesl and S. Hafstein, {\it Review on computational methods for Lyapunov functions}, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), pp. 2291-2331. · Zbl 1337.37001
[13] P. Giesl and H. Wendland, {\it Meshless collocation: Error estimates with application to dynamical systems}, SIAM J. Numer. Anal., 45 (2007), pp. 1723-1741. · Zbl 1148.65090
[14] A. Goullet, S. Harker, K. Mischaikow, W. Kalies, and D. Kasti, {\it Efficient computation of Lyapunov functions for Morse decompositions}, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), pp. 2419-2451. · Zbl 1366.37031
[15] L. Grüne, {\it An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation}, Numer. Math., 75 (1997), pp. 319-337. · Zbl 0880.65045
[16] L. Grüne, {\it Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization}, Lecture Notes in Math. 1783, Springer-Verlag, Berlin, 2002. · Zbl 0991.37001
[17] S. F. Hafstein, {\it A constructive converse Lyapunov theorem on exponential stability}, Discrete Contin. Dyn. Syst., 10 (2004), pp. 657-678. · Zbl 1070.93044
[18] S. Hafstein, {\it An Algorithm for Constructing Lyapunov Functions}, Electron. J. Differ. Equ. Monogr., Department of Mathematics, Texas State University-San Marcos, San Marcos, TX, 2007. · Zbl 1131.37021
[19] S. Hafstein, {\it Implementation of simplicial complexes for CPA functions in C++11 using the armadillo linear algebra library}, in Proceedings of SIMULTECH, Reykjavik, Iceland, 2013, pp. 49-57.
[20] C. S. Hsu, {\it Cell-to-Cell Mapping}, Appl. Math. Sci. 64, Springer-Verlag, New York, 1987. · Zbl 0632.58002
[21] A. Iske, {\it Perfect Centre Placement for Radial Basis Function Methods}, Technical Report TUM-M9809, TU Munich, Munich, Germany, 1998.
[22] W. D. Kalies, K. Mischaikow, and R. C. A. M. VanderVorst, {\it An algorithmic approach to chain recurrence}, Found. Comput. Math., 5 (2005), pp. 409-449. · Zbl 1099.37010
[23] B. Krauskopf and H. M. Osinga, {\it Computing invariant manifolds via the continuation of orbit segments}, in Numerical Continuation Methods for Dynamical Systems: Path Following and Boundary Value Problems, B. Krauskopf, H. Osinga, and J. Galán-Vioque, eds., Springer, Dordrecht, 2007, pp. 117-154. · Zbl 1126.65111
[24] B. Krauskopf, H. M. Osinga, E. J. Doedel, M. E. Henderson, J. Guckenheimer, A. Vladimirsky, M. Dellnitz, and O. Junge, {\it A survey of methods for computing (un)stable manifolds of vector fields}, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 15 (2005), pp. 763-791. · Zbl 1086.34002
[25] H. Li, S. Hafstein, and C. Kellett, {\it Computation of continuous and piecewise affine Lyapunov functions for discrete-time systems}, J. Difference Equ. Appl., 21 (2015), pp. 486––511. · Zbl 1320.93072
[26] A. M. Lyapunov, {\it Problème général de la stabilité du mouvement}, Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys (2), 9 (1907), pp. 203-474, translation of the Russian version, published 1893 in Comm. Soc. Math. Kharkow, newly printed, Ann. of Math. Stud. 17, Princeton University Press, Princeton, 1947.
[27] N. Mohammed and P. Giesl, {\it Grid refinement in the construction of Lyapunov functions using radial basis functions}, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), pp. 2453-2476. · Zbl 1366.37147
[28] A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Pranja, P. Seiler, and P. Parrilo, {\it SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB}, User’s guide, Version 3.00 ed., 2013.
[29] P. Parrilo, {\it Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimiziation}, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000.
[30] M. W. Peet, {\it Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions}, IEEE Trans. Automat. Control, 54 (2009), pp. 979-987. · Zbl 1367.93442
[31] M. W. Peet and A. Papachristodoulou, {\it A converse sum of squares Lyapunov result with a degree bound}, IEEE Trans. Automat. Control, 57 (2012), pp. 2281-2293. · Zbl 1369.93449
[32] C. Sanderson, {\it Armadillo: An Open Source C\textup++ Linear Algebra Library for Fast Prototyping and Computationally Intensive Experiments}, Technical report, NICTA, Eveleigh, Australia, 2010.
[33] Scilab Enterprises, {\it Scilab: Free and Open Source Software for Numerical Computation}, Scilab Enterprises, Orsay, France, 2012.
[34] H. Wendland, {\it Error estimates for interpolation by compactly supported Radial Basis Functions of minimal degree}, J. Approx. Theory, 93 (1998), pp. 258-272. · Zbl 0904.41013
[35] H. Wendland, {\it Scattered Data Approximation}, Cambridge Monogr. Appl. Comput. Math. 17, Cambridge University Press, Cambridge, 2005. · Zbl 1075.65021
[36] Z. M.Wu, {\it Hermite-Birkhoff interpolation of scattered data by radial basis functions}, Approx. Theory Appl., 8 (1992), pp. 1-10. · Zbl 0757.41009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.