vjordan.info · Created Date: 10/30/2008 10:15:03 AM

1 / 1 4rapport de TP "Éléments propres des matrices" - septembre 2008

1. Diagonalisation

a. Di agonal i sati on formel l e avec sympy

Étape 1 : Vérifier si une matrice est diagonalisableUne fois les valeurs et les bases de vecteurs propres trouvés, une matrice est 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 valeurs propres est égale à sa multiplicité.

Étape 2 : DiagonalisationLa matrice diagonale correspond à une matrice dont les valeurs propres se trouvent sur la diagonale,alors que la matrice de passage est celle qui contient les vecteurs propres.Exemple de diagonalisation :>>> E19[ - 5, 2, 4, - 4][ 10, - 3, - 6, 8][ 11, - 4, - 6, 8][ 22, - 8, - 14, 17]>>> diag_tst( E19. eigenvects( ) )True>>> ( D, P) = diag_sympy( E19)>>> D[ 1, 0, 0, 0][ 0, 1, 0, 0][ 0, 0, 2, 0][ 0, 0, 0, - 1]>>> P[ 1, 0, 0, - 1/2][ 1, 2, 1, 0][ 1, 0, 1/2, 1/2][ 0, 1, 1, 1]>>> E19 == P*D*P. inv( )True

Al g o ri th m i q u e N u m é ri q u eRapport de TP "Éléments propres des matrices"

Ce TP présente un certain nombre de méthodes afin d'approximer les valeurs et vecteurs propres

d'une matrice. L'utilité des ces éléments propres est montrée dans deux algorithmes : le calcul de la

puissance d'une matrice et la résolution de systèmes différentiels.


Comme prévu dans l'énoncé du TP, certaines matrices provoquent une erreur dans la méthodeeigenvects() de sympy. Cette méthode a donc été remplacée par la fonction proposée.Version utilsée : sympy 0.6.2 (Debian sid)>>> E20[ 1, 4][ - 1, - 2]>>> diag_sympy( E20)Traceback ( most recent call last) :

File " <stdin>" , line 1, in <module>File " calc_num. py" , line 577, in

diag_sympyVP = M. eigenvects( )

File " /var/lib/python-support/python2. 5/sympy/matrices/matrices. py" , line 1286, in eigenvects

assert len( basis) == kAssertionError

b. Cal cul de l a pui ssance d' une matri ce

La diagonalisation d'une matrice est utile lors du calcul de la puissance d'une matrice. Un produitmatriciel même optimisé à un coût en calcul très grand. Il est plus rapide de diagonaliser car souscette forme la calcul de la puissance d'une matrice devient :

Exemple :>>> E21matrix( [ [ 0, 1, 1] ,

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

>>> E21**8matrix( [ [ - 21844, 21845, 21845] ,

[ - 65535, 65536, 65535] ,[ - 21845, 21845, 21846] ] )

>>> puissance_appro( E21, 8)matrix( [ [ - 21844. 0000000001, 21845. 0000000001, 21845. 0000000001] ,

[ - 65535. 0000000002, 65536. 0000000002, 65535. 0000000002] ,[ - 21845. 0000000001, 21845. 0000000001, 21846. 0000000001] ] )

Calcul approché avec numpy

Ce correctif supprime simplement l'assertion qui provoque l'erreur.


Calcul de la puissanceexacte avec sympy

L'exemple proposé dans le TP (E20) a des valeurs et vecteurs propres assez complexes, la puissancen-ième a été faite mais donner le résultat prendrait une page entière. L'exemple ci-dessous montre lapuissance n-ième de la matrice E19, plus simple.>>> E20[ 1, 4][ - 1, - 2]>>> eigenvects2( E20) [ 0]( - 1/2 + I*7**( 1/2) /2, 1,[ [ - 4/( 1. 5 - 0. 5*I*7**( 1/2) ) ][ 1] ] )

>>> eigenvects2( E20) [ 1]( - 1/2 - I*7**( 1/2) /2, 1,[ [ - 4/( 1. 5 + 0. 5*I*7**( 1/2) ) ][ 1] ] )

>>> E19[ - 5, 2, 4, - 4][ 10, - 3, - 6, 8][ 11, - 4, - 6, 8][ 22, - 8, - 14, 17]>>> n = Symbol( ' n' )>>> puissance_exact( E19, n)[ - 2. 0 + 3. 0*( - 1) **n, 1. 0 - 1. 0*( - 1) **n, 2. 0 - 2. 0*( - 1) **n, - 2. 0 + 2. 0*( - 1) **n]

[ - 10. 0 + 10. 0*2**n, 5. 0 - 4. 0*2**n, 6. 0 - 6. 0*2**n, - 8. 0 + 8. 0*2**n]

[ - 2. 0 + 5. 0*2**n - 3. 0*( - 1) **n, 1. 0 + ( - 1) **n - 2. 0*2**n, 2. 0 + 2. 0*( - 1) **n - 3. 0*2**n, - 2. 0 + 4. 0*2**n - 2. 0*( - 1) **n]

[ - 4. 0 + 10. 0*2**n - 6. 0*( - 1) **n, 2. 0 + 2. 0*( - 1) **n - 4. 0*2**n, 2. 0 + 4. 0*( - 1) **n - 6. 0*2**n, - 3. 0 + 8. 0*2**n - 4. 0*( - 1) **n]


c. Résol uti on de système di fférenti el

Théorème

La solution d'un système différentiel peut être trouvée en utilisant la diagonalisation de la matrice M.

Exemple :

>>> E23[ 1, 1, 0][ - 3, 4, 3][ - 1, 1, 2]>>> E23i[ 1][ 1][ 1]>>> X = res_diff( E23, E23i)>>> X[ 2*exp( t) /3 + 1/3*exp( 4*t) ][ exp( 4*t) ][ 2*exp( t) /3 + 1/3*exp( 4*t) ]>>> X. subs( ' t' , 5) . evalf( )[ 161721830. 745369][ 485165195. 40979][ 161721830. 745369]

2. Valeurs propres par les décompositions QR et LU

a. M éthode par l a décomposi ti on QR

Lors de la décomposition QR d'une matrice A1, A1 = Q*R mais A2 = R*Q est une matrice qui conserveles mêmes valeurs propres et qui converge vers une matrice triangualaire supérieure si celles-ci sontdifférentes. On peut donc répéter l'opération pour approximer les valeurs propres tout en observant laconvergence de façon empirique.


RemarqueLa fonction QR_householder() donne des résultats différents lorsque sympy est importé ou non :Lorsque seul numpy est importé, la fonction ne provoque pas d'erreur mais le résultat est faux :>>> ( Q, R) = QR_householder( E18)>>> E18matrix( [ [ 23. , - 15. , 30. , 15. ] ,

[ - 4. , - 30. , - 15. , 55. ] ,[ - 4. , 20. , 35. , 5. ] ,[ - 8. , 40. , - 80. , - 65. ] ] )

>>> Q*Rmatrix( [ [ 2. 30000000e+01, - 2. 30000000e+01, 4. 60000000e+01,

2. 30000000e+01] ,[ - 5. 17281691e- 17, - 3. 28888889e+01, 1. 64444444e+01,

4. 93333333e+01] ,[ - 1. 00961215e- 16, - 1. 33565936e- 15, 4. 14400000e+01,

1. 38133333e+01] ,[ 4. 23907822e- 17, 2. 01380301e- 15, 1. 55352583e- 15,

1. 04133333e+01] ] )

Alors que quand sympy est importé (alors qu'il n'est pas necessaire) :>>> ( Q, R) = QR_householder( E18)>>> E18matrix( [ [ 23. , - 15. , 30. , 15. ] ,

[ - 4. , - 30. , - 15. , 55. ] ,[ - 4. , 20. , 35. , 5. ] ,[ - 8. , 40. , - 80. , - 65. ] ] )

>>> Q*R[ 23. 0, - 15. 0, 30. 0, 15. 0][ - 4. 0, - 30. 0, - 15. 0, 55. 0][ - 4. 0, 20. 0, 35. 0, 5. 00000000000001][ - 8. 0, 40. 0, - 80. 0, - 65. 0]

Je n'ai pas trouvé d'où venait ce problème, sympy surcharge un certain nombre de fonction quenumpy utilise et inversement en fonction de celui qui est importé en dernier...

La convergence est variableLa convergence est lente si les valeurs propres sont proches entre elles. Si les valeurs propres ne sontpas 2 à 2 distinctes, il n'y pas de convergence du tout.

Convergence lente>>> E25matrix( [ [ 337. , 124. , - 101. , - 11. ] ,

[ 528. , 453. , 2. , - 178. ] ,[ 1227. , 718. , - 199. , - 209. ] ,[ 2037. , 1258. , - 299. , - 279. ] ] )

>>> eig( E25) [ 0]array( [ 102. 4888 +195. 7654j , 102. 4888- 195. 7654j , 100. 4973 +0. j , 6. 5250 +0. j ] )

Convergence>>> E24matrix( [ [ - 4. , 4. , - 2. ] ,

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

>>> eig( E24) [ 0]array( [ - 10. , - 2. , 6. ] )

510152025

500100015002000

- 9. 7579 - 2. 0282 5. 7861- 10. 0159 - 1. 9977 6. 0136- 9. 9987 - 2. 0002 5. 9989

- 10. 0001 - 2. 0000 6. 0001- 10. 0000 - 2. 0000 6. 0000

- 10. 0000 6. 0000 - 2. 0000- 10. 0000 6. 0000 - 2. 0000- 10. 0000 6. 0000 - 2. 0000- 10. 0000 6. 0000 - 2. 0000

- 102. 8957 100. 9722 307. 3995 6. 524197. 5400 102. 7643 105. 1707 6. 5250

289. 3313 - 84. 7481 100. 8918 6. 5250- 176. 0836 381. 0519 100. 5066 6. 5250- 34. 0754 239. 0529 100. 4974 6. 5250

247. 6183 - 42. 6407 100. 4974 6. 525087. 8020 117. 1756 100. 4974 6. 5250

- 91. 4648 296. 4424 100. 4974 6. 5250179. 1452 25. 8324 100. 4974 6. 5250

nb itérations


>>> E26matrix( [ [ 1. , 2. , 3. ] ,

[ 3. , 2. , 1. ] ,[ 2. , 3. , 1. ] ] )

>>> eig( E26) [ 0]array( [ 6. +0. j , - 1. +1. j , - 1. - 1. j ] )

b. M éthode par l a décomposi ti on LU

Sur le même modèle que la méthode utilisant la décomposition QR, la décomposition LU peut, elleaussi, permettre de trouver une approximation des valeurs propres d'une matrice.

510152025

500100015002000

5. 9995 - 0. 5284 - 1. 47116. 0000 - 0. 8899 - 1. 11016. 0000 - 1. 5261 - 0. 47396. 0000 - 1. 0370 - 0. 96306. 0000 - 0. 5292 - 1. 4708

6. 0000 - 1. 0370 - 0. 96306. 0000 - 1. 0370 - 0. 96306. 0000 - 1. 0370 - 0. 96306. 0000 - 1. 0370 - 0. 9630

nb itérationsDans cet exemple, les valeurs propres ne sont pasdistinctes mais sans connaître ces valeurs propresque l'on cherche justement, on pourrai croire qu'ily a eu convergence sur les valeurs propres.

Exemple :>>> E27matrix( [ [ - 4. , 4. , - 2. ] ,

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

>>> vp_appro_LU( E27, 5)[ - 9. 9923273657289009, - 2. 4334282190279768, 6. 4257555847568781]>>> vp_appro_LU( E27, 10)[ - 9. 9999975424007559, - 1. 9678186980333106, 5. 9678162404340656]>>> vp_appro_LU( E27, 20)[ - 9. 999999999999746, - 1. 9998053070395203, 5. 9998053070392672]>>> vp_appro_LU( E27, 100)[ - 9. 9999999999999982, 6. 0000000000000027, - 2. 0000000000000027]

Les valeurs recherchées en utilisant numpy :>>> eig( E27) [ 0]array( [ - 10. , - 2. , 6. ] )


3. Méthode de Jacobi

La méthode de Jacobi ne s'applique qu'aux matrices symétriques. Elle s'inspire de la méthode deGivens pour la décomposition QR en l'adaptant à la recherche des valeurs propres. Des matrices derotations sont appliquées à la matrice de départ pour la faire tendre vers une matrice diagonale dontles valeurs propres sont faciles à trouver.


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

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

>>> vp_appro_j acobi( E28, 1, 0)[ 1. 0, - 3. 0, 5. 0]>>> vp_appro_j acobi( E28, 2, 0)[ - 1. 0620192023179802, - 3. 0, 7. 0620192023179804]>>> vp_appro_j acobi( E28, 3, 0)[ - 0. 88556912517370678, - 3. 1764500771442727, 7. 0620192023179804]>>> vp_appro_j acobi( E28, 4, 0)[ - 0. 88556912517370678, - 3. 1878778660166742, 7. 073446991190381]>>> vp_appro_j acobi( E28, 5, 0)[ - 0. 88679571633502474, - 3. 1878778660166742, 7. 0746735823516991]>>> eig( E28) [ 0]array( [ 7. 0746735825, - 0. 8867909863, - 3. 1878825963] )

4. Méthode des puissances itérées

Cette méthode peut être utilisée de deux façons : la méthode directe pour trouver la plus grandevaleur propre (en valeur absolue) et la méthode inverse pour trouver la plus petite valeur propre.

a. Pui ssances i térées di rectes

Le principe est de multiplier un vecteur aléatoire par la matrice pour le faire tendre vers le vecteurpropre (de la plus grande valeur propre). Pour éviter que les coefficients du vecteur ne dépassent lacapacité de stockage des nombres, le vecteur est normé à chaque itération (le type de norme peutêtre selectionné avec le paramètre 'norme').

La convergence est trèsrapide, au bout de 5 itérationsseulement, le résultat estpresque équivalent à celui denumpy (dernière ligne).


Exemple avec :>>> E30matrix( [ [ - 7. , - 3. , 0. ] ,

[ 54. , 8. , - 36. ] ,[ 3. , - 3. , - 10. ] ] )

- 1. 80136512438117- 9. 96788922561871- 9. 99093337827365- 9. 99882565452779

- 10. 000039888957- 10. 0000071888496- 10. 0000000697347- 10. 0000000718607- 10. 0000000068655

norme 1

- 1. 39026410373939- 9. 8646953724651- 9. 92935723450917- 9. 99727119344652

- 10. 0000387211931- 10. 0000082362792- 10. 0000010862499- 10. 0000000897754- 9. 99999938423851

norme 2

- 1. 63384084337154- 9. 96832679886451- 9. 9845554513707- 9. 99998297414087- 9. 99981720077175

- 10. 000002228504- 10. 0000008309013- 10. 0000000252023- 10. 0000000062021

norme 3

- 9. 11966156457101- 9. 59320853710924- 9. 96586391103081- 9. 99986507520525- 9. 99994139152361

- 10. 0000066782897- 10. 0000003426959- 10. 0000000250778- 10. 000000010167

norme infinie

123456789

itération

valeurs propres>>> eig( E30) [ 0]array( [ 2. , - 1. , - 10. ] )

valeur à trouver : -10

Le choix de la norme ne semble pas avoir beaucoups d'influence sur la vitesse de convergence vers lerésultat final. La valeur propre de module maximal est rapidement atteinte avec chaque norme.

Exemples :>>> E30matrix( [ [ - 4. , 4. , - 2. ] ,

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

>>> vp_appro_pi( E30, 0. 0001, 1000, 2)( matrix( [ [ 0. 57735113] ,

[ - 0. 57735372] ,[ 0. 57734595] ] ) , - 10. 000023939875668)

>>> eig( E30) [ 0]array( [ - 10. , - 2. , 6. ] )>>> eig( E30) [ 1]matrix( [ [ 5. 77350269e- 01, - 8. 94427191e- 01, 3. 36018950e- 17] ,

[ - 5. 77350269e- 01, - 4. 47213595e- 01, 4. 47213595e- 01] ,[ 5. 77350269e- 01, - 3. 28241137e- 17, 8. 94427191e- 01] ] )

La plus grande valeur propre (envaleur absolue) -10 et le vecteurpropre [ 0,5773 -0,5773 0,5773]sont bien confirmés par la fonctionnumpy eig()

>>> E31matrix( [ [ 15. +6. j , - 16. +7. j , 5. +10. j ] ,

[ - 8. +16. j , - 5. - 19. j , - 12. +4. j ] ,[ 11. +23. j , - 27. - 11. j , - 6. +18. j ] ] )

>>> vp_appro_pi( E31, 0. 0001, 1000, 2)( matrix( [ [ - 0. 38504726+0. 31896456j ] ,

[ - 0. 31896512- 0. 38504754j ] ,[ - 0. 70401208- 0. 06608215j ] ] ) , ( 2. 999992096060963+4. 9999905706694188j ) )

>>> eig( E31) [ 0]array( [ 3. 00000000e+00+5. j , 1. 00000000e+00- 1. j , 4. 96357465e- 15+1. j ] )>>> eig( E31) [ 1]matrix( [ [ 3. 53553391e- 01 - 3. 53553391e- 01j ,

2. 82842712e- 01 - 1. 41421356e- 01j ,- 4. 08248290e- 01 - 4. 08248290e- 01j ] ,

[ 3. 53553391e- 01 +3. 53553391e- 01j ,2. 82842712e- 01 +5. 65685425e- 01j ,

- 9. 41844616e- 16 - 5. 40729725e- 15j ] ,[ 7. 07106781e- 01 +0. 00000000e+00j ,

7. 07106781e- 01 +0. 00000000e+00j ,8. 16496581e- 01 +0. 00000000e+00j ] ] )

Convergence avec différentesnormes

La valeur propre s'approche bien de 3 + 5i(résultat de numpy)

1 0 / 1 4rapport de TP "Éléments propres des matrices" - septembre 2008

b. Vitesse de convergence

La vitesse de convergence dépend du rapport entre la deuxième plus grande et la plus grande valeurpropre. Ce rapport est indiqué sur le graphique (valeur l2/l1).

RemarqueLors du développement de cette fonction de puissances itérées, il a été remarqué que la fonctionzeros() ne retournait pas un élément de type matrice et que cela pouvait poser problème car sansprovoquer d'erreur, certains opérateurs agissent différemment.

>>> from numpy import *>>> A = zeros( ( 3, 1) )>>> Aarray( [ [ 0. ] ,

[ 0. ] ,[ 0. ] ] )

>>> for i in range( 3) :. . . A[ i, 0] = i. . .>>> Aarray( [ [ 0. ] ,

[ 1. ] ,[ 2. ] ] )

>>> B = A>>> Barray( [ [ 0. ] ,

[ 1. ] ,[ 2. ] ] )

>>> B. Tarray( [ [ 0. , 1. , 2. ] ] )>>> B. T*Aarray( [ [ 0. , 0. , 0. ] ,

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

>>> from numpy import *>>> A = matrix( ( 0, 1, 2) , dtype=' float' ) . reshape( 3, 1)>>> Amatrix( [ [ 0. ] ,

[ 1. ] ,[ 2. ] ] )

>>> B = A>>> Bmatrix( [ [ 0. ] ,

[ 1. ] ,[ 2. ] ] )

>>> B. Tmatrix( [ [ 0. , 1. , 2. ] ] )>>> B. T*Amatrix( [ [ 5. ] ] )

L'opérateur de multiplication entre 2 tableaux n'est pas unproduit matriciel.

Le nombre d'itérationsnécessaire pour augementerla précision du résultat croit demanière exponentiel (legraphique est en échellelogaritmique).Les valeurs propres de lamatrice E31 sont moinsproches entre elles que pour lamatrice E30, la convergenceest alors plus rapide.


c. M éthode de défl ati on

Pour trouver les autres valeurs propres (autre que minimale et maximale), il est possible deréexecuter l'algorithme des puissances itérées après avoir utiliser la méthode de déflation. Lanouvelle matrice a pour valeurs propres les mêms valeurs excepté la plus grande (en module).

Exemple :>>> E30matrix( [ [ - 4. , 4. , - 2. ] ,

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

>>> ( vects, vals) = vp_appro_pi_def( E30, 0. 0001, 1000, 2)>>> vals[ - 9. 9999681549216479, 6. 0000623928510235, - 1. 9999720432646368]>>> vects[ matrix( [ [ 0. 57734912] ,

[ - 0. 57734567] ,[ 0. 57735601] ] ) , matrix( [ [ - 0. 20942842] ,[ - 0. 16754333] ,[ - 0. 96336336] ] ) , matrix( [ [ 0. 06657683] ,[ - 0. 40201319] ,[ 0. 91321023] ] ) ]


[ - 5. 77350269e- 01, - 4. 47213595e- 01, 4. 47213595e- 01] ,[ 5. 77350269e- 01, - 3. 28241137e- 17, 8. 94427191e- 01] ] )

Dans le cas d'une matrice nondiagonale, la convergence estbeaucoups plus lente.


d. Pui ssances i térées i nverses

En appliquant une méthode similaire à celle des puissance itérées sur l'inverse de la matrice ontrouve la plus petite valeur propre (si celle-ci est différente de 0).Pour éviter la couteuse inversion de la matrice de départ, la méthode implémentée ici utilise unedécomposition LU. A chaque itération, deux systèmes triangulaires (avec L et U calculé au départ)sont résolus.

Exemple :>>> E30matrix( [ [ - 4. , 4. , - 2. ] ,

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

>>> vp_appro_pi_inv( E30, 0. 00001, 1000)( array( [ [ 0. 894426634089827] ,

[ 0. 447214709309765] ,[ 2. 7794898701747e- 6] ] , dtype=obj ect) , - 2. 0000016572434)


[ - 5. 7735026919e- 01, - 4. 4721359550e- 01, 4. 4721359550e- 01] ,[ 5. 7735026919e- 01, - 3. 2824113709e- 17, 8. 9442719100e- 01] ] )


e. Amél i orer l a préci si on d' une val eur propre

La méthode des puissance itérées inverses peut être utilisée pour améliorer une estimation den'importe quelle valeur propre (pas forcement minimale si l'approximation n'est pas trop proche d'uneautre valeur propre).

Exemple :>>> E30matrix( [ [ - 4. , 4. , - 2. ] ,

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

>>> eig( E30) [ 0]array( [ - 10. , - 2. , 6. ] )

>>> vp_appro_pi_am( E30, - 11. 5, 0. 0001, 1000)( array( [ [ - 0. 577338568216333] ,

[ 0. 577359837712382] ,[ - 0. 577352401438365] ] , dtype=obj ect) , - 10. 000005241477)


[ - 0. 447206585082554] ,[ - 3. 095843463415e- 5] ] , dtype=obj ect) , - 2. 00000479795784)

>>> vp_appro_pi_am( E30, 7. 0, 0. 0001, 1000)( array( [ [ - 1. 91732758599463e- 5] ,

[ 0. 447205530705179] ,[ 0. 894431223146355] ] , dtype=obj ect) , 6. 00000375560245)


Si on se place exactement entre les valeurs propres -10 et -2, l'amélioration ne peut pas se faire :>>> vp_appro_pi_am( E30, - 6. 0, 0. 0001, 1000)PivotNul, matrice non inversible

par contre lorsque l'on se rapproche de l'une ou l'autre des valeurs propres, l'amélioration est trèslongue mais aboutie bien au résultat :>>> vp_appro_pi_am( E30, - 6. 1, 0. 0001, 1000)( array( [ [ 0. 577332573423425] ,

[ - 0. 577364425529234] ,[ 0. 577353808160631] ] , dtype=obj ect) , - 9. 99995335720808)


[ - 0. 447196832776354] ,[ - 1. 3968834528292e- 5] ] , dtype=obj ect) , - 1. 99995245671529)

Documents

vjordan.info · Created Date: 10/30/2008 10:15:03 AM