4.1 Convergence des m´ ethodes it´ eratives
117
La Propri´ et´ e 1.12 et le Th´ eor` eme 1.4 permettent d’´ etablir que la condition
< 1, pour une norme matricielle consistante arbitraire, est suffisante
pour que la m´ ethode converge. Il est raisonnable de penser que la convergence
est d’autant plus rapide que ρ(B) est petit. Une estimation de ρ(B) peut donc
fournir une bonne indication sur la convergence de l’algorithme. La d´ efinition
suivante introduit d’autres quantit´ es utiles ` a l’´ etude de la convergence.
D´ efinition 4.2 Soit B une matrice d’it´ eration. On appelle :
1. B
m
le facteur de convergence ` a l’it´ eration m ;
2. B
m
1/m le facteur moyen de convergence ` a l’it´ eration m ;
3. R m (B) = −
1
m log B
m
le taux moyen de convergence ` a l’it´ eration m.
Le calcul de ces quantit´ es est trop coˆ uteux car il requiert l’´ evaluation de B
m .
On pr´ ef` ere donc en g´ en´ eral estimer le taux de convergence asymptotique d´ efini
par
R(B) = lim
k→∞
R k (B) = − log ρ(B),
(4.5)
o` u on a utilis´ e la Propri´ et´ e 1.13. En particulier, si B est sym´ etrique, on a
R m (B) = −
1
m
log B
m
2 = − log ρ(B).
Pour des matrices non sym´ etriques, ρ(B) fournit parfois une estimation trop
optimiste de B
m
1/m (voir [Axe94], Section 5.1). En effet, bien que ρ(B) < 1,
la convergence vers z´ ero de la suite B
m
peut ne pas ˆ etre monotone (voir
Exercice 1). D’apr` es (4.5), ρ(B) est le facteur de convergence asymptotique.
Nous d´ efinirons des crit` eres pour ´ evaluer toutes ces quantit´ es ` a la Section 4.5.
Remarque 4.1 Les it´ erations d´ efinies en (4.2) sont un cas particulier des
m´ ethodes it´ eratives de la forme
x
(0) = f 0 (A, b),
x
(n+1) = f n+1 (x
(n) , x
(n−1) , . . . , x
(n−m) , A, b), pour n ≥ m,
o` u les f i sont des fonctions et les x
(m) , . . . , x
(1) des vecteurs donn´ es. Le nombre
de pas dont d´ epend l’it´ eration courante s’appelle ordre de la m´ ethode. Si les
fonctions f i sont ind´ ependantes de i, la m´ ethode est dite stationnaire. Elle
est instationnaire dans le cas contraire. Enfin, si f i d´ epend lin´ eairement de
x
(0) , . . . , x
(m) , la m´ ethode est dite lin´ eaire, autrement elle est dite non lin´ eaire.
Au regard de ces d´ efinitions, les algorithmes consid´ er´ es jusqu’` a pr´ esent
sont donc des m´ ethodes it´ eratives lin´ eaires stationnaires du premier ordre.
Nous donnerons `
a la Section 4.3 des exemples de m´ ethodes instationnaires.
117
La Propri´ et´ e 1.12 et le Th´ eor` eme 1.4 permettent d’´ etablir que la condition
< 1, pour une norme matricielle consistante arbitraire, est suffisante
pour que la m´ ethode converge. Il est raisonnable de penser que la convergence
est d’autant plus rapide que ρ(B) est petit. Une estimation de ρ(B) peut donc
fournir une bonne indication sur la convergence de l’algorithme. La d´ efinition
suivante introduit d’autres quantit´ es utiles ` a l’´ etude de la convergence.
D´ efinition 4.2 Soit B une matrice d’it´ eration. On appelle :
1. B
m
le facteur de convergence ` a l’it´ eration m ;
2. B
m
1/m le facteur moyen de convergence ` a l’it´ eration m ;
3. R m (B) = −
1
m log B
m
le taux moyen de convergence ` a l’it´ eration m.
Le calcul de ces quantit´ es est trop coˆ uteux car il requiert l’´ evaluation de B
m .
On pr´ ef` ere donc en g´ en´ eral estimer le taux de convergence asymptotique d´ efini
par
R(B) = lim
k→∞
R k (B) = − log ρ(B),
(4.5)
o` u on a utilis´ e la Propri´ et´ e 1.13. En particulier, si B est sym´ etrique, on a
R m (B) = −
1
m
log B
m
2 = − log ρ(B).
Pour des matrices non sym´ etriques, ρ(B) fournit parfois une estimation trop
optimiste de B
m
1/m (voir [Axe94], Section 5.1). En effet, bien que ρ(B) < 1,
la convergence vers z´ ero de la suite B
m
peut ne pas ˆ etre monotone (voir
Exercice 1). D’apr` es (4.5), ρ(B) est le facteur de convergence asymptotique.
Nous d´ efinirons des crit` eres pour ´ evaluer toutes ces quantit´ es ` a la Section 4.5.
Remarque 4.1 Les it´ erations d´ efinies en (4.2) sont un cas particulier des
m´ ethodes it´ eratives de la forme
x
(0) = f 0 (A, b),
x
(n+1) = f n+1 (x
(n) , x
(n−1) , . . . , x
(n−m) , A, b), pour n ≥ m,
o` u les f i sont des fonctions et les x
(m) , . . . , x
(1) des vecteurs donn´ es. Le nombre
de pas dont d´ epend l’it´ eration courante s’appelle ordre de la m´ ethode. Si les
fonctions f i sont ind´ ependantes de i, la m´ ethode est dite stationnaire. Elle
est instationnaire dans le cas contraire. Enfin, si f i d´ epend lin´ eairement de
x
(0) , . . . , x
(m) , la m´ ethode est dite lin´ eaire, autrement elle est dite non lin´ eaire.
Au regard de ces d´ efinitions, les algorithmes consid´ er´ es jusqu’` a pr´ esent
sont donc des m´ ethodes it´ eratives lin´ eaires stationnaires du premier ordre.
Nous donnerons `
a la Section 4.3 des exemples de m´ ethodes instationnaires.