Abstract FR:

Cette these est consacree au calcul de solutions numeriques (resolution) de systemes de formules arithmetiques non-lineaires sur les reels (contraintes), au moyen de contraintes d'intervalles. Ce terme generique designe un ensemble de methodes de resolution couplant des techniques issues de l'analyse (methode de newton, algorithmes de bisection) et des algorithmes d'intelligence artificielle (consistance de problemes de satisfaction de contraintes), ou l'arithmetique des machines en virgule flottante est remplacee par l'arithmetique des intervalles. Ainsi, elles sont flexibles dans le sens ou elles fournissent un moyen de combiner des calculs de resolveurs heterogenes, et fiables car les solutions recherchees sont toujours contenues dans les intervalles calcules, mais leur efficacite depend fortement de la forme syntaxique des contraintes. D'une part, nous proposons la transformation symbolique d'equations polynomiales pour ameliorer la precision et la rapidite des calculs numeriques. Les transformations utilisees sont des generations de redondances par des bases de grobner, des combinaisons lineaires, factorisations et disjonctions de contraintes. En pratique, les performances varient suivant la forme syntaxique des contraintes initiales, et se degradent en meme temps que l'explosion du calcul des bases de grobner. Des heuristiques sont mises en uvre pour limiter cette complexite pratique, en appliquant les algorithmes sur des sous-ensembles des contraintes donnees et en stoppant les calculs suivant la qualite ou le nombre des polynomes generes. D'autre part, nous montrons comment eviter des calculs relativement complexes de la methode de newton par le biais de transformations symboliques de contraintes contenant des occurrences simples de variables. Il en resulte un nouvel algorithme de consistance sur les intervalles pour lequel une strategie de propagation efficace est proposee. Une implantation demontre une acceleration moyenne d'un ordre de grandeur. Enfin, la cooperation de ces differents outils symboliques et numeriques est etudiee formellement. Ils sont implantes dans notre systeme cosinus et interfaces au moyen d'un petit langage declaratif permettant la description des problemes de contraintes et la programmation des strategies de cooperation des resolveurs.