Enclosures for the solution set of parametric interval linear systems

Milan Hladík

International Journal of Applied Mathematics and Computer Science, Tome 22 (2012), p. 561-574 / Harvested from The Polish Digital Mathematics Library

Résumé

We investigate parametric interval linear systems of equations. The main result is a generalization of the Bauer-Skeel and the Hansen-Bliek-Rohn bounds for this case, comparing and refinement of both. We show that the latter bounds are not provable better, and that they are also sometimes too pessimistic. The presented form of both methods is suitable for combining them into one to get a more efficient algorithm. Some numerical experiments are carried out to illustrate performances of the methods.

Détail

Publié le : 2012-01-01

Zbl 1310.65051

EUDML-ID : urn:eudml:doc:244064

Bibliographie

[000] Alefeld, G., Kreinovich, V. and Mayer, G. (1997). On the shape of the symmetric, persymmetric, and skew-symmetric solution set, SIAM Journal on Matrix Analysis and Applications 18(3): 693-705. | Zbl 0873.15003

[001] Alefeld, G., Kreinovich, V. and Mayer, G. (2003). On the solution sets of particular classes of linear interval systems, Journal of Computational and Applied Mathematics 152(1-2): 1-15. | Zbl 1019.65023

[002] Alefeld, G. and Mayer, G. (1993). The Cholesky method for interval data, Linear Algebra and Its Applications 194: 161-182. | Zbl 0796.65032

[003] Alefeld, G. and Mayer, G. (2008). New criteria for the feasibility of the Cholesky method with interval data, SIAM Journal on Matrix Analysis and Applications 30(4): 1392-1405. | Zbl 1176.65023

[004] Beeck, H. (1975). Zur Problematik der Hüllenbestimmung von Intervallgleichungssystem en, in K. Nickel (Ed.), Interval Mathematics: Proceedings of the International Symposium on Interval Mathematics, Lecture Notes in Computer Science, Vol. 29, Springer, Berlin, pp. 150-159. | Zbl 0303.65025

[005] Busłowicz, M. (2010). Robust stability of positive continuoustime linear systems with delays, International Journal of Applied Mathematics and Computer Science 20(4): 665-670, DOI: 10.2478/v10006-010-0049-8. | Zbl 1214.93076

[006] Fiedler, M., Nedoma, J., Ramík, J., Rohn, J. and Zimmermann, K. (2006). Linear Optimization Problems with Inexact Data, Springer, New York, NY. | Zbl 1106.90051

[007] Garloff, J. (2010). Pivot tightening for the interval Cholesky method, Proceedings in Applied Mathematics and Mechanics 10(1): 549-550.

[008] Hladík, M. (2008). Description of symmetric and skewsymmetric solution set, SIAM Journal on Matrix Analysis and Applications 30(2): 509-521. | Zbl 1165.65025

[009] Horn, R.A. and Johnson, C.R. (1985). Matrix Analysis, Cambridge University Press, Cambridge. | Zbl 0576.15001

[010] Jansson, C. (1991). Interval linear systems with symmetric matrices, skew-symmetric matrices and dependencies in the right hand side, Computing 46(3): 265-274. | Zbl 0729.65016

[011] Kolev, L.V. (2004). A method for outer interval solution of linear parametric systems, Reliable Computing 10(3): 227-239. | Zbl 1055.65045

[012] Kolev, L.V. (2006). Improvement of a direct method for outer solution of linear parametric systems, Reliable Computing 12(3): 193-202. | Zbl 1094.65022

[013] Merlet, J.-P. (2009). Interval analysis for certified numerical solution of problems in robotics, International Journal of Applied Mathematics and Computer Science 19(3): 399-412, DOI: 10.2478/v10006-009-0033-3. | Zbl 1300.93120

[014] Meyer, C.D. (2000). Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, PA.

[015] Neumaier, A. (1990). Interval Methods for Systems of Equations, Cambridge University Press, Cambridge. | Zbl 0715.65030

[016] Neumaier, A. (1999). A simple derivation of the Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations, Reliable Computing 5(2): 131-136. | Zbl 0936.65055

[017] Neumaier, A. and Pownuk, A. (2007). Linear systems with large uncertainties, with applications to truss structures, Reliable Computing 13(2): 149-172. | Zbl 1117.65063

[018] Ning, S. and Kearfott, R.B. (1997). A comparison of some methods for solving linear interval equations, SIAM Journal on Numerical Analysis 34(4): 1289-1305. | Zbl 0889.65022

[019] Padberg, M. (1999). Linear Optimization and Extensions, 2nd Edn., Springer, Berlin. | Zbl 0926.90068

[020] Popova, E. (2002). Quality of the solution sets of parameterdependent interval linear systems, Zeitschrift für Angewandte Mathematik und Mechanik 82(10): 723-727. | Zbl 1013.65042

[021] Popova, E.D. (2001). On the solution of parametrised linear systems, in W. Krämer and J.W. von Gudenberg (Eds.), Scientific Computing, Validated Numerics, Interval Methods, Kluwer, London, pp. 127-138.

[022] Popova, E.D. (2004a). Parametric interval linear solver, Numerical Algorithms 37(1-4): 345-356. | Zbl 1074.65044

[023] Popova, E.D. (2004b). Strong regularity of parametric interval matrices, in I. Dimovski (Ed.), Mathematics and Education in Mathematics, Proceedings of the 33rd Spring Conference of the Union of Bulgarian Mathematicians, Borovets, Bulgaria, BAS, Sofia, pp. 446-451.

[024] Popova, E.D. (2006a). Computer-assisted proofs in solving linear parametric problems, 12th GAMM/IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, SCAN 2006, Duisburg, Germany, p. 35.

[025] Popova, E.D. (2006b). Webcomputing service framework, International Journal Information Theories & Applications 13(3): 246-254.

[026] Popova, E.D. (2009). Explicit characterization of a class of parametric solution sets, Comptes Rendus de L'Academie Bulgare des Sciences 62(10): 1207-1216. | Zbl 1199.15013

[027] Popova, E.D. and Krämer, W. (2007). Inner and outer bounds for the solution set of parametric linear systems, Journal of Computational and Applied Mathematics 199(2): 310-316. | Zbl 1108.65027

[028] Popova, E.D. and Krämer, W. (2008). Visualizing parametric solution sets, BIT Numerical Mathematics 48(1): 95-115. | Zbl 1144.65031

[029] Rex, G. and Rohn, J. (1998). Sufficient conditions for regularity and singularity of interval matrices, SIAM Journal on Matrix Analysis and Applications 20(2): 437-445. | Zbl 0924.15003

[030] Rohn, J. (1989). Systems of linear interval equations, Linear Algebra and Its Applications 126(C): 39-78. | Zbl 0712.65029

[031] Rohn, J. (1993). Cheap and tight bounds: The recent result by E. Hansen can be made more efficient, Interval Computations (4): 13-21. | Zbl 0830.65019

[032] Rohn, J. (2004). A method for handling dependent data in interval linear systems, Technical Report 911, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, http://uivtx.cs.cas.cz/˜rohn/publist/rp911.ps.

[033] Rohn, J. (2010). An improvement of the Bauer-Skeel bounds, Technical Report V-1065, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, http://uivtx.cs.cas.cz/˜rohn/publist/bauerskeel.pdf.

[034] Rump, S.M. (1983). Solving algebraic problems with high accuracy, in U. Kulisch and W. Miranker (Eds.), A New Approach to Scientific Computation, Academic Press, New York, NY, pp. 51-120.

[035] Rump, S.M. (1994). Verification methods for dense and sparse systems of equations, in J. Herzberger (Ed.), Topics in Validated Computations, Studies in Computational Mathematics, Elsevier, Amsterdam, pp. 63-136. | Zbl 0813.65072

[036] Rump, S.M. (2006). INTLAB-Interval Laboratory, the Matlab toolbox for verified computations, Version 5.3. http://www.ti3.tu-harburg.de/rump/intlab/.

[037] Rump, S.M. (2010). Verification methods: Rigorous results using floating-point arithmetic, Acta Numerica 19: 287-449. | Zbl 1323.65046

[038] Schrijver, A. (1998). Theory of Linear and Integer Programming, Reprint Edn., Wiley, Chichester. | Zbl 0970.90052

[039] Skalna, I. (2006). A method for outer interval solution of systems of linear equations depending linearly on interval parameters, Reliable Computing 12(2): 107-120. | Zbl 1085.65039

[040] Skalna, I. (2008). On checking the monotonicity of parametric interval solution of linear structural systems, in R. Wyrzykowski, J. Dangarra, K. Karczewski and J. Wasniewski (Eds.), Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, Vol. 4967, Springer-Verlag, Berlin/Heidelberg, pp. 1400-1409.

[041] Stewart, G. W. (1998). Matrix Algorithms, Vol. 1: Basic Decompositions, SIAM, Philadelphia, PA. | Zbl 0910.65012