Mathematical background

Consider a system of $n$ equations $F_1,\ldots,F_n$ in the $m$ unknowns $X=\{x_1,\ldots,x_m\}$ such that the $F_i$ may be written as:

$$F_i = G_i(X) + a_0+\sum a_j x_j$$

$F_i$ is the sum of the non-linear function $G_i$ and of the linear terms with coefficients $a_j$. Let the interval evaluation of $G_i$ be $[\underline{G_i},\overline{G_i}]$: we define a new variable $Y_i$ as $Y_i = G_i-\underline{G_i}$, which imply $Y_i \ge 0$. $F_i$ may now be written as the sum of linear term:

$$F_i = Y_i +a_0+\underline{G_i}+\sum a_j x_j$$

Hence the system is now a linear system with the additional constraint that $Y_1 \ge 0, \ldots, Y_n\ge 0$. We may now apply a well-known method in linear programming: the simplex method which can be used to find the minimum or maximum of a linear function under the $m_1$ equality constraints $G_1(X)=0,\ldots, G_{m_1}(X)=0$ and the $m_2$ inequality constraints $K_1(X)\ge 0, \ldots, K_{m_2}(X) \ge 0$. There are two phases in the simplex method: phase I verifies if a feasible solution exists and phase II is used to determine the extremum of the linear function.

In our case we may use only phase I or phase I and II by considering the $2m$ optimum problems which are to determine the minimum and maximum of the $m$ unknowns under the $2n$ constraints $F_i(X)=0, Y_i(X)=0$ and update the interval for an unknown if the simplex applied to minimize or maximize enable to improve the range. It may be seen that this is a recursive procedure: an improvement on one variable change the constraint equations and may thus change the result of the simplex method applied for determining the extremum of a variable which has already been considered.

This procedure, proposed in [25], enable to correct one of the drawback of the general solving procedures: each equation is considered independently and for given intervals for the unknowns two equations may have an interval evaluation that contain 0 although these equations cannot be canceled at the same time. The previous method enable to take into account at least partly the dependence of the equations. Clearly it will more efficient if the functions has a large number of linear terms and a "small" non-linear part.

In all of the following procedures the various storage mode and bisection mode of the general solving procedures may be used and inequalities are handled.