Algebraic approach in the ``outer problem'' for interval linear systems

S. P. Shary

Fundamentalʹnaâ i prikladnaâ matematika, Tome 8 (2002) no. 2, pp. 567-610.

Résumé

The subject of our work is the classical “outer” problem for the interval linear algebraic system $\mathbf{A}x=\mathbf{b}$ with the interval matrix $\mathbf{A}$ and right-hand side vector $\mathbf{b}$: find “outer” coordinate-wise estimates of the solution set formed by all solutions to the point systems $Ax=b$ with $A\in\mathbf{A}$ and $b\in\mathbf{b}$. The purpose of this work is to propose a new algebraic approach to the above problem, in which it reduces to solving one point (noninterval) equation in the Euclidean space of the double dimension. We construct a specialized algorithm (subdifferential Newton method) that implements the new approach, present results of its numerical tests. They demonstrate that the algebraic approach combines exclusive computational efficacy with high quality enclosures of the solution set.

Bibliographie

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

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

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

[4] Dobronets B. S., Shaidurov V. V., Dvustoronnie chislennye metody, Nauka, Novosibirsk, 1990 | MR | Zbl

[5] Shary S. P., “On optimal solution of interval linear equations”, SIAM J. Numer. Anal., 32 (1995), 610–630 | DOI | MR | Zbl

[6] Ning S., Kearfott R. B., “A comparison of some methods for solving linear interval equations”, SIAM J. Numer. Anal., 34 (1997) | DOI | MR | Zbl

[7] Shary S. P., “Algebraic approach to the interval linear static identification, tolerance and control problems, or One more application of Kaucher arithmetic”, Reliable Computing, 2:1 (1996), 3–33 | DOI | MR | Zbl

[8] Shary S. P., “Algebraic solutions to interval linear equations and their applications”, Numerical Methods and Error Bounds, eds. G. Alefeld and J. Herzberger, Akademie Verlag, Berlin, 1996, 224–233 | MR | Zbl

[9] Shokin Yu. I., “On interval problems, interval algorithms and their computational complexity”, Scientific Computing and Validated Numerics, eds. G. Alefeld, A. Frommer and B. Lang, Akademie Verlag, Berlin, 1996, 314–328 | MR | Zbl

[10] Lakeev A. V., Noskov S. I., “O mnozhestve reshenii lineinogo uravneniya s intervalno zadannymi operatorom i pravoi chastyu”, Sib. mat. zhurn., 35:5 (1994), 1074–1084 | MR | Zbl

[11] Kreinovich V., Lakeyev A., Rohn J., “Computational complexity of interval algebraic problems: some are feasible and some are computationally intractable – A survey”, Scientific Computing and Validated Numerics, eds. G. Alefeld, A. Frommer and B. Lang, Akademie Verlag, Berlin, 1996, 293–306 | MR | Zbl

[12] Kreinovich V., Lakeyev A. V., “NP-hard classes of linear algebraic systems with uncertainties”, Reliable Computing, 3:1 (1997), 51–81 | DOI | MR | Zbl

[13] Shary S. P., “A new approach to the analysis of static systems under interval uncertainty”, Scientific Computing and Validated Numerics, eds. G. Alefeld, A. Frommer and B. Lang, Akademie Verlag, Berlin, 1996, 118–132 | MR | Zbl

[14] Shary S. P., “Algebraic approach to the analysis of linear static systems with interval uncertainty”, Russian J. Numer. Anal. Math. Model, 11:3 (1996), 259–274 | DOI | MR | Zbl

[15] Kupriyanova L., “Inner estimation of the united solution set of interval linear algebraic system”, Reliable Computing, 1:1 (1995), 15–31 | DOI | MR | Zbl

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

[17] Apostolatos N., Kulisch U., “Grundzüge einer Intervallrechnung für Matrizen und einige Anwendungen”, Electron. Rechenanl., 10 (1968), 73–83 | Zbl

[18] Mayer O., “Algebraische und metrische Strukturen in der Intervallrechnung und einige Anwendungen”, Computing, 5 (1970), 144–162 | DOI | MR | Zbl

[19] Berti S., “The solution of an interval equation”, Mathematica, 11(34):2 (1969), 189–194 | MR | Zbl

[20] Nickel K., “Die Auflösbarkeit linearer Kreisscheiben- und Intervall-Gleichungssystemen”, Linear Algebra Appl., 44 (1982), 19–40 | DOI | MR | Zbl

[21] Ratschek H., Sauer W., “Linear interval equations”, Computing, 28 (1982), 105–115 | DOI | MR | Zbl

[22] Birkgof G., Teoriya reshetok, Nauka, M., 1984 | MR

[23] Sharyi S. P., Ob odnoi intervalnoi zadache lineinoi algebry, Informatsionno-operativnyi material. Preprint No 2, VTs SO AN SSSR, Krasnoyarsk, 1987, 45–46

[24] Kurosh A. G., Lektsii po obschei algebre, Nauka, M., 1973 | Zbl

[25] Kaucher E., “Algebraische Erweiterungen der Intervallrechnung unter Erhaltung Ordnungs- und Verbandsstrukturen”, Computing Suppl., 1 (1977), 65–79 | Zbl

[26] Kaucher E., “Interval analysis in the extended interval space $\mathbb{IR}$”, Computing Suppl., 2 (1980), 33–49 | MR | Zbl

[27] Gardeñes E., Trepat A., “Fundamentals of SIGLA, an interval computing system over the completed set of intervals”, Computing, 24 (1980), 161–179 | DOI | MR | Zbl

[28] Lakeyev A. V., “Linear algebraic equations in Kaucher arithmetic”, International Journal of Reliable Computing. Supplement 1995, Extended Abstracts of APIC'95: International Workshop on Applications of Interval Computations (El Paso, Texas, February 23–25, 1995), 130–133

[29] Akilov G. P., Kutateladze S. S., Uporyadochennye vektornye prostranstva, Nauka, Novosibirsk, 1978 | MR | Zbl

[30] Krasnoselskii M. A., Polozhitelnye resheniya operatornykh uravnenii, Fizmatgiz, M., 1962 | MR

[31] Krasnoselskii M. A., Lifshits E. A., Sobolev A. V., Pozitivnye lineinye sistemy, Nauka, M., 1985 | MR

[32] Ortega Dzh., Reinboldt V., Iteratsionnye metody resheniya nelineinykh sistem uravnenii so mnogimi neizvestnymi, Mir, M., 1975 | MR

[33] Rokafellar R., Vypuklyi analiz, Mir, M., 1973

[34] Oben Zh.-P., Nelineinyi analiz i ego ekonomicheskie prilozheniya, Mir, M., 1988 | MR

[35] Demyanov V. F., Malozemov V. N., Vvedenie v minimaks, Nauka, M., 1972 | MR

[36] Hansen E., “Bounding the solution of interval linear equations”, SIAM J. Numer. Anal., 29 (1992), 1493–1503 | DOI | MR | Zbl

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