1 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

Algori thm ique Numéri que

1. Le produit matriciel

a. Méthode classique

La méthode la plus simple pour calculer unproduit matriciel est de trouver les coefficientsun à un avec la formule ci-contre.

implémentation python avecnumpy

>>> E1 = matrix( ( 2) )>>> E2 = matrix( ( 3) )>>> calc_num. prod_mat_classique( E1, E2)array( [ [ 6. ] ] )

>>> E1 = matrix( ( 1, 2, 3, 4, 5, 6, 7, 8, 9) ) . reshape( 3, 3)>>> E2 = matrix( ( 2, 4, 6, 8, 10, 12, 14, 16, 18) ) . reshape( 3, 3)>>> calc_num. prod_mat_classique( E1, E2)array( [ [ 60. , 72. , 84. ] ,

[ 132. , 162. , 192. ] ,[ 204. , 252. , 300. ] ] )

Exemples

Rapport de TP "Gauss et compagnie"

Ce rapport présente deux algorithmes de produit matriciel (méthode "Classique" et de Strassen) ainsi

que 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 qui diagonalise. La dernière partie porte sur 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.

b. L'algorithme de Strassen

L'algorithme de Strassen permet de calculer un produit matriciel en effectuant moins demultiplications, car la méthode "classique" n'est pas optimale.Cet algorithme ne s'applique que sur les matrices dont la taille est une puissance de 2. Ce n'est pasvraiment une limitation car n'importe quelle matrice peut devenir de cette forme en completant leslignes et les colonnes par des 0.L'algorithme de Strassen est récursif : à chaque étape la matrice est divisée en quatres sous-matrices,l'amélioration consistant à effectuer des opérations plus simples entre celles-ci par rapport à laméthode dite classique. Le cas d'arrêt de la récusivité est celui où les matrices sont de taille 1x1.

Comparatif entre les opérations des 2 méthodes, la méthode de Strassen n'utilise que 7multiplications mais bien plus d'additions.méthode de Strassen méthode classique récursive

3 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

4 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

Comparaison des méthodes classique et Strassen

La complexité du produit classique est grande en O(n3). L'algorithme de Strassen, en économisant unemultiplication coûteuse, permet de réduire cette complexité à O(n2,8) au prix d'un plus grand nombred'opérations d'additions. La différence ne doit apparaitre que sur de grandes matrices.Le temps d'exécution a été obtenu avec le module python timeit et la commande suivante dans uneconsole :

pour la méthode classiquepython - m timeit " import random; from numpy import *; import calc_num; a =random. random( ( 4, 4) ) ; b = random. random( ( 4, 4) ) ; calc_num. prod_mat_classique( a, b) "

pour la méthode de Strassenpython - m timeit " import random; from numpy import *; import calc_num; a =random. random( ( 4, 4) ) ; b = random. random( ( 4, 4) ) ; calc_num. prod_mat_strassen( a, b) "

pour la fonction intégrée de numpy (dot)python - m timeit " import random; from numpy import *; a = random. random( ( 4, 4) ) ; b =random. random( ( 4, 4) ) ; dot( a, b) "

Remarque : Les tests ont été fait sur un ordinateur équipé d'un Athlon XP à 1,3 GHz.classique Strassen dot (numpy)

matrice 4x4 758 usec 2,89 msec 349 usecmatrice 8x8 3,27 msec 19 msec 362 usec

matrice 16x16 22 msec 131 msec 415 usecmatrice 32x32 176 msec 880 msec 622 usecmatrice 64x64 1,43 sec 6,13 sec 1,9 msec

matrice 512x512 2,38 sec

Contrairement à ce qui avaitété imaginé, l'algorithme deStrassen ne prend pas ledessus sur la méthodeclassique.Plusieurs explications sontpossibles :

La récursivité rendl'algorithme de Strassenmoins performant par rapportà celui de la méthodeclassique.

L'implémentation dansun langage interprété commepython ralentit les 2algorithmes et repousse lemoment où l'algorithme deStrassen prend l'avantage.

On remarque que la fonction interne de numpy est clairement plus performante, elle estprobablement compilée. Une version en C de l'algorithme de Strassen a été implementée pour testeravec des matrices plus grandes mais le résultat était le même.

5 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

2. Résolution de systèmes linéaires

a. Méthode du pivot de Gauss

La méthode du pivot de Gauss propose de résoudre un système d'équations en triangonalisant lamatrice contenant les inconnues des équations. La dernière équation devient une simple égalité et onremonte chaque ligne de la matrice en trouvant le résultat d'une nouvelle inconnue.

Exemple avec le systèmed'équation :

La matrice correspondante est lasuivante :>>> Mmatrix( [ [ 1. , 2. , 2. , 2. ] ,

[ 1. , 3. , - 2. , - 1. ] ,[ 3. , 5. , 8. , 8. ] ] )

>>> pivot_gauss( M)matrix( [ [ 1. , 2. , 2. , 2. ] ,

[ 0. , 1. , - 4. , - 3. ] ,[ 0. , 0. , - 2. , - 1. ] ] )

Une fois la matrice triangonalisée, la solution est rapide à trouver :

Remarque : L'algorithme du pivot de Gauss ci-dessus ne gère pas le cas où le pivot serait égal à 0 (cequi conduirai à une divison par zéro). La solution est de chercher un pivot non nul en échangeant leslignes de la matrice. Cette solution a été implementée dans la méthode suivante et aurai pu l'êtreaussi ici.

b. Méthode Gauss- Jordan

La méthode Gauss-Jordan est une variante du pivot de Gauss plus pratique en algorithmie. La matricedes équations est diagonalisée au lieu d'être triangonalisée, la solution du système d'équation estalors immédiate.

Sur l'exemple précedent :>>> E5matrix( [ [ 1. , 2. , 2. , 2. ] ,

[ 1. , 3. , - 2. , - 1. ] ,[ 3. , 5. , 8. , 8. ] ] )

>>> gauss_j ordan( E5)matrix( [ [ 1. , 0. , 0. , 3. ] ,

[ 0. , 1. , 0. , - 1. ] ,[ 0. , 0. , 1. , 0. 5] ] )

6 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

Le problème des très petites valeurs

Lorsque l'équation contient une très petite valeur, il faut éviter del'utiliser comme pivot. Dans l'exemple ci-contre, le coefficent de x esttrès petit par rapport aux autres valeurs.

>>> E6matrix( [ [ 1. 00000000e- 11, 1. 00000000e+00, 1. 00000000e+00] ,

[ 1. 00000000e+00, 1. 00000000e+00, 2. 00000000e+00] ] )>>> gauss_j ordan( E6)matrix( [ [ 1. , 0. , 1. ] ,

[ - 0. , 1. , 1. ] ] )>>> set_printoptions( precision=12, suppress=False)>>> gauss_j ordan( E6)matrix( [ [ 1. , 0. , 1. ] ,

[ - 0. , 1. , 0. 99999999999] ] )

Le calcul de x se fait avec des nombres très petits ettrès grands :>>> ( 2- 10e12) /( 1- 10e12)0. 99999999999989997

La différence entre 2 et 1 se trouve "poussée" très loinaprès la virgule, et lorsque l'on multiplie...>>> ( 2- 10e12) /( 1- 10e12) *10e129999999999999. 0

↑ Il y a perte d'une précision significative>>> 10e12 - ( 2- 10e12) /( 1- 10e12) *10e121. 0 ( la fraction a été " simplifiée" )

Le résultat final est moins précis. Afin de minimiser c'estperte de précision il faut éviter de prendre des pivots trèspetits.

Résolution "à la main" :

7 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

>>> E6matrix( [ [ 1. 000000000000e- 11, 1. 000000000000e+00, 1. 000000000000e+00] ,

[ 1. 000000000000e+00, 1. 000000000000e+00, 2. 000000000000e+00] ] )>>> gauss_j ordan( E6)matrix( [ [ 1. , 0. , 1. 00000000001] ,

[ 0. , 1. , 0. 99999999999] ] )

La valeur de x a changé.

>>> E7matrix( [ [ 10. , 7. , 8. , 7. , 32. ] ,

[ 7. , 5. , 6. , 5. , 23. ] ,[ 9. , 6. , 10. , 9. , 33. ] ,[ 7. , 5. , 9. , 10. , 31. ] ] )

>>> gauss_j ordan( E7)matrix( [ [ 1. , 0. , 0. , 0. , 0. 09] ,

[ 0. , 1. , 0. , 0. , 2. 55] ,[ 0. , 0. , 1. , 0. , 0. 55] ,[ - 0. , - 0. , - 0. , 1. , 1. 27] ] )

>>> E8matrix( [ [ 10. , 7. , 8. , 7. , 32. 1] ,

[ 7. , 5. , 6. , 5. , 22. 9] ,[ 9. , 6. , 10. , 9. , 33. 1] ,[ 7. , 5. , 9. , 10. , 30. 9] ] )

>>> gauss_j ordan( E8)matrix( [ [ 1. , 0. , 0. , 0. , 0. 84] ,

[ 0. , 1. , 0. , 0. , 1. 62] ,[ 0. , 0. , 1. , 0. , 0. 32] ,[ - 0. , - 0. , - 0. , 1. , 1. 41] ] )

L'effet papillon

De petites variations sur les coefficients du système d'équations peuvent provoquer de grandesdifférences sur la résolution. Dans l'exemple qui suit, le vecteur résultat change très peu et pourtantla résolution est différente.

Algorithme modifié

Sur l'exemple précédent, la nouvelle méthode de selection du pivot change le résultat :

Dans cet algorithme, le plusgrand pivot est selectionnépar permutation.

8 / 8rapport de TP "Gauss et Compagnie" - septembre 2008

3. Calcul de déterminants

a. En uti l isant le pivot de Gauss

Dans le cas d'une matrice triangulaire, le calcul du determinant se simplifie en étant égal au produitdes coefficients diagonaux. L'utilisation de l'algorithme du pivot de Gauss précédent permet d'aboutirfacilement à un algorithme de calcul du déterminant.

Exemple :>>> E10matrix( [ [ 1. , 2. , 3. ] ,

[ 4. , 5. , 6. ] ,[ 7. , 8. , 1. ] ] )

>>> det_gauss( E10)24. 0

Calcul du déterminant avec la fonctionintégrée de numpy :>>> from numpy. linalg import *>>> det( E10)23. 999999999999996

b. Algorithme de Jordan-Bareiss

Dans le cas particulier des matrices à coefficients entiers, l'algorithme de Jordan-Bareiss permet decalculer le déterminant sans passer par les flottants. Cet algorithme permet d'obtenir un résultat plusprécis que la méthode précédente du pivot de Gauss.

Exemple :>>> E11matrix( [ [ 1, 2, 3] ,

[ 4, 5, 6] ,[ 7, 8, 1] ] )

>>> from numpy. linalg import *>>> det( E11)23. 999999999999996

>>> det_bareiss( E11)24

Cet exemple ne montre pas l'amélioration car les erreursd'arrondis de la méthode du pivot de Gauss ont jouésdans le "bon sens".La seule amélioration est que le résultat est de type entier(le déterminant d'une matrice à coefficents entiers estentier).