TY - JOUR

T1 - On the solution of a two-sided vector equation in tropical algebra

AU - Кривулин, Николай Кимович

N1 - Krivulin N. K. On the solution of a two-sided vector equation in tropical algebra // Vestnik St. Petersb. Univ. Math. 2023. Vol. 56, N 2. P. 172-181. DOI: 10.1134/S1063454123020103. URL: https://doi.org/10.1134/S1063454123020103

PY - 2023/6/8

Y1 - 2023/6/8

N2 - In the context of tropical mathematics, the problem of solving a vector equation with two given matrices and unknown vectors, each part of which has the form of a product of one of the matrices and an unknown vector, is considered. Such an equation, which has an unknown vector on either side of the equal sign, is often called a two-sided equation. A new procedure for solving two-sided equations is proposed based on minimizing some distance function between the vectors of tropical vector spaces that are generated by the columns of each of the matrices. As a result of the procedure, a pair of vectors is obtained, which provides a minimum distance between the spaces and the value of the distance itself. If the equation has solutions, then the resulting vectors are the solution to the equation. Otherwise, these vectors define a pseudo-solution that minimizes the deviation of one side of the equation from the other. Execution of the procedure consists in constructing a sequence of vectors that are pseudo-solutions of the two-sided equation in which the left and right sides are alternately replaced by constant vectors. Unlike the well-known alternating algorithm, in which the corresponding inequalities are solved one by one instead of equations, the proposed procedure uses a different argument, looks simpler, and allows one to establish natural criteria for completing calculations. If the equation has no solutions, the procedure also finds a pseudo-solution and determines the value of the error associated with it, which can be useful in solving approximation problems.

AB - In the context of tropical mathematics, the problem of solving a vector equation with two given matrices and unknown vectors, each part of which has the form of a product of one of the matrices and an unknown vector, is considered. Such an equation, which has an unknown vector on either side of the equal sign, is often called a two-sided equation. A new procedure for solving two-sided equations is proposed based on minimizing some distance function between the vectors of tropical vector spaces that are generated by the columns of each of the matrices. As a result of the procedure, a pair of vectors is obtained, which provides a minimum distance between the spaces and the value of the distance itself. If the equation has solutions, then the resulting vectors are the solution to the equation. Otherwise, these vectors define a pseudo-solution that minimizes the deviation of one side of the equation from the other. Execution of the procedure consists in constructing a sequence of vectors that are pseudo-solutions of the two-sided equation in which the left and right sides are alternately replaced by constant vectors. Unlike the well-known alternating algorithm, in which the corresponding inequalities are solved one by one instead of equations, the proposed procedure uses a different argument, looks simpler, and allows one to establish natural criteria for completing calculations. If the equation has no solutions, the procedure also finds a pseudo-solution and determines the value of the error associated with it, which can be useful in solving approximation problems.

KW - idempotent semifield

KW - tropical vector space

KW - generalized metric

KW - two-sided vector equation

KW - iterative computational procedure

KW - pseudo-solution

UR - https://www.mendeley.com/catalogue/880dca78-07b6-3a6a-952f-47d054cb6d14/

U2 - 10.1134/S1063454123020103

DO - 10.1134/S1063454123020103

M3 - Article

VL - 56

SP - 172

EP - 181

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -