О решении двустороннего векторного уравнения в тропической алгебре
DOI:
https://doi.org/10.21638/spbu01.2023.205Аннотация
Рассматривается задача решения в контексте тропической математики векторного уравнения с двумя заданными матрицами и неизвестными векторами, каждая часть которого имеет вид произведения одной из матриц на неизвестный вектор. Такое уравнение, которое имеет неизвестные векторы по обе стороны от знака равенства, часто называют двусторонним. Предлагается новая процедура решения двустороннего уравнения на основе минимизации некоторой функции расстояния между векторами тропических векторных пространств, которые генерируются столбцами каждой из матриц. В результате получают пару векторов, которые обеспечивают минимум расстояния между пространствами и значение самого расстояния. Если уравнение имеет решения, то полученные векторы являются решением уравнения. В противном случае эти векторы определяют псевдорешение, которое минимизирует уклонение одной части уравнения от другой. Выполнение процедуры состоит в построении последовательности векторов, являющихся псевдорешениями двустороннего уравнения, в котором поочередно левая и правая части заменяются постоянными векторами. В отличие от известного алгоритма чередования (альтернирования), в котором вместо уравнений поочередно решаются соответствующие неравенства, предложенная процедура использует иное обоснование, представляется более простой и позволяет установить естественные критерии завершения расчетов. При отсутствии решений процедура также находит псевдорешение и определяет величину связанной с ним погрешности, что может оказаться полезным при решении задач аппроксимации.Ключевые слова:
идемпотентное полуполе, тропическое векторное пространство, обобщенная метрика, двустороннее векторное уравнение, итеративная вычислительная процедура, псевдорешение
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
Литература
1. Kolokoltsov V. N., Maslov V. P. Idempotent Analysis and Its Applications. In: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
2. Golan J. S. Semirings and Affine Equations Over Them. In: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
3. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
4. Gondran M., Minoux M. Graphs, Dioids and Semirings. In: Operations Research. Computer Science Interfaces, vol. 41. New York, Springer (2008). https://doi.org/10.1007/978-0-387-75450-5
5. Butkoviˇc P. Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. London, Springer (2010). https://doi.org/10.1007/978-1-84996-299-5
6. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
7. Butkoviˇc P. On certain properties of the systems of linear extremal equations. Ekonom.-Mat. Obzor 14 (1), 72-78 (1978).
8. Butkoviˇc P. Solution of systems of linear extremal equations. Ekonom.-Mat. Obzor 17 (4), 402-416 (1981).
9. Butkoviˇc P., Heged¨us G. An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. Obzor 20 (2), 203-215 (1984).
10. Cuninghame-Green R. A., Butkoviˇc P. The equation A ⊗ x = B ⊗ y over (max, +). Theoret. Comput. Sci. 293 (1), 3-12 (2003). https://doi.org/10.1016/S0304-3975(02)00228-1
11. Butkoviˇc P., Zimmermann K. A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154 (3), 437-446 (2006). https://doi.org/10.1016/j.dam.2005.09.008
12. Lorenzo E., de la Puente M. J. An algorithm to describe the solution set of any tropical linear system A ⊗ x = B ⊗ x. Linear Algebra Appl. 435 (4), 884-901 (2011). https://doi.org/10.1016/j.laa.2011.02.014
13. Jones D. On two-sided max-linear equations. Discrete Appl. Math. 254 (3), 146-160 (2019). https://doi.org/10.1016/j.dam.2018.06.011
14. Butkoviˇc P. On properties of solution sets of extremal linear programs. Algebraic and Combinatorial Methods in Operations Research. In: North-Holland Mathematics Studies, vol. 95, 41-54. Amsterdam, North-Holland (1984). https://doi.org/10.1016/S0304-0208(08)72952-9
15. Walkup E. A., Borriello G., Taylor J. M., Atiyah M. A. General linear max-plus solution technique. Idempotency. In: Publications of the Newton Institute, 406-415. Cambridge, Cambridge University Press (1998). https://doi.org/10.1017/CBO9780511662508.024
16. Cuninghame-Green R. A., Zimmermann K. Equation with residuated functions. Comment. Math. Univ. Carolin. 42 (4), 729-740 (2001).
17. Кривулин Н. К. Методы идемпотентной алгебры в задачахмоделирования и анализа сложныхсистем. С.-Петербург, Изд-во С.-Петерб. ун-та (2009).
18. Кривулин Н. К. О решении одного класса линейных векторных уравнений в идемпотентной алгебре. Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления 5 (3), 63-76 (2009).
19. Кривулин Н. К. О решении линейных векторных уравнений в идемпотентной алгебре. Математические модели. Теория и приложения 5, 105-113. Санкт-Петербург, Изд-во ВВМ (2004).
References
1. Kolokoltsov V. N., Maslov V. P. Idempotent Analysis and Its Applications. In: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
2. Golan J. S. Semirings and Affine Equations Over Them. In: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
3. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
4. Gondran M., Minoux M. Graphs, Dioids and Semirings. In: Operations Research. Computer Science Interfaces, vol. 41. New York, Springer (2008). https://doi.org/10.1007/978-0-387-75450-5
5. Butkoviˇc P. Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. London, Springer (2010). https://doi.org/10.1007/978-1-84996-299-5
6. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
7. Butkoviˇc P. On certain properties of the systems of linear extremal equations. Ekonom.-Mat. Obzor 14 (1), 72-78 (1978).
8. Butkoviˇc P. Solution of systems of linear extremal equations. Ekonom.-Mat. Obzor 17 (4), 402-416 (1981).
9. Butkoviˇc P., Heged¨us G. An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. Obzor 20 (2), 203-215 (1984).
10. Cuninghame-Green R. A., Butkoviˇc P. The equation A ⊗ x = B ⊗ y over (max, +). Theoret. Comput. Sci. 293 (1), 3-12 (2003). https://doi.org/10.1016/S0304-3975(02)00228-1
11. Butkoviˇc P., Zimmermann K. A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154 (3), 437-446 (2006). https://doi.org/10.1016/j.dam.2005.09.008
12. Lorenzo E., de la Puente M. J. An algorithm to describe the solution set of any tropical linear system A ⊗ x = B ⊗ x. Linear Algebra Appl. 435 (4), 884-901 (2011). https://doi.org/10.1016/j.laa.2011.02.014
13. Jones D. On two-sided max-linear equations. Discrete Appl. Math. 254 (3), 146-160 (2019). https://doi.org/10.1016/j.dam.2018.06.011
14. Butkoviˇc P. On properties of solution sets of extremal linear programs. Algebraic and Combinatorial Methods in Operations Research. In: North-Holland Mathematics Studies, vol. 95, 41-54. Amsterdam, North-Holland (1984). https://doi.org/10.1016/S0304-0208(08)72952-9
15. Walkup E. A., Borriello G., Taylor J. M., Atiyah M. A general linear max-plus solution technique. Idempotency. In: Publications of the Newton Institute, 406-415. Cambridge, Cambridge University Press (1998). https://doi.org/10.1017/CBO9780511662508.024
16. Cuninghame-Green R. A., Zimmermann K. Equation with residuated functions. Comment. Math. Univ. Carolin. 42 (4), 729-740 (2001).
17. Krivulin N. K. Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems. St Petersburg, St Petersburg University Press (2009). (In Russian)
18. Krivulin N. K. On solution of a class of linear vector equations in idempotent algebra. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes 5 (3), 63-76 (2009). (In Russian)
19. On solution of linear vector equations in idempotent algebra. Mathematical Models. Theory and Applications 5, 105-113. St Petersburg, VVM Publ. (2004). (In Russian)
Загрузки
Опубликован
10.05.2023
Как цитировать
Кривулин, Н. К. (2023). О решении двустороннего векторного уравнения в тропической алгебре. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 10(2), 236–248. https://doi.org/10.21638/spbu01.2023.205
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
