5.7 La m´ ethode QR avec translations
197
pour un ε fix´ e de l’ordre de l’unit´ e d’arrondi. Ce test est p. ex. adopt´ e dans la
biblioth` eque EISPACK. Si A est une matrice de Hessenberg et si a
(k)
n,n−1 est
annul´ e pour un certain k, alors t
(k)
n,n est une approximation de λ n . On peut donc
faire une nouvelle it´ eration QR avec translations sur T
(k) (1 : n−1, 1 : n−1), et
ainsi de suite. Cet algorithme est une technique de d´ eflation (voir la Remarque
5.3 pour un autre exemple).
Exemple 5.10 On consid` ere ` a nouveau la matrice A de l’Exemple 5.9. Le Programme 28, avec tol ´ egal `
a l’unit´ e d’arrondi, converge en 14 it´ erations vers la matrice suivante qui est une approximation de la forme de Schur r´ eelle de A et qui
contient sur la diagonale les valeurs propres correctes de A (jusqu’au sixi` eme chiffre
significatif) :
T
(40) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
6 5
0
0
0
0
0
−21.2768
2.5888 −0.0445 −4.2959
0
0 −13.1263 −4.0294 −13.079
0
0
0 2 1 .2768 −2.6197
0
0
0
0 1 3 .1263
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
On donne dans la Table 5.2 le taux de convergence p
(k) de la suite
t
(k)
n,n−1
(n = 5) :
p
(k) = 1 +
1
log(ηk)
log
|t
(k)
n,n−1 |
|t
(k−1)
n,n−1 |
,
k≥ 1.
Les r´ esultats sont conformes au taux quadratique auquel on s’attendait.
•
Table 5.2. Taux de convergence de la suite
t
(k)
n,n−1
pour la m´ ethode QR avec
translations
k |t
(k)
n,n−1 |/T
(0)
2
p
(k)
0
0.13865
1
1.5401 · 10
−2
2.1122
2
1.2213 · 10
−4
2.1591
3
1.8268 · 10
−8
1.9775
4
8.9036 · 10
−16
1.9449
On propose une impl´ ementation MATLAB de la m´ ethode QR avec translations (5.52) dans le Programme 34. Le code utilise le Programme 27 pour
r´ eduire la matrice A sous forme de Hessenberg sup´ erieure et le Programme 29
pour effectuer l’´ etape de factorisation QR. Les param` etres d’entr´ ee tol et
nmax sont la tol´ erance dans (5.53) et le nombre maximum d’it´ erations. En
sortie, le programme retourne la forme (approch´ ee) de Schur r´ eelle de A et le
nombre d’it´ erations effectivement effectu´ ees.
197
pour un ε fix´ e de l’ordre de l’unit´ e d’arrondi. Ce test est p. ex. adopt´ e dans la
biblioth` eque EISPACK. Si A est une matrice de Hessenberg et si a
(k)
n,n−1 est
annul´ e pour un certain k, alors t
(k)
n,n est une approximation de λ n . On peut donc
faire une nouvelle it´ eration QR avec translations sur T
(k) (1 : n−1, 1 : n−1), et
ainsi de suite. Cet algorithme est une technique de d´ eflation (voir la Remarque
5.3 pour un autre exemple).
Exemple 5.10 On consid` ere ` a nouveau la matrice A de l’Exemple 5.9. Le Programme 28, avec tol ´ egal `
a l’unit´ e d’arrondi, converge en 14 it´ erations vers la matrice suivante qui est une approximation de la forme de Schur r´ eelle de A et qui
contient sur la diagonale les valeurs propres correctes de A (jusqu’au sixi` eme chiffre
significatif) :
T
(40) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
6 5
0
0
0
0
0
−21.2768
2.5888 −0.0445 −4.2959
0
0 −13.1263 −4.0294 −13.079
0
0
0 2 1 .2768 −2.6197
0
0
0
0 1 3 .1263
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
On donne dans la Table 5.2 le taux de convergence p
(k) de la suite
t
(k)
n,n−1
(n = 5) :
p
(k) = 1 +
1
log(ηk)
log
|t
(k)
n,n−1 |
|t
(k−1)
n,n−1 |
,
k≥ 1.
Les r´ esultats sont conformes au taux quadratique auquel on s’attendait.
•
Table 5.2. Taux de convergence de la suite
t
(k)
n,n−1
pour la m´ ethode QR avec
translations
k |t
(k)
n,n−1 |/T
(0)
2
p
(k)
0
0.13865
1
1.5401 · 10
−2
2.1122
2
1.2213 · 10
−4
2.1591
3
1.8268 · 10
−8
1.9775
4
8.9036 · 10
−16
1.9449
On propose une impl´ ementation MATLAB de la m´ ethode QR avec translations (5.52) dans le Programme 34. Le code utilise le Programme 27 pour
r´ eduire la matrice A sous forme de Hessenberg sup´ erieure et le Programme 29
pour effectuer l’´ etape de factorisation QR. Les param` etres d’entr´ ee tol et
nmax sont la tol´ erance dans (5.53) et le nombre maximum d’it´ erations. En
sortie, le programme retourne la forme (approch´ ee) de Schur r´ eelle de A et le
nombre d’it´ erations effectivement effectu´ ees.