4.5 Tests d’arrˆ et
157
imposant que x
(k)
∈ Y k et que le r´ esidu r
(k) = b − Ax
(k) soit orthogonal `
a
L k . Si Y k = L k , la projection est dite orthogonale ; sinon, elle est dite oblique.
Par exemple, la m´ ethode d’Arnoldi est une m´ ethode de projection orthogonale o` u L k = Y k = K k (A; r
(0) ), tandis que GMRES est une m´ ethode de
projection oblique avec Y k = K k (A; r
(0) ) et L k = AY k . Remarquons d’ailleurs
que certaines m´ ethodes classiques introduites dans les sections pr´ ec´ edentes appartiennent aussi `
a cette cat´ egorie. Par exemple, la m´ ethode de Gauss-Seidel
est une projection orthogonale o` u K k (A; r
(0) ) = vect(e k ), pour k = 1, . . ., n.
Les projections sont effectu´ ees de mani` ere cyclique de 1 ` a n jusqu’` a convergence.
4.5 Tests d’arrˆ et
Dans cette section nous abordons le probl` eme de l’estimation de l’erreur induite par une m´ ethode it´ erative. En particulier, on cherche `
a ´ evaluer le nombre
d’it´ erations k min n´ ecessaire pour que la norme de l’erreur divis´ ee par celle de
l’erreur initiale soit inf´ erieure ` a un ε fix´ e.
En pratique, une estimation a priori de k min peut ˆ etre obtenue `
a partir de
(4.2), qui donne la vitesse `
a laquelle e
(k)
→ 0 quand k tend vers l’infini.
D’apr` es (4.4), on obtient
(k)
e (0)
≤ ≤B
k
.
Ainsi, B
k
donne une estimation du facteur de r´ eduction de la norme de
l’erreur apr` es k it´ erations. Typiquement, on poursuit les it´ erations jusqu’` a ce
que
(k)
≤ εe
(0)
avec ε < 1.
(4.65)
Si on suppose ρ(B) < 1, alors la Propri´ et´ e 1.12 implique qu’il existe une norme
matricielle · · telle que B < 1. Par cons´ equent, B
k
tend vers z´ ero quand
k tend vers l’infini ; (4.65) peut donc ˆ etre satisfait pour un k assez grand tel
que B
k
≤ ε. N´ eanmoins, puisque B
k
< 1, l’in´ egalit´ e pr´ ec´ edente revient ` a
avoir
k ≥
log(ε)
1
k
log B
k
= −
log(ε)
R k (B)
,
(4.66)
o` u R k (B) est le taux de convergence moyen introduit dans la D´ efinition 4.2.
D’un point de vue pratique, (4.66) est inutile car non lin´ eaire en k ; si le taux
de convergence asymptotique est utilis´ e (au lieu du taux moyen), on obtient
l’estimation suivante pour k min :
k min −
log(ε)
R(B)
.
(4.67)
157
imposant que x
(k)
∈ Y k et que le r´ esidu r
(k) = b − Ax
(k) soit orthogonal `
a
L k . Si Y k = L k , la projection est dite orthogonale ; sinon, elle est dite oblique.
Par exemple, la m´ ethode d’Arnoldi est une m´ ethode de projection orthogonale o` u L k = Y k = K k (A; r
(0) ), tandis que GMRES est une m´ ethode de
projection oblique avec Y k = K k (A; r
(0) ) et L k = AY k . Remarquons d’ailleurs
que certaines m´ ethodes classiques introduites dans les sections pr´ ec´ edentes appartiennent aussi `
a cette cat´ egorie. Par exemple, la m´ ethode de Gauss-Seidel
est une projection orthogonale o` u K k (A; r
(0) ) = vect(e k ), pour k = 1, . . ., n.
Les projections sont effectu´ ees de mani` ere cyclique de 1 ` a n jusqu’` a convergence.
4.5 Tests d’arrˆ et
Dans cette section nous abordons le probl` eme de l’estimation de l’erreur induite par une m´ ethode it´ erative. En particulier, on cherche `
a ´ evaluer le nombre
d’it´ erations k min n´ ecessaire pour que la norme de l’erreur divis´ ee par celle de
l’erreur initiale soit inf´ erieure ` a un ε fix´ e.
En pratique, une estimation a priori de k min peut ˆ etre obtenue `
a partir de
(4.2), qui donne la vitesse `
a laquelle e
(k)
→ 0 quand k tend vers l’infini.
D’apr` es (4.4), on obtient
(k)
e (0)
≤ ≤B
k
.
Ainsi, B
k
donne une estimation du facteur de r´ eduction de la norme de
l’erreur apr` es k it´ erations. Typiquement, on poursuit les it´ erations jusqu’` a ce
que
(k)
≤ εe
(0)
avec ε < 1.
(4.65)
Si on suppose ρ(B) < 1, alors la Propri´ et´ e 1.12 implique qu’il existe une norme
matricielle · · telle que B < 1. Par cons´ equent, B
k
tend vers z´ ero quand
k tend vers l’infini ; (4.65) peut donc ˆ etre satisfait pour un k assez grand tel
que B
k
≤ ε. N´ eanmoins, puisque B
k
< 1, l’in´ egalit´ e pr´ ec´ edente revient ` a
avoir
k ≥
log(ε)
1
k
log B
k
= −
log(ε)
R k (B)
,
(4.66)
o` u R k (B) est le taux de convergence moyen introduit dans la D´ efinition 4.2.
D’un point de vue pratique, (4.66) est inutile car non lin´ eaire en k ; si le taux
de convergence asymptotique est utilis´ e (au lieu du taux moyen), on obtient
l’estimation suivante pour k min :
k min −
log(ε)
R(B)
.
(4.67)