The paper considers methods for estimating stability using Lyapunov functions, which are used for nonlinear polynomial control systems. The apparatus of the Gr¨obner basis method is used to assess the stability of a dynamical system. To apply the method, the canonical relations of the nonlinear system are approximated by polynomials of the components of the state and control vectors. The equilibrium states of a nonlinear polynomial system are determined as solutions of a nonlinear system of polynomial equations. An example of determining the equilibrium states of a nonlinear polynomial system using the Gr¨obner basis method is given. The application of the Gr¨obner basis method for estimating the attraction domain of a nonlinear dynamic system with respect to the equilibrium point is considered. The coordination of input-output signals of the system based on the construction of Gr¨obner bases is considered.
ordering the Gr¨obner basis has a triangular structure, reminiscent of the triangular structure in the Gaussian elimination method.
The theory of control of dynamic objects can be divided into two subgroups [Khalil02]: (1) systems in which the principle of superposition operates, and linear control methods can be used; (2) systems in which the superposition principle does not work, and it is necessary to use nonlinear control methods. To improve the quality of the dynamic object control system, it is necessary to take into account the nonlinear features of the system. 1
The objects in the theory of Gr¨obner bases are polynomial ideals and algebraic varieties [Nesic02]. Let p1, ..., ps be multidimensional polynomials in variables x1, ..., xn, whose coefficients lie in the field k (we will consider the field of real numbers R). The variables x1, ..., xn are considered ”place markers” in the polynomials: p1, . . . , ps ∈ R[x1, . . . , xn]. Algebraic variety defined by the polynomials p1, . . . , ps is the collection of all solutions in Rn of the system of equations:
V (p1, ..., ps) := {(a1, ..., an) ∈ Rn : pi(x1, ..., xn) = 0, i = 1, ..., s}
The polynomial ideal I, which is generated by p1, ..., ps, is a set of polynomials obtained by combining these polynomials by multiplying and adding with other polynomials:
{ I = ⟨p1, ..., ps⟩ := f =
s ∑ gipi : gi ∈ R[x1, ..., xn] i=1 }
The polynomials pi, i = 1, . . . , s form the basis of the ideal I. A useful interpretation of the polynomial ideal I is in terms of the equations (3). Multiplying gi by arbitrary polynomials gi ∈ R[x1, ..., xn] and adding them, we get the consequence from (1):
f = g1p1 + . . . + gsps = 0, and f ∈ I. Therefore, I = ⟨p1, . . . , ps⟩ the ideal contains all ”polynomial consequences” of the equations (3).
The Gr¨obner basis method is based on the concept of monomial ordering (a monomial is a polynomial consisting of one term), since it introduces a corresponding extension of the concept of a leading term and a leading coefficient, familiar for one-dimensional polynomials, to multidimensional polynomials. Let’s consider lexicographic or lex order [Nesic02]. Let α, β be two n - tuples of integers α = (α1, . . . , αn) ∈ Nn , β = (β1, . . . , βn) ∈ Nn. n -tuple α follows β (in lex order), which is denoted as α ≻ β, if in the difference of vectors α − β = (α1 − β1, . . . , αn − βn) the leftmost nonzero element is positive. For the polynomial f = x31x2x33 + 2x31x43 using lex order x1 ≻ x2 ≻ x3 results in x31x2x33 follows x3x43, since the multidegrees of monomials satisfy: (3, 1, 3) ≻ (3, 0, 4). In this order, the 1 leading coefficient and the leading term are respectively LC(f ) = 1 and LT (f ) = x31x2x33. When using lex of order x3 ≻ x2 ≻ x1 senior term: LT (f ) = 2x31x34, since (4, 0, 3) ≻ (3, 1, 3).
The ideal I has no unique basis, but for any two different bases ⟨p1, ..., ps⟩ and ⟨g1, ..., gm⟩ of the ideal I, the varieties V (p1, . . . , ps) and V (g1, . . . , gm) are equal; the variety depends only on the ideal generated by its defining equations. If all polynomials in a given basis of an ideal have a degree lower than the degree of any other polynomial in an ideal, then this basis is the simplest. For an ideal I and a given monomial order, we denote the set of leading terms of elements I as LT (I). The ideal generated by elements from LT (I) is denoted by ⟨LT (I)⟩. The Gr¨obner basis is formally defined as a set of polynomials g1, . . . , gm, for which ⟨LT (I)⟩ = ⟨LT (g1), . . . , LT (gm)⟩. When calculating Gr¨obner bases, a monomial order is specified. We note two properties of Gr¨obner bases for a given monomial order: 1. Each ideal I ⊂ R[x1, ..., xn], different from the trivial ⟨0⟩, has a Gr¨obner basis.
2. For the ideal I ⊂ R[x1, ..., xn], different from the trivial ⟨0⟩, the Gr¨obner basis of the ideal I can be calculated using a finite number of algebraic operations.
For a given set of polynomials P , there is an algorithm that computes the Gr¨obner basis for the (ideal generated by) P in a finite number of steps [Buchberger70]. Buchberger’s algorithm generalizes algorithms: Gaussian elimination for a system of linear algebraic equations and Euclid’s algorithm for calculating the greatest common divisor of a set of one-dimensional polynomials. This algorithm was implemented on computers in symbolic computation programs using Gr¨obner bases for solving systems of polynomial equations [?, Wolfram03, Demenkov15]. 2
Finding equilibrium states of a nonlinear dynamical system
The use of the Gr¨obner basis in finding solutions to a nonlinear system of polynomial equations is similar to the application of the Gauss method for solving a quadratic system of linear equations. Consider an example of reducing a nonlinear system of polynomial equations: p1 = x1 − x22 = 0, p2 = x2 + x23 = 0, p3 = x3 − 2x21 = 0, to a triangular form using the Gr¨obner basis method for lex order: x1 ≻ x2 ≻ x3. In the WOLFRAM MATHEMATICA package, the function call
GroebnerBasis[{p1, p2, p3}, {x1, x2, x3}, {}] leads to a triangular Gaussian form of polynomial equations: x1 − x43 = 0, x2 + x23 = 0, −x3 + 2x83 = 0, which allows us to get a solution to this system.
Consider a nonlinear system without inputs x˙ (t) = f (x(t)); x, f ∈ Rn, t ∈ R, where f (x) = 0 is a vector of polynomials in x. The equilibrium states for this polynomial system are obtained as solutions of a nonlinear system of polynomial equations: f (x) = 0.
Equilibrium states of the [Nesic02] polynomial system: can be obtained as solutions of system polynomial equations:
The Gr¨obner basis for the ideal (p1, p2, p3) using lex order: x1 ≻ x2 ≻ x3, has the form:
Algebraic equations gi = 0, i = 1, 2, 3, 4 has the same solutions as pj = 0, j = 1, 2, 3. The polynomial g4 depends only on x3; from the algebraic equation g4(x3) = 0, you can determine x3. If the numerical value of x3 substitute in g3(x2, x3) = 0, then you can define x2; from g2(x1, x2, x3) = 0 you can define x1.
In the WOLFRAM MATHEMATICA package: Form an ideal of polynomials: p1 = x1 + x2 − x32; p2 = x12 + x2 − x3; p3 = −x1 + x22 + x3.
Let us define the Gr¨obner basis: grbas = GroebnerBasis[{p1, p2, p3}, {x3, x2, x1}, {}], grbas = {4x1 − 2x12 − 4x13 + x14 + x16, −x12 + x14 − 2x2 + 2x12x2, −x1 + x12 + x2 + x22, −x12 − x2 + x3}.
To find the roots of x1, we define the reduced Gr¨obner basis: grbas = GroebnerBasis [{p1, p2, p3} , {x3, x2, x1} , {x3, x2}] , grbas = {4x1 − 2x12 − 4x13 + x14 + x16}.
Let’s execute: Roots[4x1 − 2x12 − 4x13 + x14 + x16 == 0, x1].
To find the roots of x2 with known x1, we define the reduced Gr¨obner basis: grbas = GroebnerBasis [{p1, p2, p3} , {x3, x2, x1} , {x3}] , grbas = {−x1 + x12 + x2 + x22}.
Let’s execute: Roots[−x1 + x12 + x2 + x22 == 0, x2].
To find the roots of x3 with known x1, x2, execute: Roots[−x12 − x2 + x3 == 0, x3]. The results are shown in Table 1.
Application of the Grobner basis method in the theory of the method of Lyapunov functions 3.1
The set of all initial conditions of a dynamical system, which converge to the same equilibrium state, is called the area of attraction of this equilibrium state [Forsman91, Sidorov19]. One way to get an estimate of the domain of attraction is to use the Lyapunov functions.
The standard result of Lyapunov’s theory is that if x = 0 is an equilibrium point for a system with continuous time: x˙ = f (x), x ∈ D ⊂ Rn, is a domain containing x = 0 and V : D → R is a continuously differentiable Lyapunov function such that V (0) = 0 and V (x) > 0, V˙ = Vxf (x) < 0, ∀x ∈ D − {0} ; then the point x = 0 is asymptotically stable. For such a Lyapunov function, consider the sets Ω = {x ∈ Rn : Vxf (x) < 0} and Bd = {x ∈ Rn : V (x) ≤ d} . If there is a value d > 0 such that Bd ⊂ Ω, then the set Bd is an estimate of the domain of attraction.
For polynomial systems with a polynomial Lyapunov function V , the Gr¨obner basis can be used to determine Bd. You can determine the largest Bd by finding a d such that Bd ⊂ Ω. For polynomial systems with polynomial Lyapunov functions, V (x) − d and Vxf (x) are polynomials and the boundaries of the sets Bd and Ω are varieties Z(V − d) and Z(Vxf (x)), respectively. At the points of contact Z(V − d) and Z(Vxf (x)), the gradients V and Vxf (x) are parallel [Luenberger16]. Using this information, we obtain a system of n + 2 polynomial equations in n + 2 variables (x1, . . . , xn, d, λ), where λ is the Lagrange multiplier (see Appendix):
V − d = 0, Vxf = 0, ∇(Vxf ) − λ∇V = 0. (4) In the case of the vector of Lagrange multipliers λ = (λ1, . . . , λm)T ∈ Rm we obtain a system of n + m + 1 equations from n + m + 1 variables x1, ..., xn, d, λ1, . . . , λm.
Calculating the Gr¨obner basis for this system, where the variable d has the lowest rank in the lex order, we obtain a polynomial equation for d. The smallest positive solution of this equation (the value dmin > 0), is the best estimate of the area of attraction.
Consider a second-order system: x˙ = f (x) = ( x = 4x21 + 4x1x2 + 3x22, therefore: Vx = V˙ = Vxf = −8x21 + 12x1x23 − 8x1x2 + 8x21x22 − 6x22.
The fact that the gradients are parallel (∇(Vxf ) − λ · ∇V = 0) gives additional equations: potential from the vector field X by using the homotopy operator centered at the point x0 = 0 for the form ω = f (x)dx : ∂ ∂x 1 ( ∂ ) H(ω) = ∫ x 0 ∂x
1 | (f (λx)dx) dλ = ∫ xT f (λx)dλ.
0 We will assume that φ(x) = Hω(x) is a scalar potential.
Consider an example of dynamic equations:
Let’s construct a dual differential form: to which we apply the homotopy operator with x0 = 0 : x˙ 1 = −x1 + x22,
2 x˙ 2 = −x2 − x1.
ω = (−x1 + x22)dx1 + (−x2 − x12)dx2, 1 = − 2 (x21 + x22) + Let’s find the solution of the system V d = V (x) − d = 0 in the WOLFRAM MATHEMATICA package: V (x) = −6 · ϕ (x) = 3 (x21 + x22)+ 2 (x1x22 − x2x21),
The roots of the polynomial 54d − 29d2 + d3are : d1 = 0, d2 = 2, d3 = 27.
The smallest nonzero positive value d, for which there is a solution to the system: dmin = 2. 4
Conversions of input-output signals of a nonlinear system
Consider a differential ring - a ring on which the differentiation operation is defined. It is assumed that differentiation is carried out with respect to the implicit variable t. A differential ideal is an ideal that is closed under differentiation.
A polynomial system in the state space is a system of differential equations:
x˙ 1 = f1(x, u), . . . , x˙ n = fn(x, u), y = h(x, u), where h, fi ∈ R[x, u], ∀i.
Thus, every polynomial system in the form of a state space corresponds to a differential ideal in R[x, u, y] :
I = [φ1, . . . , φn, y − h], where φi = x˙ i − fi(x, u), i = 1, . . . , n.
The problem of transformation from the state space to the input-output form: let I be a differential ideal; find a generator for the differential ideal I ∩ R[u, y].
Suppose that it is necessary to find a differential relationship between u and y from the description in the state space of the system:
x˙ 1 = −2x1 + x22; x˙ 2 = −x1x2 + u; y = x2.
Differentiating the equations of the system with respect to t and replacing x˙ i by fi, we get: g1 = y − x2; g2 = y˙ − (u − x1x2); g3 = y¨ − (u˙ − (x22 − 2x1)x2 − x1(u − x1x2)).
Replace y → y0, y˙ → y1, y¨ → y2, u → u0, u˙ → u1 in gi, calculate the Gr¨obner basis G for: (y0 − x1, y1 − u0 + x1x2, y2 − u1 + (x22 − 2x1)x2 + x1(u0 − x1x2)) relative to lex order: u0 ≺ u1 ≺ y0 ≺ y1 ≺ y2 ≺ x1 ≺ x2.
Therefore, the input signals u, u˙ and the output signals y, y˙, y¨ are related by:
(−2u − u˙ + 2y˙ + y¨ + yy˙)y3 + (−3u02 + 3uy˙ − y˙2)y˙ + u30.
In the WOLFRAM MATHEMATICA package: g1 = y0 − x1, g2 = y1 − u0 + x1 ∗ x2, g3 = y2 − u1 + (x22 − 2 ∗ x1) ∗ x2 + x1 ∗ (u0 − x1 ∗ x2). grbas = GroebnerBasis[{g1, g2, g3} , {u0, u1, y0, y1, y2, x1, x2}, {x1, x2}], grbas = (−2u0 − u1 + 2y1 + y2 + y0y1)y03 + (−3u20 + 3u0y1 − y12)y1 + u0.
3
The paper considers methods for estimating stability using Lyapunov functions, applied to nonlinear systems. The canonical relations of a nonlinear system are approximated by polynomials of the components of the state and control vectors. To assess the stability, Gr¨obner bases are used. A method for finding the critical points of a given nonlinear system is proposed. The coordination of input-output signals of the system based on the construction of Gr¨obner bases is considered.
This work was supported by the Basic Research Program of the Siberian Branch of the Russian Academy of Sciences No. I.5.1., Project No. 0314-2019-0020. [Krasovsky59] N. N. Krasovsky Problems of the Theory of Stability of Motion Mir, Moscow, 1959 [Forsman91] K. Forsman Construction of Lyapunov functions using Gr¨obner bases Proceedings of the 30th IEEE
Conference on Decision and Control, 798-799, 1991 [Chukanov12] S. N. Chukanov , D. V. Ulyanov Decomposition of the vector field of control system by constructing a homotopy operator Probl. Upr., 6: 26, 2012 [Edelen85] D. G. B. Edelen Applied Exterior Calculus John Wiley & Sons, Inc., N.-Y., 1985 [Khalil02] H. K. Khalil Nonlinear systems Prentice Hall, 2002 [Luenberger16] D. G. Luenberger, Y. Ye Linear and nonlinear programming Springer, 2016 [Buchberger70] B. Buchberger Ein algorithmisches Kriterium fur die Losbarkeit eines algebraischen Gleichungssystems Aequationes Muthematicae, 4(3): 374–383, 1970