Универсальные алгоритмы решения дискретных стационарных уравнений Беллмана

В настоящей работе исследуются алгоритмы решения дискретных стационарных (или) матричных уравнений Беллмана над полукольцами, в особенности над тропическими и идемпотентными полукольцами. Также приведены оригинальные алгоритмы, приложения и программная реализация.

тропическая линейная алгебра, идемпотентные полукольца, матричные уравнения Беллмана, универсальные алгоритмы

1. Дж. Голуб, Ч.Ван Лоун, Матричные вычисления, Мир, М., 2000.

2. Н.К. Кривулин, Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем, Изд-во СПбГУ, Санкт-Петербург, 2009.

3. Г. Л. Литвинов, А.Н. Соболевский, “Точныеинтервальные решения дискретного уравнения Беллмана и полиномиальная сложность задач идемпотентной линейной алгебры”, Доклады РАН , 374:3 (2000), 304-306, arXiv:org/abs/math.LA/0101041.

4. В.П. Маслов, “Новыйподход к обобщённым решениям нелинейных систем”, Доклады АН СССР, 292:1 (1987), 29-33.

5. В.П. Маслов, “Оновом принципе суперпозиции для задач оптимизации”, УМН, 42:3(255) (1987), 39-48.

6. В.П. Маслов, В.Н. Колокольцов, Идемпотентный анализ и его применение в оптимальном управлении, Наука, М., 1994.

7. Р. Седжвик, Алгоритмы на C++, часть 5: Алгоритмы на графах, Диасофт, Киев, 2002.

8. S. Sergeev, “Universal algorithms for generalized discrete matrix Bellman equations with symmetric Toeplitz matrix”, Tambov University Reports. Series: Natural and Technical Sciences, 16:6-2 (2011), 1751-1758, arXiv:org/abs/math/0612309.

9. С.Н. Сергеев, А.В. Чуркин, “Программадля демонстрации универсальных алгоритмов решения дискретного уравнения Беллмана в различных полукольцах”, Idempotent and tropical mathematics and problems of mathematical physics. II, Международный семинар «Idempotent and Tropical Mathematics and Problems of Mathematical Physics» (Независимый московский университет, российско-французская лаборатория «J.-V. Poncelet», Россия, 25-30 августа), Независимый московский университет, М., 2007, 107-109, arXiv: org/abs/0709.4119.

10. А.Н. Соболевский, “Интервальнаяарифметика и линейная алгебра над идемпотентными полукольцами”, Доклады РАН, 369:6 (1999), 747-749.

11. Д.К. Фаддеев, В.Н. Фаддеева, Вычислительные методы линейной алгебры, 3-е изд., Издво «Лань», Санкт-Петербург, 2002.

12. G. Alefeld and J. Herzberger, Introduction to interval computations , Academic Press, New York, 1983.

13. F.L. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Synchronization and Linearity: an Algebra for Discrete Event Systems, Wiley and Sons, 1992.

14. R.C. Backhouse, B.A. Carr´e, “Regular algebra applied to path-finding problems”, Journal of the Institute of Mathematics and its Applications, 15 (1975), 161-186.

15. W. Barth, E. Nuding, “Optimale L¨osung von Intervalgleichungsystemen”, Computing, 12 (1974), 117-125.

16. P. Butkoviˇc, Max-linear Systems: Theory and Algorithms , Springer, London, 2010.

17. P. Butkoviˇc, H. Schneider and S. Sergeev, “Z -matrix equations in max algebra, nonnegative linear algebra and other semirings”, 2011, arXiv:org/abs/1110.4564.

18. B.A. Carr´e, “An algebra for network routing problems”, Journal of the Institute of Mathematics and its Applications, 7 (1971), 273-294.

19. B.A. Carr´e, Graphs and Networks, Oxford Univ. Press, Oxford, 1979.

20. K. Cechl´arov´a and R. A. Cuninghame-Green, “Interval systems of max-separable linear equations”, Linear Algebra and its Applications, 340:1-3 (2002), 215-224.

21. R.A. Cuninghame-Green, Minimax Algebra , Lecture Notes in Economics and Mathematical Systems, 166, Springer, Berlin, 1979.

22. M. Fiedler, J. Nedoma, J. Ram´ık, J. Rohn and K. Zimmermann, Linear optimization problems with inexact data, Springer, New York, 2006.

23. J. Golan, Semirings and Their Applications, Kluwer Academic Publishers, 2000.

24. M. Gondran, “Path algebra and algorithms”, Combinatorial Programming: Methods and Applications, Proceedings of the NATO Advanced Study Institute held at the Palais des Congres (Versailles, France, 2-13 September, 1974), Reidel, Dordrecht, 1975, 137-148.

25. M. Gondran and M. Minoux, Graphs et Algorithms , ´ Editions Eylrolles, Paris, 1979.

26. M. Gondran and M. Minoux, Graphs, Dioids and Semirings, Springer, New York, 2010.

27. J. Gunawardena, Idempotency, Cambridge Univ. Press, Cambridge, 1998.

28. L. Hardouin, B. Cottenceau, M. Lhommeau, and E. Le Corronc, “Interval systems over idempotent semiring”, Linear Algebra and its Applications, 431 (2009), 855-862.

29. V. Kreinovich, A. Lakeev, J. Rohn, and P. Kahl, Computational complexity and feasibility of data processing and interval computations, Applied Optimization, Kluwer Academic Publishers, Dordrecht, 1998.

30. D.J. Lehmann, “Algebraic structures for transitive closure”, Theoretical Computer Science, 4 (1977), 59-76.

31. G. L. Litvinov, “The Maslov dequantization, idempotent and tropical mathematics: a brief introduction”, Journal of Mathematical Sciences, 141:4 (2007), 1417-1428, arXiv: org/abs/ math.GM/0507014.

32. G.L. Litvinov and V.P. Maslov, “1210-1211”, Russian Mathematical Surveys, 51 (1996).

33. G. L. Litvinov and V. P. Maslov, “The correspondence principle for idempotent calculus and some computer applications”, Idempotency, Cambridge Univ. Press, Cambridge, 1998, 420- 443, arXiv: org/abs/math.GM/0101021.

34. G.L. Litvinov and V.P. Maslov, Idempotent mathematics and mathematical physics, 307, AMS Contemporary Mathematics, Providence, 2005.

35. G. L. Litvinov, V. P. Maslov, A. Ya. Rodionov, and A. N. Sobolevski˘ı, Universal algorithms, mathematics of semirings and parallel computations, Lecture Notes in Computational Science and Engineering, 75, 2011, arXiv: org/abs/1005.1252.

36. G. L. Litvinov and E. V. Maslova, “Universal numerical algorithms and their software implementation”, Programming and Computer Software, 26:5 (2000), 275-280, arXiv: org/abs/ math.SC/0102114.

37. G.L. Litvinov, A.Ya. Rodionov and A.V. Tchourkin, “Approximate rational arithmetic and arbitrary precision computations for universal algorithms”, International Journal of Pure and Applied Mathematics, 45:2 (2008), 193-204, arXiv:org/abs/math.NA/0101152.

38. G.L. Litvinov and S.N. Sergeev, Tropical and Idempotent Mathematics, 495, AMS Contemporary Mathematics, Providence, 2009.

39. G.L. Litvinov and A.N. Sobolevski˘ı, “Idempotent interval analysis and optimization problems”, Reliable Computing, 7:5 (2001), 353-377, arXiv:org/abs/math.SC/0101080.

40. G.L. Litvinov, V.P. Maslov and A.Ya. Rodionov, “A unifying approach to software and hardware design for scientific calculations and idempotent mathematics”, 2000, arXiv: org/abs/math.SC/0101069.

41. M. Lorenz, Object oriented software: a practical guide, Prentice Hall Books, Englewood Cliffs, New Jersey, 1993.

42. G. Mikhalkin, “Tropical geometry and its applications”, Proceedings of the Madrid ICM. V.2, 2006, 827-852, arXiv:org/abs/math.AG/0601041.

43. R.E. Moore, Methods and applications of interval analysis, SIAM Studies in Applied Mathematics, SIAM, Philadelphia, 1979.

44. H. Myˇskova, “Interval systems of max-separable linear equations”, Linear Algebra and its Applications, 403 (2005), 263-272.

45. H. Myˇskova, “Control solvability of interval systems of max-separable linear equations”, Linear Algebra And Its Applications, 416:2-3 (2006), 215-223.

46. A. Neumaier, Interval methods for systems of equations , Cambridge University Press, Cambridge, 1990.

47. I. Pohl, Object-Oriented Programming Using C++, 2nd ed., Addison-Wesley, Reading, 1997.

48. G. Rote, “A systolic array algorithm for the algebraic path problem”, Computing, 34 (1985), 191-219.

49. S. Sergeev, “Max-algebraic attraction cones of nonnegative irreducible matrices”, Linear Algebra And Its Applications, 435:7 (2011), 1736-1757, arXiv:org/abs/math.AG/0903.3960.

50. S. Sergeev and H. Schneider, “CSR expansions of matrix powersin max algebra”, Transactions of Amer. Math. Soc., 364 (2012), 5969-5994, arXiv:org/abs/math.AG/0912.2534.

51. I. Simon, “Recognizable sets with multiplicities in the tropical semiring”, Lecture Notes in Computer Science, 324 (1988), 107-120.

52. A. Stepanov and M. Lee, The Standard Template Library, Hewlett-Packard Company, Palo Alto, 1994.

53. O. Viro, “Dequantization of real algebraic geometry on logarithmic paper”, European Congress of Mathematics, European Congress of Mathematics (Barcelona, 2000, July 10-14), Progress in Mathematics, Birkh¨auser, Basel, 135-146, arXiv:org/abs/math/0005163.

54. O. Viro, “From the sixteenth Hilbert problem to tropical geometry”, Japanese Journal of Mathematics, 3:2 (2008), 185-214.

55. V.V. Voevodin, Mathematical Foundations of Parallel Computings, World Scientific Publ. Co., Singapore, 1992.