202
5 Approximation des valeurs propres et des vecteurs propres
5.8.2 La m´ ethode des suites de Sturm
Nous consid´ erons dans cette section le probl` eme du calcul des valeurs propres
d’une matrice sym´ etrique tridiagonale `
a coefficients r´ eels T. Typiquement,
cette question se pose quand on applique la transformation de Householder `
a
une matrice sym´ etrique A (voir Section 5.6.2) ou quand on r´ esout un probl` eme
aux limites en dimension 1 (voir Section 13.2 pour un exemple).
Analysons la m´ ethode des suites de Sturm, ou m´ ethode de Givens, introduite dans [Giv54]. Pour i = 1, . . . , n, on note d i les ´ el´ ements diagonaux de
T et b i , i = 1, . . . , n − 1, ses ´ el´ ements sur et sous-diagonaux. On supposera
b i = 0 pour tout i (autrement le calcul peut se ramener ` a des probl` emes moins
complexes).
Soit T i le mineur principal d’ordre i de la matrice T et p 0 (x) = 1, on
d´ efinit pour i = 1, . . ., n la suite de polynˆ omes p i (x) = d´ et(T i − xI i )
p 1 (x) = d 1 − x ,
p i (x) = (d i − x)p i−1 (x) − b
2
i−1 p i−2 (x), i = 2, . . . , n.
(5.60)
On peut v´ erifier que p n est le polynˆ ome caract´ eristique de T ; le coˆ ut du calcul
de l’´ evaluation de ce polynˆ ome en x est de l’ordre de 2n flops. La suite (5.60)
est appel´ ee suite de Sturm. Elle poss` ede la propri´ et´ e suivante, dont la preuve
se trouve dans [Wil65], Chapitre 2, Section 47 et Chapitre 5, Section 37.
Propri´ et´ e 5.9 (suites de Sturm) Pour i = 2, . . ., n les valeurs propres de
T i−1 s´ eparent strictement celles de T i , c’est-` a-dire
λ i (T i ) < λ i−1 (T i−1 ) < λ i−1 (T i ) < . . . < λ 2 (T i ) < λ 1 (T i−1 ) < λ 1 (T i ).
De plus, si on pose pour tout r´ eel µ
S µ = {p 0 (µ), p 1 (µ), . . . , p n (µ)},
le nombre s(µ) de changements de signe dans S µ donne le nombre de valeurs
propres de T strictement plus petites que µ, avec la convention que p i (µ) a un
signe oppos´ e ` a p i−1 (µ) si p i (µ) = 0 (deux ´ el´ ements cons´ ecutifs de la suite ne
peuvent pas s’annuler pour la mˆ eme valeur µ).
Exemple 5.12 Soit T la partie tridiagonale de la matrice de Hilbert H4 ∈ R
4×4 .
Les valeurs propres de T sont (avec 5 chiffres significatifs) λ1 = 1.2813, λ2 = 0.4205,
λ3 = −0.1417 et λ4 = 0.1161. En prenant µ = 0, le Programme 38 calcule la suite
de Sturm suivante :
S0 = {p0(0), p1(0), p2(0), p3(0), p4(0)} = {1, 1, 0.0833, −0.0458, −0.0089},
d’o` u on d´ eduit, d’apr` es la Propri´ et´ e 5.9, que la matrice T a 1 valeur propre plus
petite que 0. Dans le cas de la matrice T = tridiag 4 (−1, 2, −1), de valeurs propres
{0.38, 1.38, 2.62, 3.62}, on obtient avec µ = 3
{p0(3), p1(3), p2(3), p3(3), p4(3)} = {1, −1, 0, 1, −1},
5 Approximation des valeurs propres et des vecteurs propres
5.8.2 La m´ ethode des suites de Sturm
Nous consid´ erons dans cette section le probl` eme du calcul des valeurs propres
d’une matrice sym´ etrique tridiagonale `
a coefficients r´ eels T. Typiquement,
cette question se pose quand on applique la transformation de Householder `
a
une matrice sym´ etrique A (voir Section 5.6.2) ou quand on r´ esout un probl` eme
aux limites en dimension 1 (voir Section 13.2 pour un exemple).
Analysons la m´ ethode des suites de Sturm, ou m´ ethode de Givens, introduite dans [Giv54]. Pour i = 1, . . . , n, on note d i les ´ el´ ements diagonaux de
T et b i , i = 1, . . . , n − 1, ses ´ el´ ements sur et sous-diagonaux. On supposera
b i = 0 pour tout i (autrement le calcul peut se ramener ` a des probl` emes moins
complexes).
Soit T i le mineur principal d’ordre i de la matrice T et p 0 (x) = 1, on
d´ efinit pour i = 1, . . ., n la suite de polynˆ omes p i (x) = d´ et(T i − xI i )
p 1 (x) = d 1 − x ,
p i (x) = (d i − x)p i−1 (x) − b
2
i−1 p i−2 (x), i = 2, . . . , n.
(5.60)
On peut v´ erifier que p n est le polynˆ ome caract´ eristique de T ; le coˆ ut du calcul
de l’´ evaluation de ce polynˆ ome en x est de l’ordre de 2n flops. La suite (5.60)
est appel´ ee suite de Sturm. Elle poss` ede la propri´ et´ e suivante, dont la preuve
se trouve dans [Wil65], Chapitre 2, Section 47 et Chapitre 5, Section 37.
Propri´ et´ e 5.9 (suites de Sturm) Pour i = 2, . . ., n les valeurs propres de
T i−1 s´ eparent strictement celles de T i , c’est-` a-dire
λ i (T i ) < λ i−1 (T i−1 ) < λ i−1 (T i ) < . . . < λ 2 (T i ) < λ 1 (T i−1 ) < λ 1 (T i ).
De plus, si on pose pour tout r´ eel µ
S µ = {p 0 (µ), p 1 (µ), . . . , p n (µ)},
le nombre s(µ) de changements de signe dans S µ donne le nombre de valeurs
propres de T strictement plus petites que µ, avec la convention que p i (µ) a un
signe oppos´ e ` a p i−1 (µ) si p i (µ) = 0 (deux ´ el´ ements cons´ ecutifs de la suite ne
peuvent pas s’annuler pour la mˆ eme valeur µ).
Exemple 5.12 Soit T la partie tridiagonale de la matrice de Hilbert H4 ∈ R
4×4 .
Les valeurs propres de T sont (avec 5 chiffres significatifs) λ1 = 1.2813, λ2 = 0.4205,
λ3 = −0.1417 et λ4 = 0.1161. En prenant µ = 0, le Programme 38 calcule la suite
de Sturm suivante :
S0 = {p0(0), p1(0), p2(0), p3(0), p4(0)} = {1, 1, 0.0833, −0.0458, −0.0089},
d’o` u on d´ eduit, d’apr` es la Propri´ et´ e 5.9, que la matrice T a 1 valeur propre plus
petite que 0. Dans le cas de la matrice T = tridiag 4 (−1, 2, −1), de valeurs propres
{0.38, 1.38, 2.62, 3.62}, on obtient avec µ = 3
{p0(3), p1(3), p2(3), p3(3), p4(3)} = {1, −1, 0, 1, −1},