Abstract
Consider a linear system A(p)⋅x=b(p), where the elements of the matrix and the right-hand side vector depend linearly on a m-tuple of parameters p=(p 1,…,p m ), the exact values of which are unknown but bounded within given intervals. Apart from quantifier elimination, the only known general way of describing the solution set {x∈ℝn∣∃p∈[p],A(p)x=b(p)} is a lengthy and non-unique Fourier-Motzkin-type parameter elimination process that leads to a description of the solution set by exponentially many inequalities. In this work we modify the parameter elimination process in a way that has a significant impact on the representation of the inequalities describing the solution set and their number. An explicit minimal description of the solution set to 2D parametric linear systems is derived. It generalizes the Oettli-Prager theorem for non-parametric linear systems. The number of the inequalities describing the solution set grows linearly with the number of the parameters involved simultaneously in both equations of the system. The boundary of any 2D parametric solution set is described by polynomial equations of at most second degree. It is proven that when the general parameter elimination process is applied to two equations of a system in higher dimension, some inequalities become redundant.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ackermann, L., Bartlett, A., Kesbauer, D., Sienel, W., Steinhauser, R.: Robust Control: Systems with Uncertain Physical Parameters. Springer, Berlin (1994)
Alefeld, G., Kreinovich, V., Mayer, G.: On symmetric solution sets. Computing, Suppl. (Wien) 16, 1–22 (2002)
Alefeld, G., Kreinovich, V., Mayer, G.: On the solution sets of particular classes of linear interval systems. J. Comput. Appl. Math. 152, 1–15 (2003)
Davenport, J., Heintz, J.: Real quantifier elimination is doubly exponential. J. Symb. Comput. 5, 29–35 (1988)
Dreyer, A.: Interval Analysis of Analog Circuits with Component Tolerances. Shaker, Aachen (2005)
Elishakoff, I., Ohsaki, M.: Optimization and Anti-Optimization of Structures Under Uncertainty. Imperial College Press, London (2010)
Lagoa, C.M., Barmish, B.R.: Distributionally robust Monte Carlo simulation: a tutorial survey. In: Proceedings of the 15th IFAC World Congress, pp. 1327–1338 (2002)
Mayer, G.: On regular and singular interval systems. J. Comput. Appl. Math. 199, 220–228 (2007)
Oettli, W., Prager, W.: Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math. 6, 405–409 (1964)
Popova, E.: Explicit characterization of a class of parametric solution sets. C. R. Acad. Bulgare Sci. 62(10), 1207–1216 (2009)
Popova, E., Krämer, W.: Visualizing parametric solution sets. BIT Numer. Math. 48(1), 95–115 (2008)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)
Tarski, A.: A decision method for elementary algebra and geometry. Manuscript, Santa Monica, CA, RAND Corp. (1948). Republished by Berkeley, CA, University of California Press, 1951 and in Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer, New York, pp. 24–84 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Lars Eldén.
This work is partially supported by the Bulgarian National Science Fund under grant No. DO 02–359/2008.
Rights and permissions
About this article
Cite this article
Popova, E.D. Explicit description of 2D parametric solution sets. Bit Numer Math 52, 179–200 (2012). https://doi.org/10.1007/s10543-011-0339-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-011-0339-z