5.8 Calcul des valeurs propres des matrices sym´ etriques
203
ce qui montre que T a trois valeurs propres plus petites que 3, puisqu’il y a trois
changements de signe.
•
Pr´ esentons maintenant la m´ ethode de Givens pour le calcul des valeurs propres
de T. Posons b 0 = b n = 0, le Th´ eor` eme 5.2 donne un intervalle J = [α, β] qui
contient le spectre de T, avec
α = min
1≤i≤n
[d i − (|b i−1 | + |b i |)] ,
β = max
1≤i≤n
[d i + (|b i−1 | + |b i |)] .
L’ensemble J est utilis´ e comme donn´ ee initiale pour la recherche d’une valeur
propre λ i de T, pour i = 1, . . ., n par dichotomie (voir Chapitre 6).
Plus pr´ ecis´ ement, pour a
(0) = α et b
(0) = β, on pose c
(0) = (α + β)/2 et on
calcule s(c
(0) ) ; on pose alors, d’apr` es Propri´ et´ e 5.9, b
(1) = c
(0) si s(c
(0) ) > (n−
i), et a
(1) = c
(0) autrement. Apr` es r it´ erations, la valeur c
(r) = (a
(r) + b
(r) )/2
fournit une approximation de λ i ` a (|α| + |β|) · 2
−(r+1) pr` es (voir (6.9)).
Pendant l’ex´ ecution de la m´ ethode de Givens, il est possible de m´ emoriser
de mani` ere syst´ ematique les informations sur la position des valeurs propres
de T dans l’intervalle J . L’algorithme r´ esultant produit une suite de sousintervalles a
(r)
j , b
(r)
j , j = 1, . . . , n, de longueur arbitrairement petite et contenant chacun une valeur propre λ j de T (pour plus de d´ etails, voir [BMW67]).
Exemple 5.13 Utilisons la m´ ethode de Givens pour calculer la valeur propre λ2
2.62 de la matrice T de l’Exemple 5.12. En prenant tol=10
−4 dans le Programme
39, on obtient les r´ esultats pr´ esent´ es dans la Table 5.4 (on a not´ e s
(k) = s(c
(k) ) pour
abr´ eger). On constate la convergence de la suite c
(k) vers la valeur propre voulue en
13 it´ erations. Des r´ esultats similaires sont obtenus en ex´ ecutant le Programme 39
pour les autres valeurs propres de T.
•
Table 5.4. Convergence de la m´ ethode de Givens pour le calcul de la valeur propre
λ2 de la matrice T d´ efinie dans l’Exemple 5.12
k
a
(k)
b
(k)
c
(k)
s
(k)
k
a
(k)
b
(k)
c
(k)
s
(k)
0
0
4.000 2.0000
2
7 2.5938 2.625 2.6094
2
1 2.0000 4.000 3.0000
3
8 2.6094 2.625 2.6172
2
2 2.0000 3.000 2.5000
2
9 2.6094 2.625 2.6172
2
3 2.5000 3.000 2.7500
3
10 2.6172 2.625 2.6211
3
4 2.5000 2.750 2.6250
3
11 2.6172 2.621 2.6191
3
5 2.5000 2.625 2.5625
2
12 2.6172 2.619 2.6182
3
6 2.5625 2.625 2.5938
2
13 2.6172 2.618 2.6177
2
Une impl´ ementation MATLAB de l’´ evaluation des polynˆ omes (5.60) est
propos´ ee dans le Programme 38. Il re¸ coit en entr´ ee les vecteurs dd et bb
contenant les diagonales principales et sup´ erieures de T. Les valeurs p i (x),
i = 0, . . ., n sont stock´ ees en sortie dans le vecteur p.
203
ce qui montre que T a trois valeurs propres plus petites que 3, puisqu’il y a trois
changements de signe.
•
Pr´ esentons maintenant la m´ ethode de Givens pour le calcul des valeurs propres
de T. Posons b 0 = b n = 0, le Th´ eor` eme 5.2 donne un intervalle J = [α, β] qui
contient le spectre de T, avec
α = min
1≤i≤n
[d i − (|b i−1 | + |b i |)] ,
β = max
1≤i≤n
[d i + (|b i−1 | + |b i |)] .
L’ensemble J est utilis´ e comme donn´ ee initiale pour la recherche d’une valeur
propre λ i de T, pour i = 1, . . ., n par dichotomie (voir Chapitre 6).
Plus pr´ ecis´ ement, pour a
(0) = α et b
(0) = β, on pose c
(0) = (α + β)/2 et on
calcule s(c
(0) ) ; on pose alors, d’apr` es Propri´ et´ e 5.9, b
(1) = c
(0) si s(c
(0) ) > (n−
i), et a
(1) = c
(0) autrement. Apr` es r it´ erations, la valeur c
(r) = (a
(r) + b
(r) )/2
fournit une approximation de λ i ` a (|α| + |β|) · 2
−(r+1) pr` es (voir (6.9)).
Pendant l’ex´ ecution de la m´ ethode de Givens, il est possible de m´ emoriser
de mani` ere syst´ ematique les informations sur la position des valeurs propres
de T dans l’intervalle J . L’algorithme r´ esultant produit une suite de sousintervalles a
(r)
j , b
(r)
j , j = 1, . . . , n, de longueur arbitrairement petite et contenant chacun une valeur propre λ j de T (pour plus de d´ etails, voir [BMW67]).
Exemple 5.13 Utilisons la m´ ethode de Givens pour calculer la valeur propre λ2
2.62 de la matrice T de l’Exemple 5.12. En prenant tol=10
−4 dans le Programme
39, on obtient les r´ esultats pr´ esent´ es dans la Table 5.4 (on a not´ e s
(k) = s(c
(k) ) pour
abr´ eger). On constate la convergence de la suite c
(k) vers la valeur propre voulue en
13 it´ erations. Des r´ esultats similaires sont obtenus en ex´ ecutant le Programme 39
pour les autres valeurs propres de T.
•
Table 5.4. Convergence de la m´ ethode de Givens pour le calcul de la valeur propre
λ2 de la matrice T d´ efinie dans l’Exemple 5.12
k
a
(k)
b
(k)
c
(k)
s
(k)
k
a
(k)
b
(k)
c
(k)
s
(k)
0
0
4.000 2.0000
2
7 2.5938 2.625 2.6094
2
1 2.0000 4.000 3.0000
3
8 2.6094 2.625 2.6172
2
2 2.0000 3.000 2.5000
2
9 2.6094 2.625 2.6172
2
3 2.5000 3.000 2.7500
3
10 2.6172 2.625 2.6211
3
4 2.5000 2.750 2.6250
3
11 2.6172 2.621 2.6191
3
5 2.5000 2.625 2.5625
2
12 2.6172 2.619 2.6182
3
6 2.5625 2.625 2.5938
2
13 2.6172 2.618 2.6177
2
Une impl´ ementation MATLAB de l’´ evaluation des polynˆ omes (5.60) est
propos´ ee dans le Programme 38. Il re¸ coit en entr´ ee les vecteurs dd et bb
contenant les diagonales principales et sup´ erieures de T. Les valeurs p i (x),
i = 0, . . ., n sont stock´ ees en sortie dans le vecteur p.