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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:56279", author = "Milan Hladik", title = "A Contractor for the Symmetric Solution Set", 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.", volume = "4", number = "11", pages = "1426-6", }
