×

Extension of the Hansen-Bliek method to right-quantified linear systems. (English) Zbl 1128.65025

Given an interval matrix \({\mathbf A}\subset\mathbb{R}^{n\times n}\), an interval vector \({\mathbf b}=({\mathbf b}_i)\subset\mathbb{R}^n\), and an index \(s\leq n\) the right-quantified solution set \(\Sigma\) of the linear interval system \({\mathbf A}x= {\mathbf b}\) is defined by
\[ \begin{split} \Sigma=\{x\in\mathbb{R}^n \mid(\forall b_1\in{\mathbf b}_1) \dots(\forall b_s\in{\mathbf b}_s)(\exists A\in{\mathbf A})(\exists b_{s+1}\in{\mathbf b}_{s+1})\dots (\exists b_n\in{\mathbf b}_n)\\ Ax=(b_1,\dots,b_n)^T\}. \end{split} \]
If the midpoint of \({\mathbf A}\) is the identity matrix and if the spectral radius of the radius of \({\mathbf A}\) is less than one, the authors construct vectors \(\underline x\), \(\overline x\in\mathbb{R}^n\) which either are optimal bounds for \(\Sigma\) or which show that \(\Sigma\) is empty. The proof is lengthy, the underlying algorithm can be carried out in polynomial-time. The method extends a result due to E. R. Hansen [SIAM J. Numer. Anal. 29, No. 5, 1493–1503 (1992; Zbl 0756.65035)] and C. Bliek [Computer methods for design automation, PhD Thesis, Massachusetts Institute of Technology (1992)] which assumes the index \(s\) above to be zero.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65G30 Interval and finite arithmetic

Citations:

Zbl 0756.65035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberth O. (1997) The Solution of Linear Interval Equations by a Linear Programming Method. Linear Algebra and Its Applications 259: 271–279 · Zbl 0878.65021
[2] Bliek, C.: Computer Methods for Design Automation, PhD Thesis, Massachusetts Institute of Technology, 1992.
[3] Dantzig, G. B.: Linear Programming and Extensions, Princeton University Press, 1963. · Zbl 0108.33103
[4] Goldsztejn, A.: A Branch and Prune Algorithm for the Approximation of Non-Linear AE-Solution Sets, in: ACM SAC, 2006, pp. 1650–1654.
[5] Goldsztejn A. (2005) A Right-Preconditioning Process for the Formal-Algebraic Approach to Inner and Outer Estimation of AE-Solution Sets. Reliable Computing 11(6): 443–478 · Zbl 1081.65041
[6] Goldsztejn, A.: Définition et Applications des Extensions des Fonctions Réelles aux Intervalles Généralisés, PhDThesis, Université de Nice-Sophia Antipolis, 2005.
[7] Hansen E.R. (1992) Bounding the Solution of Interval Linear Equations. SIAM J. Numer. Anal. 29(5): 1493–1503 · Zbl 0756.65035
[8] Heindl G., Kreinovich V., Lakeyev A.V. (1998) Solving Linear Interval Systems Is NP-Hard Even If We Exclude Overflow and Underflow. Reliable Computing 4(4): 377–381 · Zbl 0920.65012
[9] Markov, S., Popova, E., and Ullrich,Ch.: On the Solution of Linear Algebraic Equations Involving Interval Coefficients, in: Margenov, S. and Vassilevski, P. (eds), Iterative Methods in Linear Algebra, II, IMACS Series in Computational and Applied Mathematics 3 (1996), pp. 216–225.
[10] Moore, R.: Interval Analysis, Prentice Hall, 1966. · Zbl 0176.13301
[11] 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
[12] Neumaier, A.: Interval Methods for Systems of Equations, Cambridge University Press, 1990. · Zbl 0715.65030
[13] Ning S., Kearfott R.B. (1997) A Comparison of Some Methods for Solving Linear Interval Equations. SIAM J. Numer. Anal. 34(1): 1289–1305 · Zbl 0889.65022
[14] Oettli W. (1965) On the Solution Set of a Linear System with Inaccurate Coefficients, SIAM J. Numer. Anal. 2(1): 115–118 · Zbl 0146.13404
[15] Rohn J. (1993) Cheap and Tight Bounds: The Recent Result by E.Hansen Can Be Made More Efficient. Interval Computations 1(4): 13–21 · Zbl 0830.65019
[16] Shary S.P. (2002) A New Technique in Systems Analysis Under Interval Uncertainty and Ambiguity. Reliable Computing 8(5): 321–418 · Zbl 1020.65029
[17] Shary, S. P.: Algebraic Solutions to Interval Linear Equations and Their Application, in: IMACS– GAMM International Symposium on Numerical Methods and Error Bounds, 1996. · Zbl 0900.65135
[18] Shary S.P. (2001) Interval Gauss-Seidel Method for Generalized Solution Sets to Interval Linear Systems. Reliable Computing 7(2): 141–155 · Zbl 0976.65032
[19] Shary S.P. (1999) Outer Estimation of Generalized Solution Sets to Interval Linear Systems. Reliable Computing 5(3): 323–335 · Zbl 0947.65033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.