A  variability  measure  for  estimates
of parameters in interval data fitting

The initial data for our problem is a set of values of independent and dependent variables for function (1), which are obtained as a result of $m$ measurements (observations):

$$\begin{array}[]{ccccc}\text{\boldmath$a$}_{11},&\text{\boldmath$a$}_{12},&\ldots&\text{\boldmath$a$}_{1n},&\text{\boldmath$b$}_{1},\\ \text{\boldmath$a$}_{21},&\text{\boldmath$a$}_{22},&\ldots&\text{\boldmath$a$}_{2n},&\text{\boldmath$b$}_{2},\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ \text{\boldmath$a$}_{m1},&\text{\boldmath$a$}_{m2},&\ldots&\text{\boldmath$a$}_{mn},&\text{\boldmath$b$}_{m}.\end{array}$$

(2)

These are intervals as we assume that these data are inaccurate and have interval uncertainty due to measurement errors, etc. Both the data (2) and other interval values throughout the text are highlighted in bold mathematical font according to the informal international standard [5]. The first index of the interval values from (2) means the measurement number, and the second one, at $\text{\boldmath$a$}_{ij}$’s, is the number of the independent variable that takes the corresponding value in this measurement.

To find an estimate $(\hat{x}_{1},\hat{x}_{2},\ldots,\hat{x}_{n})$ of the parameters of the linear function (1), we “substitute” data (2) into equality (1), thus getting an interval system of linear algebraic equations

$$\left\{\ \begin{array}[]{ccccccccc}\text{\boldmath$a$}_{11}x_{1}&+&\text{\boldmath$a$}_{12}x_{2}&+&\ldots&+&\text{\boldmath$a$}_{1n}x_{n}&=&\text{\boldmath$b$}_{1},\\[1.0pt] \text{\boldmath$a$}_{21}x_{1}&+&\text{\boldmath$a$}_{22}x_{2}&+&\ldots&+&\text{\boldmath$a$}_{2n}x_{n}&=&\text{\boldmath$b$}_{2},\\[1.0pt] \vdots&&\vdots&&\ddots&&\vdots&&\vdots\\[1.0pt] \text{\boldmath$a$}_{m1}x_{1}&+&\text{\boldmath$a$}_{m2}x_{2}&+&\ldots&+&\text{\boldmath$a$}_{mn}x_{n}&=&\text{\boldmath$b$}_{m},\end{array}\right.$$

(3)

or, briefly,

$$\text{\boldmath$A$}x=\text{\boldmath$b$}$$

(4)

with an interval $m\times n$-matrix $\text{\boldmath$A$}=(\text{\boldmath$a$}_{ij})$ and interval $m$-vector $\text{\boldmath$b$}=(\text{\boldmath$b$}_{i})$ in the right-hand side. The sets of parameters which are compatible, in this or that sense, with the measurement data (2) form various solution sets for the equations system (3). The most popular of them are the united solution set and tolerable solution set. The united solution set, defined as

$$\varXi_{uni}(\text{\boldmath$A$},\text{\boldmath$b$})=\bigl{\{}\,x\in\mathbb{R}^{n}\mid\text{ $Ax=b\,$ for some $A\in\text{\boldmath$A$}$ and $b\in\text{\boldmath$b$}$}\,\bigr{\}},$$

corresponds to the so-called weak compatibility between the parameters of function (1) and data (2) (see [6, 16, 17]). The tolerable solution set, defined as

$$\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})=\bigl{\{}\,x\in\mathbb{R}^{n}\mid\text{ $Ax\in\text{\boldmath$b$}\,$ for each matrix $A\in\text{\boldmath$A$}$}\,\bigr{\}},$$

corresponds to the so-called strong compatibility between the parameters of function (1) and data (2) (see [19]).

Further, we assume that the solution to the data fitting problem for function (1) is found by the maximum compatibility method (see [16, 17, 19]). As an estimate of the parameters of function (1), it takes the maximum point of the recognizing functional, a special function that gives a quantitative “compatibility measure” of this estimate with empirical data (2).

The maximum compatibility method has two versions, “weak” and “strong”, that differ in understanding how exactly the interval data should be “compatible” with the function that we construct on them. Weak and strong compatibility reflect two different situations that may occur in data processing. In the weak version, it is required that the graph of the constructed function just intersects the measurement uncertainty boxes (see [16, 17]). The strong version implies more stringent condition: it requires that the function graph passes within the “corridors” specified by the intervals $\text{\boldmath$b$}_{i}$, $i=1,2,\ldots,m$, for any values of the independent variables $a_{1}$, $a_{2}$, …, $a_{n}$ from the respective intervals $\text{\boldmath$a$}_{i1}$, $\text{\boldmath$a$}_{i2}$, …, $\text{\boldmath$a$}_{in}$ obtained in the $i$-th measurement (see [19]). This is illustrated in Fig. 3, where the straight line of the function graph goes through the vertical faces of the measurement uncertainty boxes. The weak compatibility is shown in Fig. 2 by two upper straight lines. The lower line in Fig. 2 does not satisfy compatibility condition at all, neither weak nor strong, since it does not intersect some boxes.

The “strong version” of the maximum compatibility method has a number of theoretical and practical advantages over the “weak version”. These are polynomial complexity, robustness of estimates and their finite variability, the fact that the strong compatibility partially overcomes the so-called Demidenko paradox, etc. (see details in [19]). Hence, we consider below a strong version of the maximum compatibility method, which corresponds to the tolerable solution set $\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})$ for the interval system of equations (4). Its recognizing functional is usually denoted by “Tol”,

$$\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$})\;=\,\min_{1\leq i\leq m}\left\{\,\mathrm{rad}\,\text{\boldmath$b$}_{i}-\left|\;\mathrm{mid}\,\text{\boldmath$b$}_{i}-\sum_{j=1}^{n}\,\text{\boldmath$a$}_{ij}x_{j}\,\right|\,\right\},$$

(5)

where

$$\mathrm{rad}\,\text{\boldmath$b$}_{i}=\tfrac{1}{2}(\overline{\text{\boldmath$b$}}_{i}-\underline{\text{\boldmath$b$}}_{i}),\hskip 65.44133pt\mathrm{mid}\,\text{\boldmath$b$}_{i}=\tfrac{1}{2}(\overline{\text{\boldmath$b$}}_{i}+\underline{\text{\boldmath$b$}}_{i})$$

are radii and midpoints of the components of the right-hand side $b$, the arithmetic operations inside the modulus in (5) are those of the classical interval arithmetic (see, e. g., [4, 8, 9]), and the modulus is understood as the maximum absolute value of the points from the interval,

$$|\text{\boldmath$a$}|=\max\,\{\,|a|\mid a\in\text{\boldmath$a$}\,\}=\max\,\bigl{\{}\,|\underline{\text{\boldmath$a$}}|,|\overline{\text{\boldmath$a$}}|\,\bigr{\}}.$$

Typical graphs of the functional Tol for the one-dimensional case are shown in Fig. 4 and Fig. 5.

To solve the data fitting problem for the linear function (1) and data set (2), it is necessary to find the unconstrained maximum, over all $x\in\mathbb{R}^{n}$, of the functional $\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$})$,

$$\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$})\rightarrow\max,$$

and the vector $\hat{x}=\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$})$ at which this maximum is attained provides an estimate of the parameters of function (1).

If $\max\,\mathrm{Tol}\,\geq 0$, then the solution set $\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})$, i. e., the set of parameters strongly compatible with the data is non-empty, and $\hat{x}\in\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})$. If $\max\,\mathrm{Tol}\,<0$, then the solution set $\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})$ is empty and there do not exist parameters that are strongly compatible with data (2). However, the argument $\hat{x}$ of $\max\,\mathrm{Tol}\,$ still provides the best compatibility of the constructed linear function with data (2) (more precisely, the least incompatibility).

To conclude this subsection, we give a useful result on the tolerable solution set that allows us to investigate whether it is bounded or unbounded, i. e., whether the tolerable solution sets is finite in size or extends infinitely.

The criterion of boundedness shows that the tolerable solution set is unbounded, in fact, under exceptional circumstances, which are almost never fulfilled in practice, when working with actual interval data. That is, the tolerable solution set is mostly bounded, and the estimates obtained by the strong version of the maximum compatibility method almost always has finite variability.

As a quantity characterizing the variability of the estimate of the parameter vector $\hat{x}=(\hat{x}_{1},\hat{x}_{2},\ldots,\hat{x}_{n})$ in the linear function (1), which is obtained by the maximum compatibility method from data (2), we propose

$$\mathrm{IVE}\,(\text{\boldmath$A$},\text{\boldmath$b$})\;=\;\sqrt{n}\;\max_{\mathbb{R}^{n}}\,\mathrm{Tol}\,\cdot\Bigl{(}\;\min_{A\in\text{\boldmath$A$}}\,\mathrm{cond}_{2}\,A\,\Bigr{)}\cdot\frac{\displaystyle\bigl{\|}\,\arg\max_{\mathbb{R}^{n}}\,\mathrm{Tol}\,\bigr{\|}_{2}}{\|\hat{\text{\boldmath$b$}}\|_{2}}.$$

(6)

In this formula,

$n$ is the dimension of the parameter vector of function (1) under construction,

$\|\cdot\|_{2}$ is the Euclidean norm (2-norm) of vectors from $\mathbb{R}^{n}$, defined as

$$\|x\|_{2}\;=\;\left(\;\sum_{i=1}^{n}|x_{i}|^{2}\,\right)^{1/2},$$

$\mathrm{cond}_{2}\,A$ is the spectral condition number of the matrix $A$, defined as

$$\mathrm{cond}_{2}\,A\;=\;\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)},$$

i. e., the ratio of the maximal $\sigma_{\max}(A)$ and minimal $\sigma_{\min}(A)$ singular values of $A$; it is an extension, to the rectangular case, of the concept of the condition number from computational linear algebra (see e. g. [2, 24]);

$\hat{\text{\boldmath$b$}}$ is a certain “most representative” point from the interval vector $b$, which is taken as

$$\hat{\text{\boldmath$b$}}\;=\;\tfrac{1}{2}(|\mathrm{mid}\,\text{\boldmath$b$}+\mathrm{rad}\,\text{\boldmath$b$}|+|\mathrm{mid}\,\text{\boldmath$b$}-\mathrm{rad}\,\text{\boldmath$b$}|),$$

(7)

where the operations “mid” and “rad” are applied in componentwise manner.

Despite the definite formula (7) for $\hat{\text{\boldmath$b$}}$, it should be noted that the introduction of this point is, to a large extent, a matter of common sense. The general approach to the definition of $\hat{\text{\boldmath$b$}}$ is that it must be a kind of “most representative” point from the right-hand side vector $b$, and in some situations this choice may be different from formula (7). For example, $\hat{\text{\boldmath$b$}}$ can be a point result of the measurement, around which the uncertainty interval is built later, based on information about the accuracy of the measuring device.

Apart from (6), as a measure of relative variability of the parameter estimate, the value

$$n\;\Bigl{(}\,\min_{A\in\text{\boldmath$A$}}\,\mathrm{cond}_{2}A\,\Bigr{)}\cdot\frac{\max_{\mathbb{R}^{n}}\,\mathrm{Tol}\,}{\|\hat{\text{\boldmath$b$}}\|_{2}},$$

(8)

can have a certain significance. Both IVE and value (8) are defined for interval linear systems (4) with nonzero right-hand sides. They can take either positive real values or be infinite. The latter occurs in the only case of $\,\min_{A\in\text{\boldmath$A$}}\,\mathrm{cond}_{2}A=\infty$, when all the point matrices $A\in\text{\boldmath$A$}$ have incomplete rank, i. e., when $\sigma_{\min}(A)=0$ for every $A\in\text{\boldmath$A$}$. Then the variability measures are set to be infinite.

The symbol IVE is built as an abbreviation of the phrase “interval variability of the estimate”. Below, we show that the value IVE adequately characterizes the size of non-empty tolerable solution set for a large class of practically important situations. But it is useful to discuss informal motivations that lead to the estimate IVE and to demonstrate that IVE has an intuitive, clear and even visual meaning.

The tolerable solution set of an interval system of linear algebraic equations is the set of zero level of the recognizing functional Tol (see details in [15]), or, in other words, the intersection of the hypograph of this functional with the coordinate plane $\mathrm{Tol}\,=0$ (this is illustrated in Fig. 4). As a consequence, the magnitude of the maximum of the recognizing functional can, with other things being equal, be a measure of how extensive or narrow the tolerable solution set is. The more $\max\,\mathrm{Tol}\,$, the larger the size of the tolerable solution set, and vice versa. An additional factor that provides “other things being equal” is the slope (steepness) of pieces of hyperplanes of which the polyhedral graph of the functional Tol is compiled (these are straight lines in the 1D case in Fig. 4 and Fig. 5). The slope of the hyperplanes is determined by the coefficients of the equations that define them, which are the endpoints of the data intervals (2). The value of this slope is summarized in terms of the condition number of point matrices from the interval data matrix $A$. Finally, the multiplier

$$\frac{\|\arg\max\,\mathrm{Tol}\,\|_{2}}{\|\hat{\text{\boldmath$b$}}\|_{2}}\ =\ \frac{\|\hat{x}\|_{2}}{\|\hat{\text{\boldmath$b$}}\|_{2}}$$

is a scaling coefficient that helps to provide the commensurability of the final value with magnitudes of the solution, $\arg\max\,\mathrm{Tol}\,$, and the right-hand side vector of the equations system. Thus, formula (6) is obtained.

The starting point of our constructions justifying the choice of (6) exactly in the form described above is the well-known inequality that estimates perturbation $\Delta x$ of a nonzero solution $x$ to the system of linear algebraic equations $Ax=b$ depending on the change $\Delta b$ of the right-hand side $b$ (see, e. g., [2, 24]):

$$\frac{\|\Delta x\|_{2}}{\|x\|_{2}}\ \leq\ \mathrm{cond}_{2}\,A\,\cdot\frac{\|\Delta b\|_{2}}{\|b\|_{2}}.$$

(9)

It is usually considered for square systems of linear equations, when $m=n$, but in the case of the Euclidean vector norm and the spectral condition number of matrices, this inequality holds true in the more general case with $m\geq n$. Naturally, estimate (9) makes sense only for $\sigma_{\min}(A)\neq 0$, when $\mathrm{cond}_{2}A<\infty$, i. e., when the matrix $A$ has full column rank. Let us briefly recall its derivation for this case.

Given

$$Ax=b\quad\text{ и }\quad A(x+\Delta x)=b+\Delta b,$$

we have

$$A\Delta x=\Delta b.$$

Further,

	$\displaystyle\displaystyle\frac{\displaystyle\phantom{M}\frac{\|\Delta x\|_{2}}{\|x\|_{2}}\phantom{M}}{\displaystyle\frac{\|\Delta b\|_{2}}{\|b\|_{2}}}\$	$\displaystyle=\ \frac{\|\Delta x\|_{2}\,\|b\|_{2}\phantom{I}}{\phantom{I}\|x\|_{2}\,\|\Delta b\|_{2}}=\ \frac{\|\Delta x\|_{2}\,\|Ax\|_{2}\phantom{I}}{\phantom{I}\|x\|_{2}\,\|A\Delta x\|_{2}}\ =\ \frac{\|\Delta x\|_{2}}{\|A\Delta x\|_{2}}\;\frac{\|Ax\|_{2}}{\|x\|_{2}}$
		$\displaystyle\leq\;\max_{\Delta x\neq 0}\frac{\|\Delta x\|_{2}}{\|A\Delta x\|_{2}}\ \max_{x\neq 0}\frac{\|Ax\|_{2}}{\|x\|_{2}}\ =\ \left(\min_{\Delta x\neq 0}\frac{\|A\Delta x\|_{2}}{\|\Delta x\|_{2}}\right)^{-1}\ \max_{x\neq 0}\frac{\|Ax\|_{2}}{\|x\|_{2}}$
		$\displaystyle=\ \bigl{(}\sigma_{\min}(A)\bigr{)}^{-1}\,\sigma_{\max}(A)\,=\ \mathrm{cond}_{2}(A)$

by virtue of the properties of the singular values (see e. g. [3, 24]). A comparison of the beginning and the end of this calculation leads to the inequality (9), which, as is easy to understand, is attainable for some $x$ and $\Delta x$, or, equivalently, for some right-hand sides of $b$ and their perturbations $\Delta b$. Naturally, the above calculations and the resulting estimate make sense only for $\sigma_{\min}(A)\neq 0$.

Let us consider an interval system of linear algebraic equations

$$Ax=\text{\boldmath$b$}$$

(10)

with a point (noninterval) $m\times n$-matrix $A$, $m\geq n$, and an interval $m$-vector $b$ in the right-hand side. We assume that $A$ has full column rank and, therefore, $\mathrm{cond}_{2}\,A<\infty$.

Suppose also that the tolerable solution set for system (10) is non-empty, i. e. $\varXi_{tol}(A,\text{\boldmath$b$})=\bigl{\{}\,x\in\mathbb{R}^{n}\mid Ax\in\text{\boldmath$b$}\,\bigr{\}}\neq\varnothing$. We need to quickly and with little effort estimate the size of this solution set, and our answer will be a “radius type” estimate for $\varXi_{tol}(A,\text{\boldmath$b$})$. More precisely, we are going to evaluate $\max\|x^{\prime}-\hat{x}\|_{2}$ over all $x^{\prime}\in\varXi_{tol}(A,\text{\boldmath$b$})$ and for a special fixed point $\hat{x}\in\varXi_{tol}(A,\text{\boldmath$b$})$, which is taken as

$$\hat{x}\ =\ \arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,(x,A,\text{\boldmath$b$}).$$

Recall that the argument $\hat{x}$ of the maximum of the recognizing functional for system (10) is an estimate of parameters of linear function (1) from empirical data. Strictly speaking, this point can be determined non-uniquely, but then let $\hat{x}$ be any one of the points at which the maximum is reached.

Let $x^{\prime}$ be a point in the tolerable solution set $\varXi_{tol}(A,\text{\boldmath$b$})$. How to evaluate $\|x^{\prime}-\hat{x}\|_{2}$? It is clear that $x^{\prime}$ and $\hat{x}$ are solutions of systems of linear algebraic equations with the matrix $A$ and some right-hand sides $b^{\prime}$ and $\hat{b}$, respectively, from the interval vector $b$. If $\hat{x}\neq 0$ and $\hat{b}\neq 0$, then we can apply inequality (9), considering a perturbation of the solution $\hat{x}$ to the system of linear algebraic equations $Ax=\hat{b}$. Then $\Delta x=x^{\prime}-\hat{x}$, $\Delta b=b^{\prime}-\hat{b}$, and we get

$$\frac{\|x^{\prime}-\hat{x}\|_{2}}{\|\hat{x}\|_{2}}\ \leq\;\mathrm{cond}_{2}\,A\cdot\frac{\|b^{\prime}-\hat{b}\|_{2}}{\|\hat{b}\|_{2}},$$

from where the absolute estimate is obtained

$$\|x^{\prime}-\hat{x}\|_{2}\ \leq\;\mathrm{cond}_{2}\,A\cdot\|\hat{x}\|_{2}\cdot\frac{\|b^{\prime}-\hat{b}\|_{2}}{\|\hat{b}\|_{2}}.$$

(11)

The point $\hat{x}$ is found as the result of maximization of the recognizing functional Tol, the point $\hat{b}$ coincides with $A\hat{x}$, the condition number $\mathrm{cond}_{2}\,A$ can be computed by well-developed standard procedures. Therefore, for practical work with inequality (11), one need somehow evaluate $\|b^{\prime}-\hat{b}\|_{2}$.

But first, bearing in mind the further application of the deduced estimate in a situation where the matrix $A$ may vary, we somewhat roughen (11) by taking approximately $\|\hat{b}\|_{2}\approx\|\hat{\text{\boldmath$b$}}\|_{2}$, that is, as the norm of the “most representative” point $\hat{\text{\boldmath$b$}}$ of the interval vector $b$, which we defined in Section 2.2:

$$\|\hat{b}\|_{2}\,\approx\,\|\hat{\text{\boldmath$b$}}\|_{2},\qquad\text{ where }\ \hat{\text{\boldmath$b$}}\,=\,\tfrac{1}{2}\,\bigl{(}\,|\mathrm{mid}\,\text{\boldmath$b$}+\mathrm{rad}\,\text{\boldmath$b$}|+|\mathrm{mid}\,\text{\boldmath$b$}-\mathrm{rad}\,\text{\boldmath$b$}|\,\bigr{)}.$$

In doing this, some coarsening is allowed, so instead of (11) we write

$$\|x^{\prime}-\hat{x}\|_{2}\ \lessapprox\;\mathrm{cond}_{2}\,A\cdot\|\hat{x}\|_{2}\cdot\frac{\|\Delta b\|_{2}}{\|\hat{\text{\boldmath$b$}}\|_{2}}.$$

(12)

Now it is necessary to determine the increment of the right-hand side $\Delta b=b^{\prime}-\hat{b}$. Its obvious upper bound is $2\,\mathrm{rad}\,\text{\boldmath$b$}$, but it is too crude. To get a more accurate estimate of $\Delta b$, we also consider, along with system (10), a system of linear algebraic equations

$$Ax=\tilde{\text{\boldmath$b$}},$$

(13)

for which the right-hand side is obtained by uniform “compressing” the interval vector $b$:

$$\tilde{\text{\boldmath$b$}}\,:=\,\bigl{[}\,\underline{\text{\boldmath$b$}}+M,\overline{\text{\boldmath$b$}}-M\,\bigr{]},$$

(14)

where

$$M\;:=\;\max_{x\in\mathbb{R}^{n}}\;\mathrm{Tol}\,(x,A,\text{\boldmath$b$})\ \geq\ 0.$$

Since the maximum $M$ is reached for a certain value of the argument, $\hat{x}$, then

$$M=\,\min_{1\leq i\leq m}\left\{\,\mathrm{rad}\,\text{\boldmath$b$}_{i}-\left|\;\mathrm{mid}\,\text{\boldmath$b$}_{i}-\sum_{j=1}^{n}\,\text{\boldmath$a$}_{ij}\hat{x}_{j}\,\right|\,\right\}\ \leq\,\min_{1\leq i\leq m}\,\mathrm{rad}\,\text{\boldmath$b$}_{i}.$$

As a result, $\underline{\text{\boldmath$b$}}+M\leq\overline{\text{\boldmath$b$}}-M$ in componentwise sense, and the endpoints in the interval vector (14) do not “overlap” each other.

But the properties of the recognizing functional imply that, for the interval system of linear algebraic equations (13) with the right-hand side (14), the maximum of the recognizing functional is zero:

$$\max_{x\in\mathbb{R}^{n}}\;\mathrm{Tol}\,(x,A,\tilde{\text{\boldmath$b$}})\ =\ 0.$$

Indeed, the values of $\mathrm{rad}\,\text{\boldmath$b$}_{i}$ are summands in all expressions in (5), for which we take the minimum over $i=1,2,\ldots,m$. Hence, if we simultaneously increase or decrease all $\mathrm{rad}\,\text{\boldmath$b$}_{i}$ by the same value, keeping the midpoints $\mathrm{mid}\,\text{\boldmath$b$}_{i}$ unchanged, then the total value of the recognizing functional will increase or decrease by exactly same value. In other words, if we take a constant $C\geq 0$ and the interval $m$-vector $\text{\boldmath$e$}=([-1,1],\ldots,[-1,1])^{\top}$, then, for the system $Ax=\text{\boldmath$b$}+C\text{\boldmath$e$}\,$ with all the right-hand sides expanded by $[-C,C]$, we have

$$\mathrm{Tol}\,(x,A,\text{\boldmath$b$}+C\text{\boldmath$e$})\ =\ \mathrm{Tol}\,(x,A,\text{\boldmath$b$})+C.$$

(15)

Therefore,

$$\max_{x\in\mathbb{R}^{n}}\;\mathrm{Tol}\,(x,A,\text{\boldmath$b$}+C\text{\boldmath$e$})\ =\ \max_{x\in\mathbb{R}^{n}}\;\mathrm{Tol}\,(x,A,\text{\boldmath$b$})+C.$$

(16)

The uniform narrowing of the right-hand side vector acts on the tolerable solution set and the recognizing functional in a completely similar way. If we narrow down all the components by the same value $M$, then the maximum of the recognizing functional of the new interval system also decreases by $M$.

By virtue of the properties of the recognizing functional, the tolerable solution set $\varXi_{tol}(A,\tilde{\text{\boldmath$b$}})$ for system (13) has empty interior (such sets are often called “non-solid” or “meager”), which we will consider equivalent to “having zero size”. Naturally, this is a simplifying assumption, since in reality the tolerable solution set corresponding to the zero maximum of the recognizing functional may be not a single-point set. But we still accept that. This implication is also supported by the fact that the situation with the zero maximum of the recognizing functional is unstable: the corresponding tolerable solution set can become empty with an arbitrarily small data perturbation (see Section 4).

Another fact concerning the auxiliary system (13) with the narrowed right-hand side, which follows from (15)–(16), is that the point $\hat{x}$ remains to be the argument of the maximum of the recognizing functional:

$$\hat{x}\ =\ \arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,(x,A,\tilde{\text{\boldmath$b$}}).$$

For this reason, the point $\hat{b}=A\hat{x}$ lies in the interval vector $\tilde{\text{\boldmath$b$}}$ defined by (14).

From what has been said, it follows that the solution set for the system $Ax=\text{\boldmath$b$}$ is obtained from the solution set of the system $Ax=\tilde{\text{\boldmath$b$}}$, which has “negligible size” and for which $\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,(x,\text{\boldmath$A$},\tilde{\text{\boldmath$b$}})=0$, through expanding the right-hand side vector $\tilde{\text{\boldmath$b$}}$ in each component simultaneously by $[-M,M]$, where

$$M=\max_{x\in\mathbb{R}^{n}}\;\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$}).$$

The interval vector $\tilde{\text{\boldmath$b$}}\ni b$ may have non-zero size, but we put

$$[-\Delta b,\Delta b]=([-M,M],\ldots,[-M,M])^{\top}$$

in order to make our estimate (12) attainable. Accordingly, in inequality (12) we take

$$\|\Delta b\|=\max_{x\in\mathbb{R}^{n}}\;\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$}),$$

if the Chebyshev norm ($\infty$-norm) is considered, or a value that differs from it by a corrective factor from the equivalence inequality for vector norms, if we take any other norm. As is known, for any vector $y\in\mathbb{R}^{n}$ (see [2])

$$\|y\|_{\infty}\leq\|y\|_{2}\leq\sqrt{n}\;\|y\|_{\infty}.$$

(17)

Then

$$\|x^{\prime}-\hat{x}\|_{2}\ \lessapprox\,\sqrt{n}\ \,\mathrm{cond}_{2}A\cdot\bigl{\|}\,\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,\bigr{\|}_{2}\cdot\frac{\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,}{\|\hat{\text{\boldmath$b$}}\|_{2}}.$$

(18)

What happens if the matrix $A$ does not have a full column rank? Then, by virtue of the Irene Sharaya criterion, the nonempty tolerable solution set to the system (10) is unbounded. This is completely consistent with the fact that then $\mathrm{cond}_{2}A=\infty$ and the value of the variability measure IVE is infinite too.

Finally, we consider a general interval system of linear equations $\text{\boldmath$A$}x=\text{\boldmath$b$}$, with an essentially interval matrix, i. e., when $\mathrm{rad}\,\text{\boldmath$A$}\neq 0$. In view of the properties of the tolerable solution set (see, e. g., [15]), it can be represented as

$$\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})\ =\ \bigcap_{A\in\text{\boldmath$A$}}\;\bigl{\{}\,x\in\mathbb{R}^{n}\mid Ax\in\text{\boldmath$b$}\,\bigr{\}}\ =\ \bigcap_{A\in\text{\boldmath$A$}}\varXi_{tol}(A,\text{\boldmath$b$}),$$

(19)

i. e., as the intersection of the solution sets to the individual systems $Ax=b$ with point matrices $A\in\text{\boldmath$A$}$.

For each interval linear system $Ax=\text{\boldmath$b$}$ with $A\in\text{\boldmath$A$}$, we have estimate (18), if $A$ has full column rank. Otherwise, if the point matrix $A$ has incomplete column rank and the corresponding solution set $\varXi_{tol}(A,\text{\boldmath$b$})$ is unbounded, then we do not take it into account. Consequently, for the tolerable solution set of the system $\text{\boldmath$A$}x=\text{\boldmath$b$}$, which is the intersection of the solution sets $\varXi_{tol}(A,\text{\boldmath$b$})$ for all $A\in\text{\boldmath$A$}$, the following should be true:

$$\|x^{\prime}-\hat{x}\|_{2}\ \lessapprox\ \min_{A\in\text{\boldmath$A$}}\,\left\{\;\sqrt{n}\;\,\mathrm{cond}_{2}A\cdot\bigl{\|}\,\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,\bigr{\|}_{2}\cdot\frac{\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,}{\|\hat{\text{\boldmath$b$}}\|_{2}}\,\right\}.$$

(20)

The transition from representation (19) to inequality (20) can be both very accurate and rather crude (as can be seen from considering the intersection of two 1D intervals). It all depends on the size of the intersection of the solution sets of individual systems $Ax=\text{\boldmath$b$}$. On the other hand, the amount of this intersection is indirectly characterized by the magnitude of $\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,$.

Taking the above facts into account, we perform approximate estimation of the right-hand side of inequality (20) by moving the minimum over $A\in\text{\boldmath$A$}$ through the curly brackets. First of all, we evaluate the factor $\|\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,\|_{2}$, which changes to the smallest extent, by the constant available to us after the numerical solution of the data fitting problem:

$$\bigl{\|}\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,(x,A,\text{\boldmath$b$})\bigr{\|}_{2}\,\approx\;\mathrm{const}\;=\;\bigl{\|}\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$})\bigr{\|}_{2}.$$

(21)

Next, the minimum of $\mathrm{cond}_{2}A$ naturally turns to $\min\mathrm{cond}_{2}A$, and the most important factor $\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,(x,A,\text{\boldmath$b$})$ will be changed to $\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,(x,\text{\boldmath$A$},\text{\boldmath$b$})$. This choice (as well as (21)) is rather rigidly determined by the following reasons.

The expression for our variability measure should preserve its simplicity and be uniform for all cases and situations. In particular, if the interval matrix $A$ squeezes to a point matrix $A$, then our measure should turn to the estimate (18) for the point case. Finally, if $\max\,\mathrm{Tol}\,=0$, then our measure must be zero too, since the size of the (stable) tolerable solution set is also zero, and our variability measure should reliably detect such situations. All this taken together leads to the estimate

$$\|x^{\prime}-\hat{x}\|_{2}\;\,\lessapprox\ \sqrt{n}\ \Bigl{(}\;\min_{A\in\text{\boldmath$A$}}\,\mathrm{cond}_{2}A\,\Bigr{)}\cdot\bigl{\|}\,\arg\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,\bigr{\|}_{2}\cdot\frac{\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,}{\|\hat{\text{\boldmath$b$}}\|_{2}}.$$

(22)

The same estimate as (22), by virtue of the equivalence inequality (17), is also true for the Chebyshev norm:

$$\max_{x^{\prime}\in\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})}\|x^{\prime}-\hat{x}\|_{\infty}\ \lessapprox\ \sqrt{n}\;\,\Bigl{(}\;\min_{A\in\text{\boldmath$A$}}\,\mathrm{cond}_{2}\,A\,\Bigr{)}\cdot\bigl{\|}\,\arg\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,\bigr{\|}_{2}\cdot\frac{\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,}{\|\hat{\text{\boldmath$b$}}\|_{2}}.$$

This completes the rationale for (6).

If we want to evaluate the relative size of the tolerable solution set, expressing it in ratio to the norm of its points, then it is reasonable to take $\hat{x}=\arg\max_{x\in\mathbb{R}^{n}}\mathrm{Tol}\,$ as the “most typical” point from the tolerable solution set $\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})$. Using (17) again, we obtain

$$\frac{\max_{x^{\prime}\in\varXi_{tol}(\text{\boldmath$A$},\text{\boldmath$b$})}\|x^{\prime}-x^{\prime\prime}\|_{\infty}}{\|\hat{x}\|_{\infty}}\ \lessapprox\ n\;\Bigl{(}\;\min_{A\in\text{\boldmath$A$}}\,\mathrm{cond}_{2}A\,\Bigr{)}\cdot\frac{\max_{x\in\mathbb{R}^{n}}\,\mathrm{Tol}\,}{\|\hat{\text{\boldmath$b$}}\|_{2}}.$$

This gives value (8).