Analyse numérique élémentaire

Chapitre 8 : Calcul numérique des valeurs propres et des vecteurs propres

Équipe de Mathématiques Appliquées

UTC

Juin 2007
5
 suivant I

Chapitre VIII
Détermination des valeurs propres et des
vecteurs propres

VIII.1 Rappels et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

VIII.2 Méthode de la puissance itérée - énoncé et hypothèses . . . . . . . . . . . . . . 5
VIII.3 Méthode de la puissance itérée - convergence et remarques . . . . . . . . . . . 7
VIII.4 Méthode de la puissance itérée inverse - principe . . . . . . . . . . . . . . . . . 10
VIII.5 Méthode de la puissance itérée inverse . . . . . . . . . . . . . . . . . . . . . . . 12 Sommaire
VIII.6 Les méthodes de déflation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Concepts

Exemples
Exercices
Documents

2
 chapitre N suivant I

VIII.1 Rappels et notations

On rappelle que, étant donnée une matrice A ∈ Mnn (IR), le problème de calcul des valeurs
propres consiste à trouver un scalaire λ tel qu’il existe un vecteur y, y 6= 0, tel que

Ay = λy.

Notations Dans tout ce chapitre on notera λ1 , λ2 , ..., λn les n valeurs propres distinctes ou non
de A et on supposera désormais que

|λ1 | ≥ |λ2 | ≥ ... ≥ |λn |,

λ1 s’appelle la valeur propre dominante de A.

On supposera que la matrice A est diagonalisable, il existe donc une base de vecteurs propres
que l’on notera y (1) , y (2) , ..., y (n) .
Le problème de la détermination des valeurs propres de A est équivalent à trouver les racines
du polynôme caractéristique
PA (s) = det(sI − A).
On pourrait penser que le calcul numérique des valeurs propres se ramène au calcul numé-
rique des racines d’un polynôme. En réalité c’est l’inverse qui se fait. En effet, étant donné un
polynôme Sommaire
p(t) = tn + an tn−1 + an−1 tn−2 + ... + a2 t + a1 , Concepts

on peut démontrer (voir exercice de TD A.2.2 ) que ce polynôme est le polynôme caractéristique
Exemples
Exercices
Documents

3 II
 chapitre N suivant I

de la matrice suivante   Rappels et

0 1 0 ... 0 notations
 0 0 1 ... 0 
.. .. ..
 
A=
 .. .. .

 . . . . . 
 0 0 ... 0 1 
−a1 −a2 ... −an−1 −an
Les matrices A qui ont la forme précédente s’appellent des matrices "Compagnon".

Sommaire
Concepts

Exemples
Exercices
Documents

JJ 4
 J précédent chapitre N suivant I

VIII.2 Méthode de la puissance itérée - énoncé et hypothèses

Exercices :
Exercice A.1.1

La méthode de la puissance itérée est la suivante :


(0) n
x donné dans IR ,

(k)
(k+1) Ax (VIII.1)
x = , k ≥ 0,
Ax(k)


où k.k désigne une norme quelconque.

Hypothèses et notations
– On suppose que
|λ1 | > |λ2 | ≥ |λ3 | ≥ ... ≥ |λn |.
On a donc que λ1 est une valeur propre réelle simple (le montrer en exercice).
– On
 (2)suppose que x(0) n’appartient pas au sous-espace engendré par les vecteurs propres
y , y , ..., y (n) .
(3)
(1) Sommaire
– Soit p un indice tel que yp 6= 0 Concepts


Théorème VIII.1. Sous les hypothèses précédentes, la suite x(k) k∈IN générée par les relations
(VIII.1) possède les propriétés suivantes :
Exemples
lim Ax(k) = |λ1 |, Exercices
k→∞ Documents

5 II
 J précédent chapitre N suivant I

on a d’ailleurs plus précisément Méthode de la

[Ax(k) ]p puissance
lim = λ1 .
k→∞ (k)
xp itérée -

énoncé et
De plus la suite x(k) k∈IN
converge vers un vecteur propre associé à λ1 de la façon suivante : hypothèses

lim [sgn (λ1 )]k x(k) = γy (1) , (VIII.2)

k→∞

où γ est une constante réelle.

Sommaire
Concepts

Exemples
Exercices
Documents

JJ 6
 J précédent chapitre N suivant I

VIII.3 Méthode de la puissance itérée - convergence et remarques

On va maintenant démontrer le théorème VIII.1.
On démontre immédiatement que l’on a :
Ak x(0)
x(k) = . (VIII.3)
Ak x(0)

En effet cette propriété est vraie pour k = 1 par construction même de x(1) , si l’on suppose que
la propriété est vraie pour k, on a alors
Ak x(0)
A
Ax(k) Ak x(0) Ak+1 x(0)
x(k+1) = = = .
Ax(k) Ak x(0) Ak+1 x(0)
A
Ak x(0)

En développant x(0) sur la base des vecteur propres on peut écrire

n
X
x(0) = ξi y (i) , ξ1 6= 0.
i=1

On obtient alors
! Sommaire
n n n  k Concepts
X X X λi
Ak x(0) = ξi Ak y (i) = ξi λki y (i) = λk1 ξ1 y (1) + ξi y (i) = λk1 w(k) , (VIII.4)
i=1 i=1 i=2
λ1

où l’on a posé Exemples

n  k Exercices
X λi
w(k) = ξ1 y (1) + ξi y (i) , Documents
i=2
λ1

7 II
 J précédent chapitre N suivant I

en utilisant (VIII.3) et (VIII.4) on obtient Méthode de la

λk1 w (k)
w(k) puissance
x(k) = = sgn (λ1 )k , (VIII.5) itérée -
|λk1 | w(k) w(k)
convergence
or lim w(k) = ξ1 y (1) , car |λi /λ1 | < 1, ∀i > 1, d’où et remarques
k→∞

ξ1
lim sgn (λ1 )k x(k) = γy (1) , où γ = .
k→∞ |ξ1 | y (1)
De même d’après (VIII.3) et (VIII.4)
Ak+1 x(0) λk+1 w(k+1) kw
(k+1)
Ax(k) = = 1
= λ 1 sgn (λ 1 ) (VIII.6)
Ak x(0) λk1 kwk k w(k)
d’où
w(k+1)
Ax(k) = |λ1 | ,
w(k)

et donc lim Ax(k) = |λ1 |.

k→∞
On a de plus en utilisant (VIII.5) et (VIII.6)
(k+1)
(Ax(k) )p wp
(k)
= λ1 (k)
.
xp wp
Sommaire
Or lim wp(k) = ξ1 yp(1) ( non nul par hypothèse ), donc Concepts
k→∞

[Ax(k) ]p
lim (k)
= λ1
k→∞ xp Exemples
Exercices
Documents
Quelques remarques :

JJ 8 II
 J précédent chapitre N suivant I

– Si l’on a par exemple λ1 = λ2 et |λ1 | > |λ3 | ≥ |λ4 | ≥ ... ≥ |λn |, c’est à dire si la valeur propre Méthode de la
dominante est double la démonstration est encore valide, il suffit d’écrire puissance
n
itérée -
convergence
X
x(0) = ξ1 y (1) + ξi y (i) ,
i=3
et remarques

où ξ1 y (1) est la composante de x(0) sur le sous espace propre associé à λ1 (qui est ici de
dimension 2).
Ce serait encore valable si λ1 était de façon générale multiple. Par contre si on a λ1 6= λ2
et |λ1 | = |λ2 |, alors la démonstration n’est pas valable, c’est ce qui se passe en particulier
dans le cas des valeurs propres complexes.
– Dans la formule (VIII.2) apparaît le signe de λ1 , ce qui veut dire que, si λ1 est négatif,
alors les vecteurs x(k) oscillent entre les deux vecteurs +γy (1) et −γy (1) . On verra en TD
(exercice A.2.1 ) une variante de la méthode de la puissance itérée qui utilise la norme
infinie judicieusement afin d’éviter ces oscillations.

Sommaire
Concepts

Exemples
Exercices
Documents

JJ 9
 J précédent chapitre N suivant I

VIII.4 Méthode de la puissance itérée inverse - principe

Si λ est valeur propre de A et que A est inversible, alors, de façon équivalente, λ−1 est valeur
propre de A−1 et les vecteurs propres associés sont les mêmes. On a en effet

Ay = λy ⇐⇒ y = λA−1 y ⇐⇒ A−1 y = λ−1 y.

Par ailleurs définissons, pour q scalaire donné, la matrice

B = A − qI.

Cette matrice admet comme valeurs propres λi −q où λi sont les valeurs propres de A, la matrice
B −1 (si elle est définie, c’est-à-dire si q n’est pas valeur propre de A) admet pour valeurs propres
1
µi = .
λi − q

En effet si z est vecteur propre de B −1 associé à (λi − q)−1 , il est vecteur propre de B, donc de A
et il est évidemment associé à la valeur propre λi . Vérification :

B −1 z = (λi − q)−1 z ⇐⇒ z = (λi − q)−1 Bz ⇐⇒ Bz = (λi − q)z ⇐⇒ (A − qI)z = (λi − q)z

⇐⇒ Az − qz = (λi − q)z ⇐⇒ Az = λi z.
Sommaire
Soit A matrice diagonalisable dans IR, soit q un réel et soit λj une valeur propre de A qui Concepts
vérifie
0 < |q − λj | < |q − λi |, ∀ i 6= j, (VIII.7)
c’est à dire q n’est pas valeur propre de A et λj est la valeur propre la plus proche de q. Il résulte Exemples
Exercices
de (VIII.7) que la matrice B −1 Documents
B −1 = (A − qI)−1

10 II
 J précédent chapitre N suivant I

admet Méthode de la
1
ν1 = puissance
λj − q itérée inverse
comme valeur propre dominante. Donc pour q donné on peut s’inspirer de l’algoritme de la - principe
puissance itérée appliqué à B −1 ce qui permet d’obtenir ν1 , et on retrouve λj en posant

1
λj = + q.
ν1
La méthode s’appelle méthode de la puissance itérée inverse.

Sommaire
Concepts

Exemples
Exercices
Documents

JJ 11
 J précédent chapitre N suivant I

VIII.5 Méthode de la puissance itérée inverse

Posons B = A − qI. On donne x(0) arbitraire (ou presque !) et on définit la suite x(k+1) par

(k+1)
Bu
 =x(k)
(k+1) u(k+1) (VIII.8)
x = (k+1)
, k ≥ 0.
u



On peut énoncer le théorème suivant :

Théorème VIII.2. Soit q ∈ IR donné tel que q 6= λi , ∀i, et soit B = A − qI. Si le vecteur

initial
x(0) n’appartient pas au sous-espace engendré par y (i) i=1...n,i6=j alors la suite x(k) k∈IN générée
par la méthode (VIII.8) possède les propriétés suivantes :
1
lim u(k) = ,
k→∞ λj − q
(j)
où λj est la valeur propre de A la plus proche de q. On a d’ailleurs plus précisément si yp 6= 0
(k+1)
up 1
lim (k)
= .
k→∞ xp λj − q


De plus la suite x(k) k∈IN
converge vers y (j) le vecteur propre de A associé à λj de la façon
Sommaire
suivante :   k Concepts
1
lim sgn x(k) = γy (j) , (VIII.9)
k→∞ λj − q
où γ est une constante réelle. Exemples
On peut montrer que la méthode converge d’autant plus vite que |q − λj | est petit devant Exercices
Documents
|q − λi |, ∀ i 6= j.

12
 J précédent chapitre N

VIII.6 Les méthodes de déflation

Les méthodes précédentes permettent de déterminer une valeur propre et le vecteur propre
associé, par exemple la méthode de la puissance itérée inverse permet de calculer la valeur
propre de plus petite valeur absolue si elle est unique. Donc si l’on a déterminé par une méthode
quelconque une valeur propre λ1 ( v.p. dominante par exemple), on peut songer à construire une
matrice dans laquelle la valeur propre que l’on vient de déterminer n’est plus dominante et qui,
par contre, possède toujours (λj ), j 6= 1 comme valeurs propres. La méthode de la puissance
(par exemple) permet alors de déterminer une nouvelle valeur propre dominante de la famille
(λj ), j 6= 1 et ainsi de suite. Cette procédure constitue ce qu’on appelle une méthode de déflation.
– 1er cas : A symétrique.
Supposons que l’on connaisse un vecteur propre y associé à la valeur propre λ avec kyk2 =
1. Considérons alors la matrice
B = A − λyy > .
Evidemment on a
By = Ay − λyy > y = λy − λy = 0.
Par ailleurs si z est un autre vecteur propre de A associé à une autre valeur propre µ on a

Bz = Az − λyy > z = µz

car y > z = 0 en vertu de l’orthogonalité des vecteurs propres. Sommaire

– 2ème cas : A quelconque (Méthode de Duncan et Collar) Concepts
Soit A une matrice quelconque et supposons qu’on a obtenu un couple propre (λ, y) et
supposons pour simplifier que la première composante de y est égale à 1. Notons A1 la
première ligne de la matrice A, par définition du couple (λ, y) on a Exemples
Exercices
Documents
A1 y = λy1 = λ. (VIII.10)

13 II
 J précédent

Définissons alors la matrice B par Les méthodes

de déflation
B = A − yA1 .
Alors la première ligne de B est nulle, en effet
B 1 = A1 − y1 A1 = 0.
Par ailleurs, d’après (VIII.10) :

By = Ay − yA1 y = λy − λy = 0. (VIII.11)
Si l’on suppose que les autres vecteurs propres de A ont leur première composante non
nulle alors on peut les normaliser de façon à ce qu’elle soit égale à 1. Dans ces conditions
si (µ, z) est un autre couple propre de A (µ 6= λ) on a Az = µz, donc
A1 z = µ
et
B(z − y) = Bz = Az − yA1 z = µz − µy = µ(z − y)
la première égalité étant une conséquence de (VIII.11). Les autres valeurs propres de B
sont donc identiques à celles de A avec pour vecteurs propres associés z − y . Réciproque-
ment si (µ, u) est un couple propre de B , si on suppose que µ 6= 0 et que A1 u = µ − λ (ceci
est toujours possible si A1 u 6= 0) alors :
Sommaire
A(u + y) = Bu + yA1 u + Ay = µu + (µ − λ)y + λy = µ(u + y) Concepts
On vient de démontrer que (u + y) est vecteur propre de A associé à la valeur propre µ.
Pour obtenir les couples propres de A autres que (λ, y) , on se ramène donc à rechercher les
couples propres de B (valeur propre non nulle). Compte tenu de la structure particulière Exemples
de B (sa première ligne étant nulle) on est ramené à un problème de calcul de valeurs Exercices
Documents
propres dans IRn−1 .

JJ 14
J précédent

Annexe A
Exercices

A.1 Exercices du chapitre VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

A.2 Exercices de TD du chapitre 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Sommaire
Concepts

Exemples
Exercices
Documents

15
 chapitre N section suivante I

A.1 Exercices du chapitre VIII

A.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Sommaire
Concepts

Exemples
Exercices
Documents

16
 section N

Exercice A.1.1
Montrer que si A ∈ Mnn , si λ1 , λ2 , ..., λn les n valeurs propres de A vérifient |λ1 | > |λ2 | ≥
... ≥ |λn |, alors λ1 est une valeur propre réelle et simple.

retour au cours
Solution

Sommaire
Concepts

Exemples
Exercices
Documents

17
 J section précédente chapitre N

A.2 Exercices de TD du chapitre 8

A.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
A.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A.2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Sommaire
Concepts

Exemples
Exercices
Documents

18
 section N suivant I

Exercice A.2.1
1. Soit A ∈ Mnn (IR), on cherche à déterminer la plus grande (à priori) valeur propre de A en
module ainsi qu’un vecteur propre associé, pour cela on peut utiliser un algorithme inspiré
de la méthode de la puissance itérée associé à la norme k.k∞ . On se donne un vecteur x
non nul et N un nombre maximal d’itérations, puis on applique l’algorithme :
1: Déterminer p tel que |xp | = kxk∞
x
2: x← xp
3: pour k = 2 jusqu’à N faire
4: y ← Ax
5: µ ← yp
6: Déterminer p tel que |yp | = kyk∞
7: si |yp | < ε alors
8: Arrêter l’algorithme et écrire 0 est valeur propre et x est vecteur propre
9: sinon
y
10: E ← x− yp
∞
y
11: x← yp
Sommaire
12: fin si Concepts
13: si E < ε alors
14: Arrêter l’algorithme et écrire µ est valeur propre et x est vecteur propre
Exemples
15: fin si Exercices
Documents
16: fin pour

19 II
 section N suivant I

17: Ecrire : l’algorithme n’a pas convergé Exercice A.2.1

   
3 0 −1 1
(a) Appliquer l’algorithme précédent à A =  0 1 0  en choisissant x =  0 .
3 0 −1 3
 
1
(b) Même question en partant de x =  1 .
3
 
1
(c) Même question en partant de x =  1 . On pourra montrer que les x obtenus sont
2
 
1
de la forme  2−k .
1
2. (a) Calculer exactement toutes les valeurs propres de A et les vecteurs propres associés.
(b) Justifier les résultats obtenus précédemment.
3. Etant donné q réel, on veut maintenant déterminer la valeur propre de A la plus proche
de q, c’est à dire déterminer λi telle que
|λi − q| ≤ |λj − q|, ∀j = 1, . . . , n, on pose µ = λi .
(a) i. Montrer que µ − q est la valeur propre de plus petit module de (A − qI).
Sommaire
ii. Que vaut µ si q est valeur propre de A ? Concepts
iii. Si q n’est pas valeur propre de A, montrer que A − qI est alors inversible et que
ν = (µ − q)−1 est la plus grande valeur propre en module de (A − qI)−1 .
(b) Montrer que l’algorithme de la puissance itérée pour trouver ν puis µ devient : on Exemples
Exercices
se donne un vecteur x non nul, N un nombre maximal d’itérations, et q réel puis on Documents
applique l’algorithme :

JJ 20 II
 section N suivant I

1: Déterminer p tel que |xp | = kxk∞ Exercice A.2.1

x
2: x← xp
3: pour k = 2 jusqu’à N faire
4: Résoudre le système linéaire (A − qI)y = x
5: si le système n’a pas de solution unique alors
6: Arrêter l’algorithme et écrire q est valeur propre
7: sinon
8: ν ← yp
9: Déterminer p tel que |yp | = kyk∞
y
10: E ← x− yp
∞
y
11: x← yp

12: fin si
13: si E < ε alors
1
14: µ= ν +q
15: Arrêter l’algorithme et écrire µ est valeur propre et x est vecteur propre.
16: fin si
Sommaire
17: fin pour Concepts
18: Ecrire : l’algorithme n’a pas convergé
(c) i. On choisit q = 3, appliquer
  cet algorithme à la matrice A précédemment définie. Exemples
1
Exercices
On partira de x =  1 . Documents
1

JJ 21 II
 section N suivant I

ii. Même question en choisissant q = 0. Exercice A.2.1

 
1
iii. Même question en choisissant q = −1, on partira de x =  1 .
3

Sommaire
Concepts

Exemples
Exercices
Documents

JJ 22
 J précédent section N suivant I

Exercice A.2.2
1. On dit que la matrice A est une matrice Compagnon, si elle s’écrit :
 
0 1 0 ... ... 0
 0 0 1 0 ... 0 
 
 ... ... ... ... ... ... 
A= ,
 ... ... ... ... ... ... 
 
 0 ... ... ... 0 1 
−a1 −a2 . . . . . . −an−1 −an
montrer que le polynôme caractéristique de A s’écrit :

p(λ) = λn + an λn−1 + . . . + a2 λ + a1 .

2. En déduire une méthode pour calculer la racine de plus grand module du polynôme

p(t) = tn + an tn−1 + . . . + a2 t + a1 .

Sommaire
Concepts

Exemples
Exercices
Documents

23
 J précédent section N

Exercice A.2.3
Soit A ∈ Mnn (IR) une matrice dont on connaît une valeur propre non nulle λ∗ et y ∗ un
vecteur propre associé. On suppose que z est un vecteur de IRn vérifiant z T y ∗ = 1. On définit la
matrice B de la façon suivante :
B = A − λ∗ y ∗ z T .
1. Montrer que y ∗ est un vecteur propre de B. Quelle est la valeur propre associée ?
2. Il existe au moins une composante de y ∗ non nulle, supposons que yp∗ 6= 0.
Ap
(a) Montrer que l’on peut choisir z T = ∗ ∗ .
λ yp
(b) Montrer que l’on a alors
1 ∗
B =A− y Ap .
yp∗
(c) En déduire que la ligne p de B est nulle.
3. (a) On suppose que µ et x sont une valeur propre et un vecteur propre associé de B, on
suppose que µ 6= 0, µ 6= λ∗ , on définit
Ap x ∗
y = (µ − λ∗ )x + y .
yp∗
Sommaire
Montrer que y 6= 0, montrer que y est vecteur propre de A associé à la valeur propre Concepts
µ.
(b) On suppose que λ et y sont une valeur propre et un vecteur propre associé à A, on
suppose que λ 6= λ∗ , λ 6= 0, on définit Exemples
Exercices
yp ∗ Documents
x=y− y .
yp∗

24 II
 J précédent section N

Montrer que x 6= 0, montrer que x est vecteur propre de B associé à la valeur propre Exercice A.2.3
λ.
(c) En déduire que si λ 6= 0, λ 6= λ∗

{λ est valeur propre de A} ⇔ {λ est valeur propre de B}

4. On définit C matrice extraite de B en supprimant la ligne p et la colonne p de B. Etant

donné v ∈ IRn−1 , on construit le vecteur x ∈ IRn de la façon suivante

xi = vi pour 1 ≤ i ≤ p − 1, xp = 0, xi = vi−1 pour p + 1 ≤ i ≤ n.

Montrer que si µ 6= 0
{Cv = µv} ⇔ {Bx = µx}.
5. On définit  
5 2 3 4
 2 5 4 3 
A=
 .
3 4 5 2 
4 3 2 5
∗
Sachant
 que  cette matrice a pour valeur propre λ = 14 et pour vecteur propre associé
1
 1 
y∗ = 
 1 , construire par la méthode précédente la matrice B et la matrice C, en déduire

Sommaire
1 Concepts
les autres valeurs propres et vecteurs propres de A.

Exemples
Exercices
Documents

JJ 25
 Index des concepts

Le gras indique un grain où le concept est dé-

fini ; l’italique indique un renvoi à un exercice ou un
exemple, le gras italique à un document, et le ro-
main à un grain où le concept est mentionné.

D
Déflation-méthodes . . . . . . . . . . . . . . . . . . . . . . . . . 13

P
Puissance itérée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Puissance itérée inverse-méthode . . . . . . . . . . 12
Puissance itérée inverse-principe . . . . . . . . . . . 10
Sommaire
Puissance itérée-convergence . . . . . . . . . . . . . . . . 7 Concepts

R Exemples
Rappels et notations . . . . . . . . . . . . . . . . . . . . . . . . . 3 Exercices
Documents

26
 Solution de l’exercice A.1.1

Si λ1 était complexe non réelle, alors λ̄1 serait une autre valeur propre λ2 et on aurait |λ1 | = |λ2 |, ce qui est faux, donc
λ1 est réelle. Il est évident que λ1 est simple.

Retour à l’exercice N