A Contractor for the Symmetric Solution Set

Authors: Milan Hladik

Abstract:

The symmetric solution set Σ sym is the set of all solutions to the linear systems Ax = b, where A is symmetric and lies between some given bounds A and A, and b lies between b and b. We present a contractor for Σ sym, which is an iterative method that starts with some initial enclosure of Σ sym (by means of a cartesian product of intervals) and sequentially makes the enclosure tighter. Our contractor is based on polyhedral approximation and solving a series of linear programs. Even though it does not converge to the optimal bounds in general, it may significantly reduce the overestimation. The efficiency is discussed by a number of numerical experiments.

Keywords: Linear interval systems, solution set, interval matrix, symmetric matrix.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333366

References:

[1] C. S. Adjiman, S. Dallwig, C. A. Floudas, and A. Neumaier. A global optimization method, ╬▒BB, for general twice-differentiable constrained NLPs - I. Theoretical advances. Comput. Chem. Eng., 22(9):1137-1158, 1998.
[2] G. Alefeld and J. Herzberger. Introduction to interval computations. Computer Science and Applied Mathematics. Academic Press, New York, 1983.
[3] G. Alefeld, V. Kreinovich, and G. Mayer. On the shape of the symmetric, persymmetric, and skew-symmetric solution set. SIAM J. Matrix Anal. Appl., 18(3):693-705, 1997.
[4] G. Alefeld, V. Kreinovich, and G. Mayer. The shape of the solution set for systems of interval linear equations with dependent coefficients. Math. Nachr., 192:23-36, 1998.
[5] G. Alefeld, V. Kreinovich, and G. Mayer. On the solution sets of particular classes of linear interval systems. J. Comput. Appl. Math., 152(1-2):1-15, 2003.
[6] G. Alefeld and G. Mayer. The cholesky method for interval data. Linear Algebra Appl., 194:161-182, 1993.
[7] G. Alefeld and G. Mayer. On the symmetric and unsymmetric solution set of interval systems. SIAM J. Matrix Anal. Appl., 16(4):1223-1240, 1995.
[8] G. Alefeld and G. Mayer. New criteria for the feasibility of the cholesky method with interval data. SIAM J. Matrix Anal. Appl., 30(4):1392- 1405, 2008.
[9] R. Araiza, G. Xiang, O. Kosheleva, and D. ˇ Skulj. Under interval and fuzzy uncertainty, symmetric markov chains are more difficult to predict. In M. Reformat and M. R. Berthold, editors, Proceedings of the 26th International Conference of the North American Fuzzy Information Processing Society NAFIPS-2007, pages 526-531, San Diego, California, 2007.
[10] O. Beaumont. Solving interval linear systems with linear programming techniques. Linear Algebra Appl., 281(1-3):293-309, 1998.
[11] A. Dreyer. Interval analysis of linear analog circuits. In Proceedings of the 12th GAMM-IMACS Symposium on Scientific Computing, Computer Artithmetic and Validated Numerics, SCAN 2006., page 14, Los Alamitos, CA, USA, 2007. IEEE Computer Society.
[12] M. Fiedler, J. Nedoma, J. Ram'─▒k, J. Rohn, and K. Zimmermann. Linear optimization problems with inexact data. Springer, New York, 2006.
[13] M. Hlad'─▒k. Description of symmetric and skew-symmetric solution set. SIAM J. Matrix Anal. Appl., 30(2):509-521, 2008.
[14] M. Hlad'─▒k, D. Daney, and E. Tsigaridas. An algorithm for the real interval eigenvalue problem. Research Report RR-6680, INRIA, France, October 2008. http://hal.inria.fr/inria-00329714/en/.
[15] C. Jansson. Interval linear systems with symmetric matrices, skewsymmetric matrices and dependencies in the right hand side. Comput., 46(3):265-274, 1991.
[16] L. V. Kolev. An improved interval linearization for solving nonlinear problems. Numer. Algorithms, 37(1-4):213-224, 2004.
[17] L. V. Kolev. Improvement of a direct method for outer solution of linear parametric systems. Reliab. Comput., 12(3):193-202, 2006.
[18] Z. Kulpa, A. Pownuk, and I. Skalna. Analysis of linear mechanical structures with uncertainties by means of interval methods. Comput. Assist. Mech. Eng. Sci., 5(4):443-477, 1998.
[19] A. Neumaier. Interval methods for systems of equations. Cambridge University Press, Cambridge, 1990.
[20] E. D. Popova. Parametric interval linear solver. Numer. Algorithms, 37(1-4):345-356, 2004.
[21] E. D. Popova. Solving linear systems whose input data are rational functions of interval parameters. Lecture Notes in Computer Science, 4310:345-352, 2007.
[22] E. D. Popova and W. Kr¨amer. Inner and outer bounds for the solution set of parametric linear systems. J. Comput. Appl. Math., 199(2):310-316, 2007.
[23] J. Rohn. Systems of linear interval equations. Linear Algebra Appl., 126(C):39-78, 1989.
[24] J. Rohn. VERSOFT: Verification software in MATLAB / INTLAB, version 10, 2009. http://uivtx.cs.cas.cz/˜rohn/matlab/.
[25] S. M. Rump. Verification methods for dense and sparse systems of equations. In J. Herzberger, editor, Topics in Validated Computations, Studies in Computational Mathematics, pages 63-136, Amsterdam, 1994. Elsevier. Proceedings of the IMACS-GAMM International Workshop on Validated Computations, University of Oldenburg.
[26] S. M. Rump. Intlab - interval laboratory, the matlab toolbox for verified computations, version 5.3, 2006. http://www.ti3.tuharburg. de/rump/intlab/.
[27] U. Sch¨afer. Two ways to extend the Cholesky decomposition to block matrices with interval entries. Reliab. Comput., 8(1):1-20, 2002.
[28] U. Sch¨afer. Aspects for a block version of the interval Cholesky algorithm. J. Comput. Appl. Math., 152(1-2):481-491, 2003.
[29] C.-J. R. Shi and M. W. Tian. Simulation and sensitivity of linear analog circuits under parameter variations by robust interval analysis. ACM Transactions on Design Automation of Electronic Systems, 4(3):280- 312, 1999.