Enclosing solutions of overdetermined systems of linear interval equations (Q1916992)

This paper is concerned with one of the standard problems in numerical linear algebra: Compute lower and upper bounds for the solution of a system of linear equations in the presence of tolerances in the input data. Let \([A]\) denote an interval of matrices in \(\mathbb{R}^{m \times n}\), let \([b]\) denote an interval of vectors in \(\mathbb{R}^m\). In view of the equation \(A \cdot x = b\) with \(A \in [A]\) and \(b \in [b]\) one is interested in the solution set \[ X := \{x \mid x \in \mathbb{R}^n,\quad \exists A \in [A], \quad \exists b \in [b] : A \cdot x = b\}. \] This problem has been extensively studied for the square case \(m = n\) by \textit{A. Neumaier} [Interval methods for systems of equations (1990; Zbl 0715.65030)]. The present paper deals with the overdetermined case \(m \geq n\). The author presents a method for constructing an interval-enclosure of \(X\), based on an auxiliary system of linear inequalities. He gives an algorithm for solving this auxiliary system and states necessary and sufficient conditions for finite termination. Once an interval-enclosure of \(X\) has been found, the optimal interval-enclosure can be computed by solving a collection of linear programming problems.