4
M´ ethodes it´ eratives pour la r´ esolution
des syst` emes lin´ eaires
Les m´ ethodes it´ eratives donnent, en th´ eorie, la solution x d’un syst` eme lin´ eaire apr` es un nombre infini d’it´ erations. A chaque pas, elles n´ ecessitent le
calcul du r´ esidu du syst` eme. Dans le cas d’une matrice pleine, leur coˆ ut est
donc de l’ordre de n
2 op´ erations `
a chaque it´ eration, alors que le coˆ ut des m´ ethodes directes est, en tout et pour tout, de l’ordre de
2
3 n
3 . Les m´ ethodes
it´ eratives peuvent donc devenir comp´ etitives si elles convergent en un nombre
d’it´ erations ind´ ependant de n, ou croissant sous-lin´ eairement avec n.
Pour les grandes matrices creuses, les m´ ethodes directes s’av` erent parfois tr` es coˆ uteuses ` a cause du remplissage (fill-in) et les m´ ethodes it´ eratives
peuvent offrir une alternative int´ eressante. Il faut n´ eanmoins savoir qu’il existe
des solveurs directs tr` es efficaces pour certains types de matrices creuses (voir
p. ex. [GL81], [DER86], [Saa90]) comme, par exemple, celles qu’on rencontre
dans l’approximation des ´ equations aux d´ eriv´ ees partielles (voir Chapitres 11
et 12).
Enfin, quand A est mal conditionn´ ee, les techniques de pr´ econditionnement
qui seront pr´ esent´ ees ` a la Section 4.3.2 conduisent `
a une utilisation combin´ ee
des m´ ethodes directes et it´ eratives.
4.1 Convergence des m´ ethodes it´ eratives
L’id´ ee de base des m´ ethodes it´ eratives est de construire une suite convergente
de vecteurs
x
(k)
telle que
x = lim
k→∞
x
(k) ,
(4.1)
o` u x est la solution de (3.2). En pratique, le calcul devrait ˆ etre interrompu `
a
la premi` ere it´ eration n pour laquelle x
(n)
− x < ε, o` u ε est une tol´ erance
fix´ ee et ·· une norme vectorielle donn´ ee. Mais comme la solution exacte n’est
´ evidemment pas connue, il faudra d´ efinir un crit` ere d’arrˆ et plus commode (voir
Section 4.5).
M´ ethodes it´ eratives pour la r´ esolution
des syst` emes lin´ eaires
Les m´ ethodes it´ eratives donnent, en th´ eorie, la solution x d’un syst` eme lin´ eaire apr` es un nombre infini d’it´ erations. A chaque pas, elles n´ ecessitent le
calcul du r´ esidu du syst` eme. Dans le cas d’une matrice pleine, leur coˆ ut est
donc de l’ordre de n
2 op´ erations `
a chaque it´ eration, alors que le coˆ ut des m´ ethodes directes est, en tout et pour tout, de l’ordre de
2
3 n
3 . Les m´ ethodes
it´ eratives peuvent donc devenir comp´ etitives si elles convergent en un nombre
d’it´ erations ind´ ependant de n, ou croissant sous-lin´ eairement avec n.
Pour les grandes matrices creuses, les m´ ethodes directes s’av` erent parfois tr` es coˆ uteuses ` a cause du remplissage (fill-in) et les m´ ethodes it´ eratives
peuvent offrir une alternative int´ eressante. Il faut n´ eanmoins savoir qu’il existe
des solveurs directs tr` es efficaces pour certains types de matrices creuses (voir
p. ex. [GL81], [DER86], [Saa90]) comme, par exemple, celles qu’on rencontre
dans l’approximation des ´ equations aux d´ eriv´ ees partielles (voir Chapitres 11
et 12).
Enfin, quand A est mal conditionn´ ee, les techniques de pr´ econditionnement
qui seront pr´ esent´ ees ` a la Section 4.3.2 conduisent `
a une utilisation combin´ ee
des m´ ethodes directes et it´ eratives.
4.1 Convergence des m´ ethodes it´ eratives
L’id´ ee de base des m´ ethodes it´ eratives est de construire une suite convergente
de vecteurs
x
(k)
telle que
x = lim
k→∞
x
(k) ,
(4.1)
o` u x est la solution de (3.2). En pratique, le calcul devrait ˆ etre interrompu `
a
la premi` ere it´ eration n pour laquelle x
(n)
− x < ε, o` u ε est une tol´ erance
fix´ ee et ·· une norme vectorielle donn´ ee. Mais comme la solution exacte n’est
´ evidemment pas connue, il faudra d´ efinir un crit` ere d’arrˆ et plus commode (voir
Section 4.5).