DOI: 10.17587/prin.17.580-590

Extreme Matrices Method for Outer Estimation of the Solution Set to Interval Systems of Linear Algebraic Equations

K. F. Ivanova, Postdoctorant, klara.i2010@yandex.ru, Saint Petersburg State University, Saint Petersburg 195252, Russian Federation

Corresponding author: Klara F. Ivanova, Postdoctorant, Saint Petersburg State University, Saint Petersburg, 195252, Russian Federation, E-mail: klara.i2010@yandex.ru

A specialized new heuristic method is proposed for the outer estimation of the united solution set of an interval system of linear algebraic equations (ISLAE). The Method of Extreme Matrices (MEM) is based on vertex realizations of interval matrices formalized from products of matrix elements and their cofactors. The conditions for the emergence of a bounded subset of extreme matrices possessing identical characteristics are established. Based on the constructed matrices, optimal right-hand side vectors are determined. Solving the resulting real-valued systems of equations enables the determination of the maximal coordinates of the deviation polyhedron of unknowns in the space Rn, which define the outer estimation of the ISLAE solution set. A theoretical justification of the method is provided, and the theorem on the existence of extreme matrices is proven. Classes of ISLAEs adapted for the proposed study are identified. The efficiency of the method is achieved through a substantial reduction in the number of algebraic equations required for computing outer estimations of the ISLAE solution set, replacing the solution of an exponentially complex problem O(2n2) with a polynomial-complexity problem O(n3). The influence of structural properties of matrices belonging to specific subclasses of interval systems on the obtained solution estimates is demonstrated. The accuracy of MEM interval estimates is compared with the results of software implementations of interval methods using the functions of the IntvalPy library. The method does not guarantee high accuracy, but it allows comparable estimates to be obtained for different classes for interval linear algebraic systems in comparison with key interval method. Conservative MEM estimates may be used as baseline approximations for further refinement by exact methods.

Keywords: outer estimation, heuristic method, extreme vertex matrices, deviation polyhedron, bounded subset, theoretical justification, classes of ISLAEs, componentwise estimates, polynomial complexity

pp. 580—590

For citation:
Ivanova K. F. Extreme Matrices Method for Outer Estimation of the Solution Set to Interval Systems of Linear Algebraic Equations, Programmnaya Ingeneria, 2026, vol. 17, no. 10, pp. 580—590. DOI: 10.17587/prin.17.580-590 (in Russian).

References:

1. Bazhenov A. N., Zhilin S. I., Kumkov S. I., Shary S. P. Processing and analysis of interval data, Moscow; Izhevsk, Institut komp'yuternyh issledovanij, 2024, 356 p. (in Russian).
2. Kinsht N. V., Petrunko N. N. Current Lines of Formalization of the Problems of Interval Analysis of Electrical Circuits, Informatika i sistemy upravleniya, 2011, no. 3 (29), pp. 9—17 (in Russian).
3. Ivanova K. F. On one algebraic way of determining the stability of linear continuous control systems with interval coefficients, Izvestiya vysshih uchebnyh zavedenij. Priborostroenie, 2018, no. 1, pp. 12—22 (in Russian).
4. Ivanova K. F. Modal Control for Systems with Limited Parameter Interval, Izvestiya vysshih uchebnyh zavedenij. Priborostroenie, 2018, no. 3, pp. 210—218 (in Russian).
5. Shary S. P. Finite-Dimensional Interval Analysis, Novosibirsk, Novosibirsk State University, 2018, 644 p. (in Russian).
6. Neumaier A. Interval Methods for Systems of Equations, Cambridge, Cambridg University Press, 1990, 255 p.
7. Rohn J. Enclosing solutions of overdetermined systems of linear interval equations, Reliable Computing, 1996, vol. 2, pp. 167—171. DOI: 10.1007/BF02425920.
8. Kearfott R. B., Hu C., Novoa III M. A review of preconditioned for the interval Gauss-Seidel method, Interval Computations, 1991, vol. 1, pp. 59—85.
9. Hansen E., Bliek C. Bounding the Solution of Interval Linear Equations, SIAM Journal on Numerical Analysis, 1992, vol. 29, no. 5, pp. 1493—1503. DOI: 10.1137/0729086.
10. Sharaya I. A. The Boundary Interval Method for Visualizing Polyhedral Solution Sets, Vychislitel'nye Tekhnologii, 2015, vol. 20, no. 1, pp. 75—103 (in Russian).
11. Androsov A. S., Shary S. P. IntvalPy — A Python Interval Computation Library, Vestnik NGU. Ser.: Informacionnye tekhnologii, 2022, vol. 20, no. 4, pp. 5—23. DOI: 10.25205/1818-7900-2022-20­4-5-23 (in Russian).