ArithmØtiqueparintervalles, rØsolutiondesystmeslinØaires ...

Publié par

DEA, Supérieur, Diplôme d'études approfondies (DEA) (bac+5)
  • rapport de stage - matière potentielle : dea d' informatique fondamentale
  • cours - matière potentielle : l' exécution du programme
ArithmØtique par intervalles, rØsolution de systŁmes linØaires et prØcision Rapport de stage de DEA d'Informatique fondamentale DESSART Nathalie encadré par Nathalie Revol Arénaire/LIP 30 Juin 2004 1
  • structure de la matrice de départ
  • réflexion sur le problème d'adaptation de la précision
  • bn 
  • méthode de gauss-seidel
  • arithmétique par intervalles
  • intervalle
  • intervalles
  • matrice
  • matrices
  • réflexion
  • réflexions
  • calculs
  • calcul
  • méthode
  • méthodes
Publié le : mercredi 28 mars 2012
Lecture(s) : 37
Source : ens-lyon.fr
Nombre de pages : 27
Voir plus Voir moins










ArithmØtique par intervalles,
rØsolution de systŁmes linØaires
et prØcision
Rapport de stage de DEA d’Informatique fondamentale
DESSART Nathalie
encadrØ par Nathalie Revol
ArØnaire/LIP
30 Juin 2004
1Table des matiŁres
1 Introduction 4
2 tat de l’art et notions essentielles 5
2.1 ArithmØtiques traditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 ArithmØtique par intervalles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 PrØsentation, points forts et points faibles . . . . . . . . . . . . . . . . . . . 6
2.2.2 DØ nitions et opØrations sur les intervalles . . . . . . . . . . . . . . . . . . 6
3 RØsolution de systŁmes linØaires 8
3.1 Quelques notions clØs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 DØ nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 MØthodes pour la rØsolution de systŁmes linØaires . . . . . . . . . . . . . . . . . . . 9
3.3.1 DØ nitions : algorithmes direct et itØratif. . . . . . . . . . . . . . . . . . . . 9
3.3.2 MØthode directe de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3.3 de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 RØsolution des systŁmes linØaires avec intervalles. . . . . . . . . . . . . . . . . . . . 15
3.4.1 DØ nition de la rØsolution d’un systŁme linØaire par intervalles . . . . . . . . 15
3.4.2 SystŁmes linØaires et intervalles . . . . . . . . . . . . . . . . . . . . . . . . 16
4 RØsumØ 18
5 Mise en oeuvre et contributions 19
5.1 Implantations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1.1 Contexte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1.2 Programmation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 Raf nement des calculs et prØcision. . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2.1 PrØcision des nombres ottants. . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2.2 La multi-prØcision. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Adapter dynamiquement la prØcision . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.1 But recherchØ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.2 Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6 Conclusion 25
A Installation des bibliothŁques 26
21 Introduction
Le but de ce stage de DEA est de rØsoudre des systŁmes linØaires en utilisant l’arithmØtique par
intervalles pour obtenir des rØsultats ables, et une prØcision de calcul arbitrairement grande pour ob-
tenir des rØsultats prØcis.
Le besoin s’est fait sentir d’introduire l’arithmØtique par intervalles a n de mener des calculs qui ga-
rantissent au mieux les rØsultats en bornant les erreurs d’arrondis. En effet certains calculs nØcessitent
une prØcision et une abilitØ trŁs poussØes. L’incident le plus citØ dans la littØrature est celui du missile
"Patriot" qui du fait d’une erreur d’arrondi a causØ la mort de 28 soldats amØricains : "On February
25, 1991, a Patriot missile defense system [. . . ] failed to track and intercept an incoming Scud. This
Scud subsequently hit an Army barracks killing 28 Americans" [20]. D’autres exemples existent pour
illustrer l’importance de pallier le problŁme des erreurs d’arrondi et de la nØcessitØ de calculs ables
et prØcis.
Tout d’abord il a ØtØ question de s’immerger dans le monde du calcul par intervalles. Cette Øtude
bibliographique a ØtØ suivie de l’implantation de quelques algorithmes basØs sur des mØthodes exis-
tantes de rØsolution de systŁmes linØaires manipulant des matrices d’ØlØments de types standard et
de type intervalle. Au terme de cela, a ØtØ menØe une rØ exion sur le problŁme d’adaptation de la
prØcision.
Dans une premiŁre partie de ce rapport l’arithmØtique par intervalles sera introduite et dØcrite. Puis
nous prØsenterons deux mØthodes existantes de rØsolution de systŁmes linØaires pour l’arithmØtique
ottante. Nous exposerons ces mØthodes dans leur adaptation à l’arithmØtique par intervalles. En n
nous verrons les rØ exions et mises en oeuvre qui constituent l’objet de ce stage ainsi que les implan-
tations effectuØes. Ces rØ exions se sont basØes sur l’idØe qu’il faudrait faire Øvoluer la prØcision des
calculs au fur et à mesure de l’exØcution, a n d’obtenir des rØsultats plus prØcis lorsque l’on mani-
pule des intervalles. Pour cela, il a fallu implanter des mØthodes de rØsolution de systŁmes linØaires et
d’observer alors quand et comment on pourrait faire varier la prØcision dans le but de parvenir à avoir
un rØsultat à la fois able et prØcis.
32 tat de l’art et notions essentielles
2.1 ArithmØtiques traditionnelles
Voici quelques arithmØtiques traditionnellement utilisØes sur ordinateur :
– l’arithmØtique ottante : manipule des nombres reprØsentØs sous la forme d’un signe, d’une
mantisse et d’un exposant. Cette notation permet des calculs simples et rapides du fait d’une
reprØsentation xe des nombres et donc d’une implØmentation de bas niveau, trŁs ef cace.
Ces deux critŁres font d’elle, l’arithmØtique la plus adaptØe pour les calculs Ønormes . Cette
arithmØtique (reprØsentation, arrondis, . . .) a ØtØ normalisØe dans la norme IEEE-754 [22].
Le schØma suivant donne la reprØsentation des nombres en arithmØtique ottante.
signe Exposant Mantisse
exposantLe nombre ottant ainsi reprØsentØ vaut : signe x mantisse xB oøB est la base utilisØe
pour reprØsenter les nombres (le plus souventB = 2).
– l’arithmØtique exacte : manipule des entiers et des rationnels et garantit un rØsultat exact car les
nombres sont reprØsentØs de fa on exacte. Elle est implantØe uniquement en logiciel et est donc
lente.
– l’arithmØtique multi-prØcision : il s’agit d’une arithmØtique ottante dans laquelle on peut spØ-
ci er une prØcision plus grande que celle disponible en machine. Cette prØcision peut-Œtre sta-
tique ou dynamique. Elle est statique si elle est choisie au dØpart et n’Øvolue pas par la suite et
dynamique si elle Øvolue au cours de l’exØcution du programme.
Le choix de l’utilisation d’une arithmØtique particuliŁre se fait en tenant compte du type de pro-
blŁme que l’on a à rØsoudre. On peut vouloir prendre en compte des incertitudes de mesures, ou
vouloir un rØsultat exact, ou bien encore effectuer des calculs avec une grande prØcision.
L’arihtmØtique par intervalles, elle, plut t que de fournir un rØsultat prØcis, veut garantir la abilitØ
de ce dernier. Son introduction permettrait de abiliser davantage certains calculs devant l’Œtre, comme
par exemple la trajectoire d’un missile, et de plus majorer les incorrections dues aux erreurs d’arrondis.
42.2 ArithmØtique par intervalles
2.2.1 PrØsentation, points forts et points faibles
Introduite par R.Moore (1959), l’arithmØtique par intervalles, comme son nom le suggŁre, fait in-
tervenir des intervalles et non plus les types standard. L’idØe est d’une part de garantir les rØsultats en
calculant un intervalle dans lequel se trouve le rØsultat effectif. D’autre part, on cherche à fournir un
encadrement satisfaisant de la solution et à avoir un rØsultat suf samment prØcis. On cherche à borner
les erreurs d’arrondi dues principalement dans notre cas à l’arithmØtique ottante, à la manipulation
de donnØes de grande taille et à un nombre important de calculs effectuØs sur ces donnØes.
L’arithmØtique par intervalles a ØtØ introduite pour fournir une alternative aux arithmØtiques exis-
tantes. En effet, seule l’arithmØtique exacte rØpond à un besoin de abilitØ mais elle est lente et ne
permet pas d’Øvaluer les fonctions mathØmatiques (sin, exp . . .) mŒme si elle permet de les manipuler.
Cette arithmØtique permet de manipuler des volumes relativement importants de donnØes mais
constitue surtout une arithmØtique dont l’axe central est de garantir la abilitØ des rØsultats quand
bien mŒme ceux-ci ne s’avŁrent pas prØcis. Le principal point faible de l’arithmØtique par intervalles
est cet encadrement que l’on obtient de la solution. En effet on peut obtenir un intervalle beaucoup
trop large qui entra neune grande imprØcision sur le rØsultat. Les calculs doivent donc Œtre menØs de
telle sorte que l’encadrement obtenu soit de largeur raisonnable.
L’arithmØtique par intervalles est prØsente trŁs t t dans la littØrature [15][16][17][18][19]. Brian Hayes
propose dans [7] un historique de l’arithmØtique par intervalles.
Dans la partie suivante nous dØ nirons ce qu’est un intervalle et verrons quelques-unes des opØ-
rations disponibles sur les intervalles et utiles par la suite.
2.2.2 DØ nitions et opØrations sur les intervalles
Un intervalle X = [x,x ] est dØ ni comme suit :x etx sont les extrØmitØs de X et X={x2R/xxx }.
fl fl flLe tableau 1 ØnumŁre diffØrentes notions liØes à celle d’intervalle.
description reprØsentation valeur
milieu de l’intervalle X mid(X) (x+x)/2

largeur de X w(X) x-x

rayon de X rad(X) w(X)/2
mignitude de X mig(X) min{jxj/x2 X}
distance de Hausdorff entre 2 intervalles d(X,Y) max{jx-yj,jx-yj}
fl fl
TAB. 1 – Notions liØes aux intervalles.
5Aux notions prØsentØes dans le tableau ci-dessus viennent s’ajouter les opØrations usuelles. Ces
opØrations sont ØnumØrØes de fa on sØlective et non exhaustive dans le tableau 2. La dØ nition d’une
opØration est la suivante si X et Y sont deux intervalles :
XY= { X Yn x2 X , y2 Y }
TAB. 2 – DØ nition des opØrations sur les intervalles.
description symbole valeur
addition X+Y [(x+y),(x+y)]
fl flsoustraction X-Y [(x-y),(x-y)]
fl flmultiplication X*Y [min(x*y,x*y,x*y,x*y),max(fl x*y,x*y,x*y,x*y)]
fl fl fl flfl fl fl fldivision X/Y [min(x/y,x/y,x/y,x/y),max(x/y,x/y,x/y,x/y)] et 02= Y
fl fl fl flfl fl fl flvaleur absolue jXj min{jxj/x2 X}
2 2 2 2 2 2 2carrØ X [x ,x ] siX 0,[x ,x ] siX 0 et [0,max(x ,x )] si 02X
fl fl fl
Les fonctions ØlØmentaires sont disponibles pour les intervalles comme par exemple, le sinus ou
le cosinus, l’exponentielle et le logarithme nØpØrien.
Une autre dØ nition est qu’un intervalle X est positif (respectivement nØgatif) si et seulement si :
8x2X; x> 0 (respectivement8x2X,x< 0).
Notons que certaines propriØtØs des opØrations, vraies dans le cadre de l’arithmØtique exacte, ne le
sont plus dans le cadre de l’arithmØtique par intervalles. Par exemple si X, Y et Z sont des intervalles.
X*(Y+Z) XY + XZ
mais il n’y a pas nØcessairement ØgalitØ.
Il n’y a plus distributivitØ mais sous-distributivitØ de la multiplication par rapport à l’addition.
Le problŁme qui nous intØresse est la rØsolution de systŁmes linØaires. Nous verrons dans la section
suivante quelques mØthodes existantes pour la rØsolution des systŁmes linØaires. Les mØthodes prØ-
sentØes, celle de Gauss et celle de Gauss-Seidel, sont celles qui ont ØtØ implantØes dans les diffØrents
algorithmes rØalisØs.
66
3 RØsolution de systŁmes linØaires
3.1 Quelques notions clØs
Voici quelques types de matrices utilisØes par la suite :
P
– matrice diagonale dominante : matrice M vØri ant)jM j > jM j (i2f1:::ng)ii ijj=i
0 1
4 1 1 1
B C1 5 1 1B Cexemple :M =@ A1 1 7 3
2 1 1 6
– matrice creuse : matrice M comportant une majoritØ de 0
– matrice triangulaire supØrieure : matrice M vØri ant)M = 08j <iij
– matrice infØrieure : matrice M vØri ant)M = 08i <jij
0 1 0 1
1 2 3 4 11 0 0 0
B C B C0 5 6 7 12 13 0 0B C B Cexemples :TS = TI =@ A @ A0 0 8 9 14 15 16 0
0 0 0 10 17 18 19 20
3.2 DØ nition
Un systŁme linØaire carrØ de dimension n est un ensemble de n Øquations à n inconnues :
8
2x +3y z = 1<
S : x 2y +z = 2
:
x +y 2z = 0:
Le systŁme S peut Œtre alors Øcrit matriciellement sous la forme Ax = b avec :
0 1 0 1
a ::: ::: a b11 n1 1
B C B C: ::: ::: ::: :B C B C
B C B CA = : ::: ::: ::: b = :B C B C
@ A @ A: ::: ::: ::: :
a ::: ::: a b1n nn n
7pour notre exemple :
0 1 0 1
2 3 1 1
@ A @ AA = 1 2 1 b = 2S S
1 1 2 0
Il s’agit alors de rØsoudre A.x=b avec x le vecteur solution :
0 1
x1
B C:B Cx =@ A:
xn
Il existe de nombreuses mØthodes pour la rØsolution des systŁmes linØaires, citons : la mØthode de
Jacobi, les mØthodes de relaxation, la mØthode de Gauss ou bien encore la mØthode de Gauss-Seidel,
les mØthodes de Krylov, GMRES . . .Ces derniŁres mØthodes sont basØes sur des orthogonalisations,
qui ne peuvent pas Œtre utilisØes en arithmØtique par intervalles et ne seront donc pas considØrØes.
Dans la section suivante les mØthodes de Gauss et de Gauss-Seidel seront prØsentØes.
3.3 MØthodes pour la rØsolution de systŁmes linØaires
3.3.1 DØ nitions : algorithmes direct et itØratif.
Il est nØcessaire de dØ nir le type d’algorithme que l’on est amenØ à utiliser. Dans [3] les dØ ni-
tions suivantes ont ØtØ donnØes :
– Un algorithme direct est un algorithme qui, si l’arithmØtique de la machine utilisØe Øtait exacte,
donnerait la solution du problŁme discret en un nombre ni d’Øtapes. Lorsqu’on utilise un
algorithme direct, il n’y a pas d’erreur de mØthode : les seules erreurs qui apparaissent sont
des erreurs d’arrondi.
– Un algorithme itØratif construit une suite d’approximations qui converge vers un rØsultat cher-
chØ. On arrŒte le calcul lorsque l’on estime qu’une certaine prØcision est atteinte - cette esti-
mation est souvent dØlicate - ou lorsque le nombre d’itØrations effectuØes dØpasse une certaine
limite, ou encore si la suite d’approximations ne converge pas.
8Le choix du type d’algorithme dØpend de ce que l’on veut rØsoudre tout autant que le type d’arith-
mØtique car suivant certains critŁres, tels que la structure de la matrice de dØpart, l’un ou l’autre type
d’algorithme est plus adØquat.
Voyons maintenant deux mØthodes de rØsolution de systŁmes linØaires et leurs caractØristiques.
3.3.2 MØthode directe de Gauss
L’algorithme de Gauss, le plus connu, est un algorithme direct. Ici, une inconnue est exprimØe en
fonction des autres, et, par substitution on dØtermine la valeur de chacune d’entre elles. La mØthode
de Gauss, ou mØthode du pivot de Gauss, a pour point central le choix du pivot qui ne doit pas Œtre
nul. Ce choix peut Œtre :
– partiel si on cherche le pivot seulement dans la ligne ou la colonne courante ; dans ce cas les
2Øchanges s’appliquent soit aux lignes soit aux colonnes (nØcessiten opØrations)
– total si on cherche le pivot parmi tous les ØlØments restants ; dans ce cas on permute lignes et
3colonnes (nØcessiten opØrations)
Le mØthode du pivot partiel est plus souvent implØmentØe car elle met en jeu un nombre de calculs
plus petit et sa stabilitØ numØrique est souvent satisfaisante.
Dans tous les cas il est plus judicieux de prendre le pivot le plus grand en terme de valeur absolue a n
de minimiser les erreurs d’arrondi.
Le choix du pivot se traduit par l’application d’opØrations (permutations) sur les lignes, les colonnes
ou les deux à la fois.
Soit :
0 1
a ::: ::: a11 n1
B Ca a ::: :::12 22B CA =@ A::: ::: ::: :::
a a ::: a1n 2n nn
emeLes opØrations permises sont les suivantes, avecL lai ligne de A et un rØel :i
L L +L ; 2<i i j
Pour simpli er les calculs, on cherche à remplacer le systŁme de dØpart par un systŁme Øquivalent
plus simple à rØsoudre. L’ idØe est de calculer la dØcomposition LU de la matrice A, c’est- -dire d’ob-
tenir deux matrices, l’une triangulaire supØrieure (U), l’autre triangulaire infØrieure (L) telles que leur
9produit L x U soit Øgal à A. Il reste à rØsoudre deux systŁmes linØaires, l’un infØrieur et l’autre supØ-
rieur, ce qui est facile.
Les diffØrentes Øtapes sont explicitØes ci-dessous.
tape 1 : calculer la dØcomposition LU de la matrice A, à l’Øtape k
On cherche à calculer :
la matrice L (triangulaire infØrieure) et la matrice U (triangulaire infØrieure)
0 1 0 1
1 0 0 0 ::: 0 u u ::: ::: ::: u11 12 1n
B C B Cl 1 0 0 ::: 0 0 u u u ::: u21 22 23 24 2nB C B C
B C B C::: ::: 1 0 ::: 0 0 0 u ::: ::: :::iiB C B C
B C B C::: ::: ::: 1 ::: ::: 0 ::: 0 u ::: :::jjB C B C
@ A @ A::: ::: ::: ::: 1 ::: 0 ::: ::: ::: u un 1;n 1 n 1;n
l ::: ::: ::: l 1 0 ::: ::: ::: 0 u1n n 1;n nn
Pntelles que A= L*U. En effectuant le produit de L et U, l’Øquationa = l u 8i;j seij ik kjk=0
dØcompose comme suit de par la structure particuliŁre des matrices L et U.
8 Pk<i l u sii<j carl =0> ik kj ijk=0>>>>>< Pk<ja = l u sii>j caru =0ij ik kj ijk=0>>>>> P: k<i l u si i=j:ik kik=0
Ce qui mŁne à :
Pk<min(i;j)a = l u 8i;jij ik kjk=0
Ceci permet de calculer les matrices L et U en initialisant la matrice LU à l’identitØ.
La matrice LU stocke en fait les deux matrices L et U dans une seule et mŒme matrice comme suit :
la U est stockØe dans la partie triangulaire supØrieure et la matrice L est stockØe dans la partie
triangulaire infØrieure. La diagonale de L n’Øtant composØe que de 1 n’est pas explicitement.
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.