Solving tied interval linear systems

S. P. Shary

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 7 (2004) no. 4, pp. 363-376.

Résumé

This paper presents a survey of modern techniques for enclosing the solution sets to interval linear systems whose parameters are subject to additional ties. For optimal (exact) component-wise estimation of the solution sets to interval linear systems with symmetric, persymmetric, Hankel and Toeplitz matrices, we develop socalled parameter partitioning methods (PPS-methods) based on adaptive partitioning of the interval initial data of the problem under consideration.

Bibliographie

[1] Alefeld G., Khertsberger Yu., Vvedenie v intervalnye vychisleniya, Mir, M., 1987 | MR

[2] Arnold V. I., Geometricheskie metody v teorii obyknovennykh differentsialnykh uravnenii, Regulyarnaya i khaoticheskaya dinamika, Izhevsk–Moskva, 2000

[3] Kalmykov S. A., Shokin Yu. I., Yuldashev Z. X., Metody intervalnogo analiza, Nauka, Novosibirsk, 1986 | MR | Zbl

[4] Papadimitriu X., Staiglits K., Kombinatornaya optimizatsiya. Algoritmy i slozhnost, Mir, M., 1985 | MR

[5] Sharyi S. P., “Novyi klass algoritmov dlya optimalnogo resheniya intervalnykh lineinykh sistem”, Konferentsiya “Aktualnye problemy prikladnoi matematiki” (Saratov, 20–22 maya 1991 g.), Saratov, 1991, 113–119

[6] Sharyi S. P., “Algebraicheskii podkhod vo “vneshnei zadache” dlya intervalnykh lineinykh sistem”, Vychislitelnye Tekhnologii, 3:2 (1998), 67–114 | MR

[7] Sharyi S. P., “Optimalnoe vneshnee otsenivanie mnozhestv reshenii intervalnykh sistem uravnenii. Chast 1”, Vychislitelnye Tekhnologii, 7:6 (2002), 90–113 ; Часть 2, Вычислительные Технологии, 8:1 (2003), 84–109 | MR | MR

[8] Alefeld G., Kreinovich V., Mayer G., “Symmetric linear systems with perturbed input data”, Numerical Methods and Error Bounds, eds. G. Alefeld and J. Herzberger, Akademie Verlag, Berlin, 1996, 16–22 | MR | Zbl

[9] Alefeld G., Kreinovich V., Mayer G., “The shape of the symmetric solution set”, Applications of Interval Computations, eds. R. B. Kearfott and V. Kreinovich, Kluwer, Dordrecht, 1996, 61–79 | MR | Zbl

[10] Alefeld G., Kreinovich V., Mayer G., “On the shape of the symmetric, persymmetric, and skew-symmetric solution set”, SIAM J. Matrix Anal. Appl., 18 (1997), 693–705 | DOI | MR | Zbl

[11] Alefeld G., Kreinovich V., Mayer G., “The shape of the solution set for systems of interval linear equations with dependent coefficients”, Mathematische Nachrichten, 192 (1998), 23–36 | DOI | MR | Zbl

[12] Alefeld G., Kreinovich V., Mayer G., “A comment on the shape of the solution set for systems of interval linear equations with dependent coefficients”, Reliable Computing, 7:3 (2001), 275–277 | DOI | MR | Zbl

[13] Alefeld G., Kreinovich V., Mayer G., “On symmetric solution sets”, Inclusion methods for nonlinear problems with applications in engineering, economics and physics, Computing Supplement, 16, ed. J. Herzberger, Springer, Wien – New York, 2003, 1–23 | MR

[14] Alefeld G., Kreinovich V., Mayer G., “On the solution sets of particular classes of linear interval systems”, J. of Comput. and Appl. Math., 152:1–2 (2003), 1–15 ; http://www.cs.utep.edu/vladik/1996/abstr96.html | DOI | MR | Zbl

[15] Alefeld G., Mayer G., “The Cholesky method for interval data”, Linear Algebra and its Applications, 194 (1993), 161–182 | DOI | MR | Zbl

[16] Gay D. M., “Solving interval linear equations”, SIAM J. Numer. Analysis, 19:4 (1982), 858–870 | DOI | MR | Zbl

[17] Jansson Ch., “Interval linear systems with symmetric matrices, skew-symmetric matrices, and dependencies in the right hand side”, Computing, 46 (1991), 265–274 | DOI | MR | Zbl

[18] Hansen E., Global optimization using interval analysis, Marcel Dekker, New York, 1992 | MR | Zbl

[19] Kearfott R. B., Rigorous global search: Continuous problems, Kluwer, Dordrecht, 1996 | MR

[20] Kearfott R. B., Kreinovich V., “Where to bisect a box? A theoretical explanation of the experimental results”, Interval Computations and its Applications to Reasoning Under Uncertainty, Knowledge Representation, and Control Theory, Proceedings of MEXICON'98, Workshop on Interval Computations, 4th World Congress on Expert Systems (Mexico City, Mexico, 1998), eds. G. Alefeld and R. A. Trejo

[21] Kearfott R. B., Nakao M. T., Neumaier A., Rump S. M., Shary S. P., van Hentenryck P., “Standardized notation in interval analysis”, Reliable Computing (to appear)

[22] Neumaier A., Interval methods for systems of equations, Cambridge University Press, Cambridge, 1990 | MR | Zbl

[23] Ratz D., Automatische Ergebnisverifikation bei globalen Optimierungsproblemen, Ph.D. Dissertation, Karlsruhe, Universitat, 1992

[24] Ratz D., “Box-splitting strategies for the interval Gauss-Seidel step in a global optimization method”, Computing, 53 (1994), 337–354 | DOI | MR

[25] Rohn J., “Cheap and tight bounds: the recent result by E. Hansen can be made more efficient”, Interval Computations, 4 (1993), 13–21 | MR | Zbl

[26] Shary S. P., “A new class of algorithms for optimal solution of interval linear systems”, Interval Computations, 2(4) (1992), 18–29 | MR | Zbl