PC-solutions and quasi-solutions of the interval system of linear algebraic equations

S. I. Noskov ; A.V.Lakeev

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 17 (2021) no. 3, pp. 262-276

Résumé

The problem of solving the interval system of linear algebraic equations (ISLAEs) is one of the well-known problems of interval analysis, which is currently undergoing intensive development. In general, this solution represents a set, which may be given differently, depending on which quantifiers are related to the elements of the left and right sides of this system. Each set of solutions of ISLAE to be determined is described by the domain of compatibility of the corresponding system of linear inequalities and, normally, one nonlinear condition of the type of complementarity. It is difficult to work with them when solving specific problems. Therefore, in the case of nonemptiness in the process of solving the problem it is recommended to find a so-called PC-solution, based on the application of the technique known in the theory of multi-criterial choice, that presumes maximization of the solving capacity of the system of inequalities. If this set is empty, it is recommended to find a quasi-solution of ISLAE. The authors compare the approach proposed for finding PC- and/or quasi-solutions to the approach proposed by S. P. Shary, which is based on the application of the recognizing functional.

Détail

Keywords: interval system of linear algebraic equations, recognizing functional, problem of linear programming.
Mots-clés : AE-solutions, РС-solution, quasi-solution

Bibliographie

[1] Kearfott R. B., Nakao M. T., Neumaier A., Rump S. M., Shary S. P., Hentenryck P., “Standardized notation in interval analysis”, Computational Technologies, 15:1 (2010), 7–13 (accessed: June 27, 2021) | Zbl

[2] Shary S. P., Finite-dimensional interval analysis, XYZ Publ, Novosibirsk, 2020, 643 pp. (In Russian) (accessed: June 27, 2021)

[3] Shary S. P., “Algebraic solutions to interval linear equations and their applications”, Numerical Methods and Error Bounds, Proceedings of IMACS-GAMM International Symposium on Numerical Methods and Error Bounds (Oldenburg, Germany, July 9–12, 1995), Mathematical Research, 89, eds. G. Alefeld, J. Herzberger, Akademie Verlag, Berlin, 1996, 224–233 (accessed: June 27, 2021) http://interval.ict.nsc.ru/shary/Papers/Herz.pdf | Zbl

[4] Shary S. P., “Outer estimation of generalized solution sets to interval linear systems”, Reliable Computing, 5 (1999), 323–335 (accessed: June 27, 2021) http://interval.ict.nsc.ru/shary/Papers/GOuter.pdf | DOI

[5] Shary S. P., “External assessment of generlized sets of solutions of interval linear systems”, Computational Terchnologies, 4:4 (1999), 82–110 (In Russian) | Zbl

[6] Oettli W., Prager W., “Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides”, Num. Math., 6 (1964), 405–409 | DOI | Zbl

[7] Oettli W., “On the solution set of a linear system with inacurate coefficients”, SIAM J. Numer. Anal., 2 (1965), 115–118 | Zbl

[8] Beeck H., “Über structur und abschatzungen der loesungsmenge von linear gleichungssystemen mit intervall koeffizienten”, Computing, 10 (1972), 231–244 | DOI | Zbl

[9] Rohn J., “Interval linear systems”, Freiburger Intervall-Berichte, 84, no. 7, Albert-Ludwigs-Universitaet, Freiburg, 1984, 33–58

[10] Shary S. P., On characterization of an integrated set of solutions of an interval linear algebraic system, Deposited in VINITI No 726-B91, 1990, 20 pp. (In Russian)

[11] Nuding E., Wilhelm J., “Über Gleichungen und über Lösungen”, Zeitschrift für Angewandte Mathematik und Mechanik, 52 (1972), T188–T190 | Zbl

[12] Rohn J., “Inner solutions of linear interval systems”, Interval Mathematics (1985), Lecture Notes in Computer Science, 212, Springer-Verlag, Berlin–Heidelberg, 1986, 157–158 | DOI

[13] Deif A., Sensitivety analysis in linear systems, Springer-Verlag, Berlin–Heidelberg, 1986, 224 pp.

[14] Neumaier A., “Tolerance analysis with interval arithmetic”, Freiburger Intervall-Berichte, 86, no. 9, Albert-Ludwigs-Universität, Freiburg, 1986, 5–19

[15] Shaidurov V. V., Shary S. P., Solving an interval algebraic problem of tolerances, Preprint of the Computing Center of USSR Acad. Sci. No 5, Acad. Sci. of USSR Press, Krasnoyarsk, 1988, 27 pp. (In Russian)

[16] Shary S. P. On solvability of the linear problem of tolerances, Interval Computations, 1991, no. 1, 92–98 (In Russian)

[17] Khlebalin N. A., Shokin Yu. I., “The interval variant of the method of modal control”, USSR Mathematical Papers, 316:4 (1991), 846–850 (In Russian) | Zbl

[18] Lakeyev A. V., Noskov S. I., “Description of sets of solutions of linear interval equation in the ordered set”, Proceedings of the International conference on interval and stochastic methods in science and engineering, INTERVAL-92 (September 22–26), v. 1, Moscow Energy Institute Publ, M., 1992, 87–89 (In Russian)

[19] Shary S. P., “On controlled solution set of interval algebraic systems”, Interval Computations, 4:6 (1992), 66–75 | Zbl

[20] Shary S. P., “Controllable solution sets to interval static systems”, Applied Mathematics and Computation, 86:2–3 (1997), 185–196 | DOI | Zbl

[21] Rohn J., E-mail letter to S. P. Shary and A. V. Lakeyev of November 18 1995 (accessed: June 27, 2021) http://www.cs.cas.cz/r̃ohn/publist/LettShaLak.ps

[22] Rohn J., $(Z,z)$-solutions, technical report No 1159, Institute of Computer Science. Academy of Sciences of the Czech Republic, Prague, 2012, 3 pp. (accessed: June 27, 2021) http://uivtx.cs.cas.cz/r̃ohn/publist/zzsols.pdf

[23] Lakeyev A. V., “Computational complexity of estimation of generalized solution sets for interval linear systems”, Computational Terchnologies, 8:1 (2003), 12–23 | Zbl

[24] Khachiyan L. G., “Polynomial algorithms in linear programming”, Journal of Computational Mathematics and Mathematical Physics, 20:1 (1980), 51–68 (In Russian) | Zbl

[25] Karmarkar N., “A new polynomial-time algorithm for linear programming”, Combinatorica, 4 (1984), 373–395 | DOI | Zbl

[26] Lakeyev A. V., Noskov S. I., “Description of a set of solutions for a linear equation with an interval given operator and a right-hand side”, USSR Mathematical Papers, 330:4 (1993), 430–433 (In Russian) | Zbl

[27] Lakeyev A. V., Noskov S. I., “On a set of solutions of a linear equation with an interval given operator and the right-hand side”, Siberian Mathematical Journal, 35:5 (1994), 1074–1084 (In Russian) | Zbl

[28] Lakeyev A. V., “On the computational complexity of the solution of linear systems with moduli”, Reliable Computing, 2:2 (1996), 125–131 | DOI | Zbl

[29] Noskov S. I., A technology of modeling objects with unstable functioning and uncertainty in data, Oblformpechat Press, Irkutsk, 1996, 320 pp. (In Russian) (accessed: June 27, 2021)

[30] Noskov S. I., “Pointwise characterization of the sets of solutions of interval systems of linear algebraic equations”, Information Technologies and Mathematical Modeling in Control of Complex Systems, 2018, no. 1(1), 8–13 (In Russian)

[31] Vassilyev S. N., Seledkin A. P., “Synthesis of the function of efficiency in multi-criterion problems of decision making”, Proceedings of USSR Academy of Sciences. Technical Cybernetics, 1980, no. 3, 186–190 (In Russian)

[32] Noskov S. I., Protopopov V. A., “Assessment of the level of vulnerability of the objects of transport infrastructure: A formalized approach”, Contemporary Technologies. Systems Analysis. Modeling, 2011, no. 4 (32), 241–244 (In Russian)

[33] Cottle R. W., Pang J. H., Stone R. E., The linear complementarity problem, Academic Press, Boston, 1992, 761 pp. | Zbl

[34] Tikhonov A. N., Arsenin V. Ya., Methods for solving incorrect problems, Nauka Publ, M., 1986, 288 pp. (In Russian)

[35] Tikhonov A. N., Goncharskij A. V., Stepanov V. V., Yagola A. G., Regulating algorithms and a priori information, Nauka Publ, M., 1983, 200 pp. (In Russian)

[36] Shary S. P., On some methods of solving the linear problem of tolerances, Preprint of the Computing Center of USSR Acad. Sci., No 6, USSR Acad. Sci. Publ., Krasnoyarsk, 1989, 45 pp. (In Russian)

[37] Shary S. P., “Solution of the linear problem of tolerances”, Automatics and Telemechanics, 2004, no. 10, 147–162 (In Russian) | Zbl

[38] Shary S. P., Sharaya I. A., “Recognition of solvability of interval equations and its applications to data analysis”, Computational Technologies, 18:3 (2013), 80–109 (In Russian) | Zbl

[39] Sharaya I. A., Shary S. P., “Reserve of characteristic inclusion as recognizing functional for interval linear systems”, Scientific Computing, Computer Arithmetic, and Validated Numerics, 16th International Symposium (SCAN 2014), Revised selected papers (Würzburg, Germany, September 21–26, 2014), eds. M. Nehmeier, J. W. von Gudenberg, W. Tucker, Springer, Heidelberg, 2016, 148–167 | DOI | Zbl

[40] Shary S. P., “Strong consistency in the problem of restoration of dependencies under interval data uncertainty”, Computational Technologies, 22:2 (2017), 150–172 (In Russian) | Zbl

[41] Vulikh B. Z., Introduction to the theory of semi-ordered spaces, GIFML Press, M., 1961, 407 pp. (In Russian)

[42] Rohn J., “Systems of linear interval equations”, Linear Algebra and its Applications, 126 (1989), 39–78 | DOI | Zbl

[43] Barth W., Nuding E., “Optimale Lösung von Intervallgleichungssystemen”, Computing, 12:2 (1974), 117–125 | DOI | Zbl

[44] Hansen E., “On linear algebraic equations with interval coefficients”, Topics in Interval Analysis, ed. E. Hansen, Oxford University Press, Oxford, 1969, 33–46

[45] Rockafellar R., Convex analysis, Mir Publ, M., 1973, 469 pp. (In Russian)