Principle

Next: Managing the bisection and Up: Mathematical background Previous: Mathematical background

La page de J-P. Merlet

J-P. Merlet home page

La page Présentation de COPRIN

COPRIN home page

La page "Présentation" de l'INRIA

INRIA home page

Principle

Let $x_1,\ldots,x_m$ be the set of unknowns and let ${\cal I}_1=\{(\underline{x_1^1},\overline{x_1^1}), \ldots (\underline{x_m^1},\overline{x_m^1})\}$ be the set of intervals in which you are searching the solutions of the equations ${\cal F}_1(x_1,\ldots,x_m)=0, \ldots {\cal F}_n(x_1,\ldots,x_m)=0$ (for the sake of simplicity we don't consider inequalities but the extension to inequalities is straightforward).

We will denote by the interval value of ${\cal F}_i$ when this function is evaluated for the box $(\underline{x_1},\overline{x_1}),\ldots,(\underline{x_m},\overline{x_m})$ of the unknowns while $F({\cal I}_j)$ will denote the -dimensional interval vector constituted of the when the unknowns have the interval value defined by the set ${\cal I}_j$ .

The algorithm will use a list of boxes ${\cal I}$ whose maximal size is an input of the program. This list is initialized with ${\cal I}_1$ . The number of ${\cal I}$ currently in the list is and therefore at the start of the program . The algorithm will also use an accuracy on the variable $\epsilon$ and on the functions $\epsilon_F$ . The norm of a ${\cal I}$ is defined as:

$\begin{displaymath} \Vert{{\cal I}^j}\Vert={\rm Max}(\overline{x_k^j}-\underline{x_k^j})~~~{\rm for}~k \in [1,m] \end{displaymath}$

The norm of the interval vector $F({\cal I}_j)$ is defined as:

$\begin{displaymath} \uparrow{F({\cal I}_j)}\uparrow ={\rm Max}(\overline{F_k({\cal I}_j)}- \underline{F_k({\cal I}_j)})~~~{\rm for}~k \in [1,n] \end{displaymath}$

The algorithm uses an index

and the result is a set ${\cal S}$ of interval vector ${\cal S}_k$ for the unknowns whose size is

. We assume that there is no

with

such that $\overline{F({\cal I}_1)}<0$ or $\underline{F({\cal I}_1)}>0$ , otherwise the equations have no solution in ${\cal I}_1$ . Two lists of interval vectors ${\cal V}, {\cal W}$ whose size is

will also be used. The algorithm is initialized with

and proceed along the following steps:

if return and ${\cal S}$ and exit
bisect ${\cal I}_i$ which produce new interval vectors ${\cal V}_l$ and set
for
1. evaluate $F({\cal V}_l)$
2. if it exist with in such that $\overline{F_k({\cal V}_l)}<0$ or $\underline{F_k({\cal V}_l)}>0$ , then and go to step 3
3. if $\Vert{{\cal V}_l}\Vert < \epsilon$ or $\uparrow{F({\cal V}_l)}\uparrow <\epsilon_f$ , then store ${\cal V}_l$ in ${\cal S}_S$ , increment and go to step 3
4. store ${\cal V}_l$ in ${\cal W}_j$ , increment and go to step 3
if increment and go to step 1
if return a failure code as there is no space available to store the new intervals
if store one of the ${\cal W}$ in ${\cal I}_i$ , the other at the end of ${\cal I}$ , starting at position . Add to and go to step 1

Basically the algorithm just bisect the box until either their width is lower than $\epsilon$ or the width of the interval function is lower than $\epsilon_f$ (provided that there is enough space in the list to store the intervals). Then if all the intervals functions contain 0 we get a new solution, if one of them does not contain 0 there is no solution of the equations within the current box. A special case occurs when all the components of the box are reduced to a point, in which case a solution is obtained if the absolute value of the interval evaluation of the function is lower than $\epsilon_f$ .

Now three problems have to be dealt with:

how to choose the ${\cal W}$ which will be put in place of the ${\cal I}_i$ and in which order to store the other ${\cal W}$ at the end of the list?
can we improve the management of the bisection process in order to conclude the algorithm with a limited number ?
how do we distinguish distinct solutions ?

The first two problems will be addressed in the next section.