rapport TP .pdf



Nom original: rapport_TP.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.14, et a été envoyé sur fichier-pdf.fr le 27/10/2015 à 16:44, depuis l'adresse IP 194.57.x.x. La présente page de téléchargement du fichier a été vue 727 fois.
Taille du document: 997 Ko (22 pages).
Confidentialité: fichier public


Aperçu du document


Compte rendue
présenté par
Idriss HASSINE

&
Safa el Khayati

Modélisation et évaluation des systèmes informatiques
Encadrant

Mr. Christophe GUYEUX

Année Universitaire 2014/2015

Table des matières

Introduction générale

1

1

.
.
.
.
.
.
.

2
2
2
2
4
6
6
7

.
.
.
.
.
.
.

8
8
8
8
9
11
11
13

.
.
.
.
.

15
15
15
15
17
18

2

3

Calcul matricielle
1.1 Introduction . . . . . . . . . . . . . . . . . . . . .
1.2 Résolution des systèmes linéaires . . . . . . . . . .
1.2.1 Méthode du pivot de Gauss . . . . . . . . .
1.2.2 Méthode de Gauss jordan . . . . . . . . . .
1.3 Calcul de déterminants . . . . . . . . . . . . . . .
1.3.1 En utilisant la méthode de pivot gauss . . .
1.3.2 En utilisant l’algorithme de Jordan-Bareiss

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

Décomposition matricielle
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Décomposition LU . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Existanse de la décomposition . . . . . . . . . . . . . . . . .
2.2.2 LU moyennant la méthode de pivot . . . . . . . . . . . . . .
2.3 La décomposition QR . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Préliminaire : Procédé d’orthonrrmalisation de Gran-Schmidt
2.3.2 Présentation de la décomposition QR . . . . . . . . . . . . .
Éléments propres des matrices
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . .
3.2 Diagonalisation . . . . . . . . . . . . . . . . . . . . .
3.2.1 Vérification de l’existence de la diagonalisation
3.2.2 Opération de la diagonalisation . . . . . . . .
3.3 Calcul de la puissance d’une matrice . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

Table des figures

1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8

La méthode du pivot de Gauss . . . . . . . . . . . . . . . . . . . .
Exécution de la code . . . . . . . . . . . . . . . . . . . . . . . . .
La méthode du de Gauss jordan . . . . . . . . . . . . . . . . . . . .
La méthode du de Gauss jordan . . . . . . . . . . . . . . . . . . . .
Calcul de déterminant par la méthode de pivot gauss . . . . . . . . .
Calcul de déterminant par la méthode de pivot gauss . . . . . . . . .
Calcul de déterminant par la méthode algorithme de Jordan-Bareiss
Calcul de déterminant par l’algorithme de Jordan-Bareiss . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

3
4
5
5
6
6
7
7

2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10

Code existanse de la décomposition LU . . . . . . . . . . . . . . . . . . . . . .
Exécution du code existanse de la décomposition LU . . . . . . . . . . . . . . .
Code fonctions addrow, mulrow, swaprow, addcol, mulcol et swap . . . . . . . .
Code de la fonction de la décomposition LU par la méthode de pivot . . . . . . .
Exécution du code de la fonction de la décomposition LU par la méthode de pivot
Code de la fonction Gram-Schmidt . . . . . . . . . . . . . . . . . . . . . . . .
Exécution du code de la fonction Gram-Schmidt . . . . . . . . . . . . . . . . . .
Vérification de Gram-Schmidt . . . . . . . . . . . . . . . . . . . . . . . . . . .
Code de la fonction décomposition QR . . . . . . . . . . . . . . . . . . . . . .
Exécution du code de la fonction décomposition QR . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

9
9
10
10
11
12
12
13
14
14

3.1
3.2
3.3
3.4
3.5
3.6

Code de la fonction de vérification de la diagonalisation
Code exécution du fonction diag_verif pour la matrice A
Code de la fonction de diagonalisation . . . . . . . . . .
Exécution du fonction diagonalisation de la matrice A . .
Code de la fonction puissance . . . . . . . . . . . . . .
Exécution du fonction puissance de la matrice A . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

16
16
17
17
18
19

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

Introduction générale

Ce travail est constitué de trois chapitres.
Le premier chapitre s’interesse au problème du calcule matricielle. On présente dans ce chapitre deux
algorithmes de résolution de systèmes linéaires. Le pivot de Gauss pour triangulariser la matrice et
la méthode de Gauss-Jordan puis on passe pour le calcul du déterminant d’une matrice avec deux
algorithmes : celui de Jordan-Bareiss qui concerne le cas particulier des matrices à cofficients entiers
et celui du pivot de gauss.
Le deuxième chapitre porte sur le problème décomposition matricielle. On va implémenter la décomposition LU par deux algorithmes : par une méthode formelle reposant sur la bibliothèque sympy et
par la méthode du pivot de Gauss. Puis on va implémenter la décomposition QR moyennant le procédé d’orthonrrmalisation de Gran-Schmidt.
Le troisième chapitre s’intéresse au problème de diagonalisation des matrices, extraction des éléments
propres et comment utiliser cette diagonalisation pour calculer la puissance d’une matrice de façon
très facile et moins couteuse.

1

Chapitre

1

Calcul matricielle
1.1

Introduction

Ce chapitre présente deux algorithmes de résolution de systèmes linéaires. Le pivot de Gauss pour
triangulariser la matrice et la méthode de Gauss-Jordan . La deuxième partie du chapitre porte sur le
calcul du déterminant d’une matrice avec deux algorithmes : celui de Jordan-Bareiss qui concerne le
cas particulier des matrices à coefficients entiers et celui du pivot de Gauss.

1.2

Résolution des systèmes linéaires

La résolution des systèmes d’équations linéaires appartient aux problèmes les plus anciens dans
les mathématiques et ceux-ci apparaissent dans beaucoup de domaines, comme en traitement numérique du signal, en optimisation linéaire, ou dans l’approximation de problèmes non linéaires en
analyse numérique.

1.2.1

Méthode du pivot de Gauss

La méthode du pivot de Gauss propose de résoudre un système d’équations en triangonalisant la
matrice contenant les inconnues des équations. La dernière équation devient une simple égalité et on
remonte chaque ligne de la matrice en trouvant le résultat d’une nouvelle inconnue.
La figure 1.1 présente le code de la méthode du pivot de Gauss.

2

F IGURE 1.1 – La méthode du pivot de Gauss
On
 va utiliser ce programme pour résoudre le système suivant :


x + 2y + 2z = 2


x + 3y − 2z = −1



 3x + 5y + 8z = 8
Pourrésoudre le système
 on doit appliquer la fonction pivot_gauss à la matrice M :

2 
 1 2 2

M= 1 3 −2 −1




3 5 8
8

3

F IGURE 1.2 – Exécution de la code



2 
 1 2 2

On a obtenu une matrice
0 1 −4 −3 . On remarque que la matrice M est triangonalisée,




0 0 −2 −1
alors la solution est facile à trouver.
-2*z=-1 alors z= 21
1*y-4*( 12 )=-3 alors y=-1
1*x+2*(-1)+2*( 21 )=2
alors x=3


x=3


d’où la solution est
y = −1



 z= 1
2

Cette méthode ne gère pas le cas où le pivot serait égal à 0 (ce qui conduirait à une division
par zéro). La solution est de chercher un pivot non nul en échangeant les lignes de la matrice. Cette
solution a été implementée dans la méthode suivante et aurait pu l’être aussi ici.

1.2.2

Méthode de Gauss jordan

La méthode Gauss-Jordan est une variante du pivot de Gauss plus pratique en algorithmie. Au lieu
d’effectuer une triangularisation de la matrice on effectue une diagonalisation ce qui nous permet de
trouver le résultat immédiatement.
La figure 1.3 présente le code de la méthode de Gauss jordan.

4

F IGURE 1.3 – La méthode du de Gauss jordan
On va utiliser
 cette méthode pour résoudre le même système linéaire résolu par la méthode de


x + 2y + 2z = 2


pivot de gauss
x + 3y − 2z = −1



 3x + 5y + 8z = 8
Cette fois le résultat va être trouver dés qu’on applique la fonction gauss jordan sur la quatrième
colonne de la matrice comme la figure 1.4 indique.

F IGURE 1.4 – La méthode du de Gauss jordan

5

1.3
1.3.1

Calcul de déterminants
En utilisant la méthode de pivot gauss

Le déterminant d’une matrice triangulaire est le produit des coefficients diagonaux . Donc on peut
utiliser la méthode de pivot gauss et l’aboutir pour le calcul du déterminant.
La figure 1.5 présente le code pour calculer le déterminant moyennant la méthode de pivot gauss.

F IGURE 1.5 – Calcul de déterminant par la méthode de pivot gauss
On trouve le même résultat soit en utilisant notre méthode soit on utilise la fonction det de la
bibliothèque numpy .Ceci est bien expliqué dans la figure 1.6.

F IGURE 1.6 – Calcul de déterminant par la méthode de pivot gauss

6

1.3.2

En utilisant l’algorithme de Jordan-Bareiss

Dans le cas particulier des matrices à coefficients entiers, l’algorithme de Jordan-Bareiss permet
de calculer le déterminant sans passer par les flottants.
La figure 1.7 présente le code pour calculer le déterminant moyennant l’algoriyhme de JordanBareiss.

F IGURE 1.7 – Calcul de déterminant par la méthode algorithme de Jordan-Bareiss
On trouve le même résultat soit en utilisant notre méthode soit on utilise la fonction det de la
bibliothèque numpy .Ceci est bien expliqué dans la figure 1.8.

F IGURE 1.8 – Calcul de déterminant par l’algorithme de Jordan-Bareiss

7

Chapitre

2

Décomposition matricielle
2.1

Introduction

Ce chapitre présente les décompostions de matrices. On va implémenter la décomposition LU par
deux algorithmes : par une méthode formelle reposante sur la bibliothèque sympy et par la méthode
du pivot de Gauss. Il faut noter que dans cette partie on a confronté beaucoup de problèmes à cause de
la bibliothèque sympy, tout d’abord on a trouvé un problème de version car en lançant la commande
aptitude install python-sympy , Mon python télécharge la version 0.7.1 qui manque plusieurs fonctions nécessaires dans notre travail tel que la fonction minorMtrix. Donc on a téléchargé la dernière
version de sympy celle de 0.7.5, un autre problème s’apparaît cette fois celui de trouver le bon lien de
téléchargement car même pour la version 0.7.5 parfois vous trouvez la bibliothèque sympy manque
de ceratins fonctions initiales telque la fonction qui calcule le déterminant. On a trouvé une version
complète dans le liens suivant https ://codeload.github.com/sympy/sympy/zip/master.

2.2

Décomposition LU

Soit A une matrice carrée. On dit que A admet une décomposition LU s’il existe une matrice
triangulaire inférieure formée de 1 sur la diagonale, notée L, et une matrice triangulaire supérieure,
notée U, qui vérifient l’égalité
A=LU.
Cette méthode permet de faciliter la résolution des systèmes linéaires AX=b. car en remplaçant A
par LU on obtient LUX=b donc X=U−1 L−1 b.

2.2.1

Existanse de la décomposition

La décomposition LU n’existe que si les sous-matrices principales de M d’ordre 1 à n-1 sont
inversibles c’est-à-direque leur déterminant
n’est pas nul.


 1 4 3 

Pour la matrice M 1 −1 1 on obtient les mineurs principaux suivant :




0 1 3
8

(

)(
) (
)
−2 1
1 3
1 4
,
et
,on calcule le déterminant de chaque mineur principal, il
1 3
0 3
1 −2
faut que tous les déterminants soient non nuls pour que la décomposition LU existe.
Dans notre cas on a les déterminants suivants : -7,3et -6 on remarque qu’ils ne sont pas nul don la
décomposition en LU existe.

F IGURE 2.1 – Code existanse de la décomposition LU
L’exécution de ce code nous donne :

F IGURE 2.2 – Exécution du code existanse de la décomposition LU

2.2.2

LU moyennant la méthode de pivot

On peut voir la décomposition comme un pivot de Gauss. Il s’agit de trouver la matrice triangulaire
supérieure U comme résultat. Par contre dans la méthode du pivot de Gauss, les opérations effectuées
pour atteindre la matrice triangulaire ne sont pas conservées. La matrice L qui permet de revenir à la
matrice de départ doit donc contenir l’inverse du produit de toutes les opérations élémentaires qui ont
amené à obtenir U.
On commence par définir les fonctions addrow, mulrow, swaprow, addcol, mulcol, swap col pour
effectuer les opérations sur les lignes et les colonnes et faciliter notre développement à la suite.
9

La figure 2.3 montre la strecture et le corps de ces fonctions.

F IGURE 2.3 – Code fonctions addrow, mulrow, swaprow, addcol, mulcol et swap
Le code de la fonction de la décomposition LU par la méthode de pivot est le suivant :

F IGURE 2.4 – Code de la fonction de la décomposition LU par la méthode de pivot


8 5 1




 9 2 1

On applique cette fonction pour la matrice M indiqué dans l’énoncé de TP, M 6 1 4


 7 5 4




9 6 7
10

7
7
4
9
9

9
1
8
6
6

















On obtient le résultat suivant (Figure 2.5) , on vérifit aprés la décomposition si M=L*U.

F IGURE 2.5 – Exécution du code de la fonction de la décomposition LU par la méthode de pivot

2.3
2.3.1

La décomposition QR
Préliminaire : Procédé d’orthonrrmalisation de Gran-Schmidt

L’objectif de cette procédure est de commencer par une famille libre(b1 ,b2 ,...,bk ) et la transformer
en une base orthonormée (e1 ,e2 ,...,ek ) tels que la norme de chaque ei,i∈{1,..k} =1, et les vecteurs de cette


base sont deux à deux orthogaux c’est à dire : ∀ei,i∈{1,..k} , ∀e j, j∈{1,..k}, j6=i , < ei , e j >= 0 .
La méthode de Gram-Schmidt consiste à former une famille orthonormale en "redressant", puis
en normant, progressivement chacun des vecteurs fournis, pour les rendre orthogonaux aux vecteurs
déjà formés.
La figure 2.6 montre le code de procédure de Gram-Schmidt .

11

F IGURE 2.6 – Code de la fonction Gram-Schmidt
Ainsi que l’entré de cette fonction est une matrice qui contient en colonnes la famille des vecteurs
qu’on va les orthonormaliser, la sortie de cette fonction est une matrice qui contient en colonnes les
vecteurs orthonormalisées et orthogonales deux à deux donc ils forment une base orthonormale. on
applique cette méthode au vecteurs [2,1, 2] ,[12, −6, 0]et
 [−3, −3, 18]. Pour effectuer cette opération

 2 12 −3 

on doit les mettre dans une matrice A
1 −6 −3 .




2 0 18
La figure 2.7 montre le résultat de l’exécution ce cette fonction.

F IGURE 2.7 – Exécution du code de la fonction Gram-Schmidt
Une fois le résultat est retourné on peut effectuer une vérification sur les vecteurs retournées :
2 1 2




e0 = 3 , 3 , 3 , e1 = 23 , − 23 , − 13 et e2 = − 31 , − 32 , 23 .
12

Ils doivent être orthogaux (deux à deux) en utilisant la fonction dot( ) qui calcule le produit scalaire
de deux vecteurs : par exemple pour deux vecteurs u et v pour vérifier si ils sont orthogaux il faut que
u.dot(v)=0.
Ils doivent aussi être orthonormalisées en utilisant la fonction c’est à dire leurs normes égales à 1
norm( ) par exemple pour un vecteur u pour qu’il soitt orthonormale il faut que u.norm()=1.
La figure 2.8 montre le résultat de la vérification de cette fonction.

F IGURE 2.8 – Vérification de Gram-Schmidt
Ainsi on remarque qu’on trouver le bon résultat, en fête les trois vecteurs sont tous orthogaux
(deux à deux) et la norme de chaque vecteur est égale à 1.

2.3.2

Présentation de la décomposition QR

L’écriture QR d’une matrice inversible A est intimement liée à l’orthonormalisation de la famille
des vecteurs colonnes de A par Gram-Schmidt. Q est une matrice orthogonale c’est à dire Q*Qt =I
où I est la matrice identité. R est matrice triangulaire supérieur à coefficients diagonaux strictement
positifs.
Soient (a1 ,...,ak ) les vecteurs colonnes de A ; ils forment une base, vu que A est inversible. A peut
être interprétée comme la matrice de passage de la base canonique (e1 ,...,ek ) à la base (a1 ,...,ak ) .
Soient (q1 ,...,qk ) est la base orthonormale trouvé par orthonrrmalisation de (a1 ,...,ak ). On peut
analyser le problème comme suit :
Q est la matrice de passage de la base canonique à la base (q1 ,...,qk ) . Elle doit être orthogonale car il
s’agit d’une matrice de passage entre deux bases orthonormées.
R est une matrice de passage de (q1 ,...,qk ) à (a1 ,...,ak ) . Elle peut être calculé par la multiplication de
la transposé de matrice Q par la matrice A.
La figure 2.9 montre le code du décomposition QR .

13

F IGURE 2.9 – Code de la fonction décomposition QR



 2 12 −3 

On va appliquer la fonction QR_decomp sur la matrice A
1 −6 −3 . On va vérifier par




2 0 18
la suite que le produit Q*R soit égale à la matrice A.
La figure 2.10 montre le résultat de l’exécution du code du décomposition QR .

F IGURE 2.10 – Exécution du code de la fonction décomposition QR
14

Chapitre

3

Éléments propres des matrices
3.1

Introduction

Ce chapitre montre les différentes techniques de calcul des éléments propres d’une matrice donnée, ainsi que des applications associées.

3.2
3.2.1

Diagonalisation
Vérification de l’existence de la diagonalisation

Une matrice est dite diagonalisable si :
— la somme des multiplicités des valeurs propres est égale à la taille de la matrice.
— la somme des dimensions des sous-espaces propres est égale à la taille de la matrice.
On vérifie que le nombre de vecteurs propres de chaque valeur propres est égal à sa multiplicité.
La figure suivante 3.1 montre le code de la fonction diag_verif qui vérifie si une matrice est
diagonalisable ou non en vérifiant si la taille du sous espace de vecteurs propres engendré par chaque
valeur propre est à égale à la multiplicité de valeur propre correspondant ou non.

15

F IGURE 3.1 – Code de la fonction de vérification de la diagonalisation
On remarque que il suffit pour une seule valeur propre la taille de sous espace de vecteurs propres
engendré par la valeur propre correspondante n’est pas égale à sa multiplicité pour que cette fonction
retourne False.




−5
2
4
−4





 10 −3 −6 8 

Par la suite on teste cette fonction sur la matrice A
.


11
−4
−6
8





 22 −8 −14 17 

La figure 3.2 montre le résultat de cette exécution.

F IGURE 3.2 – Code exécution du fonction diag_verif pour la matrice A

16

3.2.2

Opération de la diagonalisation

Le but de la diagonalisation est d’écrire une matrice A sous la forme A=PDP−1 , tels que la matrice
D est diagonale et la matrice P est une matrice de passage de A vers D et elle est construite par les
vecteurs propres en colonnes.

F IGURE 3.3 – Code de la fonction de diagonalisation
Le résultat de cette exécution est dans la figure suivant :

F IGURE 3.4 – Exécution du fonction diagonalisation de la matrice A

17

3.3

Calcul de la puissance d’une matrice

L’objectif principal de la diagonalisation est le calcul de la puissance d’une matrice car en écrivant
une matrice A sous la forme PDP−1 , An est égale à PDn P−1 .
Et comme D est une matricediagonale donc Dn est égale
 à la puissance de n de chaque élément de
d1 0 · · · 0 0 







.


.


0
d
0
0
.


2


..
la diagonale c’est-à-dire si D =
. 0 d3 0 0  alors





..

. 0 


0 0 0






0 · · · 0 0 dn


n
d
0
·
·
·
0
0


1






.


n
.


0
d
0
0
.


2


.
n
n
.
D =
. 0 d3 0 0 .On remarque ainsi que cette opération est plus optimisée et a un





...




0
0
0
0






n
0 · · · 0 0 dn
coût en calcul très petit par rapport à la multiplication n fois de la matrice A.
Le code suivant résume tout ce qu’on a fait pour calculer la puissance d’une matrice par sympy.

F IGURE 3.5 – Code de la fonction puissance




−5
2
4
−4





 10 −3 −6 8 

Dans l’étape suivante on calcule la puissance 10 de la matrice A
.


11
−4
−6
8





 22 −8 −14 17 


18

Et on vérifie si le résulat est vrai ou non en le comparant par le calcul de la multiplication 10 fois
de la matrice A.

F IGURE 3.6 – Exécution du fonction puissance de la matrice A

19


Aperçu du document rapport_TP.pdf - page 1/22

 
rapport_TP.pdf - page 3/22
rapport_TP.pdf - page 4/22
rapport_TP.pdf - page 5/22
rapport_TP.pdf - page 6/22
 




Télécharger le fichier (PDF)


rapport_TP.pdf (PDF, 997 Ko)

Télécharger
Formats alternatifs: ZIP Texte



Documents similaires


rapport tp
exoreduction
program ing cna maths phyik
algebre lineaire
serie 6 valeurs propres vecteurs propres diagonalisation
cours algebre

Sur le même sujet..




🚀  Page générée en 0.01s