PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations linéaires u Affichage des résultats (tp 1 a) u Élimination de Gauss u Élimination

PROGRAMMATION SCIENTIFIQUE EN C

PRO-1027

Résolution de système d’équations linéaires

Affichage des résultats (tp 1 a) Élimination de Gauss Élimination de Gauss avec pivot Travail pratique 1 b

Affichage des résultats

Affichage de données réellesfloat epsilon1;

double epsilon2;

epsilon1 = 0.00000011921;

epsilon2 = 0.00000000000000022204;

printf("\n Valeur de epsilon1: %13.11f ",epsilon1);

printf("\n Valeur de epsilon2: %22.20f ",epsilon2);

Élimination de Gauss

Exemple de système d’équations linéaires– Un alliage est composé de manganène, silice et de

cuivre

– Cet alliage est composé de 15 livres de Mn, 22 livres de Si et 39 livres de Cu par tonne d’alliage

– Les ingrédients de l’alliage (Mn, Si, Cu) sont extraits de minerai provenant de 3 fournisseurs différents

– De plus, la concentration des ingrédients est différente pour les 3 minerais


Fournisseur 1(lb/tonne de minerai)



Manganèse 1 3 2Silice 2 4 3Cuivre 3 4 7

Nous voulons alors déterminer quelle quantité de minerai nous devons acheter de chaque fournisseur pour éviter l’achat inutile d’ingrédient


Pour trouver une solution à ce problème nous devons définir les variables suivantes:

– Xj: la quantité de minerai achetée du fournisseur j (tonne de minerai)

– Ci: la quantité d’ingrédient i par tonne d’alliage (lb/ tonne d’alliage)

– aij: la quantité d’ingrédient i par tonne de minerai achetée du fournisseur j (lb/tonne de minerai)


Nous pouvons déduire une expression générale pour le calcul des Ci

mi

CXa ij

n

jij

,......,2,1

1

m représente le nombre d’ingrédients et n le nombre de fournisseurs


Le problème précédent peut être représenté par un système d’équations linéaires de la forme

39743

22342

1523

321

321

321

XXX

XXX

XXX

La solution de ce système correspond aux quantités de minerai à acheter de chaque fournisseur


Détermination des courants dans un circuit électrique

4042

6502

0

321

321

321

III

III

III


Forme générale d’un système d’équations linéaires

nnnnnn

nn

nn

CXaXaXa

CXaXaXa

CXaXaXa

.....

.....

.....

2211

22222121

11212111


Solution de 2 équations (n=2)

2222121

1212111

CXaXa

CXaXa

Isolons X2 de la seconde équation

22

12122 a

XaCX

Substituons X2 de la première équation

122

121212111 C

a

XaCaXa


Nous pouvons alors isoler X1

12212211

2121221 aaaa

CaCaX

Nous pouvons alors déduire X2 par

12212211

1212112 aaaa

CaCaX


Classification des systèmes d’équations– Systèmes ayant des solutions

– Systèmes sans solution

– Systèmes avec une infinité de solutions



L’élimination de Gauss est similaire à la procé-dure de substitution utilisée précédemment pour déduire les valeurs de X1 et X2

L’élimination consiste à effectuer un ensemble d’opérations valides sur les équations pour arriver à obtenir une matrice dont la partie triangulaire inférieure (sous la diagonale) est nulle et une diagonale à 1 (Gauss-Jordan)

Nous pouvons alors isoler chacune de nos inconnues


Opérations valides sur les équations– Permuter deux équations

– Multiplier ou diviser une équation par une constante

– Additionner deux équations ensembles


Représentation matricielle d’un système d’équations linéaires

nnnnnn

n

n

C

C

C

X

X

X

aaa

aaa

aaa

2

1

2

1

21

22221

11211


Représentation sous forme de matrice augmen-tée

nnnnn

n

n

C

C

C

aaa

aaa

aaa

2

1

21

22221

11211


La procédure d’élimination de Gauss est subdi-visée en une phase d’élimination avant suivie d’une phase de substitution arrière. Avec l’élimination avant nous obtenons un système

n

n

n

e

e

e

d

dd

2

1

2

112

100

10

1


Si nous réinsérons les inconnues nous obtenons le système d’équations suivant

1,111,122,13132121 eXdXdXdXdXdX nnnnnn

2,211,222,23232 eXdXdXdXdX nnnnnn

3,311,322,33 eXdXdXdX nnnnnn

2,211,22 nnnnnnnn eXdXdX

1,11 nnnnn eXdX

nn eX


A partir du système précédent, nous pouvons déduire les inconnues Xi en commençant par l’inconnue Xn et par substitution arrière les autres inconnues X1 … Xn-1

nn eX

nnnnn XdeX ,111


L’élimination de Gauss appliquée à un circuit électrique (phase d’élimination avant)

4260

6720

0111

'2'

'2'

'

4042

6502

0111

133

122

11

RRR

RRR

RR

141900

32

710

0111

'6'2

'

'

4260

6720

0111

233

22

11

RRR

RR

RR

19

14100

32

710

0111

19'

'

'

141900

32

710

0111

33

22

11

RR

RR

RR


Algorithme d’élimination de Gauss (élimination avant)

Entrées: matrice A de nxn et un vecteur C de n éléments

Élimination avant

POUR j=1à n-1 FAIRE /* Pour chaque élément de la diagonale */

POUR i=j+1 à n FAIRE /* Pour chaque rangée sous la diagonale */

mij = aij/ajj

aij = 0; Ci = Ci - mij * Cj

POUR k = j+1 à n FAIRE /* Pour les éléments restant de la rangée i */

aik = aik - mij * ajk


Algorithme d’élimination de Gauss (substitution arrière)

Substitution arrière

POUR i= n à 1 FAIRE

xi=Ci

POUR j=i+1 à n FAIRE

xi = xi - aij * xj

xi = xi/aii

Sortie: vecteur x des solutions


Problèmes d’erreurs– Représentation des nombres

– Utilisation de pivot très petit (division par 0) Pour minimiser ces problèmes nous pouvons

utiliser l’élimination de Gauss avec pivot


Problèmes d’erreurs (exemple)

0.6

9.3

3.13

0303

10182

0637

3

2

1

x

x

x

En arithmétique exacte, la première étape de l’élimination donne

3.0030

1.01000

3.1306377

3,

7

23121 mm


Problèmes d’erreurs (exemple)– La dernière étape produit un élément diagonal

a22 nul

– L’élément pivot (diagonal) de la prochaine étape est donc nul

– Le rapport m23 = 3/0 ce qui cause erreur de division par 0


Nous pouvons corriger cette anomalie en permutant les rangées 2 et 3 permettant de déduire le vecteur solution exacte

01.0

1.0

1

x


Sur l’ordinateur, les rapports 2/7 et 3/7 ne sont pas représentés avec exactitude ce qui produit un élément diagonal a22 très petit. L’élimination avant peut quand même se poursuivre produi-sant des solutions erronnées

01000.0

10547.0

95078.0

10031.112031.100000.000000.0

01000.101000.111910.200000.0

01330.100000.001300.600000.7

x

EEEE

EEEE

EEEE

Élimination de Gauss avec pivot

Pour éviter les problèmes liés à l’utilisation de pivots petits nous devons avant chaque étape de l,élimination chercher la rangée dont la valeur pivot est maximale

Élimination avant

POUR j=1à n-1 FAIRE /* Pour chaque élément de la diagonale */

trouver_pivot(n,j,A,kp)./*rangée où se trouve le pivot max */

Permuter les rangées j et kp

POUR i=j+1 à n FAIRE /* Pour chaque rangée sous la diagonale */

mij = aij/ajj

aij = 0; Ci = Ci - mij * Cj

POUR k = j+1 à n FAIRE /* Pour les éléments restant de la rangée i */

aik = aik - mij * ajk

Élimination de Gauss avec pivot

trouver_pivot(n,j,A,kp)

pivot = abs(A[j][j])

kp=j

POUR i=j+1à n FAIRE /* Pour chaque rangé sous la diagonale */

SI abs(A[i][j])>pivot ALORS

pivot = abs(A[i][j])

kp = i

FINSI

FIN POUR

Travail pratique 1b

Documents

PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations linéaires u Affichage des résultats (tp 1 a) u Élimination de Gauss u Élimination