4.3 M´ ethodes it´ eratives stationnaires et instationnaires
131
ou
P
−1
L AP
−1
R y = P
−1
L b, y = P R x.
On parle de pr´ econditionneurs ponctuels (resp. pr´ econditionneurs par blocs),
s’ils sont appliqu´ es aux coefficients (resp. aux blocs) de A. Les m´ ethodes it´ eratives consid´ er´ ees jusqu’` a pr´ esent correspondent ` a des it´ erations de point
fixe sur un syst` eme pr´ econditionn´ e ` a gauche. L’algorithme (4.24) montre qu’il
n’est pas n´ ecessaire de calculer l’inverse de P ; le rˆ ole de P est en effet de
“pr´ econditionner” le r´ esidu r
(k) par la r´ esolution du syst` eme suppl´ ementaire
Pz
(k) = r
(k) .
Le pr´ econditionneur agissant sur le rayon spectral de la matrice d’it´ eration,
il serait utile de d´ eterminer, pour un syst` eme lin´ eaire donn´ e, un pr´ econditionneur optimal, i.e. un pr´ econditionneur qui rende ind´ ependant de la taille du
syst` eme le nombre d’it´ erations n´ ecessaires ` a la convergence. Remarquer que
le choix P=A est optimal mais trivialement inefficace ; nous examinons cidessous des alternatives plus int´ eressantes pour les calculs.
Nous manquons de r´ esultats th´ eoriques g´ en´ eraux pour construire des pr´ econditionneurs optimaux. Mais il est commun´ ement admis que P est un bon
pr´ econditionneur pour A si P
−1 A est “presque” une matrice normale et si ses
valeurs propres sont contenues dans une r´ egion suffisamment petite du plan
complexe. Le choix d’un pr´ econditionneur doit aussi ˆ etre guid´ e par des consid´ erations pratiques, en particulier son coˆ ut de calcul et la place qu’il occupe
en m´ emoire.
On peut s´ eparer les pr´ econditionneurs en deux cat´ egories principales :
les pr´ econditionneurs alg´ ebriques et fonctionnels. Les pr´ econditionneurs alg´ ebriques sont ind´ ependants du probl` eme dont est issu le syst` eme ` a r´ esoudre :
ils sont construits par une proc´ edure purement alg´ ebrique. Au contraire, les
pr´ econditionneurs fonctionnels tirent avantage de la connaissance du probl` eme
et sont construits en cons´ equence.
D´ ecrivons ` a pr´ esent d’autres pr´ econditionneurs alg´ ebriques d’usage courant qui viennent s’ajouter aux pr´ econditionneurs d´ ej` a introduits `
a la Section 4.2.5.
1. Pr´ econditionneurs diagonaux : ils correspondent au cas o` u P est simplement une matrice diagonale. Pour les matrices sym´ etriques d´ efinies
positives, il est souvent assez efficace de prendre pour P la diagonale de
A. Un choix habituel pour les matrices non sym´ etriques est de prendre
p ii =
⎛
⎝
n
j=1
a
2
ij
⎞
⎠
1/2
.
En se rappelant les remarques faites au sujet du scaling d’une matrice (voir
Section 3.11.1), on comprendra que la construction d’un P qui minimise
K(P
−1 A) est loin d’ˆ etre triviale.
131
ou
P
−1
L AP
−1
R y = P
−1
L b, y = P R x.
On parle de pr´ econditionneurs ponctuels (resp. pr´ econditionneurs par blocs),
s’ils sont appliqu´ es aux coefficients (resp. aux blocs) de A. Les m´ ethodes it´ eratives consid´ er´ ees jusqu’` a pr´ esent correspondent ` a des it´ erations de point
fixe sur un syst` eme pr´ econditionn´ e ` a gauche. L’algorithme (4.24) montre qu’il
n’est pas n´ ecessaire de calculer l’inverse de P ; le rˆ ole de P est en effet de
“pr´ econditionner” le r´ esidu r
(k) par la r´ esolution du syst` eme suppl´ ementaire
Pz
(k) = r
(k) .
Le pr´ econditionneur agissant sur le rayon spectral de la matrice d’it´ eration,
il serait utile de d´ eterminer, pour un syst` eme lin´ eaire donn´ e, un pr´ econditionneur optimal, i.e. un pr´ econditionneur qui rende ind´ ependant de la taille du
syst` eme le nombre d’it´ erations n´ ecessaires ` a la convergence. Remarquer que
le choix P=A est optimal mais trivialement inefficace ; nous examinons cidessous des alternatives plus int´ eressantes pour les calculs.
Nous manquons de r´ esultats th´ eoriques g´ en´ eraux pour construire des pr´ econditionneurs optimaux. Mais il est commun´ ement admis que P est un bon
pr´ econditionneur pour A si P
−1 A est “presque” une matrice normale et si ses
valeurs propres sont contenues dans une r´ egion suffisamment petite du plan
complexe. Le choix d’un pr´ econditionneur doit aussi ˆ etre guid´ e par des consid´ erations pratiques, en particulier son coˆ ut de calcul et la place qu’il occupe
en m´ emoire.
On peut s´ eparer les pr´ econditionneurs en deux cat´ egories principales :
les pr´ econditionneurs alg´ ebriques et fonctionnels. Les pr´ econditionneurs alg´ ebriques sont ind´ ependants du probl` eme dont est issu le syst` eme ` a r´ esoudre :
ils sont construits par une proc´ edure purement alg´ ebrique. Au contraire, les
pr´ econditionneurs fonctionnels tirent avantage de la connaissance du probl` eme
et sont construits en cons´ equence.
D´ ecrivons ` a pr´ esent d’autres pr´ econditionneurs alg´ ebriques d’usage courant qui viennent s’ajouter aux pr´ econditionneurs d´ ej` a introduits `
a la Section 4.2.5.
1. Pr´ econditionneurs diagonaux : ils correspondent au cas o` u P est simplement une matrice diagonale. Pour les matrices sym´ etriques d´ efinies
positives, il est souvent assez efficace de prendre pour P la diagonale de
A. Un choix habituel pour les matrices non sym´ etriques est de prendre
p ii =
⎛
⎝
n
j=1
a
2
ij
⎞
⎠
1/2
.
En se rappelant les remarques faites au sujet du scaling d’une matrice (voir
Section 3.11.1), on comprendra que la construction d’un P qui minimise
K(P
−1 A) est loin d’ˆ etre triviale.