American Institute of Mathematical Sciences

Advanced
October  2015, 20(8): 2453-2476. doi: 10.3934/dcdsb.2015.20.2453

Grid refinement in the construction of Lyapunov functions using radial basis functions

Najla Mohammed 1, and  Peter Giesl 1,

1. 

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

Received  September 2014 Revised  January 2015 Published  August 2015

Lyapunov functions are a main tool to determine the domain of attraction of equilibria in dynamical systems. Recently, several methods have been presented to construct a Lyapunov function for a given system. In this paper, we improve the construction method for Lyapunov functions using Radial Basis Functions. We combine this method with a new grid refinement algorithm based on Voronoi diagrams. Starting with a coarse grid and applying the refinement algorithm, we thus manage to reduce the number of data points needed to construct Lyapunov functions. Finally, we give numerical examples to illustrate our algorithms.
Keywords: refinement., Lyapunov function, Radial Basis Function, mesh-free collocation, domain of attraction, Voronoi diagram.
Mathematics Subject Classification: Primary: 37B25, 65N50; Secondary: 37M99, 65N3.
Citation: Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453
References:
[1]

M. Berg, O. Cheong, M. Kerveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 2008. Google Scholar

[2]

M. D. Buhmann, Radial basis functions, in Acta Numerica, 2000, Acta Numer., 9, Cambridge Univ. Press, Cambridge, 2000, 1-38. doi: 10.1017/S0962492900000015.  Google Scholar

[3]

F. Camilli, L. Grüne and F. Wirth, A generalization of Zubov's method to perturbed systems, SIAM J. Control Optim., 40 (2001), 496-515. doi: 10.1137/S036301299936316X.  Google Scholar

[4]

M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems, in Handbook of Dynamical Systems, Vol. 2, North-Holland, Amsterdam, 2002, 221-264. doi: 10.1016/S1874-575X(02)80026-1.  Google Scholar

[5]

M. Floater and A. Iske, Multistep scattered data interpolation using compactly supported Radial Basis Functions, J. Comput. Appl. Math., 73 (1996), 65-78. doi: 10.1016/0377-0427(96)00035-0.  Google Scholar

[6]

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

[7]

P. Giesl, Construction of a local and global Lyapunov function using Radial Basis Functions, IMA J. Appl. Math., 73 (2008), 782-802. doi: 10.1093/imamat/hxn018.  Google Scholar

[8]

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

[9]

P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions, Discrete and Continuous Dynamical Systems - Series B, 8 (2015), 2291-2331. doi: 10.3934/dcdsb.2015.20.2291.  Google Scholar

[10]

P. Giesl and H. Wendland, Meshless collocation: Error estimates with application to Dynamical Systems, SIAM J. Numer. Anal., 45 (2007), 1723-1741. doi: 10.1137/060658813.  Google Scholar

[11]

L. Grüne, An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation, Numer. Math., 75 (1997), 319-337. doi: 10.1007/s002110050241.  Google Scholar

[12]

L. Grüne, Asymptotic Behavior of Dynamical and Control Systems Under Perturbation and Discretization, Lecture Notes in Mathematics, 1783, Springer-Verlag, Berlin, 2002. doi: 10.1007/b83677.  Google Scholar

[13]

S. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete and Continuous Dynamical Systems - Series A, 10 (2004), 657-678. doi: 10.3934/dcds.2004.10.657.  Google Scholar

[14]

S. Hafstein, An algorithm for constructing Lyapunov functions, Monograph. Electron. J. Diff. Eqns., (2007), 101pp. Google Scholar

[15]

C. S. Hsu, Cell-to-cell Mapping, Applied Mathematical Sciences, 64, Springer-Verlag, New York, 1987. doi: 10.1007/978-1-4757-3892-6.  Google Scholar

[16]

A. Iske, On the construction of kernel-based adaptive particle methods in numerical flow simulation, in Recent Developments in the Numerics of Nonlinear Hyperbolic Conservation Laws, Notes Numer. Fluid Mech. Multidiscip. Des., 120, Springer, Heidelberg, 2013, 197-221. doi: 10.1007/978-3-642-33221-0_12.  Google Scholar

[17]

S. Iyengar, K. Boroojeni and N. Balakrishnan, Mathematical Theories of Distributed Sensor Networks, Springer, New York, 2014. doi: 10.1007/978-1-4419-8420-3.  Google Scholar

[18]

Z. Jian, Development of Strong Form Methods with Applications in Computational Mechanics, PhD thesis, National University of Singapore, Singapore, 2008. Google Scholar

[19]

C. Kellett, Classical converse theorems in Lyapunov’s second method, Discrete and Continuous Dynamical Systems - Series B, 8 (2015), 2333-2360. doi: 10.3934/dcdsb.2015.20.2333.  Google Scholar

[20]

R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1989. doi: 10.1007/3-540-52055-4.  Google Scholar

[21]

J. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721.  Google Scholar

[22]

A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Pranja, P. Seiler and P. Parrilo, SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB, User's guide. Version 3.00 edition, 2013. Google Scholar

[23]

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

[24]

F. Preparata and M. Shamos, Computational Geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. doi: 10.1007/978-1-4612-1098-6.  Google Scholar

[25]

J. Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, J. Approx. Theory, 18 (1995), 548-585. doi: 10.1006/jagm.1995.1021.  Google Scholar

[26]

R. Sibson, Development of strong form methods with applications in computational mechanics, in Interpolating Multivariate Data, Chapter 2 (ed. V. Barnett), John Wiley and Sons, New York, 1981. Google Scholar

[27]

H. Wendland, Error estimates for interpolation by compactly supported Radial Basis Functions of minimal degree, J. Approx. Theory, 93 (1998), 258-272. doi: 10.1006/jath.1997.3137.  Google Scholar

[28]

H. Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, 17, Cambridge University Press, Cambridge, 2005.  Google Scholar

[29]

X. Zhang, R. Ding and Y. Li, Adaptive RPIM meshless method, in Proceedings of the 2011 International Conference on Multimedia Technology (ICMT), IEEE, 2011, 2388-2392. Google Scholar

show all references

References:
[1]

M. Berg, O. Cheong, M. Kerveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 2008. Google Scholar

[2]

M. D. Buhmann, Radial basis functions, in Acta Numerica, 2000, Acta Numer., 9, Cambridge Univ. Press, Cambridge, 2000, 1-38. doi: 10.1017/S0962492900000015.  Google Scholar

[3]

F. Camilli, L. Grüne and F. Wirth, A generalization of Zubov's method to perturbed systems, SIAM J. Control Optim., 40 (2001), 496-515. doi: 10.1137/S036301299936316X.  Google Scholar

[4]

M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems, in Handbook of Dynamical Systems, Vol. 2, North-Holland, Amsterdam, 2002, 221-264. doi: 10.1016/S1874-575X(02)80026-1.  Google Scholar

[5]

M. Floater and A. Iske, Multistep scattered data interpolation using compactly supported Radial Basis Functions, J. Comput. Appl. Math., 73 (1996), 65-78. doi: 10.1016/0377-0427(96)00035-0.  Google Scholar

[6]

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

[7]

P. Giesl, Construction of a local and global Lyapunov function using Radial Basis Functions, IMA J. Appl. Math., 73 (2008), 782-802. doi: 10.1093/imamat/hxn018.  Google Scholar

[8]

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

[9]

P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions, Discrete and Continuous Dynamical Systems - Series B, 8 (2015), 2291-2331. doi: 10.3934/dcdsb.2015.20.2291.  Google Scholar

[10]

P. Giesl and H. Wendland, Meshless collocation: Error estimates with application to Dynamical Systems, SIAM J. Numer. Anal., 45 (2007), 1723-1741. doi: 10.1137/060658813.  Google Scholar

[11]

L. Grüne, An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation, Numer. Math., 75 (1997), 319-337. doi: 10.1007/s002110050241.  Google Scholar

[12]

L. Grüne, Asymptotic Behavior of Dynamical and Control Systems Under Perturbation and Discretization, Lecture Notes in Mathematics, 1783, Springer-Verlag, Berlin, 2002. doi: 10.1007/b83677.  Google Scholar

[13]

S. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete and Continuous Dynamical Systems - Series A, 10 (2004), 657-678. doi: 10.3934/dcds.2004.10.657.  Google Scholar

[14]

S. Hafstein, An algorithm for constructing Lyapunov functions, Monograph. Electron. J. Diff. Eqns., (2007), 101pp. Google Scholar

[15]

C. S. Hsu, Cell-to-cell Mapping, Applied Mathematical Sciences, 64, Springer-Verlag, New York, 1987. doi: 10.1007/978-1-4757-3892-6.  Google Scholar

[16]

A. Iske, On the construction of kernel-based adaptive particle methods in numerical flow simulation, in Recent Developments in the Numerics of Nonlinear Hyperbolic Conservation Laws, Notes Numer. Fluid Mech. Multidiscip. Des., 120, Springer, Heidelberg, 2013, 197-221. doi: 10.1007/978-3-642-33221-0_12.  Google Scholar

[17]

S. Iyengar, K. Boroojeni and N. Balakrishnan, Mathematical Theories of Distributed Sensor Networks, Springer, New York, 2014. doi: 10.1007/978-1-4419-8420-3.  Google Scholar

[18]

Z. Jian, Development of Strong Form Methods with Applications in Computational Mechanics, PhD thesis, National University of Singapore, Singapore, 2008. Google Scholar

[19]

C. Kellett, Classical converse theorems in Lyapunov’s second method, Discrete and Continuous Dynamical Systems - Series B, 8 (2015), 2333-2360. doi: 10.3934/dcdsb.2015.20.2333.  Google Scholar

[20]

R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1989. doi: 10.1007/3-540-52055-4.  Google Scholar

[21]

J. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721.  Google Scholar

[22]

A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Pranja, P. Seiler and P. Parrilo, SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB, User's guide. Version 3.00 edition, 2013. Google Scholar

[23]

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

[24]

F. Preparata and M. Shamos, Computational Geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. doi: 10.1007/978-1-4612-1098-6.  Google Scholar

[25]

J. Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, J. Approx. Theory, 18 (1995), 548-585. doi: 10.1006/jagm.1995.1021.  Google Scholar

[26]

R. Sibson, Development of strong form methods with applications in computational mechanics, in Interpolating Multivariate Data, Chapter 2 (ed. V. Barnett), John Wiley and Sons, New York, 1981. Google Scholar

[27]

H. Wendland, Error estimates for interpolation by compactly supported Radial Basis Functions of minimal degree, J. Approx. Theory, 93 (1998), 258-272. doi: 10.1006/jath.1997.3137.  Google Scholar

[28]

H. Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, 17, Cambridge University Press, Cambridge, 2005.  Google Scholar

[29]

X. Zhang, R. Ding and Y. Li, Adaptive RPIM meshless method, in Proceedings of the 2011 International Conference on Multimedia Technology (ICMT), IEEE, 2011, 2388-2392. Google Scholar

[1]

Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete & Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101
[2]

Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure & Applied Analysis, 2007, 6 (3) : 569-585. doi: 10.3934/cpaa.2007.6.569
[3]

Peter Giesl. Construction of a finite-time Lyapunov function by meshless collocation. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2387-2412. doi: 10.3934/dcdsb.2012.17.2387
[4]

Hjörtur Björnsson, Sigurdur Hafstein, Peter Giesl, Enrico Scalas, Skuli Gudmundsson. Computation of the stochastic basin of attraction by rigorous construction of a Lyapunov function. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 4247-4269. doi: 10.3934/dcdsb.2019080
[5]

Jeremy Levesley, Xinping Sun, Fahd Jarad, Alexander Kushpel. Interpolation of exponential-type functions on a uniform grid by shifts of a basis function. Discrete & Continuous Dynamical Systems - S, 2021, 14 (7) : 2399-2416. doi: 10.3934/dcdss.2020403
[6]

Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 521-542. doi: 10.3934/jimo.2014.10.521
[7]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[8]

Prabhat Mishra, Vikas Gupta, Ritesh Kumar Dubey. A mesh adaptation algorithm using new monitor and estimator function for discontinuous and layered solution. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021029
[9]

Andrei Korobeinikov, Philip K. Maini. A Lyapunov function and global properties for SIR and SEIR epidemiological models with nonlinear incidence. Mathematical Biosciences & Engineering, 2004, 1 (1) : 57-60. doi: 10.3934/mbe.2004.1.57
[10]

Łukasz Struski, Jacek Tabor. Expansivity implies existence of Hölder continuous Lyapunov function. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3575-3589. doi: 10.3934/dcdsb.2017180
[11]

Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33
[12]

Zhi-Min Chen. Straightforward approximation of the translating and pulsating free surface Green function. Discrete & Continuous Dynamical Systems - B, 2014, 19 (9) : 2767-2783. doi: 10.3934/dcdsb.2014.19.2767
[13]

Luís Tiago Paiva, Fernando A. C. C. Fontes. Adaptive time--mesh refinement in optimal control problems with state constraints. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4553-4572. doi: 10.3934/dcds.2015.35.4553
[14]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
[15]

Sohana Jahan, Hou-Duo Qi. Regularized multidimensional scaling with radial basis functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 543-563. doi: 10.3934/jimo.2016.12.543
[16]

Lianzhang Bao, Wenxian Shen. Logistic type attraction-repulsion chemotaxis systems with a free boundary or unbounded boundary. I. Asymptotic dynamics in fixed unbounded domain. Discrete & Continuous Dynamical Systems, 2020, 40 (2) : 1107-1130. doi: 10.3934/dcds.2020072
[17]

Markus Dick, Martin Gugat, Günter Leugering. A strict $H^1$-Lyapunov function and feedback stabilization for the isothermal Euler equations with friction. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225
[18]

Martin Gugat, Günter Leugering, Ke Wang. Neumann boundary feedback stabilization for a nonlinear wave equation: A strict $H^2$-lyapunov function. Mathematical Control & Related Fields, 2017, 7 (3) : 419-448. doi: 10.3934/mcrf.2017015
[19]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049
[20]

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

2020 Impact Factor: 1.327

Tools

Metrics

  • PDF downloads (72)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy