Abstract
In this paper, theidentification problem, thetolerance problem, and thecontrol problem are treated for the interval linear equation Ax=b. These problems require computing an inner approximation of theunited solution set Σ∃∃(A, b)={x ∈ ℝn | (∃A ∈ A)(Ax ∈ b)}, of thetolerable solution set Σ∀∃(A, b)={x ∈ ℝn | (∀A ∈ A)(Ax ∈ b)}, and of thecontrollable solution set Σ∃∀(A, b)={x ∈ ℝn | (∀b ∈ b)(Ax ∈b)} respectively. Analgebraic approach to their solution is developed in which the initial problem is replaced by that of finding analgebraic solution of some auxiliary interval linear system in Kaucher extended interval arithmetic. The algebraic approach is proved almost always to give inclusion-maximal inner interval estimates of the solutionsets considered. We investigate basic properties of the algebraic solutions to the interval linear systems and propose a number of numerical methods to compute them. In particular, we present the simple and fastsubdifferential Newton method, prove its convergence and discuss numerical experiments.
Abstract
Б этой работе рассматриваютсяэa¶rt;aчa u¶rt;eнmuфuxaцuu, эa¶rt;aчa o ¶rt;onyckax н эa¶rt;aчa o¶rt; ynpaвlenuu для интервальной линейной системы Ax=b, требующие нахожления внутренней оценки дляоб Σ∃∃(A, b)={x ∈ ℝn | (∃A ∈ A)(Ax ∈ b)}, Σ∀∃(A, b)={x ∈ ℝn | (∀A ∈ A)(Ax ∈ b)}, и Σ∃∀(A, b)={x ∈ ℝn | (∀b ∈ b)(Ax ∈b)} соответственно. Развиваетсян к их решению, при котором исходная задача заменяется задачей отысканиян для некоторой вспомогательной интервальной линейной системы в расширенной интервальной арифметике Каухера. Показано, что алгебраический нодход почти всегда дает максимальные по включению внутренние оценки для рассматриваемых множеств решений. Исследуются основные свойства алгебраическнх решений интервальных систем, обсужлаются численные метолы для их нахожления. Б частности, мы предалагаем простой и быстрыйн, доказываем его сходимость и приводим результаты численных экспериментов с ним.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alefeld, G. and Herzberger, J.Introduction to interval computations. Academic Press, New York, 1983.
Aubin, J.-P.L'analyse non linéaire et ses motivation économiques. Masson, Paris, 1984.
Barth, W. and Nuding, E.Optimale Lösung von Intervallgleichungssystemen. Computing12 (1974), pp. 117–125.
Beeck, H.Über Struktur und Abschätzungen der Lösungsmenge von linearen Gleichungssystemen mit Intervallkoeffizienten. Computing10 (1972), pp. 231–244.
Birkhoff, G.Lattice theory. AMS, Providence, 1967.
Bourbaki, N.Eléménts de mathématique. Topologie générale. Hermann, Paris, 1958.
Collatz, L.Funktionalanalysis und numerische Mathematik. Springer-Verlag, Berlin, Höttingen, Heidelberg, 1964.
Dobronets, B. S. and Shaidurov, V. V.Two-sided numerical methods. Nauka, Novosibirsk, 1990 (in Russian).
Gardeñes, E. and Trepat, A.Fundamentals of SIGLA, an interval computing system over the completed set of intervals. Computing24 (1980), pp. 161–179.
Gardeñes, E. and Trepat, A.SIGLA-PL/1. Development and applications. In: “Interval Mathematics 1980”, Academic Press, New York, 1980, pp. 301–315.
Kaucher, E.Algebraische Erweiterungen der Intervallrechnung unter Erhaltung Ordnungs- und Verbandsstrukturen. Computing, Suppl.1 (1977), pp. 65–79.
Kaucher, E.Interval analysis in the extended interval space Iℝ. Computing, Suppl.2 (1980), pp. 33–49.
Kelling, B. and Oelschlägel, D.Zur Lösung von linearen Toleranzproblemen. Wiss. Zeitschrift TH Leuna-Merseburg33 (1) (1990), pp. 121–131.
Krasnoselskii, M., Vainikko, G., Zabreiko, P., Rutitskii, Y., and Stetsenko, V.Approximate solutions of operator equations. Noordhoff, Groningen, 1972.
Kupriyanova, L.Inner estimation of the united solution set of interval linear algebraic system. Reliable Computing1 (1) (1995), pp. 15–31.
Lakeyev, A. V. and Noskov, S. I.Description of the solution set to linear equation with the intervally defined operator and right-hand side. Doklady Akademii Nauk330 (4) (1993), pp. 430–433 (in Russian).
Moore, R. E.Methods and applications of interval analysis. SIAM, Philadelphia, 1979.
Neumaier, A.Tolerance analysis with interval arithmetic. Freiburger Intervall-Berichte86 (9) (1986), pp. 5–19.
Neumaier, A.Interval methods for systems of equations. Cambridge University Press, Cambridge, 1990.
Ortega, J. M. and Rheinboldt, W. C.Iterative solutions of nonlinear equations in several variables. Academic Press, New York, 1970.
Radström, H.An embedding theorem for spaces of convex sets. Proc. Amer. Math. Soc.3 (1952), pp. 165–169.
Ratschek, H. and Sauer, W.Linear interval equations. Computing28 (1982), pp. 105–115.
Rockafellar, R. T.Convex analysis. Princeton University Press, Princeton, 1970.
Rohn, J.NP-hardness results for linear algebraic problems with interval data. In: Herzberger, J. (ed.) “Topics in Validated Computations”, North-Holland, Amsterdam, 1993, pp. 463–471.
Shary, S. P.On an interval problem of linear algebra. In: “Informacionno-operativnyi material”, Preprint No 2/1987, Computer Center of Siberian Department of the USSR Academy of Sciences, Krasnoyarsk, 1987, pp. 45–46 (in Russian).
Shary, S. P.On controlled solution set of interval algebraic systems. Interval Computations4 (6) (1992), pp. 66–75.
Shary, S. P.Algebraic approach to some interval problems, or One more application of Kaucher arithmetic. In: “Interval'94 (International Conference on Interval and Computer-Algebraic Methods in Science and Engineering, St.Petersburg, Russia, March 7–10, 1994). Abstracts”, St.Peterburg, 1994, pp. 212–216.
Shary, S. P.Solving the tolerance problem for interval linear equations. Interval Computations 2 (1994), pp. 6–26.
Shary, S. P.On optimal solution of interval linear equations. SIAM J. Numer. Anal.32 (1995), pp. 610–630.
Zakharov, A. V. and Shokin, Yu. I.Synthesis of the control systems under conditions of interval uncertainty in parameters of their mathematical models. Doklady Akademii Nauk299 (2) (1988), pp. 292–295 (in Russian).
Zyuzin, V. S.On a way of finding two-sided approximation to the solution of system of linear interval equations. In: “Differential Equations and the Theory of Functions”, Saratov State University, Saratov, 1987, pp. 28–32 (in Russian).
Zyuzin, V. S.An iterative method for solving system of algebraic segment equations of the first order. In: “Differential Equations and the Theory of Functions”, Saratov State University, Saratov, 1989, pp. 72–82 (in Russian).
Zyuzin, V. S.An interval arithmetic solution of a system of interval algebraic equations of the first order. In: “International Symposium on Computer Arithmetic, Scientific Computation and Mathematical Modelling, Albena, Bulgaria, September 23–28, 1990 (SCAN-90)”, Bulgarian Academy of Sciences, Sofia, 1990, pp. 160–162.
Author information
Authors and Affiliations
Additional information
© S. P. Shary, 1996
Rights and permissions
About this article
Cite this article
Shary, S.P. Algebraic approach to the interval linear static identification, tolerance, and control problems, or one more application of kaucher arithmetic. Reliable Comput 2, 3–33 (1996). https://doi.org/10.1007/BF02388185
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02388185