Mathematical background

Let us assume that we have an $n \times n$ interval linear system:

$${\bf A}({\bf X}). Y = b({\bf X})$$ (7.1)

where the ${\bf A}, b$ elements are functions of the unknowns ${\bf X}$. The above equation describes a family of linear system and the enclosure of this interval linear system is a box that enclose the solutions for $Y$ of each member of the family of linear systems.

A classical scheme for finding the enclosure is to use an interval variant of the Gauss elimination scheme [18].

When the unknowns lie in given ranges we may compute an interval evaluation ${\bf A}^{(0)}$ of ${\bf A}$ and an interval evaluation $b^{(0)}$ of $b$. The Gauss elimination scheme may be written as [18]

$$A_{ik}^{(j)}=A_{ik}^{(j-1)}-A_{ij}^{(j-1)}A_{jk}^{(j-1)}/A_{jj}^{(j-1)} ~~\forall~i~ {\rm with}~j>k$$ (7.2)

$$b_i^{(j)}=b_i^{(j-1)}-A_{ij}^{(j-1)}b_j^{(j-1)}/A_{jj}^{(j-1)}$$ (7.3)

The enclosure of the variable $Y_j$ can then be obtained from $Y_{j+1},\ldots,Y_n$ by

$$Y_j=(b_j^{(j-1)}-\sum_{k>j} A_{jk}^{(j-1)}Y_k)/A_{jj}^{(j-1)}$$ (7.4)

Note that the elements at iteration $j$ can be computed only if the interval $A_{jj}^{(j-1)}$ does not include 0.

A drawback of this scheme is that the family of linear systems that will be obtained for all instances of ${\bf X}$ is usually a subset of the family of linear systems defined by ${\bf A}^{(0)}$, $b^{(0)}$, as we do not take into account the dependency of the elements of ${\bf A}, b$. Furthermore the calculation in the scheme involves products, sums and ratio of elements of ${\bf A}, b$ and their direct interval evaluation again do not take into account the dependency between the elements. Hence a direct application of the Gauss scheme will usually lead to an overestimation of the enclosure.

A possible method to reduce this overestimation is to consider the system

$$J{\bf A}({\bf X}). Y = J b({\bf X})$$

where $J$ is an arbitrary $n \times n$ matrix. The above system has the same solutions than the system (7.1) but for some matrix $J$ the enclosure of the above interval system may be included in the enclosure obtained by the Gauss elimination scheme on the initial system: this is called a pre-conditioning of the initial system. It is usually considered that a good candidate for $J$ is the matrix whose elements are the mid-point of the ranges for the elements of ${\bf A}$.

But even with a possible good $J$ the dependency between the elements of ${\bf A}, b$ are not taken into account and hence the overestimation of the enclosure may be large.

A first possible way to reduce this overestimation is to improve the interval evaluation of ${\bf A}^{(0)}$, $b^{(0)}$ by using the derivatives of their elements with respect to ${\bf X}$ and the procedure described in section 2.4.2.3. Note that the procedures necessary to compute the elements of ${\bf A}^{(0)}$, $b^{(0)}$ and their derivatives may be obtained by using the MakeF, MakeJ procedures of ALIAS-maple.

But to improve the efficiency of the procedure it must be noticed that at iteration $j$ an interval evaluation of the derivatives of $A_{ik}, b_i$ with respect to ${\bf X}$ may be deduced for the derivatives of the elements computed at iteration $j-1$. As we have the derivatives of the elements at iteration 0 we may then deduce the derivatives of the elements at any iteration and use these derivatives to improve the interval evaluation of these elements (see sections 2.4.1.1 and 2.4.2.3).