Extension of the Hansen-Bliek method to right-quantified linear systems (Q2641465): Difference between revisions

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{multlined} \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{multlined} \] 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 \textit{E. R. Hansen} [SIAM J. Numer. Anal. 29, No.~5, 1493--1503 (1992; Zbl 0756.65035)] and \textit{C. Bliek} [Computer methods for design automation, PhD Thesis, Massachusetts Institute of Technology (1992)] which assumes the index \(s\) above to be zero.