134
Méthode de Rutishauser
et notons E n la sous-matrice
E n =
3
E
E
E
E
E
E
E
C
e 1 f 1 0
···
0
f 1 e 2 f 2
. . .
. . .
0 f 2
. . .
. . .
0
. . .
. . .
. . .
. . .
f n1
0 ··· 0
f n1 e n
4
F
F
F
F
F
F
F
D
Les polynômes caractéristiques des matrices E n vérifient les relations de
récurrence
s 0 ()=1 s 1 ()=e 1
s n ()=(e n )s n1 () f
2
n1 s n2 () pour n =2>===>q
Ils vérifient les propriétés suivantes
lim
$4
s n ()=+4
Si s n ( 0 )=0 > alors s n1 ( 0 )s n+1 ( 0 ) ? 0 pour n =1 > ===> q 1= Le polynôme s n a n racines réelles distinctes qui séparent les (n +1) racines du
polynôme s n+1 (i.e. {?|?}avec s n+1 ({)=s n+1 (})=0et s n (|)=0 ).
Soit d un réel quelconque, si on pose
Vjq(s n (d)) =
½
vjq(s n (d))
si
s n (d) 6 =0
vjq(s n1 (d))
si
s n (d)=0
alors on démontre que le nombre Q (n> d) de changements de signes entre
éléments de l’ensemble ordonné {+>Vjq(s 1 (d))> ===> Vjq(s n (d))} est égal au
nombre de racines du polynôme s n qui sont strictement inférieures à d.
Algorithme de Givens. Pour déterminer une valeur propre de la matrice E,
on se donne un intervalle arbitraire [d 0 >e 0 ] contenant l = On prendra par
exemple d 0 = e 0 = kEk = Soit f 0 le milieu de l’intervalle [d 0 >e 0 ]
si Q (q> f 0 ) l l 5 [d 0 >f 0 [
si Q (q> f 0 ) ?l
l 5 [f 0 >e 0 ]
On restreint alors l’intervalle de recherche à [d 1 >e 1 ] dans lequel on peut
trouver l = On détermine ainsi une suite d’intervalles emboîtés [d n >e n ]
contenant l et de longueur (e 0 d 0 )@2
n
.
6.5 Méthode de Rutishauser
La méthode de Rutishauser est fondée sur la décomposition OX où O est
une matrice triangulaire inférieure dont les éléments diagonaux sont égaux
Méthode de Rutishauser
et notons E n la sous-matrice
E n =
3
E
E
E
E
E
E
E
C
e 1 f 1 0
···
0
f 1 e 2 f 2
. . .
. . .
0 f 2
. . .
. . .
0
. . .
. . .
. . .
. . .
f n1
0 ··· 0
f n1 e n
4
F
F
F
F
F
F
F
D
Les polynômes caractéristiques des matrices E n vérifient les relations de
récurrence
s 0 ()=1 s 1 ()=e 1
s n ()=(e n )s n1 () f
2
n1 s n2 () pour n =2>===>q
Ils vérifient les propriétés suivantes
lim
$4
s n ()=+4
Si s n ( 0 )=0 > alors s n1 ( 0 )s n+1 ( 0 ) ? 0 pour n =1 > ===> q 1= Le polynôme s n a n racines réelles distinctes qui séparent les (n +1) racines du
polynôme s n+1 (i.e. {?|?}avec s n+1 ({)=s n+1 (})=0et s n (|)=0 ).
Soit d un réel quelconque, si on pose
Vjq(s n (d)) =
½
vjq(s n (d))
si
s n (d) 6 =0
vjq(s n1 (d))
si
s n (d)=0
alors on démontre que le nombre Q (n> d) de changements de signes entre
éléments de l’ensemble ordonné {+>Vjq(s 1 (d))> ===> Vjq(s n (d))} est égal au
nombre de racines du polynôme s n qui sont strictement inférieures à d.
Algorithme de Givens. Pour déterminer une valeur propre de la matrice E,
on se donne un intervalle arbitraire [d 0 >e 0 ] contenant l = On prendra par
exemple d 0 = e 0 = kEk = Soit f 0 le milieu de l’intervalle [d 0 >e 0 ]
si Q (q> f 0 ) l l 5 [d 0 >f 0 [
si Q (q> f 0 ) ?l
l 5 [f 0 >e 0 ]
On restreint alors l’intervalle de recherche à [d 1 >e 1 ] dans lequel on peut
trouver l = On détermine ainsi une suite d’intervalles emboîtés [d n >e n ]
contenant l et de longueur (e 0 d 0 )@2
n
.
6.5 Méthode de Rutishauser
La méthode de Rutishauser est fondée sur la décomposition OX où O est
une matrice triangulaire inférieure dont les éléments diagonaux sont égaux