Exemples d'utilisation de l'analyse par intervalles

Catégorie: calcul sur les valeurs des racines d'un polynôme paramétré, vérification sur les valeurs de la plus petite et de la plus grande racine réelle

Applications:: vérification du conditionnement d'un robot

Date: Juillet 2002

Note préliminaire: L'analyse par intervalle peut être vue comme une approche possible pour résoudre des problèmes ayant été formulés dans le but premier de le résoudre avec une autre méthode. Mais dans de nombreux cas il sera possible de reformuler le problème de manière plus appropriée à l'analyse par intervalles, avec des gains de performance parfois très importants. En ce sens l'analyse par intervalle n'est plus une boîte noire que l'on appelle de manière aveugle mais devient un "art" qui nécessite d'être maîtrisé. Les exemples de ce document veulent illustrer cet aspect: ils ont été choisis pour leur simplicité mais peuvent être étendus à des cas beaucoup plus complexes pour lesquelles l'analyse par intervalle est probablement la seule à pouvoir apporter une réponse.

Les algorithmes proposés dans ce document ne sont que des "maquettes": une implantation efficace ferait appel à de multiples outils de l'analyse par intervalles qui en améliorerait sensiblement l'efficacité, mais dont l'exposé dépasserait les objectifs de ce document.

Une autre difficulté de l'analyse par intervalles est qu'il est difficile de prédire à-priori l'efficacité des méthodes et de déterminer parmi l'ensemble des méthodes possibles celle qui sera la plus efficace, voire même si l'analyse par intervalle ne sera pas mis en échec: l'honnêteté nous impose de mentionner cette possibilité même si nous estimons que cette approche mérite d'être testée car elle est souvent très compétitive par rapport à d'autres approches, et est parfois, à notre connaissance, la seule qui puisse apporter éventuellement une réponse.

Enfin une grosse limitation de l'analyse par intervalles est la nécessité de pouvoir définir des bornes sur les inconnues. Cette limitation est parfois un avantage car elle permet de concentrer les recherches sur un domaine d'intérêt et les exemples proposés illustreront le fait que dans certains cas des bornes peuvent être trouées facilement.

Ce document a été rédigé dans le cadre du programme ROBEA-MAX du CNRS et les exemples proposés sont dérivés d'un problème posé par l'équipe de l'IRCYNN de Nantes.

On va donner ici quelques exemples de méthodes permettant de vérifier certains résultats sur le conditionnement du robot. Le conditionnement du robot est défini par les racines d'un polynôme (qui est le polynôme caractéristique d'une certaine matrice, même si nous n'utiliserons pas cette propriété). Les coefficients de ce polynômes sont des fonctions des paramètres définissant la position/orientation de l'organe terminal du robot.

Les méthodes donnés ici illustrent certains principes de base de l'analyse par intervalles qui vont permettre d'obtenir des résultats sur les racines de polynômes paramétrés.

Pour illustrer ces méthodes nous choisissons un robot à 2 degrés de liberté x et y dont le polynôme caractéristique P sera supposé être le suivant:

P=l²-2 ly-2 l-3 xl+6 xy+3 x+2 y+1

Une pose du robot est définie par la donnée de valeurs pour x, y. On remarque qu'ici les coefficients du polynôme sont des fonctions algébriques de x,y: cela n'est en aucun cas une obligation et les algorithmes que nous allons présenter marcherait à l'identique si le polynôme était,par exemple P=l²-l(2cos(y)-3x)+6xsin(y)+2cosh(y)+1

On supposera le lecteur familier avec les principes élémentaires de l'arithmétique d'intervalles qui permettent de calculer un majorant et un minorant de toute expression mathématique si les inconnues de l'expression sont contraintes à être dans des intervalles. L'annexe à la fin de ce document fournira quelques indications sur la mise en oeuvre informatique des méthodes.

1 Le problème M1

1.1 Le problème

Le problème M1 est le suivant: étant donné un rectangle R en x, y définissant un ensemble de pose possible pour le robot existe t'il dans le rectangle au moins une pose où une racine de P est plus grande que 2 ? Si c'est le cas on dira que le rectangle est invalide alors qu'un rectangle pour lequel on peut garantir qu'il ne contient que des poses pour lesquels les racines de P sont inférieures à 2 sera valide.

On verra que l'algorithme proposé permettrait de résoudre le problème identique où l'on désire déterminer si une racine de P est plus petite que 1/4.

Préalable:

Le polynôme P s'écrit

P= l²+a₁ l+ a₀

avec

		a₁=(-2y-2-3x)
		a₀=(2y+1)(3x+1)

Le théorème de Cauchy indique que les racines l de P vérifie:

|l| < 1+ Max{|a₁|,|a0|}

Étant donné des intervalles pour x, y on pourra donc trouver un majorant A pour les l (il faut aussi indiquer que les bornes présentées ci-dessus ne sont pas les meilleures: la bibliothèque ALIAS propose un algorithme qui applique tout une panoplie de théorème sur les bornes des racines d'un polynôme univarié).

1.2 L'algorithme

Notation:

une boîte B est un ensemble d'intervalles pour x,y,l

On va utiliser ici une liste L de boîtes. Cette liste contient initialement une seule boîte qui est constituée du rectangle R et pour l de l'intervalle [2,A]. Au cours du déroulement de l'algorithme on adjoindra à la liste L d'autres boîtes et n désigne le nombre total de boîte présente dans L, B_i désignant la boîte de numéro i de L.

si i>n: SORTIR EN INDIQUANT QUE LE RECTANGLE EST VALIDE
prendre comme valeur pour x,y le centre des intervalles pour ces inconnues
résoudre P numériquement
si une racine de P vérifie l>2: SORTIR EN INDIQUANT QUE LE RECTANGLE EST INVALIDE
sinon: soit G l'évaluation par intervalles de P en B_i
si G ne contient pas 0, alors i =i+1 et aller en 1
sinon: prendre la variable dont l'intervalle est le plus large et créer 2 nouvelles boîtes en coupant son intervalle en deux. Ces 2 boîtes sont rajoutées à L, n=n+2, i =i+1 et aller en 1

1.3 Exemple pratique

Examinons le cas où R est un rectangle défini par x dans [0,0.2] et y dans [-0.1,0].

Les coefficients du polynômes sont alors:

a₁	=	(-2y-2-3x)=-2[-0.1,0]-2-3[0,0.2]=[0,0.2]-2-[0,0.6]=[-2.6,-1.8]
a₀	=	(2y+1)(3x+1)=(2[-0.1,0]+1)(3[0,0.2]+1)=([0.8,1])([1,1.6])=[0.8,1.6]

La valeur absolue des racines du polynôme étant inférieures à 1+ Max{|a₁|,|a0|} on a:

|l|<1 +Max{|[-2.6,-1.8]|,|[0.8,1.6]|}=3.6

La boîte initiale de l'algorithme est donc:

B₁={[0,0.2], [-0.1,0], [2,3.6]}

Au centre du rectangle (x=0.1, y=-0.05) les racines du polynôme sont 0.9, 1.3 donc bien inférieures à 2.

On va donc calculer des bornes pour P lors x,y, l sont dans les intervalles de B₁. Ici il faut attirer l'attention sur le fait que la manière d'écrire P joue un rôle sur son évaluation par intervalle. Par exemple si l'on écrit P sous la forme:

P=l²-2 ly-2 l-3 xl+6 xy+3 x+2 y+1

on obtient [-4.68,11.28] comme évaluation pour P lorsque x,y, l sont les intervalles de B₁

Par contre si l'on écrit P sous la forme (que nous utiliserons maintenant):

(

-2+l

)

(

-2 l+2

)

(

6 y+3-3 l

)

on obtient [-0.68,7.28] comme résultat de l'évaluation.

A ce stade on ne peut pas conclure: on est à l'étape 7 de l'algorithme. L'intervalle pour l étant le plus large on va le couper en 2. La liste L contient maintenant 3 boîtes:

		B₁={[0,0.2], [-0.1,0], [2,3.6]}
		B₂={[0,0.2], [-0.1,0], [2.8,3.6]}
		B₃={[0,0.2], [-0.1,0], [2,2.8]}

et nous avons à examiner les boîtes à partir de B₂. L'évaluation par intervalle de P en B₂ est [1.56,7.28]: on peut donc garantir que quelle que soit les valeurs de x dans [0,0.2] et de y dans [-0.1,0] il n'existe aucune racine de P dans l'intervalle [2.8,3.6].

On examine alors B₃: l'évaluation de P pour cette boîte est [-0.2,3.6]. Il nous donc encore bissecter et la liste L contient maintenant 5 boîtes:

		B₁={[0,0.2], [-0.1,0], [2,3.6]}
		B₂={[0,0.2], [-0.1,0], [2.8,3.6]}
		B₃={[0,0.2], [-0.1,0], [2,2.8]}
		B₄={[0,0.2], [-0.1,0], [2.4,2.8]}
		B₅={[0,0.2], [-0.1,0], [2,2.4]}

et nous traitons la boîte B₄. L'évaluation de P pour cette boîte est [0.76,3.6]: on peut donc passer à la boîte B₅. Pour celle ci l'évaluation de P est [0.04,2.24]. A ce stade on a examiné l'ensemble des boîtes de L (on est à l'étape 1 de l'algorithme): on peut donc conclure que le rectangle est valide.

1.4 Étendre et améliorer l'algorithme

1.4.1 Améliorer l'algorithme

Il y a de multiples astuces possibles pour améliorer le fonctionnement de l'algorithme et je me contenterais d'en donner une, que l'on appelle la méthode 2B dans le jargon de l'analyse par intervalles.

Si l'on reprend le polynôme P on voit que l'on pourrait l'écrire sous la forme

l²= 2 l-1+

(

2 l-2

)

(

-6 y-3+3 l

)

Soit U le terme de droite et V le terme de gauche. Si x, y, l sont dans des intervalles et qu'il des valeurs de ces variables pour lesquels P s'annule, alors les évaluations par intervalles de U, V doivent avoir une intersection. Soit [a,b] l'évaluation par intervalle de U et [e,f] celle de V. Si P a une solution ou des solutions en l alors l'évaluation de U doit avoir une intersection avec V. On peut remplacer U par l'intersection de U, V. Si cette intersection est plus petite que U (qui représente le carré de l) on pourra éventuellement remplacer l'intervalle par l par un intervalle plus petit.

Reprenons l'exemple précédent où l est dans l'intervalle [2,3.6], x dans [0,0.2] et y dans [-0.1,0]. L'évaluation de U pour cet intervalle est [4,12.96] et celle de V [1.68,8.68]. Le carré de l doit donc se trouver dans l'intervalle [4,8.68], dont on déduit que l doit se trouver dans l'intervalle [2,2.946183973]. Et l'on peut itérer le processus puisqu'en modifiant l'intervalle pour l on vient de modifier l'évaluation par intervalle de V qui passe à [1.81,6.98]. Le carré de l se trouve à l'intersection de l'intervalle pour U [4,8.68] et de l'intervalle pour V [1.81,6.98], donc dans [4,6.98]. On en déduit que l doit se trouver dans l'intervalle [2,2.6419]. Si l'on itérait le processus on obtiendrait que l'intervalle pour l est [2,2.487794064], puis [2,2.405881245]. On voit que l'amélioration sur l'intervalle pour l décroît rapidement: on a donc intérêt à alterner bissection et utilisation de la technique 2B pour obtenir la meilleure efficacité.

Une autre technique d'amélioration consiste à utiliser les dérivées des expressions. La dérivée de P par rapport à l est:

2 l-2 y-2-3 x

Si l'on évalue cette expression pour l dans [2,3.6], x dans [0,0.2] et y dans [-0.1,0] on obtient [1.4,5.4]. Cela veut dire que la dérivée est toujours positive quelque soit la valeur de x, y, l. La valeur minimum du polynôme sera donc obtenu pour l ayant la valeur la plus petite dans l'intervalle alors que la valeur maximum le sera pour l le plus grand dans l'intervalle. Pour l=2 et x dans [0,0.2], y dans [-0.1,0] on obtient que P est dans [0.28,1.2]: cela veut dire que quelle que soit l dans [2,3.6], x dans [0,0.2] et y dans [-0.1,0], P sera supérieur ou égal à 0.28 et ne s'annulera donc jamais. On peut donc directement conclure que le rectangle est valide.

Un autre type d'amélioration possible repose sur une implantation distribuée de l'algorithme. En effet on remarque que dans l'algorithme le traitement d'une boîte est indépendant ce celui des autres boîtes: on pourrait alors l'utilisation d'un programme maître sur un ordinateur qui gérerait la liste des boîtes de L et distribuerait vers des ordinateurs esclaves le traitement des boîtes de L. La bibliothèque ALIAS permet d'ailleurs d'utiliser une implantation distribuée pour la plus grosse majorité de ces algorithme directement à partir de Maple en utilisant le mécanisme de transmission de messages PVM

D'autres améliorations pourraient porter sur le choix de la variable qui est coupée lors d'une bissection (choisir celle dont l'intervalle est le plus large n'est pas forcément le meilleur choix) ou sur la manière dont est gérée la liste L (il existe par exemple des possibilités qui assurent que si l'algorithme échoue cela ne sera pas en raison d'une manque de mémoire pour stocker les boîtes dans L).

1.4.2 Étendre l'algorithme

A partir de l'algorithme de base on peut étendre les fonctionnalités. Tout d'abord il apparaît clairement que dans le principe on peut parfaitement utiliser le même algorithme pour des polynômes de plus haut degré et avec plus de paramètres.

On pourrait aussi procéder à une vérification de la valeur minimum de la racine, par exemple vérifier que dans le rectangle toutes les racines sont supérieures à 1/4. En effet on pourrait trouver une borne B sur la valeur inférieure des racines de P, initialiser L avec une boîte dont l'intervalle pour l serait [B,1/4] et remplacer le test de l'étape 4 par: si une racine de P vérifie l<1/4.

De la même manière on pourrait vérifier dans un seul algorithme si les racines de P sont inférieures à 2 et supérieures à 1/4. Pour cela il faudrait initialiser L avec deux boîtes, l'une contenant comme intervalle pour l [2,A] et l'autre [B,1/4] avec comme test à l'étape 4: si une racine de P vérifie l<1/4 ou si si une racine de P vérifie l>2.

On pourrait aussi imposer des contraintes supplémentaires au problème. Par exemple on pourrait s'imposer de vérifier que les racines de P soit inférieures à 2 dans le rectangle mais uniquement pour les poses vérifiant x²+y² inférieure ou égale à 0.02

Pour cela il suffirait de rajouter une étape directement après l'étape 1 de l'algorithme:

soit G l'évaluation par intervalle de x²+y²: si la borne supérieure de G est supérieure à 0.02 alors aller directement à l'étape 5

Le but de cette étape est simplement d'éviter l'application du test sur la valeur des racines pour des boîtes donc le rectangle en x, y contient des poses ne satisfaisant pas l'inégalité. Toutefois on s'assure en allant à l'étape 5 que cette boîte puisse éventuellement contenir des poses où le polynôme peut avoir des racines contenues dans l'intervalle pour l, donc éventuellement supérieure à 2.

1.5 Les échecs

L'algorithme M1 tel que décrit pourrait être mis en échec par exemple si la pose où une racine est supérieure à 2 est un coin du rectangle et qu'en ce point une racine du polynôme est effectivement supérieure à 2 mais avec un écart avec 2 qui serait en dessous de la précision machine. Certaines méthodes de l'analyse par intervalle permettraient de détecter ce problème sans toutefois que l'on puisse déterminer avec exactitude si la racine est inférieure ou supérieure à 2. Dans ce cas l'algorithme signalerait qu'il ne peut pas conclure (c'est l'intérêt de la certification qu'apporte l'analyse par intervalles) et il conviendrait de traiter de manière particulière ce type de cas. Des solutions sont possibles (par exemple utiliser une arithmétique multi-précision comme cela sera proposé prochainement dans ALIAS avec l'utilisation de MPFI pour l'arithmétique d'intervalles à la place de BIAS/Profil).

1.6 Traitement par ALIAS

Le problème présenté peut être directement traité par ALIAS, soit en utilisant sa couche C++, soit directement à partir de son interface Maple. En effet les procédures MinMax_Polynom, MinMax_Polynom_Gradient permettent de calculer à une précision e près les valeurs minimale et maximal des racines réelles d'un polynôme paramétré. Une option permet d'ailleurs de spécifier l'arrêt de l'algorithme dès que l'extremum courant est plus grand ou plus petit qu'une valeur fixée.

2 Le problème M2

2.1 Le problème

Étant donné des valeurs x₁, y₁ pour x, y définissant une pose X telles que les racines du polynôme en cette pose soient inférieures à 2, trouver le plus grand carré centré en X tel que pour toutes les poses du carré les racines du polynôme soient inférieures à 2.

Ce que nous allons calculer est en fait un carré valide dont l'arête sera de longueur R tel que pour un e donné le carré ayant une arête de longueur R+e contiendra des poses avec des racines du polynôme supérieure à 2. La valeur de e définit donc la précision avec laquelle nous calculons le plus grand carré.

2.2 L'algorithme

Notation:

C(r): carré centré en X d'arête de longueur r
M1(C(r)): application de l'algorithme M1 au carré centré en X d'arête r. L'algorithme retourne VALIDE si le carré ne contient pas de pose où au moins une racine du polynôme est supérieure à 2

k=1, r=R=R₁=0, R=0
si R-R₁=e alors SORTIR: le plus grand carré trouvé a comme arête R₁
si M1(C(r+ke))=VALIDE alors R₁=r+ke, k=2k,R=r=r+ke et répéter
sinon poser r=R₁, k=1, aller en 2

Le principe est très simple: puisque l'on dispose de l'algorithme M1 qui permet de tester si un carré est valide on teste successivement avec M1 les carrés d'arête e, 3e, 7e, 15 e,.. jusqu'à ce l'on arrivé à un carré invalide à l'itération j. A ce stade on sait que le carré d'arête R₁=(2^j-1-1)e est valide alors que celui d'arête (2^j-1)e ne l'est pas. Partant de l'arête R₁ on réitère l'algorithme en ajoutant successivement e, 2e,...à la valeur courante de l'arête jusqu'à ce que l'écart entre l'arête du carré invalide et du et celle du dernier carré valide soit e (test de l'étape 2).

2.3 Exemple pratique

On définit la pose X par les valeurs x=0, y=0. En cette pose les racines du polynômes sont 1,1 et satisfont donc nos hypothèses. On pose e=0.1.

On commence donc par examiner le carré défini par x dans [-0.05,0.05], y dans [-0.05,0.05]. On trouve alors que a₁ est dans [-2.25,-1.75] et a₀ dans [0.735,1.265]. La valeur maximum des racines de P est donc 3.25. Pour l dans l'intervalle [2,3.25] on trouve que l'évaluation du polynôme est [0.4225,5.64]. L'algorithme M1 retourne donc VALIDE. On essaye alors le carré défini par x dans [-0.15,0.15], y dans [-0.15,0.15] qui est VALIDE, puis le le carré d'arête 0.7 (x dans [-0.35,0.35], y dans [-0.35,0.35]) qui lui ne l'est pas: par exemple pour x=0.34, y= 0 une racine est 2.02. On essaye alors le carré d'arête 0.4 qui est VALIDE, puis d'arête 0.6 qui l'est aussi. A ce stade on aurait à tester le carré d'arête 1 mais cela n'est pas nécessaire puisque l'on sait que le carré d'arête 0.7 n'est pas valide. On peut donc directement indiquer que le plus grand carré a une longueur d'arête 0.6 +[0,0.1[.

2.4 Amélioration et Généralisation

2.4.1 Amélioration

Une amélioration importante concerne le test M1. En effet à partir du moment où ce test à indiqué à l'étape j-1 que le carré d'arête 2^j-1-1 était valide il convient de considérer à l'étape j qu'une partie du carré d'arête 2^j-1 a déjà été testé pour la validité. Il faut donc simplement utiliser le test M1 sur la différence entre le carré d'arête 2^j-1 et celui d'arête 2^j-1-1. Pour cela une méthode simple repose sur une analyse des bornes sur les intervalles pour x, y. Soit [x₁-u,x₁+u] l'intervalle définissant les bornes en x pour le carré valide à l'étape j-1 et un intervalle [f,g] pour x lorsque l'on examine dans M1 le carré à l'étape j: on peut alors réduire l'intervalle pour x en suivant les règles suivantes:

si f<x₁-u et g<x₁+u alors remplacer g par x₁-u
si f>x₁-u et g>x₁+u alors remplacer f par x₁+u

De plus si f>x₁-u et g<x₁+u on peut passer directement à l'examen de la boîte suivante dans la liste.

Ainsi dans l'exemple précédent après avoir vérifié que le carré d'arête 0.3 pour lequel x est défini par [-0.15,0.15] est valide on passe à la vérification du carré d'arête 0.7 par l'algorithme M1. Lors de ce test on est amené à considérer un carré dont les coordonnées en x sont définies par l'intervalle [0,0.7]: cet intervalle peut être substitué par l'intervalle [0.15,0.7].

Une autre amélioration consisterait à permettre un calcul incrémental, c'est-à-dire de permettre le calcul de M1 pour une précision donné en réutilisant les résultats d'un calcul précédent obtenus pour une précision plus grossière. En effet on pourrait démarrer l'algorithme en fournissant un carré dont on sait qu'il est déjà valide.

2.4.2 Généralisation

Nous avons déjà vu dans l'algorithme M1 que l'on pouvait introduire des contraintes supplémentaires, comme par exemple introduire une contrainte supplémentaire de type x²+y² inférieure ou égal à un seuil. On pourrait de la même manière introduire comme contrainte supplémentaire (x-x₁)²+(y-y₁)² inférieur ou égal à r: dans ce cas l'algorithme M1 teste la validité non pas du carré d'arête r mais du cercle inscrit dans ce carré. Avec cet adaptation l'algorithme M2 détermine le rayon du plus grand cercle où les poses sont toutes valides.

3 Le problème M3

Il s'agit d'une généralisation du problème M2.

3.1 Le problème

Trouver le plus grand carré tel que pour toutes les poses du carré les racines du polynôme soient inférieures à 2.

De la même manière que pour M2 nous étudierons le problème de déterminer l'arête du plus grand carré avec une précision e fixée à l'avance.

3.2 Un squelette d'algorithme

Notre propos est plutôt ici de montrer comment on pourrait construire un algorithme pour M3 sans entrer dans tous les détails. On est de plus obligé de fournir des contraintes sur l'espace de recherche: on supposera donc que x, y sont bornés et que W sera le rectangle dans lequel on cherchera le carré le plus grand, alors que R sera l'arête du carré le plus grand.

Tout d'abord on peut minorer R en choisissant (par tirage au hasard par exemple) une pose X dans laquelle les racines du polynôme sont inférieures à 2. En appliquant l'algorithme M2 on peut alors construire le plus grand carré valide centré en X et la longueur r de ce carré constitue un minorant de R.

On peut ensuite utiliser un algorithme où les boîtes sont constituées de 2 intervalles pour x, y qui vont représenter les coordonnées du centre du carré le plus grand.

Une possibilité de filtrage va s'appliquer sur les boîtes pour lesquelles la largeur la plus grande des intervalles est inférieure à r. On va calculer numériquement les racines de P aux 4 coins de la boîte: si pour au moins un de ces coins une des racines est supérieure à 2 alors la boîte ne pourra pas contenir le centre d'un carré valide d'arête plus grande que r puisqu'un tel carré contiendrait le coin où les racines ne sont pas valides.

La mise à jour de r pourrait ensuite être effectuée en exécutant l'algorithme M2 en prenant comme centre du carré le centre des boîtes qui ont passé le premier filtrage. Une seconde possibilité de filtrage s'offre alors: si d est la largeur de l'intervalle le plus large de la boîte et r_c la longueur de l'arête du carré obtenue par M2 pour le centre de la boîte on peut éliminer la boîte entière si d-r_c < r.

3.3 Traitement par ALIAS

Le problème présenté peut être directement traité par ALIAS, soit en utilisant sa couche C++, soit directement à partir de son interface Maple. En effet la procédure MinMax_Square_Polynom_Gradient permet de calculer le centre et la longueur de l'arête (à une précision e près) du plus grand carré contenu dans l'espace des paramètres tel que tout les polynômes correspondant à un point du carré ont leurs racines réelles toute comprise dans un intervalle donné.

4 Annexes

4.1 Informatique et arithmétique d'intervalles

L'implantation des méthodes proposées dans ce document repose tout d'abord sur la possibilité d'utiliser une arithmétique d'intervalles. Il ne sera pas nécessaire d'implanter une telle arithmétique puisqu'il existe pour cela des logiciels performants. Dans la bibliothèque ALIAS nous utilisons le logiciel BIAS/Profil écrit en C++ qui permet une utilisation simple de l'arithmétique d'intervalles.

Par exemple l'évaluation par intervalles du polynôme utilisé dans ce document s'écrirait simplement:

X=INTERVAL(-0.2,0.);

Y=INTERVAL(-0.1,0.);

L=INTERVAL(2.,3.6);

P=Sqr(L)-2*L*Y-2*L-3*X*L+6*X*Y+3*X+2*Y+1;

où X,Y,L représente les intervalles pour les variables x, y, l et P est l'évaluation par intervalles du polynôme. On pourrait écrire de la même manière:

P=Sqr(L)-L*(Cos(Y)-3*X)+6*X*Sin(Y)+2*Cosh(Y)+1

5 Exemple d'utilisation d'ALIAS

On reprend l'exemple utilisé dans le problème M1. Il peut être résolu directement avec l'interface Maple d'ALIAS. Si l'on suppose que l'on recherche les racines réelles minimale et maximale du polynôme lorsque x,y sont dans l'intervalle [-3,3] on écrirait:

 
with(ALIAS):

P:=l^2-2*l*y-2*l-3*x*l+6*x*y+3*x+2*y+1:

MinMax_Polynom_Gradient([P],[l,x,y],[[-10,10],[-3,3],[-3,3]],2,3,100,10,'Xmin','Ymin','Xmax','Ymax'):

On trouve alors que le minimum est -8 obtenu, par exemple, pour x=-3, y=-3 et que le maximum est 10 obtenu, par exemple, pour x=3, y=-3.

This document was translated from L^AT_EX by H^EV^EA.