Asymptotically Optimal Algorithm for Checking Whether a Given Vector Is a Solution to a Given Interval-Quanti er Linear System

In many practical situations, we have a linear dependence between different quantities. In such situations, we often need to solve the corre-sponding systems of linear equations. Often, we know the parameters of these equations with interval uncertainty. In this case, depending on the practical problem, we have different notions of a solution. For example, if we determine parameters from observations, we are interested in all the unknowns xj which satisfy the given system of linear equations for some possible values of the parameters. If we design a system so that it does not exceed given tolerance bounds, then we need to make sure that for all possible values of the design parameters there exist possible values of the outcome parameters for which the system is satisfied, etc. In general, we can have an arbitrary sequence of quantifiers corresponding to different parameters. The resulting systems are known as interval-quantifier linear systems