No label defined (Q4428070)

The classical ``outer'' problem for the interval linear system \({\mathbf A}x={\mathbf b}\) is under consideration, here \({\mathbf A}\) is an interval matrix, \({\mathbf b}\) is an interval vector, the problem is to find ``good'' coordinate-wise estimates for the set of all solutions of all linear systems \(Ax=b\) with a matrix \(A\in {\mathbf A}\) and a vector \(b\in {\mathbf b}\). It is known that to find a coordinate-wise estimates with any given ratio or absolute error and even to determine is there a solution or not are the problems of class~NP. However, there is a criterion for the existence of a unique algebraic solution in terms of the spectral radii. The author provides a new algebraic approach which is based on the extension of interval arithmetic to the algebraic system with better algebraic properties, in particular, it is a commutative group under the addition. The problem under consideration is reduced to the solving a non-interval equation in the Euclidean space of double dimension. A special algorithm (subdifferential Newton method with a special initial approximation) is constructed. It is proved that under some natural assumptions on the interval \({\mathbf A}\) this algorithm converges to the unique algebraic solution. A modified algorithm which gives estimates of the solution set in more general situation is given and tested. The results of its numerical tests are presented. They show that the proposed algorithm combines high computational efficiency with the good estimates of the solution set.