The article examines the problem of constructing an algorithm for finding positive definite matrices that are the solution to Sylvester's three-term matrix equation. The problem is that, unlike the Lyapunov equation, such a condition cannot be written in terms of eigenvalues. The condition for the existence of a solution to the Sylvester equation is based on the principle of contraction mappings. The article also proposes an iterative procedure and algorithm for finding a solution.
+
= , also sometimes called the continuous Sylvester equation, and the Stein matrix equation + = , in turn, sometimes called the discrete Sylvester equation, as well as their special cases - the Lyapunov equations + = and − = , are well-studied and frequently encountered (for example, in the theory of differential equations) classes of matrix equations [1-6]. The conditions for the unique solvability of these equations have long been known; there are numerical algorithms for solving them, for example, the Bartels
= .
An analogue of Sylvester's equation + = began to attract the attention of researchers relatively recently [7-9]. Although this equation is superficially very similar to Sylvester's equation, their natures are profoundly different. Let's give a simple example to illustrate this difference. If all matrices are square and
= , then Sylvester’s equation has a unique solution - for any right-hand side . For the same coefficients and , the equation + = has a solution only if the matrix is symmetric. If this condition is met and satisfies this equation, then + , where is an arbitrary skew-symmetric matrix, is also a solution.
Equation + = , as well as the equations + = we will generally call two member equations of Sylvester type. The relevance of studying this kind of equations is beyond doubt. Let us give several examples showing why the study of equations of Sylvester type is justified. Equation = was first encountered by us in article [10-12], where it was studied under the additional Solvability conditions and a description of the general solution were given in terms of generalized inverses for matrices and
and their associated projectors. These conditions are not entirely
2023 Copyright for this paper by its authors. CEUR
ceur-ws.org constructive and are difficult to verify. Homogeneous equation + = was studied in article [2] in the special case = . The authors were motivated by the fact that the set + ∈ × is the tangent space (calculated at point ) of the orbit of matrix under the action of congruences. The codimension of this orbit is exactly the dimension of the space of solutions to the equation + = 0. The main result of work [2,3] was the establishment of the canonical structure of matrices in general position with respect to congruences. In a similar way, the same authors in [4] studied the equation + = 0. In the publication [4] the equations + = arise when constructing an algorithm for palindromic eigenvalue problems = .
In the process of reducing matrix A to antitriangular form, the need arises to solve these equations numerically. In article [5], the conditions for unique solvability and a numerical algorithm for solving the equation + = are formulated.
By analogy with equations of Sylvester type, equations of Stein type will be called equations + = . The first of them was partially studied in publication [6]. The question naturally arises about the completion of this study. The topic of solvability of the other two equations, on the contrary, is explored exhaustively in this publication.
No less interesting is the problem of obtaining sufficient solvability conditions for the Sylvester matrix equation + + = − , where is a positive definite matrix. The need to solve such equations is emphasized in [13-14].
It is noted in [9] that there are now several approaches to solving the Sylvester equation. The first is to reduce the matrix equation to a vector (linear algebraic equation of increased dimension) and then the condition for the solvability of this equation is expressed through the non-degeneracy of the corresponding matrix. The second approach uses the small parameter method. It is also possible to obtain a spectral sparsity criterion for an equation with mutually commutable matrices. An analytical solution of this equation is possible only for the case of the two-term Sylvester equation.
At the same time, the question of the existence of a positive definite solution in the general case remains open. The procedure for finding this solution is also of interest for another investigations [1516]. The purpose of the article is to obtain sufficient conditions for the existence of a solution to the Sylvester matrix equation on a set of positive definite matrices. The article will also present an iterative procedure and algorithm for finding these solutions.
The approach is based on a modification of the contraction mapping method. If on a complete metric space the following operator is specified [ ], ∈ , that maps points ∈ to points of the same space [ ] ∈ and satisfies the contraction condition ( [ ], [ ]) ≤ ( , ), 0 < < 1, where ( , ) is the metric of the space M, then the operator equation has a unique solution ∗ ∈ , and it can be found by the method of successive iterations = li→m∞ , = [ −1], = 1,2, … , 0 = 0.
Let 0 - be an arbitrary point in space, H is some complete metric space with metric ( 1, 2). Let us fix the following operators:
Consider the operator equation
= [ ] , :
→ . [ ] = [ ] (1)
Let us show that to solve this equation we can use an iterative procedure based on the following implicit scheme
[ +1] = [ ], 0 = 0, = 1,2,..,; 0 ∈H
Definition. We call method (2) converging to the solution of equation (1) if the sequence { }, = [ ], at → ∞ converges. Let us prove a theorem whose conditions ensure the convergence of method (2) to the solution of equation (1).
( , ) = { ∈ : ( [ ], [ ])⟨ }.
Theorem 1. Let us fix the set ( , ), i.e. the values of and are determined. If for arbitrary 1, 2 ∈ ( , ) operators , : → satisfy the contraction condition and ( [ 1], [ 2]) < ( [ 1], [ 2]),0 < < 1,
( [ ], [ ]) < (1 − ) , then operator equation (1) has a unique solution in the set ( , ) and the sequence { }, = [ ] constructed according to scheme (2) converges to ∗ = [ ∗] for any starting point 0 ( , ). For the error of method (2), the following estimate is valid:
( [ ], [ ∗]) < 1− ( [ 0], [ 0]).
Proof. Let 0 - be an arbitraryelement of H(A, r) . Let us prove that the sequence built according to scheme (2) will not leave the set H(A, r). By condition 0 ∈ ( , ). Let us assume that ∈ ( , )for some fixed k. Let us show that then +1 ∈ ( , ). Consider the equality: [ +1] = [ ]
[ +1] − [ ] = [ ] − [ ] = ( [ ] − [ ]) + ( [ ] − [ ])
( [ +1], [ ]) < ( [ ], [ ]) + ( [ ], [ ]).
Using the induction hypothesis, we have and since by the conditions of the theorem ( [ ], [ ]) < (1 − ) we get that ( [ ], [ ]) < ( [ ], [ ]) < qr ( [ +1], [ ]) < qr + (1 − ) = . (2) (3) (4) (5) (6) Thus +1 ∈ ( , ).
Now we will show that the following sequence { }, = [ ] is Cauchy. Let's consider the difference [ +1] − [ ]:
[ +1] − [ ] = [ ] − [ −1]
( [ +1], [ ]) = ( [ ], [ −1]) < ( [ ], [ −1]) and therefore
( [ +1], [ ]) < ( [ 1], [ 0]) Let ∈ . Then it's fair
[ + ] − [ ] = ∑ =1( [ + ] − [ + −1]).
( [ + ], [ ]) < 1− ( [ 1], [ 0]). (7) Because li→m¥1− = 0 and does not depend on , then the sequence { } - Cauchy. Therefore there Let us pass to the limit in (2) at → ∞, then we get that [ ∗] = [ ∗]. Hence ∗- is a solution of equation (1). Let us prove the uniqueness of this solution. Let ∗ is a some another solution (1) and ∗ ∈ ( , ). Then li→m∞ = ∗, ∗ = [ ∗], ∗ ∈ ( , ) [ ∗] − [ ∗] = [ ∗] − [ ∗]
( [ ∗], [ ∗]) < ( [ ∗], [ ∗]). is a limit and
Because 0 < < 1, That ∗ = ∗.
Let us prove the estimate of the error of method (2). Let k be fixed and → ∞. Then from (7) we obtain
( [ ], [ ∗]) < 1− ( [ 1], [ 0]), = 1,2, .
Denote as H the space of symmetric matrices with the metric - ( 1, 2) = | 1 − 2|.
[ 1] − [ 2] = 2( )( 1 − 2), [ 1] − [ 2] = 1( )( 1 − 2),
Assume that there is an inverse operator 2−1. Then we get: [ 1] − [ 2] = 1( ) 2−1( )( [ 1] − [ 2]).
| [ 1] − [ 2]| ≤ | 1( ) 2−1( )|| [ 1] − [ 2]|
| 1( ) 2−1( )| ≤ < 1.
This condition is not always convenient. Using Theorem 1 and inequality (9), we obtain the conditions for the solvability of the Sylvester matrix equation.
[ ]=- − HA, [ ] = + HB, where , are some matrices, is a positive definite matrix. Then the Sylvester matrix equation can be rewritten as:
[ ] = [ ].
Lemma 1. A necessary condition for the solvability of the Sylvester matrix equation on the set of positive definite matrices is that the matrix is Hurwitz.
− 0 − 0 = + 0 .
Let's denote 1 = + 0 . Because and 0 are positive definite, then 1 will be a positive definite. Then (8) (9) (10) is a matrix Lyapunov equation and since 0 is his solution, then is a Hurwitz matrix. 2.2.
Lemma 2. Let matrices , satisfy the following conditions:
1) - is Hurwitz matrix, 2)|( ×B)(− ×I − I×A)−1| ≤ , (11) (12) − +1 − +1 = + ,
1( ) = ×B.
2−1( ) = (− xI − IxA)−1.
where × denotes the Kronecker product, then there is a unique positive definite solution to the
where is an arbitrary positive definite matrix. we have:
Proof. Let us apply inequality (9) to the operators defining the Sylvester equation. For operator Since is Hurwitz, then the operator 2−1( ) exists and can be written
Consequently, we find that inequality (12) ensures that condition (3) of Theorem 1 is satisfied. Let us take as the working set the entire space of positive definite matrices, then =∞. Thus, we obtain conditions for the existence and uniqueness of a solution to the Sylvester matrix equation.
− +1 − +1 = + will be a positive definite matrix. Let us prove this by mathematical induction. Matrix 0 positive definite - due to the choice of the starting point. Let is a positive definite matrix. Let's show positive definiteness +1.
where = + , = 1,..., ,... equation will be a positive definite matrix. The lemma is proven. 2.3.
Application examples
− +1 − +1 = , example
Since is Hurwitz and - is always positive definite, then +1, as a solution to the Lyapunov
Let us consider examples of the fulfillment of the conditions of Lemma 2. Let in the first where matrix is Hurwitz. We substitute the values of matrices and into condition (12), carry out calculations and find that all elements in the resulting matrix are less than 1 in absolute value, which indicates that the condition is met.
In the second example = ( 2 we carry out similar calculations and obtain the fulfillment of conditions (11) and (12).
Let us give an example of non-fulfillment of the conditions of Lemma 2. Let the values of the matrices be as follows: values greater than 1, and this indicates that the condition is not met. 2.4.
Sylvester equation, we apply the following algorithm: 1. Check the Hurwitz property of matrix . 2. Check the condition |( ×B)(− ×I − I×A)−1| ≤ . 3. If 1.2 are true, then a solution exists and perform step 4. Otherwise, step 9. 4. We let = 0, 0 = , − identity matrix. 5. At the kth step we calculate 1 = + .
6. Solve the Lyapunov equation − +1 − +1 = 1. go to step 5, otherwise go to step 8.
9. The end.
Let us consider an algorithm for finding positive definite solutions. For finding a solution of the 7. Check the condition for ending the iteration procedure. If it is not fulfilled, then = + 1 and
The article studies the solvability of Sylvester's three-term matrix equation. Using the principle of contraction mappings, a sufficient condition for the existence of a positive definite solution is obtained. It should be noted that such conditions have not been published before. In other works authors solve similar equations by expanding the equation into a system of linear algebraic equations with constant coefficients and then solving it, for example, using the Gauss method. This approach does not allow us to obtain the condition for the existence of the necessary solution. In this article, in addition to the sufficient condition for the existence of a positive definite solution to the three-term matrix Sylvester equation, an algorithm for finding it is proposed and the convergence of this algorithm is proven.
The method presented in this article will allow us to more effectively solve problems of stability and controllability, which are presented in [17-22]. The solvability condition for Sylvester's three-term matrix equation is easy to verify. It is constructive. The proposed algorithm effectively finds a symmetric positive definite solution. 5. References [1]. Xing Lili, Li Weiguo, Bao Wendi, Some results for Kaczmarz method to solve Sylvester matrix equations, Journal of the Franklin Institute, Volume 360, Issue 11, 2023, pp. 7457-7461.