Article Contents
Article Contents

# Modified refinement algorithm to construct Lyapunov functions using meshless collocation

• *Corresponding author: Najla Mohammed
• Lyapunov functions are functions with negative derivative along solutions of a given ordinary differential equation. Moreover, sublevel sets of a Lyapunov function are subsets of the domain of attraction of the equilibrium. One of the numerical construction methods for Lyapunov functions uses meshless collocation with radial basis functions.

Recently, this method was combined with a grid refinement algorithm (GRA) to reduce the number of collocation points needed to construct Lyapunov functions. However, depending on the choice of the initial set of collocation point, the algorithm can terminate, failing to compute a Lyapunov function. In this paper, we propose a modified grid refinement algorithm (MGRA), which overcomes these shortcomings by adding appropriate collocation points using a clustering algorithm. The modified algorithm is applied to two- and three-dimensional examples.

Mathematics Subject Classification: Primary: 37C75, 37D05, 65M50; Secondary: 37M22, 65P99.

 Citation:

• Figure 1.  The Voronoi diagram for a set of sites (green o) with a Voronoi region, Voronoi edge and Voronoi vertex (red *)

Figure 2.  Example 7.1, system (17). (a) The points in $PO_1$ (green *) lie in the patches where $v_{9}'(x, y) > 0$, and the centers to be added to $X_{9}$ (black *), (b) the level set of $v_{10}'(x, y) = 0$, where $v_{10}$ is the constructed function after adding the 5 centers and the red areas are the patches remaining where $v_{10}'(x, y) > 0$

Figure 3.  Example 7.1, system (17). (a) The level set of $v_{11}'(x, y) = 0$ of the constructed function $v_{11}$ with the set of grid points $X_{11}$, obtained from the second refinement step. Again, the (red) patches are the areas where $v_{11}'(x, y) > 0$, (b) The points in $PO_2$ (green *) grouped into 2 clusters, and the cluster centers (black *), calculated by the subtractive clustering method

Figure 4.  Example 7.1, system (17). (a) The level set of $v_{13}'(x, y) = 0$ and the 104 grid points $X_{13}$ (blue *), as we can see there are no patches remaining at the end, (b) the constructed Lyapunov function $v_{13}(x, y)$ after the second refinement step

Figure 5.  Example 7.2, system (18). (a) The level set of $v_1'(x, y) = 0$ of the constructed function $v_1$ after the last refinement step, started with 48 points and ended up with 60 points, where the (red) patches are the areas where $v_1'(x, y) > 0$. (b) The points in $PO_1$ (green *) grouped into 8 clusters, and the centers to be added to $X_1$ (black *)

Figure 6.  Example 7.2, system (18). (a) The level set of $v_5'(x, y) = 0$ of the constructed function $v_5$ with the set $X_5$ of grid points obtained from the second refinement step. Again, the (red) patches are the areas where $v_5'(x, y)>0$, (b) The points in $PO_2$ (green *) grouped into 4 clusters, and the cluster centers (black *), calculated by the subtractive clustering method

Figure 7.  Example 7.2, system (18). (a) The level set of $v_7'(x, y) = 0$ and the grid points $X_7 = 96$ (blue *): no patches remain, (b) the constructed Lyapunov function $v_7(x, y)$ with the MGRA

Figure 8.  Example 7.3, system (19). (a) The level set of $v_{{2}}'(x, y, z) = 0$ (green area) and the 13,908 points in $PO_1$ where $v_{{2}}'(x, y, z)>0$ (red *); we can see some of the cluster centers as (black *), (b) the level set of $v_{{3}}'(x, y, z) = 0$ after adding the 36 cluster centers to the grid points; the green patches denote the points where $v_{{3}}'(x, y, z)>0$

Figure 9.  Example 7.3, system (19). (a) The points in $PO_4$, (red *), lie inside the patches where $v_{{6}}'(x, y, z)>0$ and some of the cluster centers, which will be added to the grid, are shown as (black *), (b) the level set $v_{{7}}'(x, y, z) = 0$ of the orbital derivative calculated with $X_{{7}} = 462$ grid points, after adding the 12 centers obtained from the final extension step; no patches remain at the end

Table 1.  Example 7.1, system (17). The steps of the MGRA performed in sequence, with the number of points added after each step as well as the total number of grid points $N$ and the functions $v_i$ in each step. The table also shows the time required, split into the time for computing the coefficients of the function (solving the linear system of size $N$) and the time to check whether the function $v_n'$ is negative on the test grid $X_{test}$

 points constructed Time Time Steps added $N$ functions (computing) (checking) 1A refinement 77 93 $v_0$–$v_9$ 0.30 sec. 8.8 sec. 1B extension 5 98 $v_{10}$ 4.6 sec. 9.4 sec. 2A refinement 2 100 $v_{11}$ 0.06 sec. 9.5 sec. 2B extension 2 102 $v_{12}$ 5 sec. 9.7 sec. 3A refinement 2 104 $v_{13}$ 0.07 sec. 9.9 sec. total=10.03 sec. total= 47.3 sec.

Table 2.  Example 7.2, system (18). The steps of the MGRA performed in sequence, with the number of points added after each step as well as the total number of grid points $N$ and the functions $v_i$ in each step. The table also shows the time required, split into the time for computing the coefficients of the function (solving the linear system of size $N$) and the time to check whether the function $v_n'$ is negative on the test grid $X_{test}$

 points constructed Time Time Steps added $N$ functions (computing) (checking) 1A refinement 12 60 $v_0$–$v_1$ 0.05 sec. 4.2 sec. 1B extension 8 68 $v_2$ 2.2 sec. 4.6 sec. 2A refinement 20 88 $v_3$–$v_5$ 0.11 sec. 6.0 sec. 2B extension 4 92 $v_6$ 3.1 sec. 6.3 sec. 3A refinement 4 96 $v_7$ 0.04 sec. 6.7 sec. total=5.5 sec. total=27.8 sec.

Table 3.  Example 7.3, system (19). The steps of the MGRA performed in sequence, with the number of points added after each step as well as the total number of grid points $N$ and the functions $v_i$ in each step. The table also shows the time required, split into the time for computing the coefficients of the function (solving the linear system of size $N$) and the time to check whether the function $v_n'$ is negative on the test grid $X_{test}$

 points constructed Time Time Steps added $N$ functions (computing) (checking) 1A refinement 56 180 $v_0$–$v_2$ 0.28 sec. 5 min. 48 sec. 1B extension 36 216 $v_3$ 1 min. 20 sec. 6 min. 55 sec. 2A refinement 0 216 – 0.4 sec. – 2B extension 22 238 $v_4$ 1 min. 34 sec. 7 min. 38 sec. 3A refinement 0 238 – 0.53 sec. – 3B extension 44 282 $v_5$ 1 min. 44 sec. 9 min. 0 sec. 4A refinement 168 450 $v_6$ 1.1 sec. 14 min. 38 sec. 4B extension 12 462 $v_{7}$ 3 min. 20 sec. 15 min. 0 sec. total=8 min. total=59 min.

Table 4.  A comparison of the three algorithms, using basic refinement (1), GRA (2) and MGRA (3). Starting with the same initial grid, we list the final number of points, the overall computation time, including the checking on $X_{test}$, and separately the time to check the final Lyapunov function on the finer grid $X_{check}$ with $h_{check} = 10^{-2}$. The checking time is proportional to the number of collocation points as the checking requires a large number of evaluations of the function

 System Time Time starting grid Final number entire final ($h$, number of points) Algorithm of points algorithm checking (17), $h=1$, $N_0=8$ 1 1088 146 sec. 105 sec. 2 88 9 sec. 8 sec. 3 88 9 sec. 8 sec. (17), $h=2/3$, $N_0=16$ 1 624 84 sec. 61 sec. 2 624 102 sec. 61 sec. 3 104 57 sec. 10 sec. (18), $h=0.6$, $N_0=16$ 1 168 16 sec. 11 sec. 2 168 25 sec. 11 sec. 3 105 70 sec. 7 sec.

Table 5.  The number of initial grid points $N_0$ and the value of $h$, which we have used to construct Lyapunov functions for Example 7.1, system (17) with GRA. In more detail, the collocation points are $\{(x, y)\in \mathbb R^2 \mid x, y\in \{-1, -1+h, -1+2h, \ldots, 1-h, 1\}\setminus [-0.1, 0.1]\}$. The last column shows the final number of points after the termination of GRA. "Patches" means that after termination of GRA there are still areas with positive orbital derivative remaining, so no Lyapunov function was constructed

 $h$ $N_{{0}}$ $N_{final}$ 2/3 16 93 (patches) 1/2 24 88 2/5 36 104 (patches) 1/3 48 94 (patches) 1/4 80 86 (patches) 1/5 120 124 (patches) 1/6 168 168 (patches) 1/7 224 224 (patches) 1/8 288 288 (patches) 1/9 360 360

Figures(9)

Tables(5)