Valeurs et vecteurs propres
Université René Descartes
Problème très important en analyse numérique
UFR de mathématiques et informatique Difficile
Remarque :
- les valeurs propres peuvent être complexes,
même si la matrice est réelle
- les valeurs propres d’une matrice symétrique
chapitre 9 sont réelles
Théorème de Gerschgorin-Hadamard
Valeurs propres et vecteurs propres
Si A est une matrice carrée d’ordre n
P 0 Pn
Ai = n j=1,j6=i | aij |, Aj = i=1,i6=j | aij |
alors les valeurs propres de A appartiennent à la
réunion des n disques définis par | z − aii |≤ Ai.
De même elles appartiennent à la réunion des
n disques définis par | z − ajj |≤ A0j
Ce théorème permet de situer grossièrement
Méthodes numériques 2003/2004 - [Link] les valeurs propres.
La localisation est d’autant meilleure que les
licence de mathématiques et licence MASS
termes diagonaux sont grands devant les autres.
Cas extrême : matrice diagonale
1 2
Théorème - Soit A une matrice carrée d’ordre
n vérifant les propriétés suivantes :
1) ses valeurs propres λi vérifient | λ1 |>| λi |
Algorithme de la puissance itérée
pour i = 2...n
2) A admet n vecteurs propres indépendants
Calcul de la valeur propre de plus grand module x(1), x(2), ..., x(n),
P
et du vecteur propre associé, dans le cas où il 3) le vecteur initial v (0) s’écrit ni=1 cix
(i) avec
existe une seule valeur propre plus grande en (1) (2)
c1 6= 0 dans la base x , x , ..., x , (n)
(p−1)
module que toutes les autres. alors v (p) = Av (p−1) devient proportionnel à
kAv k
x(1) quand p → ∞ et k Av p k→| λi |
On forme la suite de vecteurs
(p−1)
v (p) = Av(p−1) Aspect algorithmique
kAv k
a) test d’arrêt : si λ1 > 0 (resp. < 0), on
avec v (o) vecteur arbitraire de Rn
s’arrête si les rapports des composantes de
et k k norme de C n v (p+1) et v (p) appartiennent à ]1−, 1+[ (resp.
] − 1 − , −1 + [)
Soit λ1 la valeur propre de plus grand module b) vitesse de convergence : d’autant plus grande
et x(1) un vecteur propre associé. que | λ 2
λ1 | est petit où λ2 est la plus grande
Sous certaines conditions, v (p) devient propor- valeur propre en valeur absolue après λ1 .
tionnel à x(1) quand p → ∞ et k Av (p) k→| λ1 | c) cas où c1 = 0 : on fait la même chose
avec λ2 et x(2) sous des hypothèses similaires
à celles du théorème.
3 4
Algorithme de déflation
calcule les autres valeurs propres de A Algorithme de Rutishauser
(Autre méthode)
Principe : λ1 étant calculée, on déduit une Recherche, au moyen de décompositions LU succes-
matrice A1 qui admet les valeurs propres 0, sives, d’une matrice semblable à la matrice étudiée et
triangulaire supérieure.
λ2 , ..., λn . Les valeurs propres sont alors les éléments diagonaux de
On détermine alors λ2, etc ... la matrice triangulaire.
Principe de l’algorithme
Détermination de A1 - décomposition LU , A = LU
- calcul, à l’aide de la matrice de passage L, de la ma-
λ1 est aussi valeur propre de tA de vecteur pro- trice L−1 AL = L−1LU L = U L semblable à A
pre y - iteration, à partir de la nouvelle matrice U L du pro-
cessus
alors A1 = A − t λ1(1) x(1) ty convient.
yx
On définit ainsi les suites Ak , Lk , Uk de matrices par
A = A 1 = L1 U1
Suite du calcul : l’algorithme de la puissance A 2 = U 1 L1 = L 2 U 2
...
itérée appliqué à A1 donne λ2 valeur propre de
Ak+1 = Uk Lk = Lk+1Uk+1
plus grand module de A1. Les matrices Ak sont toutes semblables à A.
En réitérant ce processus de déflation, on pourra Sous certaines conditions, Ak → une matrice triangulaire
calculer successivement toutes les valeurs pro- supérieure quand k → ∞
pres de A, à condition qu’elles soient toutes
différentes en module.
5 6
Theorème de convergence
Si A est une matrice telle que
1) ses valeurs propres λi sont non nulles et
Test d’arrêt
différentes en modules,
soient | λ1 |>| λ2 |> ... >| λn |> 0, On pourra s’arrêter, par exemple, lorsque les
d’où A diagonalisable, avec une matrice de pas- éléments diagonaux des matrices Ak ne varient
sage X (dans la base de vecteurs propres), pratiquement plus, c’est-à-dire si
2) pour tout k, Ak est décomposable en pro- Pn
duit LU , |(Ak+1)ii−(Ak )ii|
i=1P
n <
3) les matrices X et Y = X −1 sont décomposables i=1|(Ak )ii|
en produit LU ,
alors Ak converge, quand k → ∞ vers une ma- Complément
trice triangulaire supérieure ayant les valeurs Si dans la décomposition LU on rencontre un
propres de A ordonnées en valeurs absolues sur pivot nul, on modifie la matrice en ajoutant un
sa diagonale. nombre fixe, par exemple 1, aux termes diag-
onaux.
La vitesse de convergence de Ak vers la forme
(Les valeurs propres de A + µI sont λi + µ).
triangulaire dépend des rapports en modules
des valeurs propres entre elles : si i > j, (Ak )i,j → On retranchera alors ce nombre des résultats
0 comme | λλi |k . finaux.
j
La convergence est donc d’autant meilleure
que les valeurs propres sont bien séparées en
modules.
7 8
